長いよ

発端

【問題】
Aさんはある巨大な素数pの素因数分解をすることに成功し、素因数分解に成功したことをBさんに伝えようとしています。
しかし、Bさんが先にpの素因数を世間に発表することは避けたいため、素因数を伝えることなく、pの素因数を知っていることを示したいです。
どうすればいいでしょうか。
— 数学を愛する会 (@mathlava) 2022年10月12日

【問題】 Aさんはある巨大な素数pの素因数分解をすることに成功し、素因数分解に成功したことをBさんに伝えようとしています。しかし、Bさんが先にpの素因数を世間に発表することは避けたいため、素因数を伝えることなく、pの素因数を知っていることを示したいです。どうすればいいでしょうか。

巨大な整数の素因数分解でした…
— 数学を愛する会 (@mathlava) 2022年10月12日

ということなので、「巨大な素数p」は「素数の積N=pq」ということにしておきます。

問題の定式化

簡単のため言語を $\{N \in \mathbb{Z} \mid N = pq \land (p,q) \in\mathbb{P} \}$ とNが2つの素数p,qの積からなる言語として、プロトコルに従う検証者だけを考えるゼロ知識証明を考えます。（専門用語でいうところのHVZK PoK, honest-verifier zero-knowledge proof of knowledge)

要件は以下の3つです

正当性: プロトコルへの共通入力が言語に入っているとき、正直な証明者は正直な検証者を納得させられる
正直な検証者に対するゼロ知識性 (HVZK): 検証者が正直な場合のプロトコルのやりとりをシミュレーションできる
知識証明 (PoK): 証明者へブラックボックスアクセスできる期待多項式時間で動き知識抽出機械 E が存在し, そのEがxの証拠wを出力できる確率は、証明者が正直な検証者を納得させる確率から無視できる分だけしか離れていないこと。
- 具体的に書くと, $\Pr({E^{\tilde{P}}(x)} \in W(x)) = \Pr(\langle\tilde{P} \leftrightarrow V\rangle(x) \to 1) - \kappa(|x|)$ でEの期待動作時間が $\mathrm{poly}(|x|)$ で, $\kappa(|x|)$ は無視できる関数

案1. RSA暗号を使う

「合成数Nが半素数で、その素因数分解N=pqができた」と仮定してみます。

Aはm=φ(N)=(p-1)(q-1)と互いに素なeを探しBにeを伝える。
Bは（Aに秘密に）xを選び、x^e≡y (mod N)を計算しyをAに伝える。
Aはed-mv = 1を満たす(d, v)を互除法で計算し、y^d≡z(mod N)なるzをBに返送。
Bはx≡zを確認。 https://t.co/4IfQlnKK1X
— tsujimotter 日曜数学者 (@tsujimotter) 2022年10月13日

Aはp, q、そこから得られるmの情報を持っているが、いずれも外部に漏らしていない。

また、Bは x を鍵(e, N)で暗号化しAに送っているが、Aから x が返ってきたことにより、Aが復号鍵を持つことを確認できる。
復号鍵は N の素因数 p, q がないと得られないため、Aが素因数を持っていると証明できる。
— tsujimotter 日曜数学者 (@tsujimotter) 2022年10月13日

「合成数Nが半素数で、その素因数分解N=pqができた」と仮定してみます。 Aはm=φ(N)=(p-1)(q-1)と互いに素なeを探しBにeを伝える。 Bは（Aに秘密に）xを選び、x^e≡y (mod N)を計算しyをAに伝える。 Aはed-mv = 1を満たす(d, v)を互除法で計算し、y^d≡z(mod N)なるzをBに返送。 Bはx≡zを確認。

Aはp, q、そこから得られるmの情報を持っているが、いずれも外部に漏らしていない。また、Bは x を鍵(e, N)で暗号化しAに送っているが、Aから x が返ってきたことにより、Aが復号鍵を持つことを確認できる。復号鍵は N の素因数 p, q がないと得られないため、Aが素因数を持っていると証明できる。

案1の問題点

案1のプロトコルにより、証明者Aはe乗根、すなわちd乗を行うことが証明できます。ここまではOKです。

さて、問題は3の知識証明です。案1のプロトコルで検証者を納得させられる場合に、その証明者からp, qの素因数分解ができるでしょうか?

割と有名な事実として、(N, e, d) が揃えば素因数分解を行うことができることが知られています。*1 詳しくはおまけを見てください。そのため、案1のプロトコルがdを知っていることの証明になっていれば、それは素因数分解ができることと等価なため、案1のプロトコルは素因数分解の証明になっています。

残念ながら一般的には仮定が証明されていません。例えば、素因数分解を行った別の人がRSA方式のようにeとdを計算し、証明者Aには eの値とd乗を行う謎の機械を証明者に渡すかもしれません。もしこの謎の機械が難読化 *2 されていてdが読みとれないのであれば、証明者にはdが分かりません。そのため、証明者には素因数分解ができない可能性があります。RSA問題（=d乗すること）を解けることと素因数分解の等価性はここ40年ほど未解決問題になっています。

案2. Rabin暗号を使う

RSA暗号の暗号文を復号するという操作は素因数分解と等価ではありません。そこで自然な考えとして、復号する操作が素因数分解と等価な暗号を使えばいいのではないかというアイデアがあります。ということで、そのようなことが知られている平方剰余を使ったRabin暗号を使ってみましょう。

(Bが暗号文を生成する) Bは秘密にxを選び y≡x²(mod N) を計算し、Aにyを伝える
(Aが復号する) Aはyの平方zを計算し、Bにzを伝える
(Bが確認する) Bはz²≡y (mod N) ならば受理、そうでなければ拒否とする

案2の問題点

残念ながら案2のプロトコルでは素因数分解の知識が漏れてしまいます。 Bがプロトコルに従っていても、Bは確率的ですが素因数分解できてしまいます。中国式剰余定理で, Bが秘密に選んだx in Z/NZを, (x mod p, x mod q) in Z/pZ x Z/qZと同一視します。平方剰余yの平方根は (± x mod p, ± x mod q) の4通りあるんですが、Aから見るとどの組み合わせを自乗したのか識別できません。そのため、Aがどのような方法で4通りを決めたとしてもBが選んだものと一致する確率は1/4です。ということで, 非自明な組み合わせ (x mod p, -x mod q) または (-x mod p, x mod q) を証明者Aが選んでzとして送ってくると, Bは gcd(x-z,N)で素因数分解ができてしまいます。

案2の改良に必要な平方根を知っていることを示すゼロ知識証明

ということでいったん話を変えて、平方根を知っていることを示すゼロ知識証明を考えてみます。

証明者Pは検証者Vと対話して、入力(t, N)について, その平方根 w を知っていることを示したいとします。

プロトコル1:

Pはrをランダムに選んで a = r² mod Nを計算し, Vにaを送る
Vはcを0/1からランダムに選び, cを送る
Pはz = r w^c mod Nを計算し, Vにzを送る
Vは z² ≡ a t^c (mod N) ならば受理、そうでなければ拒否とする
正当性は自明なので略
HVゼロ知識性: 先にcを選んでzを計算してからaを計算すると辻褄が合います。しかもこれは正しいP, Vのやりとりと見分けがつきません。
知識証明: $\tilde{P}$ を使って, aを得ます。c=0の場合の $z_0$ を得た後, $\tilde{P}$ を巻き戻します（または同じ乱数テープを使う）。同じaに対してc=1の場合の $z_1$ を得ます。このとき, ${z_0^{2}}\equiv a \pmod{N}$ かつ ${z_1^{2}}\equiv a t \pmod{N}$ なので, ${(z_1/z_0)^{2}} \equiv t \pmod{N}$ となり $z_1/z_2$ がtの平方根になります。（確率の問題がありますが、 $\tilde{P}$ の乱数テープを取り換えていろんなaで試すことで確率を増幅でき、κを減らすことができます。詳細略）

これを繰り返し（または並列に）行うとtの平方根wを知っていることを証明できていると考えてください（証明は略）

案2の改良

これは『ゼロ知識証明』と呼ばれている証明方法(厳密には数学的な証明では無い)を用いれば解決することが出来ます！
詳しくは以下のリンクを参考にしてくださいhttps://t.co/rGPIzxszAQ https://t.co/NgYqDgt3yS
— 数学を愛する会 (@mathlava) 2022年10月19日

のリンク先に書いてあるプロトコルです。

プロトコル1を使って案2の問題を解決したものが以下です。

(Bが暗号文を生成し、原像を知っていることを示す):
1. Bは秘密にxを選び y≡x²(mod N) を計算し、Aにyを伝える
2. Bが証明者, Aが検証者になって, プロトコル1を使い, Bはyの平方根xを知っていることを証明する
(Aが復号する)
1. Aはyの平方zを計算する
2. Aが証明者, Bが検証者になって, プロトコル1を使い, Aはyの平方根zを知っていることを証明する
(Bの出力) 2-2の結果をBは出力する

リンク先の小山（情報処理 vol.32, No.6 http://id.nii.ac.jp/1001/00004658/) に書かれてます。このプロトコル自体はTompa and Woll (FOCS 1987, https://ieeexplore.ieee.org/document/4568301) が初出だと思います。

（補足）検証者が正直であるという条件を使う場合は、1.で単にyを送ってプロトコル1を省いても大丈夫な気がします。

案3

これ以外の方法もあります。

link.springer.com

Poupard and Stern (PKC 2000) では、プロトコル1のような感じでゼロ知識証明を行います。

$z_1,\dots,z_K$ は1以上N未満でNと互素な整数からランダムに選ばれているとします。またパラメータA, B, K, 繰り返し回数のLなどは気を付けて選ぶ必要があります。

A-1:
1. rを1以上A未満の整数からランダムに選ぶ.
2. $x_i = {z_i^{r}} \bmod{n}$ を計算し, Bに $x_1,\dots,x_K$ を送る
B-1:
1. eを1以上B未満の整数からランダムに選び, Aに送る
A-2:
1. y = r + (n-φ(n)) × eを計算し, Bにyを送る
B-2:
1. 0 <= y < Aをチェック
2. ${z_i^{y-ne}} \equiv x_i \pmod{N}$ をチェック

とします。

ざっくりいうと、これでカーマイケル数 λ(N) の倍数を知っていることが証明できています。

正当性: B-2-1のところで正当性が統計的になっている点に注意してください。A, B, Kなどの設定が
HVゼロ知識性: eを先に選んで, yを決めてから, x_iを計算します。
知識証明 (PoK): 平方根を知っていることを証明するプロトコルの際と同様に、A-1の後、2通りのe, e'でy,y'を得て, λ=|y-y'-n(e-e')|を計算します。 ${z_i^{y-ne}} \equiv {z_i^{y'-ne'}} \pmod{N}$ を使って, 色々頑張るとλがカーマイケル数 λ(N) の倍数になっていることが示せます。おまけに書いてある Millerの技法を使ったφ(N)の倍数から素因数分解を行う方法と同様に、λ(N)の倍数から素因数分解ができます。

おまけ (RSA原論文のAppendix Cの方法)

RSAの鍵生成の結果から、 $e d \equiv 1 \pmod{\phi(N)}$ . よって, $m = e d - 1$ は $\phi(N)$ の倍数
一方, Millerの論文には, の倍数を使って, 確率的にを素因数分解する方法が書いてある。
1. ( $a \in {1,2,\dots,N-1}$ をランダムに選ぶ)
2. $a \mid N$ をチェック
3. 割り切れないなら, $\mathrm{gcd} \big( (a^{m/{2^{k}}} \bmod{N})-1, N\big)$ を $1 \leq k \leq \lg(N-1)$ について調べる