一次不定方程式に基づくゼロ知識対話証明

概要

論文の詳細を見る
「ゼロ知識対話証明」の具体的な実現法は,大きな素数の積を法とする平方剰余問題や離散的対数問題に基づくものや,二つのグラフの同形問題に基づくもの等多くの事例が発表されている.本論文でディオファンタスの一次不定方程式に基づく一方向関数を利用したゼロ知識対話証明の具体的な実現方法を提案する.本方法では,扱うビット長,演算量が小さくなるためゼロ知識対話証明やマルチパーティプロトコルを実現するのに必要な計算量が,大きな素数の積を法とする多次剰余暗号系を利用した方法に比較して,かなり少なくなる利点がある.系の構成は,次のようになる.正整数α_iを系数,Cを与えられた整数,t_iを未知数とするディオファンタスの一次不定方程式C=α_1t_1+…α_nt_nを利用して,0≦t_i<P(Pは適当な正整数)なるt_iを入力,Cを出力とする問題を構築する.ここで,T=(t_1,…,t_n),C=f(T)とおく.乱数D=(d_1,…,d_n)を選び,z_1=t_1+d_1mod P,…,z_n=t_n+d_nmod Pとする.このとき,t_i+d_i-z_i=0 or P(i=1,…,n)であり,z_1,…,z_nにはランダム自己帰着性がある.このz_iを用いてゼロ知識対話証明を実現できる.
1994-03-15