(57)【特許請求の範囲】
【請求項１】
デジタル・メッセージｍを、符号化装置により符号化し、復号化装置により復号する方法であって、
符号化装置の選択手段に、環Ｒのイデアルｐおよびｑを選択させるステップと、
符号化装置の第１の生成手段に、環Ｒの要素ｆおよびｇを生成させ、ｆ（ｍｏｄ  ｑ）の逆数である要素Ｆqを生成させ、ｆ（ｍｏｄ  ｐ）の逆数である要素Ｆpを生成させるステップと、
符号化装置の第２の生成手段に、ｇおよびＦqを使用して得ることのできる積とｍｏｄ  ｑで合同であるｈを含む公開鍵を生成させるステップと、
符号化装置の第３の生成手段に、ｆおよびＦpを含む専用鍵を生成させるステップと、
符号化装置の第４の生成手段に、公開鍵およびランダム要素φを使用してメッセージｍを符号化させることによって、ｈ及びφを含む積と、メッセージｍとの和と、ｍｏｄ  ｑで合同である符号化メッセージｅを生成させるステップと、
復号化装置の生成手段に、専用鍵を使用して符号化メッセージｅの復号をさせることによって復号メッセージを生成させるステップとを含み、
復号メッセージは、ａ≡ｆ*ｅ（ｍｏｄ  ｑ）を計算し、復号メッセージｍ’を、ｍ’≡Ｆp*ａ（ｍｏｄ  ｐ）として計算する、
方法。
【請求項２】
前記環Ｒが環Ｚを覆うモジュールであることを特徴とする請求の範囲第１項に記載の方法。
【請求項３】
Ｚを覆うＲの次元がＮであり、Ｎが１より大きな整数であることを特徴とする請求の範囲第１項に記載の方法。
【請求項４】
環Ｒが、特定の多項式を法とする多項式の環であることを特徴とする請求の範囲第３項に記載の方法。
【請求項５】
要素を生成する前記ステップがさらに、ｇ（ｍｏｄ  ｑ）の逆数である要素Ｇqを生成し、ｇ（ｍｏｄ  ｐ）の逆数である要素Ｇpを生成するステップを含むことを特徴とする請求の範囲第１項に記載の方法。
【請求項６】
前記要素Ｇqが前記公開鍵を得るのに使用され、前記要素Ｇpが前記専用鍵の一部であることを特徴とする請求の範囲第５項に記載の方法。
【請求項７】
前記選択ステップがさらに正の整数Ｋを選択するステップを含み、前記要素ｇがｇi（ｉ＝１，２,...,Ｋ）を含み、前記公開鍵ｈがｈi（ｉ＝１，２,...,Ｋ）を含むことを特徴とする請求の範囲第１項に記載の方法。
【請求項８】
前記ランダム要素φがイデアルｐ中にφi（ｉ＝１，２,...,Ｋ）を含み、前記符号化メッセージが、
0004068664.tif 000063
として生成されることを特徴とする請求の範囲第７項に記載の方法。
【請求項９】
前記公開鍵および専用鍵がそれぞれ、ｐとｑをふくむことを特徴とする請求の範囲第１項に記載の方法。
【請求項１０】
前記イデアルｐとｑが相対的に素な整数によって生成されることを特徴とする請求の範囲第１項に記載の方法。
【請求項１１】
前記整数ｐとｑが等しくなく、ｐとｑがともに１より大きいことを特徴とする請求の範囲第１０項に記載の方法。
【請求項１２】
前記符号化メッセージが、あるユーザによってある場所で生成され、前記ある場所から別の場所に伝送され、前記別の場所であるユーザによって復号されることを特徴とする請求の範囲第１項に記載の方法。
【請求項１３】
デジタル・メッセージｍを、符号化装置により符号化し、復号化装置により復号する方法であって、
符号化装置の選択手段に、整数ｐおよびｑを選択させるステップと、
符号化装置の第１の生成手段に、多項式ｆおよびｇを生成させるステップと、
符号化装置の決定手段に、逆数Ｆqおよび逆数Ｆpを決定させるステップであって、
Ｆq*ｆ≡１（ｍｏｄ  ｑ）
Ｆp*ｆ≡１（ｍｏｄ  ｐ）
であるステップと、
符号化装置の第２の生成手段に、ｐ、ｑ、ｈを含む公開鍵を生成させるステップであって、
ｈ≡Ｆq*ｇ（ｍｏｄ  ｑ）
であるステップと、
符号化装置の第３の生成手段に、ｆおよびＦpを含む専用鍵を生成させるステップと、
符号化装置の第４の生成手段に、公開鍵およびランダム多項式φを使用して多項式で表現されたメッセージｍを符号化させることによって符号化メッセージｅを、ｅ≡ｐφ*ｈ＋ｍ（ｍｏｄ  ｑ）として生成させるステップと、
復号化装置の生成手段に、専用鍵を使用して符号化メッセージｅの復号をさせることによって復号メッセージを生成させるステップとを含み、
復号メッセージは、ａ≡ｆ*ｅ（ｍｏｄ  ｑ）を計算し、復号メッセージｍ’を、ｍ’≡Ｆp*ａ（ｍｏｄ  ｐ）として計算する、
方法。
【請求項１４】
多項式ｆおよびｇを生成する前記ステップが、正の整数Ｋを選択し、Ｋ個の多項式ｇをｇ1，ｇ2,...,ｇkとして生成するステップを含み、前記公開鍵がｈ1，ｈ2,...,ｈkを含み、
上式で
ｈi≡Ｆq*ｇi（ｍｏｄ  ｑ）、ｉ＝１，２,...,Ｋ
であることを特徴とする請求の範囲第１３項に記載の方法。
【請求項１５】
前記符号化メッセージｅが、
ｅ≡ｐφ1*ｈ1＋ｐφ2*ｈ2＋...＋ｐφK*ｈK＋ｍ（ｍｏｄ  ｑ）
として生成され、
上式でφ1，φ2,...,φKがＫ個のランダム多項式であることを特徴とする請求の範囲第１４項に記載の方法。
【請求項１６】
前記符号化メッセージが、あるユーザによってある場所で生成され、前記ある場所から別の場所に伝送され、前記別の場所であるユーザによって復号されることを特徴とする請求の範囲第１３項に記載の方法。
【請求項１７】
モニック多項式Ｍ（Ｘ）が選択され、多項式の乗算が、まず多項式の通常の乗算を行い、次いで結果をＭ（Ｘ）で割り、剰余だけを保持することによって実施されることを特徴とする請求の範囲第１３項に記載の方法。
【請求項１８】
非ゼロの整数Ｎが選択され、多項式の乗算が、Ｎを法とする指数を整約することによって実施されることを特徴とする請求の範囲第１３項に記載の方法。
【請求項１９】
前記多項式ｆ、ｇ、ｍ、φが有界係数をもつように制約されることを特徴とする請求の範囲第１３項に記載の方法。
【請求項２０】
前記整数ｑが、前記整数ｐと、前記多項式ｆ、ｇ、ｍ、φの次数と、前記ｆ、ｇ、ｍ、φの係数に対する前記制約とによって決まる量よりも小さく選ばれることを特徴とする請求の範囲第１９項に記載の方法。
【請求項２１】
前記整数ｑが、前記整数ｐと、前記多項式ｆ、ｇ、ｍ、φの次数と、前記ｆ、ｇ、ｍ、φの係数に対する前記制約とによって決まる量よりも大きく選ばれることを特徴とする請求の範囲第１９項に記載の方法。
【請求項２２】
デジタル・メッセージを、符号化装置により符号化し、復号化装置により復号する方法であって、
符号化装置の第１の選択手段に、相対的に素な整数ｐおよびｑを選択させるステップと、
符号化装置の第２の選択手段に、非ゼロの整数Ｋを選択させるステップと、
符号化装置の第１の生成手段に、整数係数を有し、ｗi≡０（ｍｏｄ  ｐ）（ｉ＝１，２,...,Ｋ）である行列の環からＫ＋２個の行列ｆ，ｇ，ｗ1，ｗ2,...,ｗKを生成させるステップと、
符号化装置の第２の生成手段に、前記行列の環から逆行列Ｆp，Ｆq，Ｇp，Ｇqを生成させるステップであって、
ｆＦp≡Ｉ（ｍｏｄ  ｐ）
ｆＦq≡Ｉ（ｍｏｄ  ｑ）
ｇＧp≡Ｉ（ｍｏｄ  ｐ）
ｇＧq≡Ｉ（ｍｏｄ  ｑ）
上式でＩが単位行列であるステップと、
符号化装置の第３の生成手段に、公開鍵をＫ個の行列（ｈ1，ｈ2,...,ｈk）のリストとして生成させるステップであって、
ｈi≡ＦqｗiＧq（ｍｏｄ  ｑ），ｉ＝１，２,...,Ｋ；
であるステップと、
符号化装置の第４の生成手段に、専用鍵を行列（ｆ，ｇ，Ｆp，Ｇp）として生成させるステップと、
符号化装置の第５の生成手段に、公開鍵およびランダム整数φ1，φ2,...,φKを使用してメッセージｍを符号化させることによって符号化メッセージｅを
ｅ≡φ1ｈ1＋φ2ｈ2＋...＋φKｈK＋ｍ（ｍｏｄ  ｑ）；
として生成させるステップと、
復号化装置の生成手段に、
ａ≡ｆｅｇ（ｍｏｄ  ｑ）
および
ｂ≡ａ（ｍｏｄ  ｐ）
を計算させ、ついで復号メッセージｍ’を
ｍ’＝ＦpｂＧp（ｍｏｄ  ｐ）
として計算させることによって復号メッセージｍ’を生成させるステップと
を含む方法。
【請求項２３】
前記符号化メッセージが、あるユーザによってある場所で生成され、前記ある場所から別の場所に伝送され、前記別の場所であるユーザによって復号されることを特徴とする請求の範囲第２２項に記載の方法。
【請求項２４】
前記行列ｗ1，ｗ2,...,ｗK，ｆ，ｇ，ｍが有界係数をもつように制約され、整数φ1，φ2,...,φKが有界であるように制約されることを特徴とする請求の範囲第２２項に記載の方法。
【請求項２５】
前記整数ｑが、前記整数ｐと、前記整数Ｋと、前記多項式ｗ1，ｗ2,...,ｗK，ｆ，ｇ，ｍの次数と、前記多項式ｗ1，ｗ2,...,ｗK，ｆ，ｇ，ｍの係数に対する前記制約と、整数φ1，φ2,...,φKに対する前記制約とによって決まる量よりも小さく選ばれることを特徴とする請求の範囲第２４項に記載の方法。
【請求項２６】
前記整数ｑが、前記整数ｐと、前記整数Ｋと、前記多項式ｗ1，ｗ2,...,ｗK，ｆ，ｇ，ｍの次数と、前記多項式ｗ1，ｗ2,...,ｗK，ｆ，ｇ，ｍの係数に対する前記制約と、整数φ1，φ2,...,φKに対する前記制約とによって決まる量よりも大きく選ばれることを特徴とする請求の範囲第２４項に記載の方法。
【請求項２７】
デジタル・メッセージｍを、符号化プロセッサにより符号化し、復号化プロセッサにより復号するシステムであって、
イデアルｐおよびｑを選択する手段と、
環Ｒの要素ｆおよびｇを生成し、ｆ（ｍｏｄ  ｑ）の逆数である要素Ｆqを生成し、ｆ（ｍｏｄ  ｐ）の逆数である要素Ｆpを生成する手段と、
ｇおよびＦqを使用して得ることのできる積とｍｏｄ  ｑで合同であるｈを含む公開鍵を生成する手段と、
ｆおよびＦpを含む専用鍵を生成する手段と、
公開鍵およびランダム要素φを使用してメッセージｍを符号化することによって、ｈ及びφを含む積と、メッセージｍとの和と、ｍｏｄ  ｑで合同である符号化メッセージｅを生成する手段と、
専用鍵を使用して符号化メッセージｅを復号することによって復号メッセージを生成する手段と
を備え、
復号メッセージは、ａ≡ｆ*ｅ（ｍｏｄ  ｑ）を計算し、復号メッセージｍ’を、ｍ’≡Ｆp*ａ（ｍｏｄ  ｐ）として計算する、
システム。
【請求項２８】
前記符号化メッセージが、あるユーザによってある場所で生成され、前記ある場所から別の場所に伝送され、前記別の場所であるユーザによって復号されることを特徴とする請求の範囲第２７項に記載のシステム。
【請求項２９】
通信システムのユーザ間で情報を通信する方法であって、
第１の装置の第１の生成手段に、リングＲと、Ｒ中のイデアルＰおよびＱと、イデアルＱを法とする環Ｒに対する代表剰余系ＣQの集合と、イデアルＰを法とする環Ｒに対する代表剰余系Ｃpの集合とを生成させるステップと、
第１の装置の第２の生成手段に、Ｒ中の少なくとも２つの専用鍵要素ｆ1,...,ｆnおよび第１のユーザのイデアルＱの関数として環Ｒ中の少なくとも１つの公開鍵要素ｈ1,...,ｈkを生成させるステップと、
第１の装置の伝送手段に、環Ｒと、イデアルＱと、イデアルＰと、Ｒ中の要素ｈ1,...,ｈkとの記述を、第２のユーザが使用する第２の装置へ伝送させるステップと、
第２の装置の生成手段に、イデアルＰおよびＱと、公開鍵要素ｈ1,...,ｈkと、Ｒ中の専用メッセージ要素ｍと、第２のユーザの少なくとも１つの専用ランダム要素φ1,...,φlとの関数として環Ｒ中の要素ｅを生成させるステップと、
ｅ，ｆ1,...,ｆnの関数Ｆを評価するＲ中の結果Ａを計算し、代表剰余系ＣQの集合中のＡの代表剰余系ａを計算し、ａ，ｆ1,...,ｆnの関数Ｇを評価する結果Ｂを計算し、代表剰余系Ｃpの集合中のＢの代表剰余系ｂを計算し、ｂ，ｆ1,...,ｆnの関数Ｈを評価する代表剰余系Ｃpの集合中の結果ｃを計算することによって、第１のユーザが使用する第１の装置の決定手段が、メッセージ要素ｍを決定できるように、第２の装置の伝送手段に、要素ｅを、第１の装置へ伝送させるステップと、
を含み、
公開鍵要素ｈ1,...,ｈkと、専用ランダム要素φ1,...,φk+1と、専用メッセージ要素ｍとの関数として生成される要素ｅが、イデアルＱを法としてφ1ｈ1＋φ2ｈ2＋,...,＋φkｈk＋φk＋ｍと合同であるＣQの要素として生成される方法。
【請求項３０】
メッセージ要素ｍが、ｍがＣPの要素であるという条件を満たすことを特徴とする請求の範囲第２９項に記載の方法。
【請求項３１】
ａ，ｂ，ｃ，ｆ1,...,ｆnの関数を計算することによって、第１のユーザがメッセージ要素ｍを決定することを特徴とする請求の範囲第２９項に記載の方法。
【請求項３２】
公開鍵要素ｈ1,...,ｈkが、１とｋの間の各ｉについて要素ｆiがイデアルＱを法としてＲ中で積ｈiｆk+1と合同であるという条件を満たすことを特徴とする請求の範囲第２９項に記載の方法。
【請求項３３】
専用鍵要素ｆ1,...,ｆk+1が、要素ｆ1,...,ｆkがイデアルＰ中にあるという条件を満たすことを特徴とする請求の範囲第２９項に記載の方法。
【請求項３４】
専用ランダム要素φ1,...,φlがイデアルＰ中にあることを特徴とする請求の範囲第２９項に記載の方法。
【請求項３５】
ｅ，ｆ1,...,ｆnの関数Ｆを評価する結果Ａが積ｅｆk+1であることを特徴とする請求の範囲第２９項に記載の方法。
【請求項３６】
ａ，ｆ1,...,ｆnの関数Ｇを評価する結果Ｂが要素ａであることを特徴とする請求の範囲第２９項に記載の方法。
【請求項３７】
ａ，ｆ1,...,ｆnの関数Ｈを評価する代表剰余系ＣPの集合中の結果ｃが、ｃｆk+1がイデアルＰを法としてｂと合同であるという条件を満たすことを特徴とする請求の範囲第２９項に記載の方法。
【請求項３８】
結果ｃが、代表剰余系ＣPの集合中のメッセージｍの代表剰余系に等しいことを特徴とする請求の範囲第２９項に記載の方法。
【請求項３９】
環Ｒが、次数Ｎのモニック多項式Ｍ（Ｘ）によって生成されるＲのイデアルを法として１つの変数Ｘ中の多項式の環であり、ＲのイデアルＱが整数ｑによって生成されるイデアルであり、ＲのイデアルＰが整数ｐによって生成されるイデアルであり、代表剰余系ＣQの集合が、次数がせいぜいＮ−１でｑを法とする代表剰余系の固定した集合中の係数を有するＲ中の多項式の集合であり、代表剰余系ＣPの集合が、次数がせいぜいＮ−１でｐを法とする代表剰余系の固定した集合中の係数を有するＲ中の多項式の集合であることを特徴とする請求の範囲第２９項に記載の方法。
【請求項４０】
専用鍵要素ｆ1,...,ｆn、Ｒ中の専用メッセージ要素ｍ、および専用ランダム要素φ1,...,φlが、その係数に対する境界を含むという条件を満たすことを特徴とする請求の範囲第３９項に記載の方法。
【請求項４１】
環Ｒが非可換体であることを特徴とする請求の範囲第２９項に記載の方法。
【請求項４２】
要素ｈ1,...,ｈkが、１とＫの間の各ｉについて要素ｆk+1ｈiｆk+2がイデアルＱを法としてＲ中でｆiと合同であるという条件に従ってＣQ中で生成されることを特徴とする請求の範囲第２９項に記載の方法。
【請求項４３】
専用鍵要素ｆ1,...,ｆkがイデアルＰ中にあることを特徴とする請求の範囲第２９項に記載の方法。
【請求項４４】
専用ランダム要素φ1,...,φ2k+1が、要素φ1,...,φkがイデアルＰ中にあるという条件を満たすことを特徴とする請求の範囲第２９項に記載の方法。
【請求項４５】
公開鍵要素ｈ1,...,ｈkと、専用ランダム要素φ1,...,φ2k+1と、専用メッセージ要素ｍとの関数として生成される要素ｅが、イデアルＱを法としてφ1ｈ1φk+1＋φ2ｈ2φk+2＋,...,＋φkｈkφ2k＋φ2k+1＋ｍと合同であるＣQの要素として生成されることを特徴とする請求の範囲第４１項に記載の方法。
【請求項４６】
環Ｒが整数係数をもつ行列の環であり、ＲのイデアルＱが、固定整数ｑで割り切れるすべての行列からなるイデアルであり、ＲのイデアルＰが、固定整数ｐで割り切れるすべての行列からなるイデアルであり、代表剰余系ＣQの集合が、ｑを法とする代表剰余系の固定した集合中の係数を有するＲの要素の集合であり、代表剰余系ＣPの集合が、ｐを法とする代表剰余系の固定した集合中の係数を有するＲの要素の集合であることを特徴とする請求の範囲第２９項に記載の方法。
【請求項４７】
専用鍵要素ｆ1,...,ｆn、専用メッセージ要素ｍ、および専用ランダム要素φ1,...,φlが、その係数に対する境界を含むという条件を満たすことを特徴とする請求の範囲第４６項に記載の方法。
【請求項４８】
専用ランダム要素φ1,...,φlが、要素φ1,...,φlが単位行列の定数倍であるという条件を満たすことを特徴とする請求の範囲第４６項に記載の方法。
【請求項４９】
環Ｒが群Ｇの群環であり、ＲのイデアルＱが、整数ｑによって生成されるイデアルであり、ＲのイデアルＰが、整数ｐによって生成されるイデアルであり、代表剰余系ＣQの集合が、ｑを法とする代表剰余系の固定した集合中の係数を有するＲの要素の集合であり、代表剰余系ＣPの集合が、ｐを法とする代表剰余系の固定した集合中の係数を有するＲの要素の集合であることを特徴とする請求の範囲第２９項に記載の方法。
【請求項５０】
専用鍵要素ｆ1,...,ｆn、専用メッセージ要素ｍ、および専用ランダム要素φ1,...,φlが、その係数に対する境界を含むという条件を満たすことを特徴とする請求の範囲第４９項に記載の方法。
【請求項５１】
環Ｒが、二面関係ＸN＝１、Ｙ2＝１、ＸＹ＝ＹＸN-1に従うことを条件として２つの変数ＸおよびＹ中の多項式の非可換環であり、ＲのイデアルＱが整数ｑによって生成されるイデアルであり、ＲのイデアルＰが整数ｐによって生成されるイデアルであり、代表剰余系ＣQの集合が、次数がせいぜいＮ−１でｑを法とする代表剰余系の集合から選ばれた係数を有する変数ＸにおけるＲ中の多項式の集合であり、代表剰余系ＣPの集合が、次数がせいぜいＮ−１でｐを法とする代表剰余系の固定した集合から選ばれた係数を有する変数ＸにおけるＲ中の多項式の集合であることを特徴とする請求の範囲第２９項に記載の方法。
【請求項５２】
専用鍵要素ｆ1,...,ｆn、専用メッセージ要素ｍ、および専用ランダム要素φ1,...,φlが、その一部が、条件Ｙψ＝ψＹを満たすＲのすべての要素ψからなるＲの可換部分環Ｒ0中にあるという条件を含む諸条件を満たすことを特徴とする請求の範囲第５１項に記載の方法。
【請求項５３】
前記符号化装置は、符号化コンピュータプログラムによりプログラムされ、前記復号化装置は、復号化コンピュータプログラムによりプログラムされている、請求の範囲第１項、１３項、２２項のいずれか１項に記載の方法。
【請求項５４】
前記符号化プロセッサは、符号化コンピュータプログラムによりプログラムされ、前記復号化プロセッサは、復号化コンピュータプログラムによりプログラムされている、
請求の範囲第２７項に記載のシステム。
【請求項５５】
前記第１の装置及び第２の装置は、前記方法を実行させるコンピュータプログラムによりプログラムされている、
請求の範囲第２９項に記載の方法。
【発明の詳細な説明】
関連出願
本出願は、１９９６年８月１９日に出願された米国仮特許出願第６０／０２４１３３号の優先権を主張するものであり、この仮特許出願は引用によって本明細書に組み込まれる。
発明の分野
本発明は、情報の符号化および復号に関し、詳細には、プロセッサ・システムによってデジタル・メッセージを暗号化し復号する公開鍵暗号システムに関する。
発明の背景
２つの当事者、たとえば、２つのコンピュータの間でデータを安全に交換するには暗号化が必要である。現在使用されている一般的な暗号化方法には、専用鍵暗号化と公開鍵暗号化の２つがある。専用鍵暗号化では、２つの当事者が符号化および復号に使用される鍵を秘密裏に交換する。専用鍵暗号システムの広く使用されている例にはＤＥＳ、すなわちデータ暗号化標準がある。このようなシステムは非常に高速であり、かつ非常に安全であるが、２つの当事者が鍵を秘密裏に交換しなければならないという欠点を有する。
公開鍵暗号システムは、各当事者が復号プロセスのセキュリティを損なわずに暗号化プロセスを公開することのできるシステムである。この暗号化プロセスは一般に落とし戸関数と呼ばれている。公開鍵暗号システムは、一般に専用鍵暗号システムよりも低速であるが、クレジット・カード番号など少量のデータを送信するために使用され、また、専用鍵暗号化に使用される専用鍵を送信するためにも使用される。
従来、公開鍵暗号システムには様々な落とし戸関数が提案され実施されている。
公開鍵暗号システムを作成するために使用されているある種類の落とし戸関数では、ある群のべき乗が使用され、すなわち、ある群の要素が取り出され、群演算を使用してその要素のべき乗が反復的に求められる。最も頻繁に選択される群は、大きな素数ｐおよびｑのｐｑを法とする乗法群である。ただし、楕円曲線、アーベル多様体、場合によっては非可換行列群など他の群も提案されている。しかし、この種の落とし戸関数は、それぞれ１００桁程度の大きな素数を必要とし、鍵の作成が面倒であり、暗号化および復号に使用されるべき乗プロセスは多数の計算を必要とし、Ｎビットからなるメッセージを暗号化し復号するには百桁の数の多数の乗算とＮ3個程度の演算を必要とする。
公開鍵暗号システムを作成するために使用されている第２の種類の落とし戸関数は、群中のどの数が平方であるか、すなわち通常は、大きな素数ｐおよびｑのｐｑを法とする乗法群を判定するのが困難であることに基づく。第１の種類の場合と同様に、鍵作成が面倒であり、符号化および復号に多数の計算が必要であり、Ｎビットからなるメッセージを符号化し復号するにはＮ3個程度の演算が必要である。
第３の種類の落とし戸関数では、群中で離散対数問題が使用され、一般には、大きな素数ｐを法とする乗法群または楕円曲線が使用される。この場合も、素数ｐが少なくとも１５０桁を必要とし、ｐ−１が大きな素因数を必要とするので、鍵作成は面倒である。このようなシステムはべき乗を使用し、したがってこの場合も、Ｎビットからなるメッセージを符号化し復号するにはＮ3個程度の演算を必要とする。
公開鍵暗号システムを作成するために使用されている第４の種類の落とし戸関数は、ナップサック問題または部分集合和問題に基づく。このような関数は、部分群、通常は、加算される正の整数の部分群を使用する。この種の多くの公開鍵暗号システムは、格子整約技法を使用して破られており、したがって、もはや安全なシステムとはみなされていない。
公開鍵暗号システムを作成するために使用されている第５の種類の落とし戸関数は、誤り訂正符号、特にゴッパ符号に基づく。このような暗号システムは、有限体、一般には２つの要素を含む有限体上で線形代数を使用する。このような暗号システムに対する線形代数アタックがあり、したがって、安全な暗号システムの鍵は４０００００ビット程度の大きな矩形行列である。これは大部分の応用分野で大きすぎる。
公開鍵暗号システムを作成するために使用されている第６の種類の落とし戸関数は、大きな次元Ｎの大きな格子で極めて短い基本ベクトルを見つけることが困難であることに基づく。このようなシステムの鍵は、Ｎ2ビット程度の長さを有し、これは多くの応用分野では大きすぎる。また、このような格子整約公開鍵暗号システムは非常に新しく、したがって、そのセキュリティは完全には分析されていない。
したがって、大部分のユーザは、比較的短く容易に作成される鍵を比較的高速の暗号化プロセスおよび復号プロセスと組み合わせる公開鍵暗号システムを有することが望ましいと考えている。
本発明の目的は、鍵が比較的短く、かつ容易に作成され、符号化プロセスおよび復号プロセスを高速に実行することのできる公開鍵暗号化システムを提供することである。本発明の目的は、比較的低いメモリ要件を有し、かつセキュリティ・レベル、鍵長、符号化・復号速度、メモリ要件、帯域幅をかなり柔軟に兼ね合わせることを可能にする様々なパラメータに依存する公開鍵暗号化システムを提供することである。
発明の概要
本発明は、鍵長が他の一般的な公開鍵暗号システムの鍵長に匹敵する鍵を、ベクトルの大きな集合からほぼ無作為に選択することを可能にし、適切な（たとえば、現状では＝２80）セキュリティ・レベルを備え、最も一般に使用されている公開鍵暗号システム、すなわち前述のべき乗暗号システムよりも１桁ないし２桁程度高速の符号化プロセスおよび復号プロセスを提供する。
本発明の公開鍵暗号システムの実施形態の符号化技法は、２つの数ｐおよびｑを法とする多項式代数および整約に基づく混合システムを使用し、それに対して復号技法は、妥当性が基本確率理論に依存する非混合システムを使用する。本発明の公開鍵暗号システムのセキュリティは、多項式混合システムとｐおよびｑを法とする規約化の独立性との相互作用によってもたらされる。セキュリティは、実験によって観測されるように、たいていの格子では、最も短いベクトルよりもわずかに長いに過ぎない多数のベクトルがある場合に最も短いベクトルを見つけることが非常に困難であることにも依存する。
本発明の実施形態は、環Ｒのイデアルｐおよびｑを選択するステップと、環Ｒの要素ｆおよびｇを生成するステップと、要素Ｆq、すなわちｆ（ｍｏｄ  ｑ）の逆数を生成し、Ｆp、すなわちｆ（ｍｏｄ  ｐ）の逆数を生成するステップと、ｇおよびＦqを使用して得ることのできる積とｍｏｄ  ｑで合同であるｈを含む公開鍵を生成するステップと、ｆおよびＦpを得ることのできる専用鍵を生成するステップと、公開鍵およびランダム要素φを使用してメッセージｍを符号化することによって符号化メッセージｅを生成するステップと、専用鍵を使用して符号化メッセージｅを復号することによって復号メッセージを生成するステップとを含む、デジタル・メッセージｍを符号化し復号する方法の形態である。
本発明の他の特徴および利点は、以下の詳細な説明と添付の図面から容易に明らかになろう。
【図面の簡単な説明】
図１は、本発明の実施形態を実施する際に使用することのできるシステムのブロック図である。
図２は、この流れ図で引用された補助流れ図と共に、本発明の実施形態を実施する際に使用することのできる公開鍵暗号化システムの流れ図である。
図３は、公開鍵および専用鍵を生成するための、本発明の実施形態によるルーチンの流れ図である。
図４は、公開鍵を使用してメッセージを符号化するための、本発明の実施形態による流れ図である。
図５は、専用鍵を使用して符号化メッセージを復号するための、本発明の実施形態による流れ図である。
図６は、公開鍵および専用鍵を生成する、本発明の他の実施形態によるルーチンの流れ図である。
図７は、公開鍵を使用してメッセージを符号化するための、本発明の他の実施形態による流れ図である。
図８は、専用鍵を使用して符号化メッセージを復号するための、本発明の他の実施形態による流れ図である。
詳細な説明
図１は、本発明の実施形態を実施する際に使用できるシステムのブロック図である。２つのプロセッサ・ベース・サブシステム１０５および１５５は、セキュリティの保障されないチャネル５０、たとえば電話やインターネット通信チャネルなどの有線通信チャネルまたは無線通信チャネルを介して通信するように示されている。サブシステム１０５はプロセッサ１１０を含み、サブシステム１５５はプロセッサ１６０を含む。プロセッサ１１０および１６０とそれに関連する回路を後述のようにプログラムすると、これらを使用して本発明の実施形態を実装し、本発明の方法の実施形態を実現することができる。プロセッサ１１０および１６０はそれぞれ、任意の適切なプロセッサ、たとえば電子デジタル・プロセッサまたはマイクロプロセッサでよい。任意の汎用プロセッサまたは特殊目的プロセッサ、あるいは本明細書に記載した機能を電子的または光学的に、あるいは他の手段によって実行することのできる他の機械または回路を使用できることが理解されよう。プロセッサはたとえば、Ｉｎｔｅｌ  Ｐｅｎｔｉｕｍプロセッサでよい。サブシステム１０５は通常、メモリ１２３、クロック・タイミング回路１２１、入出力機能１１８、モニタ１２５を含み、これらはすべて従来型の種類のものでよい。入力には、１０３で示したキーボード入力を含めることができる。通信はトランシーバ１３５を介して行われ、トランシーバ１３５は、モデム、または信号を伝達する任意の適切な装置を備えることができる。
この例示的な実施形態のサブシステム１５５は、サブシステム１０５と同様な構成を有することができる。プロセッサ１６０は、関連する入出力回路１６４、メモリ１６８、クロック・タイミング回路１７３、モニタ１７６を有する。入力にはキーボード１５５が含まれる。サブシステム１５５と外部との通信はトランシーバ１６２を介して行われ、この場合も、トランシーバ１６２はモデム、または信号を伝達する任意の適切な装置を備えることができる。
本発明の公開鍵暗号システム実施形態の符号化技法は、２つの数ｐおよびｑを法とする多項式代数および整約に基づく混合システムを使用し、それに対して復号技法は、妥当性が基本確率理論に依存する非混合システムを使用する。［多項式が順序係数の好都合な表現（いくつかの係数がゼロであってよい、Ｎ個の順序係数を有するＮ−１次の多項式）であり、プロセッサが、指定された演算を係数に対して実行することが理解されよう。］本発明の公開鍵暗号システムのセキュリティは、多項式混合システムとｐおよびｑを法とする規約化の独立性との相互作用によってもたらされる。セキュリティは、実験によって観測されるように、たいていの格子では、最も短いベクトルよりもわずかに長いに過ぎない多数のベクトルがある場合に最も短いベクトルを見つけることが非常に困難であることにも依存する。
本発明の暗号システムは、M. Blum他著「An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information」(Advances in Cryptology: Proceedings of CRYPT0 84, Lecture Notes in Computer Science、第１９６巻、Springer-Verlag、１９８５年、２８９ページないし２９９ページ）およびS. Goldwasser他著「Probabilistic Encryption 」J. Computer and Systems Science 28（１９８４年）、２７０ページないし２９９ページ）に記載された確率暗号システムの一般的な枠組みに適合する。このことは、暗号化がランダム要素を含み、したがって各メッセージが多数の可能な暗号化を有することを意味する。符号化および復号ならびに鍵作成は、本発明の技法を使用して比較的高速にかつ容易に行われ、長さＮのメッセージ・ブロックを符号化または復号するのに必要な演算はＯ（Ｎ2）個であり、したがって、ＲＳＡで必要とされるＯ（Ｎ3）個の演算よりもかなり高速である。鍵長はＯ（Ｎ）であり、R.J. McEliece著「A Public -Key Cryptosystem Based On Algebraic Coding Theory」（JPL Pasadena, DSN Progress Reports 42-44（１９７８年）、１１４ページないし１１６ページ）およびO. Goldreich等著「Public-Key Cryptosystems From Lattice Reduction Problems」（MIT-Laboratory for Computer Science再版、１９９６年１１月）に記載されたような他の「高速」公開鍵システムで必要とされるＯ（Ｎ2）鍵長に匹敵する。
本発明の暗号システムの実施形態は、４つの整数パラメータ（Ｎ、Ｋ、ｐ、ｑ）と、整数係数を有するＮ−１次多項式の３つの集合Ｌq、Ｌφ、Ｌmとに依存する。この実施形態は、環Ｒ＝Ｚ［Ｘ］／（ＸN−１）で働く。要素Ｆ∈Ｒは多項式またはベクトルとして書かれる。
0004068664.tif 000002
星印「*」はＲの乗算を示す。この星印乗算は巡回畳み込み積、すなわち次式のＦ*Ｇ＝Ｈとして明示的に与えられる。
0004068664.tif 000003
（たとえば）ｑを法とする乗算を実行する際、係数はｑを法として整約される。詳細は、付録１を参照されたい。
以下に公開鍵暗号システムの発明による実施形態の例を示す。例示を容易にするために非常に小さな数が使用されており、したがって、この例は暗号に関して安全ではない。例と共に、二重括弧（［［  ］］）内のマテリアルとして、現在の条件の下で暗号に関して安全な実際的な暗号システムを形成する動作パラメータについて説明する。特定のセキュリティ・レベルを達成する動作パラメータの詳細な議論は付録１に記載されている。付録１には、本発明の暗号システムの実施形態の、様々なアタック・タイプに対する耐性についても記載されている。
本発明の実施形態で使用される対象はＮ−１次の多項式である。
ａ1ｘN-1＋ａ2ｘN-2＋...＋ａN-1ｘ＋ａN
上式で、係数ａ1,...,ａNは整数である。本発明の「星印」乗算では、ｘNが１で置き換えられ、ｘN+1がｘで置き換えられ、ｘN-2がｘ2で置き換えられ、以下同様である。［多項式をＮ組の数
［ａ1，ａ2,...,ａN］
で表すこともできる。このような場合、星印積を畳み込み積とも呼ぶ。Ｎの値が大きい場合、実行するステップがＮ2個ではなくＮｌｏｇＮ個程度である高速フーリエ変換法を使用して畳み込み積をより高速に計算することができる。］たとえば、Ｎ＝５とし、２つの例示的な多項式を用いた場合、星印乗算は以下の数式を与える。
(x4+2x2-3x+2)*(2x4+3x3+5x-1)
＝2x8+3x7+4x6+5x5-6x4+16x3-17x2+13x-2
＝2x3+3x2+4x+5x-6x4+16x3-17x2+13x-2
＝-6x4+18x3-14x2+17x+3
［［安全なシステムはたとえば、Ｎ＝１６７またはＮ＝２６３を使用することができる］］［この実施形態は、ｘN−１のすべての倍数からなるイデアルを法とする整数係数を含む多項式の環を使用する。より一般的には、異なるイデアルを法とする多項式を使用することができる。さらに一般的には、他の何らかの環Ｒを使用することができる。環およびイデアルの詳細については、たとえば、I.N.Herstein著「Topics in Algebra」を参照することができる。
この実施形態の他の態様では、イデアルｑなどの整数を法として多項式の係数が整約される。このことは基本的に、各係数をｑで除し、係数をその剰余で置き換えることを意味する。たとえば、ｑ＝１２８であり、ある係数が２３７７である場合、２３７７を１２８で除すると１８であり、剰余が７３であるので、この係数は７３で置き換えられる。しかし、「対称剰余」を使用した方が容易である。このことは、剰余が０ないしｑ／２である場合、係数はそのままであるが、ｑ／２ないしｑである場合は係数からｑが減じられることを意味する。したがって、ｑ＝１２８に対称剰余を使用する場合、−５５＝７３−１２８であるので２３７７は−５５で置き換えられる。
この剰余プロセスが実行されていることを示すには、３重等号（≡）を符号「ｍｏｄ  ｑ」と共に使用する。以下に、２つの多項式の星印乗算を５を法とする規約化と組み合わせる例を示す。答えには対称剰余が使用される。
(x4+2x2-3x+2)*(2x4+3x3+5x-1)≡-6x4+18x3-14x2+17x+3
≡-x4-2x3+x2+2x-2(mod 5)
本発明の実施形態によって（かつ例示を容易にするために、上記で指摘した小さな数を用いて）公開鍵暗号システムを作成する際、第１のステップは整数パラメータＮ、Ｋ、ｐ、ｑを選択することである。以下に例を示す。
Ｎ＝５、Ｋ＝１、ｐ＝３、ｑ＝１２８
［［安全なシステムはたとえば、Ｎ＝１６７、Ｋ＝６、ｐ＝３、ｑ＝２16＝６５５３６を使用することができる］］好ましくは、ｐとｑは互いに素であり、すなわち、１よりも大きな共通因子を有さない。イデアルｐとイデアルｑを互いに素にすることが望ましいことについては付録１に記載されている。以下のように、多項式のいくつかの集合が選択される。
Ｌg＝｛係数が−２、−１、０、１、２である多項式｝
Ｌφ＝｛２つの−１、２つの１、１つの０を係数として有する多項式｝
Ｌm＝｛係数が−１、０、１である多項式｝
［［安全なシステムはたとえば、以下の集合を使用することができる。
Ｌg＝｛係数が−１７７ないし１７７である多項式｝
Ｌφ＝｛係数が４０個の１、４０個の−１、残りの０である多項式｝
Ｌm＝｛係数が−３ないし３である多項式｝
（注：  多項式はＮ−１次を有し、したがって、この例の安全なパラメータの場合、多項式は１６６次を有する。さらに、符号化されている実際のメッセージｍの係数をｐ、すなわちこの例ではｐ＝３で除すると、このメッセージは剰余で構成される）］］。
集合Ｌgは、暗号システムの鍵を作成するために使用され、集合Ｌφはメッセージを符号化するために使用され、集合Ｌmは、可能なメッセージの集合である。たとえば、
2x4-x3+x-2は集合Ｌgに存在し、
x4-x3-x2+1は集合Ｌφに存在する。
鍵作成者Ｄａｎは、この例の鍵作成を実施するとき、集合Ｌgから２つの多項式ｆおよびｇを選択する。この簡略化された例ではＫ＝１であり、したがって１つの多項式ｇのみが存在する。Ｄａｎが次式を選択するものと仮定する。
f＝x4-x3+2x2-2x+1
g＝x4-x3+x2-2x+2
［［安全なシステムはたとえば、Ｋ＋１個の多項式ｆ，ｇ1,...,ｇK∈ＬgをＫ＝６と共に使用することができる。］］
本発明の要件は、ｆが、ｑを法とする逆数とｐを法とする逆数を有さなければならないことである。このことは、次式が成立するように多項式ＦqおよびＦpが存在しなければならないことを意味する。
Fq*f≡1(mod q)およびFp*f≡1(mod p)
周知のユークリッド・アルゴリズムを使用してＦqおよびＦpを算出することができる。たとえば、本明細書の付録ＩＩを参照することができる。（いくつかのｆが逆数を有さないことがある。この場合、Ｄａｎは最初に戻り、別のｆを選択する。）上記の例ｆでは、次式が成立する。
Fq＝103x4+29x3+116x2+79x+58
Fp＝2x4+2x
これがｆの正しいＦqであることを検査するには、以下の乗算を行うことができる。
Fq*f＝(103x4+29x3+116x2+79x+58)*(x4-x3+2x2-2x+1)
＝256x4+256x-127
≡1(mod 128)
同様に、Ｆpが正しいことを検査するには、以下の乗算を行うことができる。
Fp*＝(2x4+2x)*(x4-x3+2x2-2x+1)
＝6x3-6x2+6x-2
≡1(mod 3)
これで、鍵作成者Ｄａｎが自分の公開鍵、すなわち、次式によって与えられる多項式ｈを作成する準備が完了した。
h≡Fq*g(mod q)
［［安全なシステムは、次式によって与えられるＫ個の多項式ｈ1,...,ｈKを使用することができる。］］
hi≡Fq*gi(mod q)、i＝1,2,...,K、K＝6
この例では続いて、Ｄａｎが次式を計算する。
Fq*g＝(103x4+29x3+116x2+79x+58)*(x4-x3+x2-2x+2)
＝243x4-50x3+58x2+232x-98
≡-13x4-50x3+58x2-24x+30(mod 128)
Ｄａｎの公開鍵は以下の多項式である。
h＝-13x4-50x3+58x2-24x+30
Ｄａｎの専用鍵は多項式対（ｆ，Ｆp）である。原則的に、Ｆpは常にｆから計算することができるので、多項式ｆ自体が専用鍵として働くことができる。しかし、実際には、Ｄａｎはおそらく、Ｆpを事前に算出し保存しておく必要がある。
この例の次の部分における専用鍵による符号化について説明する。符号化側ＣａｔｈｙがＤａｎの公開鍵ｈを使用してＤａｎにメッセージを送信する必要があると仮定する。Ｃａｔｈｙは可能なメッセージの集合Ｌmからあるメッセージを選ぶ。たとえば、Ｃａｔｈｙが以下のメッセージを送信すると仮定する。
m＝x4-x3+x2+1
Ｃａｔｈｙは、このメッセージを符号化するとき、集合Ｌφから無作為に多項式φを選択する。たとえば、Ｃａｔｈｙは次式を選択する。
φ＝-x4+x3-x2+1
Ｃａｔｈｙは、無作為に選択したこの多項式φ、Ｄａｎの公開鍵ｈ（ならびにｐおよびｑ、すなわち、公開鍵の一部）、Ｃａｔｈｙの平文メッセージを使用し、以下の公式を使用して符号化メッセージｅを作成する。
e≡pφ*h+m(mod q)
[[安全なシステムはＫ個の公開鍵ｈ1,...,ｈKを、安全な例についてのＫ＝６と共に使用することができる。Ｃａｔｈｙは、メッセージを符号化するときに、集合ＬφからＫ個の多項式φ1,...,φKを無作為に選択し、次いでe≡pφ1*h1+pφ2*h2+...+pφK*hK+m(mod q)を計算することによって符号化メッセージｅを作成することができる。］］別法として、ｈがpFq*g(mod q)と等しくされ、その場合、公式e≡φ*h+m(mod q)を使用してメッセージを符号化することができる。この例では、Ｃａｔｈｙは以下の計算を行う。
pφ*h+m＝3(-x4+x3-x2+1)*(-13x4-50x3+58x2-24x+30)+(x4-x3+x2+1)
＝-374x4+50x3+196x2-357x+487
≡10x4+50x3-60x2+27x-25(mod 128)
したがって、Ｃａｔｈｙの符号化メッセージは以下の多項式であり、
e＝10x4+50x3-60x2+27x-25
Ｃａｔｈｙはこの符号化メッセージをＤａｎに送信する。
この例の次の部分における専用鍵を使用した復号について説明する。Ｄａｎは、メッセージｅを復号するためにまず、専用鍵ｆを使用して以下の多項式を計算する。
a≡f*e(mod q)
使用中の例では、Ｄａｎは以下の計算を行う。
f*e＝(x4-x3+2x2-2x+1)*(10x4+50x3-60x2+27x-25)
＝-262x4+259x3-124x2-13x+142
≡-6x4+3x3+4x2-13x+14(mod 128)
したがって、多項式ａは次式で表される。
a＝-6x4+3x3+4x2-13x+14
次に、ＤａｎはＦp、すなわち自分の専用鍵の他方の半分を使用して以下の計算を行う。
Fp*a(mod p)
この結果が復号メッセージである。したがって、この例では、Ｄａｎは以下の計算を行う。
Fp*a＝(2x4+2x)*(-6x4+3x3+4x2-13x+14)
＝34x4-4x3-20x2+36x-38
≡x4-x3+x2+1(mod 3)
この復号がなぜ有効であるかの詳細な説明については、付録Ｉを参照することができる。
本発明の他の実施形態では、環は行列の環である。たとえば、環Ｒ＝（整数係数を有するＭ×Ｍ個の行列の環）を使用することができる。
Ｒの要素を以下に示す。
0004068664.tif 000004
上式で係数ａijは整数である。加算および乗算は、行列に対して通常行われる加算および乗算であり、このプロセッサが行列のメンバーを、従来型の方式で記憶され処理される数として扱えることが理解されよう。Ｎ＝Ｍ2である場合、Ｒの行列はＮ個の係数を有する。互いに素な整数ｐとｑが選択される。
この場合、Ｄａｎは、専用鍵を作成するために、ＲからＫ＋２個の行列を選択する。これらの行列を
ｆ，ｇ，ｗ1，ｗ2,...,ｗK
と呼ぶ。これらの行列は、ｆ，ｇ，ｗ1,...,ｗKがかなり小さな係数を有し、あらゆるｗiが次式を満たすという特性を有するべきである。
ｗi≡０（ｍoｄ  ｐ）
（言い換えれば、あらゆるｗiのあらゆる係数がｐの倍数である。）Ｄａｎは、自分の鍵を作成するときに、ｐおよびｑを法とするｆおよびｇの逆数を見つける必要がある。したがって、Ｄａｎは、次式を満たすＲ内の行列Ｆp、Ｆq、Ｇp、Ｇqを見つける。
ｆＦp≡Ｉ（ｍｏｄ  ｐ）
ｆＦq≡Ｉ（ｍｏｄ  ｑ）
ｇＧp≡Ｉ（ｍｏｄ  ｐ）
ｇＧq≡Ｉ（ｍｏｄ  ｑ）
上式で、ＩはＭ×Ｍ識別行列である。一般に、これを実行するのは容易であり、何らかの理由で１つの逆数が存在しない場合でも、Ｄａｎは新しいｆまたはｇを選択するだけでよい。
Ｄａｎの公開鍵は、以下の条件によって決定されるＫ個の行列（ｈ1，ｈ2,...,ｈK）の並びである。
ｈi≡ＦqｗiＧq（ｍｏｄ  ｑ）（ｉ＝１，２,...,Ｋ）
（ｗiがｐを法とするゼロと合同であることに留意されたい。）Ｄａｎの専用鍵は４つの行列（ｆ，ｇ，Ｆp，Ｇp）である。原則的に、ｆおよびｇのみを専用鍵として使用できるが、実際にはＦp、Ｇpを事前に計算し記憶しておいた方が効率的である。
この行列の例の符号化について次に説明する。Ｃａｔｈｙがメッセージｍを符号化する必要があるものと仮定する。メッセージｍは、ｐを法とする係数を有する行列である。Ｃａｔｈｙは、自分のメッセージを符号化するために、ある条件を満たすいくつかの整数φ1,...,φKを無作為に選択する。たとえば、これらの整数としては、和φ1＋...＋φKが所定の値ｄと等しい非負整数を選択することができる。（φiが通常の整数であり、行列ではないことに留意されたい。同様に、φiは、識別行列の倍数とみなすことができ、したがって環Ｒのあらゆる要素と交換することができる。）
Ｃａｔｈｙは、自分のφiを選択した後、以下の規則によって符号化メッセージｅを作成する。
e≡φ1h1+φ2h2+...+φKhK+m(mod q)
次に、この行列の例の復号について説明する。Ｄａｎが符号化メッセージｅを受信しており、それを解読する必要があるものと仮定する。Ｄａｎはまず、次式を満たす行列ａを計算する。
ａ≡ｆｅｇ（ｍｏｄ  ｑ）
Ｄａｎは、通常どおり、−ｑ／２ないしｑ／２（すなわち、ゼロ対称係数）や０ないしｑ−１など、ある限られた範囲内でａの係数を選択する。
パラメータが適切に選択される場合、行列ａは以下の和に丁度等しくなる。
a＝φ1w1+φ2w2+...φKwK+fmg
（これは常に、ｑを法として真であるが、重要な点は、ｑが十分大きい場合に、上式が、ｑを法とする場合だけではなく厳密な等式になることである。）Ｄａｎの次のステップは、たとえば次式のように、ｐを法としてａを整約することである。
ｂ≡ａ（ｍｏｄ  ｐ）
ｗiのすべての係数をｐで除することができるので、これは、以下のことを意味する。
ｂ≡ｆｍｇ（ｍｏｄ  ｐ）
最後に、Ｄａｎは以下の計算を行い、
ＦpｂＧp（ｍｏｄ  ｐ）
最初のメッセージｍを再生する。
前述のＭ×Ｍ行列の実施形態は優れた動作時間を有する。符号化は、加算しか必要とせず、Ｍ2個程度の演算を実行する。復号はＭ×Ｍ行列の２回の行列乗算を必要とし、したがって、Ｍ3個の演算を実行する。メッセージ長はＭ2程度であり、したがって、Ｎが固有メッセージ長（すなわち、Ｎ＝Ｍ2）を示す場合、行列実施形態は、符号化にはＯ（Ｎ）個のステップを必要とし、復号にはＯ（Ｎ3/2）個のステップを必要とする。これに対して、多項式実施形態は、符号化にＯ（Ｎ2）個のステップを必要とし、復号にＯ（Ｎ2）個のステップを必要とし、ＲＳＡ公開鍵システムは、符号化にＯ（Ｎ3）個のステップを必要とし復号にＯ（Ｎ3）個のステップを必要とする。
予備的な分析により、次元がＮ2＋Ｎ（またはそれ以上）である格子を使用する必要があるのは、行列実施形態に対する固有格子アタックだけであることがわかっている。これは、多項式実施形態を解読するために使用される２Ｎ次元格子に対する著しいセキュリティの向上である。
暴力的（または潜在的なｍｅｅｔ−ｉｎ−ｔｈｅ−ｍｉｄｄｌｅ）アタックを回避するには、φiのサンプル空間をかなり大きくし、たとえば２100ないし２200にする必要がある。しかし、こうするのは困難である。たとえば、φiが、和ｄを有する非負の値として選択された場合、サンプル空間は、
0004068664.tif 000005
個の要素を有する。したがって、たとえばＫ＝１５およびｄ＝１０２４を選択した場合、２103.8個の要素を有するサンプル空間が得られる。
公開鍵サイズはＫＭ2ｌｏｇ2（ｇ）ビットであり、専用鍵サイズは２Ｍ2ｌｏｇ2（ｐｑ）ビットである。これらは共に実際的なサイズである。
図２は、公開鍵暗号化システムと共に使用できる基本手順を示し、本発明の実施形態による特徴を説明する参照される他の流れ図によって示されるルーチンを指す。ブロック２１０は、公開鍵情報および専用鍵情報の生成と、公開鍵の「公開」を表す。本発明の実施形態のルーチンについて図３の流れ図に関して説明する。この例では、この演算がプロセッサ・システム１０５で実行されるものと仮定することができる。公開鍵情報は、公開することができ、すなわち、公衆の任意のメンバー、または専用鍵保持者が暗号化メッセージを受信する必要のある所望の群に利用させることができる。通常、必ずしも必要ではないが、公開鍵保持者およびその公開鍵のディレクトリが維持されている中央公開鍵ライブラリ施設またはウェブサイトで公開鍵を利用可能にすることができる。この例では、プロセッサ・システム１５５のユーザがプロセッサ・システム１０５のユーザに秘密のメッセージを送信する必要があり、プロセッサ・システム１５５のユーザがプロセッサ・システム１５０のユーザの公開済みの公開鍵を知っているものと仮定する。
ブロック２２０は、所期のメッセージ受信側の公開鍵を使用して平文メッセージを符号化するためにメッセージ送信側（すなわち、この例ではプロセッサ・システム１５５のユーザ）によって使用することのできるルーチンを表す。本発明の実施形態によるこのルーチンについては、図４の流れ図に関して説明する。この場合、暗号化メッセージはチャネル５０（図１）を介して送信される。
図２のブロック２６０は、暗号化メッセージを復号して平文メッセージを再生するルーチンを表す。この例では、この機能は、専用鍵情報を使用するプロセッサ・システム１０５のユーザによって実行される。本発明の実施形態の復号ルーチンについては図５の流れ図に関して説明する。
次に、図３を参照すると、全体的に図２のブロック２１０で表された、公開鍵および専用鍵を生成するルーチンの流れ図が示されている。このルーチンはこの例では、プロセッサ・システム１０５のプロセッサ１１０をプログラムするために使用することができる。ブロック３０５は、整数パラメータＮ、ｐ、ｑの選択を表す。前述のように、Ｎは、生成される多項式ｆおよびｇiの次数を決定し、ｐおよびｑはそれぞれ、星印積を生成する際に使用される２つのイデアルである。ブロック３１５はＫ、すなわち使用される多項式ｇiの数を表す。上記の簡略化された例では、Ｋは１であり、例示的で比較的安全な特定のシステムがＫ＝６を使用できることに留意されたい。次に、ブロック３２５は無作為な多項式ｆ、ｇ1、ｇ2...ｇKの選択を表す。係数はたとえば、乱数発生装置を使用して選択することができ、乱数発生装置は、利用可能なハードウェアまたはソフトウェアを使用して周知の方法で実装することができる。この実施形態では、各プロセッサ・システムが乱数発生装置を備え、乱数発生装置は図１ではそれぞれ、ブロック１３０および１８５で指定されている。
ブロック３４０は、選択済みの多項式ｆの逆数ＦqおよびＦpが存在する場合に、それらの逆数を前述のように求めるためにユークリッド・アルゴリズムを応用することを表す。Ｆp、Ｆqが存在しない場合、再びブロック３２５に入り、新しい多項式ｆが選択される。ループ３３０は、定義済みの逆数を算出できる多項式が選択されるまで継続する。［所与の多項式について逆数が存在する確率は比較的高く、したがって一般に、この条件が満たされるまでにループ３３０を横断する回数は比較的少ないことが予期される。］次いで、ブロック３５０に入る。このブロックは前述のように、
ｈ＝Ｆq*ｇ（ｍｏｄ  ｑ）
による公開鍵ｈの計算を表す。［Ｋ＞１の場合、ｉ＝１，２,...,Ｋについて公開鍵構成要素ｈiがある。］ブロック３６０で表されるように、専用鍵は多項式ｆ、ＦPとして保持され、この場合、ブロック３７０で表されるように、公開鍵を公開することができる。
図４は、平文メッセージｍの符号化を実施するようにプロセッサ・システム１５５（図１）のプロセッサ１６０などのプロセッサをプログラムするルーチンの、図２のブロック２４０によって一般的に表される流れ図である。符号化されるメッセージが入力され（ブロック４２０）、ランダム多項式φが選択される（ブロック４３０）。［Ｋ＞１の場合、Ｋ個の無作為多項式φ1，φ2,...,φKが選択される。］この多項式は、前述のように集合Ｌφの多項式でよく、ランダム係数は、任意のハードウェア手段またはソフトウェア手段、たとえば、乱数発生装置１８５によって選択することができる。次いで、符号化メッセージｅを次式のように算出することができる（ブロック４５０）。
ｅ＝ｐφ*ｈ＋ｍ（ｍｏｄ  ｑ）
上記で指摘したように、Ｋが１よりも大きい場合、符号化メッセージはe≡pφ1*h1+pφ2*h2+....+pφK*hK+m(mod q)になる。この符号化メッセージは、チャネル５０を介して鍵保持者、すなわち、この例ではプロセッサ・システム１０５のユーザに送信する（ブロック４６０）ことができる。
図５は、図２で全体的にブロック２６０によって表された、暗号化メッセージを復号する本発明の実施形態によるルーチンの流れ図である。ブロック５３０は暗号化メッセージｅの受信を表す。定義済みの多項式ｆおよびＦpと整数Ｎ、ｐ、ｑとを含む保持されている専用鍵情報が取り出される（ブロック５５０）。次に、ブロック５７０は次式の計算を表している。
ａ≡ｆ*ｅ（ｍｏｄ  ｑ）
次いで、本明細書ではｍ’として指定された復号メッセージを次式のように算出することができる（ブロック５８０）。
ｍ’≡Ｆp*ａ（ｍｏｄ  ｐ）
図６、図７、図８は、前述の行列実施形態に関する流れ図である。図６は、全体的に図２のブロック２１０によって表された、公開鍵および専用鍵を生成するルーチンの流れ図である。前述のように、このルーチンをこの例で使用して、プロセッサ・システム１０５のプロセッサ１１０をプログラムすることができる。ブロック６０５は、整数パラメータＮ、ｐ、ｑの選択を表し、Ｎは行列係数の数であり、ｐおよびｑは互いに素な整数である。ブロック６１５はＫの選択を表し、Ｋを選択することによって行列の数が決定される。次に、ブロック６２５はランダム行列ｆ，ｇ，ｗ1，ｗ2,...,ｗKの選択と、ｗ1，ｗ2,...,ｗKがすべて、ｐを法として０と合同であるという要件とを表す。この場合も、この目的のために乱数発生装置１３０（図１）を使用することができる。
ブロック６４０は、定義済みの行列Ｆp、Ｆq、Ｇp、Ｇqの決定を表す。これらの行列が存在しない場合、再びブロック６２５に入り、新しい行列ｆおよびｇが選択される。ループ６３０は、定義済みの逆数を算出できる行列が選択されるまで継続する。次いで、ブロック６５０に入る。このブロックは、公開鍵、すなわち、以下の条件によって決定されるＫ個の行列（ｈ1，ｈ2,...,ｈK）のリストの算出を表す。
hi≡FqwiGq(mod q)(i＝1,2,...,K)
ブロック６６０で表されているように、専用鍵は行列（ｆ，ｇ，Ｆp，Ｇp）として保持され、その場合、ブロック６７０で表したように公開鍵を公開することができる。
図７は、この行列実施形態の技法を使用して平文メッセージｍの符号化を実施するようにプロセッサ・システム１５５（図１）のプロセッサ１６０などのプロセッサをプログラムする、全体的に図２のブロック２４０で表されたルーチンの流れ図である。符号化されるメッセージが入力され（ブロック７２０）、ランダム整数φ1，φ2,...,φKが選択される（ブロック７３０）。これらの整数は乱数発生装置１８５（図１）によって選択することができる。次いで、符号化メッセージｅを次式のように算出することができる（ブロック７５０）。
e≡φ1h1+φ2h2+...+φkhk+m(mod q)
この符号化メッセージは、チャネル５０を介して鍵保持者、すなわち、この例ではプロセッサ・システム１０５のユーザに送信することができる（ブロック７６０）。
図８は、図２で全体的にブロック２６０によって表された、この行列実施形態によって暗号化メッセージを復号するルーチンの流れ図である。ブロック８３０は暗号化メッセージｅの受信を表す。定義済みの多項式Ｆ、ｇ、Ｆp、Ｇpと整数Ｎ、ｐ、ｑとを含む保持されている専用鍵情報が取り出される（ブロック８５０）。次に、ブロック８７０は次式の計算を表している。
ａ≡ｆｅｇ（ｍｏｄ  ｑ）
次に、ａは、次式のように、ｐを法としてｂに整約される（ブロック８８０）。
ｂ≡ａ（ｍｏｄ  ｐ）
次いで、次式のように復号メッセージが算出される（ブロック８９０）。
ｍ’≡ＦpｂＧp（ｍｏｄ  ｐ）
特定の好ましい実施形態を参照して本発明を説明したが、当業者には本発明の趣旨および範囲内の変形形態が企図されよう。たとえば、公開鍵または専用鍵を任意の適切な媒体、たとえば「スマート・カード」上に記憶し、符号化および／または復号を実行できるマイクロプロセッサをこのスマート・カードに備え、それによって暗号化メッセージをスマート・カードへ伝達し、かつ／あるいはスマート・カードから伝達することができることが理解されよう。
ＮＴＲＵ：環ベースの公開鍵暗号システム
JEFFREY HOFFSTEIN、JILL PIPHER、JOSEPH H.SILVERMAN
要約  ＮＴＲＵ、すなわち新規の公開鍵暗号システムについて説明する。ＮＴＲＵは、鍵がかなり短く容易に作成されること、高速であること、およびメモリ要件が低いことを特徴とする。ＮＴＲＵの符号化および復号は、基本確率理論に基づくクラスタ化原則と組み合わされた、多項式代数によって提案されている混合システムを使用する。ＮＴＲＵ暗号システムのセキュリティは、多項式混合システムと、互いに素な２つの整数ｐおよびｑを法とする整約の独立性との相互作用によってもたらされる。
目次
０．はじめに
１．ＮＴＲＵアルゴリズムの説明
２．パラメータの選択
３．セキュリティ分析
４．実施にあたって考慮すべき点
５．ＮＴＲＵの適度なセキュリティ・パラメータ
６．他のＰＫＣＳとの比較
付録Ａ．基本補題
§０．はじめに
ＤｉｆｆｅおよびＨｅｌｌｍａｎ［４］が、どのようにすれば１方向関数を使用して効率的で計算コストの低い公開鍵暗号を作成できるかについて説明して以来、このようなシステムの作成にかなりの関心が払われている。現在の所、最も広く使用されている公開鍵システムはＲＳＡである。ＲＳＡは、１９７８年にＲｉｖｅｓｔ、Ｓｈａｍｉｒ、Ａｄｅｌｍａｎによって作成されたものであり［１０］、大きな数を因数分解することが困難であることに基づく。他のシステムには、誤り補正符号に依存するＭｃＥｌｉｅｃｅシステム［９］と、格子整約問題の難点に基づくＧｏｌｄｒｅｉｃｈ、Ｇｏｌｄｗａｓｓｅｒ、Ｈａｌｅｖｉ［５］の最近のシステムが含まれる。
この論文では、新規の公開鍵暗号システムについて説明する。この暗号システムをＮＴＲＵシステムと呼ぶ。符号化手順では、多項式代数と２つの数ｐおよびｑを法とする整約に基づく混合システムを使用し、これに対して、復号手順では、妥当性が基本確率理論に依存する非混合システムを使用する。ＮＴＲＵ公開鍵暗号システムのセキュリティは、多項式混合システムと、互いに素な２つの整数ｐおよびｑを法とする整約の独立性との相互作用によってもたらされる。セキュリティは、（実験によって観測されるように）、たいていの格子では、（適度に短いベクトルではなく）極めて短いベクトルを見つけることが困難であることにも依存する。
この論文で発表する内容は、すでに広く配布されているが未公表の前刷り［７］とは２つの主要な点で異なる。第１に、より良好な動作特性を有するシステムを生成するために使用できる新しいパラメータＫを導入した。第２に、主として、ｅメールを介してＤｏｎＣｏｐｐｅｒｓｍｉｔｈ、Ｊｏｈａｎ  Ｈａｓｔａｄ、Ａｄｉ  Ｓｈａｍｉｒから頂いた多数のコメントと最近の論文［３］中の多数のコメントに基づいて、格子ベースのアタックの分析を展開し明確化した。この機会を利用して、この研究に関心を抱き援助していただいた上記の各氏に対して謝意を表したい。
ＮＴＲＵは、［１］および［６］に記載されたように確率暗号システムの一般的な枠組みに適合する。このことは、暗号化がランダム要素を含み、したがって各メッセージが多数の可能な暗号化を有することを意味する。ＮＴＲＵを用いた符号化および復号は極めて高速であり、鍵の作成は高速で容易である。詳細は第４章および第５章を参照されたいが、ＮＴＲＵでは、長さＮのメッセージ・ブロックを符号化または復号するのに必要な演算がＯ（Ｎ2）個であり、ＲＳＡで必要とされるＯ（Ｎ3）個の演算よりもかなり高速であることに留意されたい。さらに、ＮＴＲＵ鍵長はＯ（Ｎ）であり、［９，５］など他の「高速」公開鍵で必要とされるＯ（Ｎ2）鍵長に匹敵する。
§１  ＮＴＲＵアルゴリズムの説明
§１．１  表記法
ＮＴＲＵ暗号システムは、４つの整数パラメータ（Ｎ、Ｋ、ｐ、ｑ）と、整数係数を有するＮ−１次多項式の３つの集合Ｌg、Ｌφ、Ｌmに依存する。環Ｒ＝Ｚ［Ｘ］／（ＸN−１）を使用する。要素Ｆ∈Ｒを多項式またはベクトルとして書く。
0004068664.tif 000006
▲×▼を使用してＲの乗算を示す。この星印乗算は、巡回畳み込み積として明示的に与えられる。
0004068664.tif 000007
（たとえば）ｑを法とする乗算を行う際、ｑを法として係数を整約する。
注  原則的に、積Ｆ▲×▼Ｇの計算にはＮ2回の乗算が必要である。しかし、ＮＴＲＵによる典型的な積の場合、ＦとＧのうちの一方が小さな係数を有し、したがって、Ｆ▲×▼Ｇの計算は非常に高速である。一方、Ｎが大きいとみなされる場合は、高速フーリエ変換を使用してＯ（ＮｌｏｇＮ）個の演算で積Ｆ▲×▼Ｇを計算した方が高速である。
§１．２  鍵の作成
ＮＴＲＵ鍵を作成する場合、Ｄａｎは、Ｋ＋１個の多項式ｆ，ｇ1,...,ｇK∈Ｌgを無作為に選択する。多項式ｆは、ｑおよびｐを法とする逆数を有するという追加の要件を満たさなければならない。パラメータが適切に選択される場合、これはｆの大部分の選択肢について真であり、これらの逆数の実際の計算は、修正されたユークリッド・アルゴリズムを使用して容易に行うことができる。これらの逆数をＦqおよびＦpによって示す。
Fq▲×▼f≡1(mod q)  および  Fp▲×▼f≡1(mod p)    (1)
Ｄａｎは次に、以下の数量を計算する。
hi≡Fq▲×▼gi(mod q)  1≦i≦K    (2)
Ｄａｎの公開鍵は、以下に示す多項式の並びである。
（ｈ1，ｈ2,...,ｈK）
Ｄａｎの専用鍵は単一の多項式ｆである。ただし、実際には、ＤａｎはＦpを記憶する必要がある。
§１．３  符号化
Ｃａｔｈｙ（符号化側）がＤａｎ（復号側）にメッセージを送信する必要があるものと仮定する。Ｃａｔｈｙはまず、１組の平文Ｌmからメッセージｍを選択する。次に、ＣａｔｈｙはＫ個の多項式φ1,...,φK∈Ｌφを無作為に選択し、Ｄａｎの公開鍵（ｈ1,...,ｈKを使用して以下の計算を行う。
0004068664.tif 000008
これが、ＣａｔｈｙがＤａｎに送信する符号化メッセージである。
§１．４  復号
ＤａｎがＣａｔｈｙからメッセージｅを受信しており、自分の専用鍵ｆを使用してこのメッセージを復号するものと仮定する。これを効率的に行うために、Ｄａｎは第１．１節で説明した多項式Ｆpを事前に計算しておくべきである。
ｅを復号するために、Ｄａｎはまず以下の計算を行う。
a≡f▲×▼e(mod q)
この場合、Ｄａｎは−ｑ／２ないしｑ／２の間隔でａの係数を選択する。次に、Ｄａｎは、ａを整数係数を有する多項式とみなして、以下の計算を行うことによってメッセージを再生する。
Fp▲×▼a(mod p)
注  パラメータ値が適切である場合、この復号手順によって最初のメッセージが再生される確率は極めて高い。しかし、ある種のパラメータ選択肢では、復号が失敗することがあり、したがっておそらく、各メッセージ・ブロックにいくつかの検査ビットを含めるべきである。復号が失敗する通常の原因は、メッセージのセンタリングが不適切であることである。この場合、Ｄａｎは、わずかに異なる間隔、たとえばｘがある小さな（正または負の）値である場合の−ｑ／２＋ｘないしｑ／２＋ｘでａ≡ｆ▲×▼ｅ（ｍｏｄ  ｑ）の係数を選択することによってメッセージを回復することができる。ｘのどの値も機能しない場合には、間隔障害があり、メッセージを容易に復号することはできない。パラメータ値が適切に選択される場合には、間隔障害が起こることはまれであり、したがって、実際上間隔障害を無視することができる。
§１．５  なぜ復号が機能するか
Ｄａｎが計算した多項式ａは以下の数式を満たす。
0004068664.tif 000009
この最後の多項式について検討する。
0004068664.tif 000010
パラメータの選択が適切である場合は、（ほぼ常に）すべての係数が−ｑ／２とｑ／２の間に位置し、したがって、ｑを法として係数が整約される場合でもこの多項式は変化しない。このことは、Ｄａｎが、ｑを法とするｆ▲×▼ｅの係数を−ｑ／２ないしｑ／２の間隔に整約するときに、以下の多項式を厳密に再生することを意味する。
0004068664.tif 000011
次いで、ｐを法としてａを整約すると、多項式ｆ▲×▼ｍ（ｍｏｄ  ｐ）が与えられ、Ｆpによる乗算によってメッセージｍ（ｍｏｄ  ｐ）が取り込まれる。
§２  パラメータの選択
§２．１  表記およびノルム推定
要素Ｆ∈Ｒの幅を次式のように定義する。
0004068664.tif 000012
我々の表記が示すように、これは、Ｒ上の一種のＬ∞ノルムである。同様に、次式によってＲ上の対称Ｌ2を定義する。
0004068664.tif 000013
（同様に、
0004068664.tif 000014
はＦの係数の標準偏差である。）
前提  任意のε＞０について、ε、Ｎ、Ｋに応じて定数ｃ1、ｃ2＞０があり、したがって、無作為に選択された多項式Ｆ1,...,ＦK、Ｇ1,...,ＧK∈Ｒについて、これらの多項式が次式を満たす確率は１−εよりも大きくなる。
0004068664.tif 000015
もちろん、この前提は、比ｃ2／ｃ1が小さなεに対して非常に大きい場合には、実際的な観点から無用である。しかし、ＮおよびＫが適度に大きな値を有し、εの値が非常に小さい場合でも、定数ｃ1、ｃ2が極端な値を有することはないことが判明している。このことは、実験によって多数の状況で検証されており、この論文において理論的な証拠の概要を示す。
§２．２  サンプル空間
典型的なサンプル空間の例として以下のものを使用する。
Ｌg＝｛ｇ∈Ｒ：ｇは−（ｒ−１）ないし（ｒ−１）／２の係数を有する｝
Ｌφ＝｛φ∈Ｒ：φは、１に等しいｄ個の係数と、−１に等しいｄ個の係数を有し、残りは０である｝
Ｌm＝｛ｍ∈Ｒ：ｍは−（ｓ−１）ないし（ｓ−１）／２の係数を有する｝
後で、セキュリティを達成するためにｒ、ｄ、ｓが満たさなければならない様々な制約があることが理解されよう。また、あらゆるφ∈ＬφがＬ2ノルム
0004068664.tif 000016
を有し、それに対して、平均要素ｇ∈Ｌgおよびｍ∈ＬmがＬ2ノルム
0004068664.tif 000017
を有することにも留意されたい。表記を容易にするために、Ｌg、Ｌφ、Ｌmの要素の平均Ｌ2ノルムをＬg、Ｌφ、Ｌmと書くことにする。
厳密に必要なことではないが、
0004068664.tif 000018
という追加の仮定を行う。この仮定によって、可能な格子アタックを分析すると共に、そのようなアタックを有効でなくすことが容易になる。一例として
0004068664.tif 000019
を選択すると仮定する。この場合、
0004068664.tif 000020
が選択される。したがって、無作為にｍの係数にｐを加算し、ｍの係数からｐを減算することによって、ｍに含まれる固有ｍｏｄ  ｐ情報の「密度を高くする」必要がある。
§２．３  復号基準
§１．５で説明したように、｜Σｐφi▲×▼gi＋ｆ▲×▼ｍ｜∞＜ｑである場合、Ｄａｎは符号化メッセージｍを復号することができる。上記の前提の不等式（３）を使用して（Ｋの代わりにＫ＋１を用い、εとして十分に小さな値を選択する）以下の推定を行うことができる。
0004068664.tif 000021
したがって、（確率１−εで）復号を行うために、Ｄａｎは、以下の復号制約を満たすパラメータを選択する必要がある。
ｃ2ｐＬgＬφ（Ｋ＋１）＜ｑ    (4)
§３  セキュリティ分析
§３．１  Ｍｅｅｔ−ｉｎ−ｔｈｅ−ｍｉｄｄｌｅアタック
説明を簡単にするために（かつアタッカを助けるために）、Ｋ＝１であり、したがって、符号化メッセージがｅ≡φ▲×▼ｈ＋ｍ（ｍｏｄ  ｑ）として表されるものと仮定する。Ａｎｄｒｅｗ  Ｏｄｌｙｚｋｏは、φに対して使用することのできるｍｅｅｔ−ｉｎ−ｔｈｅ−ｍｉｄｄｌｅアタックがあると指摘しており、専用鍵ｆにも同様なアタックが適用されると考えられる。簡単に言えば、ｆをｆ＝ｆ1＋ｆ2に分割し、ｆ1▲×▼ｅを−ｆ2▲×▼ｅと突き合わせ、対応する係数がほぼ同じ値を有するような（ｆ1、ｆ2）を見つける。したがって、（たとえば）２80のセキュリティ・レベルを得るには、約２160個の要素を含む集合からｆ、ｇ、φを選択しなければならない。
§３．２  多重送信アタック
やはり説明を簡単にするために、Ｋ＝１と仮定する。Ｃａｔｈｙが、同じ公開鍵と異なるランダムφを使用して単一のメッセージｍを数回にわたって送信する場合、アタッカＢｅｔｔｙは、メッセージの大部分を再生できると考えられる。簡単に言えば、Ｃａｔｈｙがｅi≡φi▲×▼ｈ＋ｍ（ｍｏｄ  ｑ）（ｉ＝１，２,...,ｒ）を送信すると仮定した場合、Ｂｅｔｔｙは（ｅi−ｅ1）▲×▼ｈ-1（ｍｏｄ  ｑ）を計算し、それによってφi−φ1（ｍｏｄ  ｑ）を再生することができる。しかし、φの係数は非常に小さいので、Ｂｅｔｔｙはφi−φ1のみを再生し、これからφ1の多数の係数を再生する。ｒが適度なサイズ（たとえば、４または５）である場合でも、Ｂｅｔｔｙは、ｂｒｕｔｅ  ｆｏｒｃｅによってすべての可能性を試験するのに十分なφ1を再生し、それによってｍを再生する。したがって、基本メッセージの他の何らかのスクランブリングを行わずに多重送信を行うことは好ましくない。Ｂｅｔｔｙが単一のメッセージをこのように復号する場合でも、この情報は、他のメッセージを復号するうえで助けとならないことに留意されたい。
§３．３  格子ベースのアタック
まず格子整約に関するいくつかの語について説明する。格子整約の目標は、所与の格子Ｍ内の１つまたは複数の「小さな」ベクトルを見つけることである。理論的には、Ｍ内の最小のベクトルはしらみつぶし的探索によって見つけることができるが、実際には、Ｍの次元が大きい場合、これは不可能である。Ｓｃｈｎｏｒｒ［１１、１２］およびその他によって様々な改良を施されたＬｅｎｓｔｒａ−Ｌｅｎｓｔｒａ−Ｌｏｖａｓｚ［８］のＬＬＬアルゴリズムでは、多項式時間でＭの最小ベクトルが見つかるが、次元の大きな（たとえば、≧１００）たいていの格子では、最小ベクトルは見つからず、最小のＬＬＬ判定可能ベクトルと実際の最小ベクトルとの間のギャップは次元と共に指数関数的に増加するようである。格子アタックに対するＮＴＲＵのセキュリティについて説明するために、大きな次元の格子に関する以下の３つの仮説を考える。
（Ｈ1）たいていの格子Ｍでは、Ｍの最小非ゼロ・ベクトルの長さσ（Ｍ）は次式を満たす。
0004068664.tif 000022
したがって、ｖ∈Ｍが次式を満たす場合、
0004068664.tif 000023
ｖはほぼ同じ長さの指数関数的に多数のベクトルに隠される。
（Ｈ2）格子Ｍが、（Ｈ1）によって説明した予期される最短ベクトルよりも小さなベクトルｗを有するが、他の場合には「ランダムな」格子であるものと仮定する。ｗが次式を満たす場合、
0004068664.tif 000024
格子整約によってｗが見つかる可能性は非常に低い。
（Ｈ3）（Ｈ2）の状況であると仮定する。この場合、格子整約方法によって算出される最小非ゼロ・ベクトルｖLLLはほぼ確実に次式を満たす。
|vLLL｜≧κdim(M)｜w｜
注  仮説（Ｈ2）および（Ｈ3）に現われる格子整約定数ｋは、実験および経験によって決定しなければならない。これは、ＲＳＡＰＫＣＳを用いた場合と同様であり、セキュリティは、積ｐｑを因数分解する現在の機能の推定に依存する。これは、［５］に記載されたＰＫＣＳにより類似しており、ＰＫＣＳのセキュリティは、格子の小さな（ほぼ直交化された）基を見つけるのが困難なことに直接関連している。次元の大きな（≧１００）格子を用いた実験によって、κ＝１．５1/100を使用できることがわかっている。（たとえば、［１１］および［１２］を参照されたい。）因数分解が進むにつれて、ＲＳＡ  ＰＫＣＳで大きな素数を使用することが必要になり、したがって、格子の整約が進むにつれて、より小さな値のｋとそれに対応するより大きなパラメータをＮＴＲＵで使用することが必要になるのは間違いない。また、７００よりも大きな次元の格子については仮説（Ｈ2）および（Ｈ3）を仮定するだけでよい。このような高次元の格子では、場合によってはＳｃｈｎｏｒｒのブロック整約改良を含むＬＬＬアルゴリズムでも長時間を必要とする。次元が約３００の格子について仮説（Ｈ2）および（Ｈ3）を仮定する場合、ずっと優れた動作特性を有するＮＴＲＵパラメータを選択することができる。
§３．３．１  鍵ｆに対する小格子アタック
まず、恐らく最も自然な格子から始め、すなわち、任意の１つのｈiを選択し、ｈi▲×▼ｆ（ｍｏｄ  ｑ）も小さいという特性を有する小さなベクトルｆを探索する。これを行うには、ｈi＝［ｈi1,...,ｈiN］とし、以下の行列の列によって生成される格子Ｍを検討する。
0004068664.tif 000025
将来の表記に関する都合上、この行列を次式のように書く。
0004068664.tif 000026
アタックを最適化するためにアタッカによって数量λが選択される。Ｍは次式を満たすと考えられる。
ｄｉｍ（Ｍ）＝２ＮおよびＤｉｓｃ（Ｍ）＝λNｑN
考慮すべき２つの問題がある。第１の問題は、Ｍに短いベクトルとして埋め込まれる実際の鍵ｆである。Ｍが以下の目標ベクトルを含み、
ｖtarg＝［λｆN,...,λｆ1，ｇi1,...,ｇiN］
ｖtargがわかることによってｆを再生できることに留意されたい。しかし、ｖｔａｒｇの長さを次式のように算出することができる。
0004068664.tif 000027
仮説（Ｈ1）によれば、｜ｖtarg｜2が以下の不等式を満たす場合、ｆはアタックを受けても安全である。
0004068664.tif 000028
言い換えれば、次式が成立する必要がある。
0004068664.tif 000029
アタッカは左辺を最小化したいので、アタッカの視点からの最適なλはλ＝１（補題Ａ．１参照）である。したがって、次式が成立する場合は安全である。
0004068664.tif 000030
考慮すべき第２の点は、Ｍ内の他のある小さなベクトルによって、アタッカがメッセージを復号できるかどうかである。したがって、任意の小さなベクトル［ｆ’，ｇ’］∈Ｍは、ｆ’とｈi▲×▼ｆ’≡ｇ’（ｍｏｄ  ｑ）が共に小さいという特性を有する。しかし、アタッカが以下の計算を行った場合、
0004068664.tif 000031
ｑを法とする小さな係数を有するのは、ｊ＝ｉを含む項だけである。したがって、単一のｈiを小さくするｆ’は復号鍵としては働かない。このことは、すべてのｈjを同時に検討していることを示し、したがって次の格子に進む。
§３．３．２  鍵ｆに対する大格子アタック
アタッカは、１つのｈiのみを使用するのではなく、ｈiのある部分集合を使用して格子を形成することができる。アタッカが、ｈ1,...,ｈk（１≦ｋ≦Ｋ）を使用し、以下の行列の列によって生成される格子Ｍを形成するものと仮定する。
0004068664.tif 000032
（前の節の略号を使用している）この格子は次式を満たす。
ｄｉｍ（Ｍ）＝（ｋ＋１）ＮおよびＤｉｓｃ（Ｍ）＝λNｑkN
この格子は、（自明のショートハンドを使用する）目標ベクトルを含む。
ｖtarg＝｛λｆ，ｇ1，ｇ2,...,ｇk｝
（より厳密に言えば、ｆの座標を反転する必要がある。）この目標ベクトルは以下の長さを有する。
0004068664.tif 000033
仮説（Ｈ2）によれば、ｖtargの長さが次式を満たしているかぎり、格子整約ではｖtargを見つけることはできない。
0004068664.tif 000034
したがって、次式が成立する場合にはアタックを受けても安全である。
0004068664.tif 000035
前述のように、アタッカはλを選択して左辺を最小化する。この場合も、λ＝１の場合に最小値が得られ（補題Ａ．１参照）、したがって、次式が成立するかぎり仮説（Ｈ2）の下で実際の鍵は安全である。
0004068664.tif 000036
§３．３．３  スプリアス鍵ｆに対する大格子アタック
アタッカは、真の鍵ｆを探索するのではなく、復号鍵として働く他の何らかの鍵Ｆを見つけることを試みることがある。Ｆ自体と各積ｈj▲×▼Ｆ（ｍｏｄ  ｑ）をスプリアス鍵にするには、これらを小さくしなければならない。話を厳密にするために、アタッカがＦを見つけ次式を計算するものと仮定する。
Ｇj≡ｈj▲×▼Ｆ（ｍｏｄ  ｑ）（ｊ＝１、２,...,Ｋ）
次式の幅（Ｌ∞ノルム）が一般に、
φ1▲×▼Ｇ1＋φ2▲×▼Ｇ2＋...＋φK▲×▼ＧK＋ｍ▲×▼Ｆ
あるラッピング係数Ｗについて少なくともＷqであることを知る必要がある（システムが安全であるにはＷをどのくらい大きくしなければならないかの問題については第４章で論じる）。
アタッカは、スプリアス鍵Ｆを見つけるために、第３．３．２節で説明した格子Ｍを取り出し、格子整約技法を使用して小さなベクトルｖLLLを見つける。Ｍ内の最小非ゼロ・ベクトルはベクトルｖtarg＝｛λｆ，ｇ1,...,ｇK｝であり、したがって、仮説（Ｈ3）によれば次式が成立する。
｜ｖLLL｜2≧κ(K+1)N｜ｖtarg｜2
ｖLLL＝［λＦ，Ｇ1，Ｇ2,...,ＧK］とすると、次式が成立することがわかる。
0004068664.tif 000037
格子整約によって得られるベクトルｖLLLは、サイズが多少とも無作為に分散する成分を有する。特に、すべての長さ｜λＦ｜2，｜Ｇ1｜2,...,｜ＧK｜2がほぼ同じであり、したがって、（ほぼ）次式が得られる。
｜λＦ｜2，｜Ｇ1｜2,...,｜ＧK｜2≧κ(K+1)NＬg
一方、これと（３）を使用して以下の推定を行うことができる。
|φ1▲×▼G1+φ2▲×▼G2+...+φK▲×▼GK+m▲×▼F|∞
≧c1(|φ1|2・|G1|2+...+|φK|2・|GK|2+|m|2・|F|2)
=c1Lφ(|G1|2+...+|GK|2+|F|2)
≧c1(K+1)LφLgκ(K+1)N
したがって、ラッピング係数Ｗを用いた場合、パラメータとして次式を満たすパラメータが選択されるかぎり、スプリアス鍵を得ることはできない。
Ｗq≦ｃ1（Ｋ＋１）ＬφＬgκ(K+1)N    (7)
（これを復号不等式（４）と比較することができる）
§３．３．４  個々のメッセージに対する大格子アタック
考慮しなければならない他の種類の格子アタックがある。アタッカは、あらゆるメッセージを復号する鍵を探索するのではなく、個々のメッセージを探索する格子を構築することができる。以下の格子について考える。この格子は第３．３．２節で使用した格子に類似している。以下の行列の列によって生成される格子をＭとする。
0004068664.tif 000038
この格子は次式を満たし、
ｄｉｍ（Ｍ）＝（Ｋ＋１）ＮおよびＤｉｓｃ（Ｍ）＝λKNｑN
以下のベクトルを含む（自明の表記を使用する）。
［λφ1，λφ2,...,λφK，ｅ−ｍ］
この格子がこのベクトルを含むのは、符号化メッセージｅが以下の規則に従って作成されたからである。
pφ1▲×▼h1+pφ2▲×▼h2+...+pφK▲×▼hK+m≡e(mod q)
ｅ−ｍ（ｍｏｄ  ｑ）の係数が小さくないので（８）が短いベクトルになる可能性が低いことは明らかである。しかし、アタッカはｅの値を知っており、したがって、既知の非格子ベクトル［０，０,...,０，ｅ］に近いベクトルをＭで探索することができる。探索中の格子ベクトルおよび既知の非格子ベクトルからの距離は、以下のベクトルの長さである。
ｖtarg＝［λφ1，λφ2,...,λφK，−ｍ］
これは、非斉次格子問題の例である。非斉次問題は斉次問題よりもいくらか難しくなる傾向があるが、重大な誤りを犯すのを回避するために、アタッカが非斉次問題を斉次問題を解くのとまったく同じ程度に解くことができると仮定する。したがって、アタッカが以下の長さのベクトルを見つけられるかどうかを調べる必要がある。
0004068664.tif 000039
（あらゆるｍ∈Ｌmおよびあらゆるφ∈Ｌφについて｜ｍ｜2＝ｐ｜φ｜2であることを想起されたい）仮説（Ｈ2）によれば、次式が成立する場合、
0004068664.tif 000040
あるいは言い換えれば、次式が成立する場合には、アタックは失敗する。
0004068664.tif 000041
アタッカは、λ＝ｐ（補題Ａ．１参照）を使用することによって左辺を最小化し、したがって、次式が成立する場合、アタックは失敗する。
0004068664.tif 000042
この数式は、これによって補われる（６）と比較することができる。
§３．３．５  格子アタック・パラメータ制約の要約
本節の前の部分では、様々な格子アタックについて説明し、これらのアタックが成功するのを妨げる、パラメータに対する制約を考案した。すべての制約を満たすパラメータの選択肢が存在するかどうかという問題が残っている。読者に好都合なように、本節のすべての不等式を、真の鍵ｆの所有者がメッセージを復号する場合に必要な基本不等式（４）と共にリストする。
0004068664.tif 000043
任意の固定値ｃ1、ｃ2、ｐ、Ｌφ＞０であり、ｐ、ｋ、Ｗ＞１である場合、これらの不等式には常に解Ｎ、ｋ、Ｌg、ｑが存在すると考えられる。次に、解を求める際に助けとなるいくつかの注意事項について述べる。
まず、これらの不等式を様々な方法で組み合わせる。まず、（４）と（７）を組み合わせると（ある代数計算の後で）次式が与えられる。
0004068664.tif 000044
（基本的に）ｃ1、ｃ2、κを自由に選択することはできず、Ｗが所望のセキュリティ・レベルに応じて５と１０の間で選択されることに留意されたい。これによって、通常はかなり小さなｐが選択される。この場合の重要な点は、（１０）が（Ｋ＋１）Ｎの下限を与え、これを超えるとほとんど制御できなくなることである。
次に、（４）と（５）を組み合わせると次式が得られる。
0004068664.tif 000045
ｑを選択する際にいくらか融通を利かせるには、Ｌgの値として、指定されたこの下限よりも（たとえば）１．５倍ないし２倍大きな値を選択するとよい。
たとえば、ＬφおよびＬgが第２．２節で説明したような値である場合、
0004068664.tif 000046
であり、大部分のｇ∈Ｌgは
0004068664.tif 000047
を満たす。したがって、（１１）を使用してＬgを選択した後、
0004068664.tif 000048
を選択することができ、この場合、大部分のｇ∈Ｌgは所望のＬgに非常に近いＬ2ノルムを有する。さらに、Ｌgから要素を選択するのは符号作成者のＤａｎだけであり、このような選択は１度行うだけでよいので、Ｄａｎが、ほぼＬgのノルムを有するＬgで必要なＫ＋１個の多項式を見つけるのは難しいことではない。長さの制約がある場合でも、実際にはｒNが少なくとも２500になる傾向があるので、Ｌg内のそのような多項式の数はアタッカがしらみつぶし的探索を介して検査できるよりもはるかに多い。
§４  実施にあたって考慮すべき点
§４．１  セキュリティ係数およびラッピング係数
アタッカが、格子整約によって生成されたスプリアス鍵を使用するときにどの程度のラッピングを期待できるかを、ラッピング係数Ｗが制御することを想起されたい。Ｗが小さすぎ、たとえばW=１．５である場合、アタッカは多数の（場合によっては最も多くの）係数を回復することができる。これは、これらの値が平均の周りに集中する傾向があるからである。厳密には、アタッカはＮ個の未知の係数に関して（たとえば）０．９５Ｎ個の一次方程式を再生し、この場合、暴力的探索によってアタックが終了する。
ＣｏｐｐｅｒｓｍｉｔｈおよびＳｈａｍｉｒ［３］は、Ｗがこれよりも大きなビットであり、たとえばＷ＝２．５である場合でも、アタッカはクラスタ化により、Ｎ個の未知の係数について約０．６７Ｎ個の一次方程式を得ることができると考えた。ＣｏｐｐｅｒｓｍｉｔｈおよびＳｈａｍｉｒは次いで、アタッカが２つの独立のスプリアス鍵を構築し適用した場合、システムの解を求めるのに十分な数の独立の等式を得ることができると考えている。ＣｏｐｐｅｒｓｍｉｔｈおよびＳｈａｍｉｒはさらに、Ｗ＝４である場合、いくつかの短いベクトルを使用し、ある種の誤り補正技法を使用することによって、アタックを成功させることができるが、Ｗが１０程度である場合には、この種のアタックは成功しないと述べている。詳細については［３］を参照されたい。
これらのことに基づいて、ラッピング係数Ｗ＝１０を使用してサンプル動作パラメータを構築する。
§４．２  サンプル動作パラメータ
この節では、第３節の仮説の下で安全であるＮＴＲＵ  ＰＫＣＳの２組の使用可能なパラメータを考案する。これらのパラメータ集合によってかなり高度なメッセージ拡張が行われ、したがって、メッセージ拡張を管理可能な２対１に低減するＮＴＲＵの２段階バージョンに関する以下の第４．３節を参照されたい。
まず、実験による証拠によって得られた３つの値と、スプリアス鍵アタックを妨げるのに十分なラッピングが確保されるように選択された第４の値から始める。
0004068664.tif 000049
ｃ1およびｃ2の値は所望の範囲の広範囲な数値試験によって決定されているが、これらの値を確率的に正当化するにはどうすべきかについてかなり良好な考え方がある。上記の第４．１節でラッピング係数Ｗ＝１０について論じた。最後に、第３．３節の注で格子整約定数κの選択について論じた。ただし、格子整約技法の将来の改良に備えるために、セキュリティを意識するユーザはこの代わりにκ＝１．３1/100を選択し、他のパラメータをわずかに変更することができる。
まず選択肢ｐ＝２について考える。第３．３．５節の不等式（１０）によって、次式を選択する必要があることがわかる。
（Ｋ＋１）Ｎ≧１００９．７９
したがって、以下の値を選択する。
Ｎ＝１６７およびＫ＝６
（Ｎと（Ｎ−１）２が共に素数であると好都合である。ただし、これは必要なことではない）。この選択によって、残りの係数を選択するための十分な許容差が与えられる。
Ｌφを第２．２節と同様に選択し、ｄ＝２０とし、したがって、
0004068664.tif 000050
となる。これはｍｅｅｔ−ｉｎ−ｔｈｅ−ｍｉｄｄｌｅアタックに対する十分なセキュリティを与える。さらに、
0004068664.tif 000051
とし、これらの選択肢を（１１）に代入すると、Ｌg＞４１４．０７が与えられる。いくらかの許容差を与えるためにγ＝１６７を選択する。これによって、Ｌgの期待値は６２２．９８に等しくなる。最後に、第３．３．５節の５つの基本不等式により、ｑが次式を満たさなければならないことがわかる。
213.6924<q≦max｛214.2766,214.7278,214.6238,252.481｝
（もちろん、第３．３．５節の不等式（６k）は実際には、各１≦ｋ≦６ごとに１つの６つの不等式である。）したがって、ｑ＝２14−１＝１６３８３を選択することができる。（ｇｃｄ（ｐ，ｑ）＝１が必要であることに留意されたい。）簡単に言えば、第３．３節の仮説を仮定した場合、以下のパラメータによって安全なＮＴＲＵＰＫＣＳが与えられる。
N=167,k=6,q=16383=214-1,p=2,r=167,d=20,s=3
この場合、第２．２節で説明したように、Ｌφ、Ｌg、Ｌmが選択される。これらのパラメータでは以下の値が得られる。
公開鍵長＝Ｎｋｌｏｇ2ｑ＝１４０２８ビット
専用鍵長＝Ｎｌｏｇ2ｐｒ＝１４００ビット
メッセージ拡張＝ｌｏｇｑ／ｌｏｇｐ＝１４対１
同様な分析を使用して、より大きな値のｐを有する第２の１組の安全なＮＴＲＵパラメータを構築する。すべての演算が２16よりも小さな数に対して行われ、ｑが２のべき乗であり、したがって、剰余を含むｑによる除算が簡単なシフト演算になるので、これらのパラメータは既存のマイクロプロセッサにうまく適合するように思われる。以下の値を選択する。
N=167,K=6,q=216,p=3,r=354,d=40,s=7
これらのパラメータは
0004068664.tif 000052
と、以下の値を与える。
公開鍵長＝ＮＫｌｏｇ2ｑ＝１６０３２ビット
専用鍵長＝Ｎｌｏｇ2ｐｒ＝１６７８ビット
メッセージ拡張＝ｌｏｇｑ／ｌｏｇｐ＝１０．１対１
§４．３  ２段階ＮＴＲＵおよび改良型メッセージ拡張
第４．２節に示したサンプル・パラメータのＮＴＲＵ  ＰＫＣＳはかなり大きなメッセージ拡張を有する。この拡張を減少する１つの方法は、より大きな値のｐを使用することであるが、この場合、（Ｋ＋１）Ｎの値が著しく大きくなり、そのため両方の鍵サイズが大きくなり計算効率が低下する。
メッセージ拡張を減少する他の方法は、実際のメッセージを符号化するための１種のワンタイム・パッドとして各ＮＴＲＵメッセージを使用することである。ＮＴＲＵのこの２段階バージョンでは、符号化側のＣａｔｈｙがランダム多項式ｍ∈Ｌmを選択し、これに対して、Ｃａｔｈｙの実際の平文メッセージＭとしては、ｑを法とする任意の多項式が許容される。Ｃａｔｈｙは、メッセージを符号化するために、以下の２つの等式を計算する。
0004068664.tif 000053
符号化メッセージは対（ｅ，Ｅ）である。
復号プロセスは前述のプロセスと類似しているが、１つの余分のステップを含む。したがって、復号側のＤａｎは、第１．４節で説明した手順に従って多項式ｍを計算する。Ｄａｎは次いで、次式を計算することによってメッセージを再生する。
Ｅ−ｍ▲×▼ｈ1（ｍｏｄ  ｑ）
平文メッセージＭの長さがＮｌｏｇ2ｑビットであり、それに対して符号化メッセージ（ｅ，Ｅ）の長さが２Ｎｌｏｇ2ｑビットであり、したがってメッセージ拡張は２対１に減少すると考えられる。
別の点について述べる。Ｃａｔｈｙは同じ多項式および法を使用してｍとＭの両方を符号化している。これによってセキュリティが損なわれることは考えられないが、セキュリティを強化した場合、Ｃａｔｈｙは異なる（公開）多項式Ｈおよび法ＱについてＥ≡ｍ▲×▼Ｈ＋Ｍ（ｍｏｄ  Ｑ）を計算することができる。
§４．４  理論上の動作仕様
この節では、ＮＴＲＵ  ＰＫＣＳの理論上の動作特性について考える。４つの整数パラメータ（Ｎ、Ｋ、ｐ、ｑ）と、第２．２節で説明したように、それぞれ、整数ｒ、ｄ、ｓによって決定される、３つの集合Ｌg、Ｌφ、Ｌmと、実験的に決定される定数ｃ1、ｃ2、κと、ラッピング定数Ｗがある。セキュリティを保証するには、これらのパラメータとして、第３．３．５節にリストした不等式を満たすパラメータを選択しなければならない。以下の表は、これらのパラメータで表したＮＴＲＵ  ＰＫＣＳ動作特性を要約したものである。
0004068664.tif 000054
第４．４節で説明した２段階ＮＴＲＵについては以下の項目が異なる。
0004068664.tif 000055
§４．５  実施上の他の考慮すべき点
ＮＴＲＵを実施する際に考慮すべき他のいくつかの因子について簡単に述べる。
（１）ｇｃｄ（ｑ，ｐ）＝１であることが重要である。基本的にＮＴＲＵはこの要件がなくても働くが、実際には、ｇｃｄ（ｑ，ｐ）＞１である場合、セキュリティが低下する。極端な範囲では、ｐ｜ｑである場合、（ｅｘｅｒｃｉｓｅ）符号化メッセージｅはｅ≡ｍ（ｍｏｄ  ｐ）を満たし、ＮＴＲＵのセキュリティは完全に失われる。
（２）大部分のｆがｐおよびｑを法とする逆数を有することが望ましい。というのは、そうでない場合、鍵の作成が困難になるからである。第１の要件はｇｃｄ（ｆ（１），ｐｑ）＝１であるが、これが、ある選択されたｆに対して無効であった場合、符号作成者はこの代わりにたとえば、ｆ（Ｘ）＋１またはｆ（Ｘ）−１を使用することができる。ｇｃｄ（ｆ（１），ｐｑ）＝１と仮定すると、Ｎとして素数を選択し、ｐおよびｑを除する各素数Ｐについて、（Ｚ／ＮＺ）*中のＰのオーダーを大きくし、たとえばＮ−１または（Ｎ−１）／２にした場合、ほぼすべてのｆ、が必要な逆数を有する。たとえば、これは、（Ｎ−１）／２自体が素である（すなわち、ＮがＳｏｐｈｉｅ  Ｇｅｒｍａｉｎ素数である）場合は確実に真である。このような素数の例には１０７および１６７が含まれる。
§５  ＮＴＲＵの適度なセキュリティ・パラメータ
現実には、高速および／または低メモリ要件が重要であり、適度なセキュリティ・レベルが受け入れられる多数の状況がある。この場合、実際の格子整約方法［１１、１２］はＣＰＵを酷使し、そればかりでなく、次元２００ないし３００の格子に対して格子整約を実行するのに長いコンピュータ時間を必要とする。もちろん、この場合の「長い」は相対的な語であるが、３００次元格子整約を実行して１セントの数分の１に相当するコストを削減しても恐らく無効であり、現行の方法を使用してこのような格子整約を短時間（たとえば２、３分間）で実行すると（完全に実現不能ではない場合）コストが非常に高くなることは確実である。したがって、大次元格子アタックを可能にする必要のある状況で使用できる１組のＮＴＲＵパラメータを作成すると有効である。
格子アタックによってもたらされるパラメータ制約をなくした場合、残るのは以下の復号制約と、
ｃ2ｐＬgＬφ（Ｋ＋１）＜ｑ    (4)
ｆ、ｇ、φの探索空間が暴力的（多分ｍｅｅｔ−ｉｎ−ｔｈｅ−ｍｉｄｄｌｅ）アタックを防止するほど大きいという条件だけである。話を簡単にするために、Ｋ＝１を選択する。ｆ、ｇ、φがすべて、集合Ｌφ、すなわち、ｄ個の係数が１に等しく、ｄ個の係数が−１に等しく、他のＮ−２ｄ個の係数が０に等しい多項式の集合に含まれるものとみなす。（厳密には、ｆはｐおよびｑを法として可逆である必要があるので、ｆを余分の１つの係数を有するものとみなすが、これは後に続く分析にほとんど影響を与えず、したがってこれを無視することにする。）ｃ2＝０．２４を通常どおりに使用すると、復号制約は単に次式のようになる。
ｑ＞２ｐｄ    (4)
他の制約を次式に示す。
0004068664.tif 000056
上式で、σは必要なセキュリティ・レベルである。適度なセキュリティの処理系の場合、セキュリティ・レベルは約２40でほぼ十分であり、したがって
0004068664.tif 000057
を選択する。
以下の表は、ＮＴＲＵの適度なセキュリティの処理系の受け入れられる動作パラメータを示す。セキュリティを評価する際、利用可能な格子アタックが次元２Ｎの格子を使用することに留意されたい。また、ｑのリストされた値は最小許容値であるが、ｇｃｄ（ｐ，ｑ）を満たす、これよりもいくらか大きなｑも受け入れられることに留意されたい。特に、ｑ＝６４を選択することによってとりわけ高速な処理系を使用することができる。
0004068664.tif 000058
最後に、鍵サイズが非常に小さくなると考えられる。
公開鍵：  Ｎｌｏｇ2（ｑ）ビット
専用鍵：  ２Ｎｌｏｇ2（ｐ）ビット
たとえば、（Ｎ，ｄ，ｐ，ｑ）＝（１６７，７，３，６４）は、それぞれ長さ１００２ビットおよび５３０ビットの公開鍵および専用鍵を含むシステムを形成する。
§６  他のＰＫＣＳとの比較
現在、因数分解の難点に基づくＲｉｖｅｓｔ、Ｓｈａｍｉｒ、Ａｄｅｌｍａｎ（ＲＳＡ［１０］）のシステム、誤り補正符号に基づくＭｃＥｌｉｅｃｅ［９］のシステム、ほぼｖ直交化された短い基を格子内で見つけることが困難であることに基づくＧｏｌｄｒｅｉｃｈ、ＧｏｌｄＷａｓｓｅｒ、Ｈａｌｅｖｉ（ＧＧＨ［５］）の最近のシステムを含め、いくつかの公開鍵暗号システムが文献に記載されている。
ＮＴＲＵシステムは、環Ｒ内の星印乗算を（特殊な種類の）行列の乗算として公式化することができ、次いで、システムでの符号化を行列乗算Ｅ＝ＡＸ＋Ｙ（Ａは公開鍵である）として書くことができるという点で、ＭｃＥｌｉｅｃｅのシステムと共通するいくつかの特徴を有する。２つのシステムの間の小さな違いは、ＮＴＲＵ符号化では、Ｙがメッセージであり、Ｘがランダム・ベクトルであるが、ＭｃＥｌｉｅｃｅシステムではこれらの割当てが逆になることである。しかし、実際の違いは、復号を可能にする基本トラップドアである。ＭｃＥｌｉｅｃｅシステムの場合、行列Ａが誤り補正（ゴッパ）符号に関連付けされ、ランダム寄与がゴッパ符号によって「補正される」ほど小さいために復号が作用する。ＮＴＲＵの場合、行列Ａは巡回行列であり、復号は、Ａの、特殊な形式を有する２つの行列の積へ分解と、ｍｏｄ  ｑからｍｏｄ  ｐへのリフティングに依存する。
我々の知るかぎりでは、ＮＴＲＵシステムにはＲＳＡシステムとの共通点がほとんどない。同様に、ＮＴＲＵシステムは格子整約アタックを防止するようにセットアップしなければならないが、その基本復号方法は、復号が短い格子基の知識に基づいて行われるＧＧＨシステムとはかなり異なるものである。なお、ＧＧＨは実際には、ＭｃＥｌｉｅｃｅシステムに類似している。これは、どちらの場合でも、小さなランダム寄与を認識してなくすことによって復号が実行されるからである。これに対して、ＮＴＲＵは、可分性（すなわち、合同）を考慮することによってずっと大きなランダム寄与をなくす。
以下の表は、ＲＳＡ暗号システム、ＭｃＥｌｉｅｃｅ暗号システム、ＧＧＨ暗号システム、ＮＴＲＵ暗号システムのいくつかの理論的動作特性を比較したものである。それぞれの場合において、数Ｎは固有セキュリティ／メッセージ長パラメータを表す。
0004068664.tif 000059
付録Ａ．基本補題
以下の結果は格子アタックを最適化するうえで有用である。
補題Ａ．１．α＋β＝１を有するすべてのＡ、Ｂ、α、βについて、
0004068664.tif 000060
が成立し、ｘ＝βＢ／αＡで下限が生じる。
証明ｆ（ｘ）＝Ａｘα＋Ｂｘ-βとする。この場合、ｆ’（ｘ）＝αＡｘα-1−βＢｘ-β-1＝ｘβ+1（αＡｘ−βＢ）である。したがって、絶対最小値はｘ＝βＢ／αＡで生じる。（ｘ→０+およびｘ→∞のときにｆ（ｘ）→∞であることに留意されたい。）
0004068664.tif 000061
0004068664.tif 000062
【図１】
0004068664.tif 000064
【図２】
0004068664.tif 000065
【図３】
0004068664.tif 000066
【図４】
0004068664.tif 000067
【図５】
0004068664.tif 000068
【図６】
0004068664.tif 000069
【図７】
0004068664.tif 000070
【図８】
0004068664.tif 000071