C++でNaor-Reingold擬似ランダム関数を実装する方法

Naor-Reingold擬似ランダム関数は、乱数を生成するためのもう一つの強力な手法です。本記事では、その数学的な背景とアルゴリズムを解説し、実際にC++で実装する方法を紹介します。

Naor-Reingold擬似ランダム関数とは

1997年、Moni Naor（モニ・ナオール）とOmer Reingold（オメル・ラインゴールド）は、共通鍵暗号および公開鍵暗号の両分野において、さまざまな暗号プリミティブの効率的な構成方法を提唱しました。

p と l を素数とし、l | p−1（つまり l が p−1 を割り切る）であるとします。さらに、乗法位数が l である元 g ∈ F_p* を選択します。このとき、各n次元ベクトル a = (a₀, a₁, ..., a_n) に対して、次の関数が定義されます。

fa(x) = ga0 · a1^x1 · a2^x2 · … · an^xn ∈ Fp

ここで、x = x₁ … x_n は整数 x（0 ≤ x ≤ 2ⁿ⁻¹）のビット表現を表します。

この関数は、対称鍵暗号、認証、デジタル署名など、多くの暗号方式の基盤として活用できることが知られています。

アルゴリズム

開始
   変数 p, l, g, n, x を宣言する
   変数 p, l, g, n の値を読み込む
   配列 a[], b[] を宣言する
   i = 0 から 10 まで繰り返す:
      x = rand() mod 16
      j = g から 0 まで繰り返す:
         b[j] = x mod 2
         x = x ÷ 2
      繰り返し終了
      mult = 1 を代入する
      k = 0 から n まで繰り返す:
         mult = mult × (pow(a[k], b[k]))
      繰り返し終了
      乱数を出力する
   繰り返し終了
終了

C++サンプルコード

#include <iostream>
using namespace std;
int main(int argc, char **argv) {
    int p = 7, l = 2, g = 3, n = 6, x;
    int a[] = { 1, 2, 2, 1 };
    int b[4];
    cout << "The Random numbers are: ";
    for (int i = 0; i < 10; i++) {
        x = rand() % 16;
        for (int j = 3; j >= 0; j--) {
            b[j] = x % 2;
            x /= 2;
        }
        int mult = 1;
        for (int k = 0; k < 6; k++)
            mult *= pow(a[k], b[k]);
        cout << pow(g, mult)<<" ";
    }
}

コードの解説

このプログラムでは、まず rand() % 16 によって 0〜15 の範囲の乱数 x を生成し、それを4桁の2進数に変換して配列 b に格納します。続いて、指数部 mult を a[0]・a[1]^b[1]・… の形で計算し、最後に g の mult 乗を求めることで、Naor-Reingold関数の値を得ています。b[k] は 0 または 1 のみを取るため、mult の計算では対応する a[k] を掛けるかどうかが決まります。

実行結果

The Random numbers are: 81 81 3 9 3 81 9 9 3 9

出力を見ると、生成された値はすべて有限体 F_p の元となっており、入力のわずかな違いが異なる出力につながる様子が確認できます。これこそが擬似ランダム関数としての重要な性質です。