(57)【要約】      （修正有）【課題】ナップザック暗号の公開鍵である数列を完全な乱数列とした暗号化方法を実現する。【解決手段】I個（I≧3）の秘密鍵ei-1と、I個の秘密鍵Pi（ei-1とPiは互いに素）と、ベクトルの次元を表す数nと法Zとに対し、公開鍵メモリに、成分が0以上Pi未満でn次元のI個の公開鍵ベクトルaiと、成分が0以上Z未満でn次元のJ個（Jは2以上）の公開鍵ベクトルbjとを記憶する。乱数発生器と演算器とにより、成分が0以上Z未満でn次元のI個の乱数ベクトルriと、成分が0以上Z未満でn次元のJ個の乱数平文ベクトルvjとを生成する。検査器により、平文mに対し、m≡Σj=1…Jbj・vj(modZ)が成立するかどうかを検査し、成立しない場合は、乱数ベクトルriと乱数平文ベクトルvjを再生成させる。演算器により、Ci=ai・riから成るI個の暗号文Ciを生成する。【選択図】図１
2017016048.tif 000002
【特許請求の範囲】
【請求項１】
I個（I≧3）の秘密鍵ei-1と、I個の秘密鍵Pi（ei-1とPiは互いに素）と、ベクトルの次元を表す数nと法Zとに対し、
成分が0以上Pi未満でn次元のI個の公開鍵ベクトルai（i=1〜I）と、成分が0以上Z未満でn次元のJ個（Jは2以上）の公開鍵ベクトルbj（j=1〜J）とを記憶する公開鍵メモリと、
成分が0以上Z未満でn次元のI個の乱数ベクトルri（i=1〜I）と、成分が0以上Z未満でn次元のJ個の乱数平文ベクトルvj（j=1〜J）とを生成するための、乱数発生器と演算器と、
平文mに対し、  m≡Σj=1…J bj・vj (mod Z)  が成立するかどうかを検査し、（ここに bj・vjはベクトルbjとベクトルvjとの内積を表す）、成立しない場合は、乱数ベクトルriと乱数平文ベクトルvjを再生成させる検査器と、
Ci=ai・ri  （i=1〜I）  （ここに ai・riはベクトルaiとベクトルriとの内積を表す）、によりI個の暗号文Ciを生成する演算器とを備え、
si≡ei-1×ai mod Pi  で定まる、I個のn次元秘密鍵ベクトルsiに対し、s1〜sIのk番目の成分（s1k,s2k,…,sIk）により、b1〜bJのk番目の成分（b1k,b2k,…,bJk）を定め、かつ{（s1k,s2k,…,sIk）}から{（b1k,b2k,…,bJk）}への像が単射でない写像φが存在し、
v1〜vJのk番目の成分（v1k,v2k,…,vJk）により、r1〜rIのk番目の成分（r1k,r2k,…,rIk）を定め、かつ{（v1k,v2k,…,vJk）}から{（r1k,r2k,…,rIk）}への像が全射でも単射でもない写像ρが存在し、
Mi=ei-1 Ci mod Pi  に対して  Σi=1…I  Mi ≡Σi=1…I  si・ri ≡Σj=1…J  bj・vj (mod Z)  が成立するように、写像φ、ρが定められ、
Ci ≡ai・ri' （ri'はriとは異なるn次元のベクトルで、成分は0以上Z未満とは限らない）を満たすベクトルri'（i=1〜I）から、写像ρが全射でも単射でもないため、vj（j=1〜J）が推定困難にされ、かつ写像φが単射でないため、公開鍵ベクトルbj（j=1〜J）からsi mod Z（i=1〜I）が推定困難にされている、公開鍵暗号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、公開鍵暗号化装置に関する。
【背景技術】
【０００２】
従来のナップザック暗号は、超増加数列等の特殊な数列をモジュラー乗算して公開鍵である数列としていた。しかしながらこのような公開鍵には元の特殊な数列の影響が残り、完全な乱数列とは言えない。そこで発明者らは、秘密鍵に完全な乱数列を使用するナップザック公開鍵暗号を提案した（特許文献１  特開2013-152389）。またこの暗号では、0からZ未満、例えば1ビットの平文mを暗号化する。特許文献１での暗号システムの概要を以下に示す。
【０００３】
秘密鍵: ベクトルs; 素数P; 整数e
公開鍵: ベクトルa; b;法Z
鍵生成
Step 1: 公開鍵ベクトルaの次元n と法Z を決める。
Step 2: n次元の秘密鍵ベクトルsをランダムに生成する。
Step 3: 次式を満たす素数P をランダムに生成する。
P > sum(s) >P/2   （sum(s)はベクトルsの成分の和）        (1)
Step 4: 次式を満たす整数e をランダムに生成する。
e < P                                                           (2)  
Step 5: 次式により秘密鍵ベクトルs から公開鍵ベクトルa を得る。
a = e×s mod P                                                 (3)
Step 6: 法Z とn次元の公開鍵ベクトルbを公開する
b = s mod Z                                                     (4)
【０００４】
暗号化
Step 1: 0〜Z-1までの数から成る平文をmとする。
Step 2: 2 進乱数ベクトルr∈{0,1}n を
m = b・r mod Z                                                  (5)
を満たすようにランダムに生成する。
Step 3: 暗号文C を
C = a・r                                                         (6)
により計算する。
【０００５】
復号
中間平文M をM = s・r で定義する。
Step 1: 次式により中間平文M を計算する。
M = e-1C mod P                                                (7)
Step 2: 平文m を次式により計算する。
m=M mod Z                                                    (8)
M=s・r=e-1C mod P  が成立し、s≡b (mod Z) より、M≡b・r (mod Z) が成立する。したがって式(8) が成立する。
【０００６】
別解攻撃
式(6)での乱数ベクトルの成分は0か1である。0と1に制限されない成分から成り、式(6)を満たす解を別解と呼ぶことにする。長尾と森井は、式(6)の別解から平文mを求める手法（別解攻撃）を発表した。r′を  C = a・ｒ'を満たす別解とすると、r′は成分が整数のn次元ベクトルである。r'が暗号化に用いた2 進乱数ベクトルr∈{0,1}n と異なっていても、解読条件
M = s・r′                                                    (9)
を満たす場合には,平文m を
m = b・r′mod Z                                              (10)
として求めることができることを、長尾らは発見した（非特許文献１）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開2013-152389
【非特許文献】
【０００８】
【非特許文献１】長尾篤、森井昌克  ”ナップザック暗号における高密度化手法に関する考察”  CSS2013,CSS2013_1C2-4,pdf.Oct.2013
【発明の概要】
【発明が解決しようとする課題】
【０００９】
発明者は考察を重ねた結果、別解攻撃による解読要因は別解が求まることにあるのではなく、秘密鍵sの下位側ビットから成る公開鍵ベクトルbにあることを導いた。即ち、仮に別解が求められても、秘密鍵sの下位側ビットから成るベクトルを推定できなければ、別解ｒ'から平文mは求められないことを確認した。そこで発明者は、秘密鍵s等の系列を3系列以上にすることにより、秘密鍵sの下位側ビットを秘密にするように、特許文献１の暗号システムを拡張できることを発見した。
【００１０】
この発明の課題は、ナップザック暗号方式あるいは積和暗号方式で、かつ別解攻撃に対し安全な、公開鍵暗号化装置を提供することにある。
【課題を解決するための手段】
【００１１】
この発明の公開鍵暗号化装置は、I個（I≧3）の秘密鍵ei-1と、I個の秘密鍵Pi（ei-1とPiは互いに素）と、ベクトルの次元を表す数nと法Zとに対し、
成分が0以上Pi未満でn次元のI個の公開鍵ベクトルai（i=1〜I）と、成分が0以上Z未満でn次元のJ個（Jは2以上）の公開鍵ベクトルbj（j=1〜J）とを記憶する公開鍵メモリと、
成分が0以上Z未満でn次元のI個の乱数ベクトルri（i=1〜I）と、成分が0以上Z未満でn次元のJ個の乱数平文ベクトルvj（j=1〜J）とを生成するための、乱数発生器と演算器と、
平文mに対し、  m≡Σj=1…J bj・vj (mod Z)  が成立するかどうかを検査し、（ここに bj・vjはベクトルbjとベクトルvjとの内積を表す）、成立しない場合は、乱数ベクトルriと乱数平文ベクトルvjを再生成させる検査器と、
Ci=ai・ri  （i=1〜I）  （ここに ai・riはベクトルaiとベクトルriとの内積を表す）、によりI個の暗号文Ciを生成する演算器とを備えている。
【００１２】
この発明の公開鍵暗号化装置では、  si=ei-1×ai mod Pi  で定まる、I個のn次元秘密鍵ベクトルsiに対し、s1〜sIのk番目の成分（s1k,s2k,…,sIk）により、b1〜bJのk番目の成分（b1k,b2k,…,bJk）を定め、かつ{（s1k,s2k,…,sIk）}から{（b1k,b2k,…,bJk）}への像が単射でない写像φが存在し、
v1〜vJのk番目の成分（v1k,v2k,…,vJk）により、r1〜rIのk番目の成分（r1k,r2k,…,rIk）を定め、かつ{（v1k,v2k,…,vJk）}から{（r1k,r2k,…,rIk）}への像が全射でも単射でもない写像ρが存在し、
Mi=ei-1 Ci mod Pi  に対して  Σi=1…I  Mi ≡Σi=1…I  si・ri ≡Σj=1…J  bj・vj (mod Z)  が成立するように、写像φ、ρが定められ、
Ci = ai・ri' （ri'はriとは異なるn次元のベクトルで、成分は0以上Z未満とは限らない）を満たすベクトル ri’ がMi = si・ri’ を満たしていても、ri’ (i=1〜I) から、写像ρが全射でも単射でもないため、vj（j=1〜J）が推定困難にされ、かつ写像φが単射でないため、公開鍵ベクトルbj（j=1〜J）からsi mod Z（i=1〜I）が推定困難にされている。
【００１３】
なお写像φの定義域の{（s1k,s2k,…,sIk）}は（s1k,s2k,…,sIk）として可能な全てのものを含み、値域の{（b1k,b2k,…,bJk）}は（b1k,b2k,…,bJk）として可能な全てのものを含んでいる。同様に写像ρの定義域{（v1k,v2k,…,vJk）}は（v1k,v2k,…,vJk）として可能な全てのものを含み、値域の{（r1k,r2k,…,rIk）}は（r1k,r2k,…,rIk）として可能な全てのものを含んでいる。図1，図2に示すように、乱数平文ベクトルvjを乱数発生器により生成し、これから演算器により乱数ベクトルriを生成しても良い。あるいは図３〜図５に示すように、乱数ベクトルriを乱数発生器により生成し、これから演算器により乱数平文ベクトルvjを生成しても良い。検査器の検査で、m≡Σj=1…J bj・vj (mod Z)が成立しなかった場合riとvjを再生成しても、生成済みのriとvjの一部を変更しても良い。
【００１４】
Z=2、I=J=3の場合について、写像φの例を挙げる。この写像は、b1=b2=b3の各成分が0の解として、s1 mod 2、s2 mod 2、s3 mod 2の各成分が0と１とを有し、単射ではない。またb1の各成分が1、b2=b3の各成分が0には解を持たないので、全射でもない。n次元のベクトルb1,b2,b3の成分毎に、s1、s2、s3の成分の組み合わせが複数あるので、nが例えば512,1024などと大きい場合、ベクトルs1、s2、s3として考えられる組み合わせは極めて大きな数になり、r1,r2,r3の推定値から平文mを推定するのは実質的に不可能である。
【００１５】
b1 = (s2 + s3) mod 2
b2 = (s3 + s1) mod 2
b3 = (s1 + s2) mod 2
【００１６】
Z=2、I=J=3の場合について、写像ρの例は、写像φと同様の
r1 = (v2 + v3) mod 2
r2 = (v3 + v1) mod 2
r3 = (v1 + v2) mod 2
である。写像ρも全射でも単射でも無い。別解攻撃は、暗号化に用いたr1,r2,r3を解読するのではなく、その代用品となる別解ri'で、Ci = ai・ri’ を満たすものを発見することである。発見したri' が Mi = si・ri' を満たすとき、b1,b2,b3からs1,s2,s3の下位側ビットが推定できれば、上の式からMiを推定できる。しかしながら次元数nが大きいときに、φが単射でないため、b1,b2,b3からs1,s2,s3の下位側ビットを推定することは非現実的である。v1,v2,v3からr1,r2,r3への変換アルゴリズム（写像ρ）は公開されているものとし、ρは単射でないので、写像φの場合と同様に、r1,r2,r3からv1,v2,v3を推定することは難しい。また別解攻撃によって得られるr1',r2'.r3'は,v1,v2,v3からの像としては有り得ないベクトルであることがほとんどである。ρが全射でなく、次元数nが大きいためである。すると、r1',r2'.r3'から意味のあるベクトルv1,v2,v3を推定することは実質的に不可能である。
【００１７】
Z=2の場合、写像ρは、見かけ上riからvjへの写像として表すこともできる。I=J=3の場合の例を示す。  
v1=r2＆r3
v2=r3＆r1
v3=r1＆r2
r1+r2+r3≡0 (mod 2)
これらの関係を、v1〜v3からr1〜r3への写像ρとして考えると、この写像は単射でも全射でもない。そして前記と同様に、別解r1',r2',r3'からv1,v2,v3を推定することは困難である。
【００１８】
I=J=3に限らず、I,Jを共に4にすることもでき、5以上の数にすることもできる。また図5に示すように、I=4,J=2なども可能である。この発明では、別解攻撃に対して安全な公開鍵暗号が得られる。
【図面の簡単な説明】
【００１９】
【図１】実施例の、I系列の暗号通信装置のブロック図
【図２】XOR方式で３系列の暗号通信装置のブロック図
【図３】AND方式で３系列の暗号通信装置のブロック図
【図４】AND方式で４系列の暗号通信装置のブロック図
【図５】変形例の、AND方式で４系列の暗号通信装置のブロック図
【発明を実施するための形態】
【００２０】
以下に本発明を実施するための最適実施例を示す。この発明の範囲は、特許請求の範囲の記載に基づき、明細書の記載とこの分野での周知技術とを参酌し、当業者の理解に従って定められるべきである。
【実施例】
【００２１】
図１〜図５に、実施例の公開鍵暗号通信装置2,40,60,70,80を示す。主な記号は以下の通りである。また各図のkは第k成分を表す。
【００２２】
表１
記号          意      味                                                  
n          公開鍵ベクトルの次元
I          系列数で3以上
J          公開鍵ベクトルbjの数を表し、Jは2以上、例えば  J=I
Z          法  ２以上の整数で公開する。２τ等が望ましいがこれに限らない。
例えば  Z=2
{}        集合を表す記号で、例えば{si}はベクトルsiの集合（i=１〜I）を表す
・        内積記号  例えば  Ci=ai・ri  はベクトルai,riの内積が暗号文Ci
であることを表す
＆        各成分毎の1ビットアンド演算
si         I個の秘密鍵ベクトル  siはn次元ベクトルで、個々のベクトルは
s1,s2,s3,s4等のように表し、ベクトルの成分は
sik（ベクトルsiの第k成分）のように表す
Pi        I個の自然数でPiは例えば素数      Pi＞(Z-1)sum(si)を満たす
ように選択する。(Z-1)sum(si)＞Pi/2  を満たすことが好ましいが、
これに限らない。ここにsum（si）はi番目の秘密鍵ベクトルsi
の成分の総和を表す
ei        I個の秘密の整数  gcd（ei,Pi）=1
m        平文で0以上Z未満の整数  法Zが2の場合、0または1  
C1〜CI  暗号文
Mi       I個の中間平文（i=1〜I）   Mi=ei-1Ci mod Pi  
平文mは中間平文から復号式  m=(Σi=1…I Mi ) mod Z  により
復号される
ai         I個の公開鍵ベクトル  ai=ei×si mod Pi  で定められ、×は
数eiとベクトルsiとの積を表す  aiはn次元ベクトルで、
個々のベクトルはa1,a2,a3,a4等のように表し、
Piを法とする剰余演算は、siの成分毎に行う
低密度攻撃を避けるため、次元nと公開鍵ベクトルaiでの
最大の成分aimaxとに対し、密度diが次式を満たすように、
aimaxを選択することが好ましい。di=n/（log2 aimax）≧0.9408
bj         J個の公開鍵ベクトル（j=1〜J）で、成分は0以上Z未満  
個々のベクトルはb1,b2,b3,b4等のように表す  
bjは{si}から、siの成分の最下位ビット（Z=2の場合）が露呈しない
ように発生させる
Zが2よりも大きい場合、si mod Zが露呈しないように発生させる
vj         乱数平文  J個のn次元ベクトルで、成分は0以上Z未満  
個々のベクトルはv1,v2,v3,v4等のように表す  
平文mと乱数平文vjの間には、検査式  m≡Σj=1…J bj・vj (mod Z)
の関係がある  
ri         乱数ベクトル  I個のn次元ベクトルで、成分は0以上Z未満  
個々のベクトルはr1,r2,r3,r4等のように表す    
{vj}から{ri}を発生させるか、{ri}から{vj}を発生させる
また  Mi=si・ri’ mod Pi  を満たすベクトルri'の集合を
別解{ri'}と呼ぶと、別解から{vj}の推定は不能である  
なお別解の成分は0以上Z未満には限らない
G          {vj}と{ri}との間の不可逆な変換を表し、行列表記する場合は成分
をgij等で表し、  gcd(｜G｜,Z ) ≠1    である
【００２３】
図１に、実施例の公開鍵暗号通信装置2を示し、4は暗号化装置で、6は復号装置、8は通信インターフェースで、公開鍵暗号通信装置2は暗号化装置4と復号装置6の一方のみを備えていても良い。公開鍵メモリ10はI個の公開鍵ベクトルai、J個の公開鍵ベクトルbjを記憶し、bjの成分は0以上Z未満で、aiの成分は秘密の法Pi未満である。公開鍵メモリ１０はさらに公開の係数の集合{gij}を記憶する。係数gijの集合を行列表記でGと表す。また公開の法Zが2よりも大きい場合、Zも記憶する。Zは例えば２のべき乗である。ベクトルai、bj等の次元数nは例えば512,1024など、2のべき乗である。この明細書で、有限成分の数列とベクトルとは同じ意味である。
【００２４】
公開鍵ベクトルbjと秘密鍵ベクトルsiの集合{si}は、
bj=（Σi=1…I  gij×si）mod Z                                      (11)
の関係があり、bjからsiの下位側ビットが推定できないように、言い換えるとbjからsiの下位側ビットへの逆変換が不能なように定める。
【００２５】
乱数発生器12はJ個の乱数平文ベクトルvjを発生させ、成分は0以上Z未満で、次元数はnである。演算器14はJ個の乱数平文ベクトルvjをI個の乱数ベクトルriへ
ri=（Σj=1…J  gij×vj）mod Z                                      (12)
により変換し、これは逆変換不能な変換である。検査器16は、例えば1ビット、一般的には0〜Z-1の数から成る平文mに対し、乱数ベクトルvjが
m≡Σj=1…J（bj・vj）(mod Z)                                      (13)
を満たすか否かを検査する。式(13)を満たさない場合、例えば乱数ベクトルvjを再発生させる。乱数ベクトルvjは平文mと密接な関係があり、乱数平文ベクトルということがある。
【００２６】
演算器18は図１に示す式によりI個の暗号文Ciを発生させ、通信インターフェース8を介して送信する。
【００２７】
復号装置6は、秘密鍵メモリ30に、秘密の法Piと秘密鍵ei-1（i=1〜I）とを記憶し、法Zが2以外の場合、Zも記憶する。秘密鍵ベクトルsiと公開鍵ベクトルaiとは、
ai=ei×si  mod Pi                                                (14)
の関係が有り、
si=ei-1×ai mod Pi                                                (15)
でもある。暗号文C1〜CIを受信した復号装置６は、暗号文メモリ32にC1〜CIを記憶し、乗算器34により
ei-1 Cｉ                                                         (16)
を求める。剰余演算器36によりPiを法とする剰余を求めると、
ei-1 Cｉmod Pi = si・ri ＝Mi                                      (17)
により、中間平文Miが求まる。そして演算器（加算器）38により、中間平文の和から成る別の中間平文Mを求め、Zを法とする剰余を求めると、
m=Σi=1…I Mi mod Z                                              (18)
により、平文mを復号できる。
【００２８】
復号の正当性は以下のように示すことができる。
M=Σi=1…I  （si・ri）≡Σi=1…I  （si・（Σj=1…J  gij×ｖj））≡Σi=1…I  Σj=1…J（si・gij×ｖj）
≡Σj=1…J（vj・（Σi=1…I  gij×si））≡Σj=1…J（bj・ｖj）
≡m  (mod Z)                                                    (19)
【００２９】
別解攻撃への安全性
別解ri’ から平文mを推定するには、秘密鍵ベクトルsiの下位側ビットを推定できるか、乱数平文vjを推定できることが必要である。しかし公開鍵ベクトルbj から秘密鍵ベクトルsiの下位側ビットへの逆変換は式(11)により不能で、別解ri’から乱数平文vjへの変換は式(12)により不能である。従って、別解攻撃に対し安全な公開鍵ナップザック暗号通信が可能になる。
【００３０】
安全性は、{gij}から成る行列Gが不可逆な変換であるため、言い換えると
gcd(｜G｜, Z ) ≠1  が成立するのでZを法としてGの逆行列が存在しないためということもできる。Gが不可逆な変換で有り得るのは、系列数Iが3以上であるためでもある。乱数平文ベクトルの集合{vj}から乱数ベクトルの集合{ri}への写像が行列Gで与えられるとする。gcd(｜G｜, Z ) ≠1  とすると、乱数ベクトルriの中には、{vj}からの変換では発生し得ないもの、言い換えると{vj}からの像に含まれないものが生じる。{vj}からの像を乱数ベクトルの成分毎に考えると、次元数nが増すと共に、別解攻撃で求めた乱数ベクトルri'が{vj}からの像に含まれない確率が1に漸近する。そして別解攻撃で求めた乱数ベクトルri'が{vj}からの像に含まれない場合、別解攻撃が成立しないので、暗号の安全性が増す。
【００３１】
なお、例えば法Zが2の場合、I=2とすると、b1=（s1+s2） mod 2  とb1を定めると、  b2=(s1 mod 2) or (s2 mod 2) 位しか変換の可能性がない。ここで例えばs1の第1成分の最下位ビットが0、s2の第1成分の最下位ビットが1とすると、（0,1）または（1,0）まで、最下位ビットを推定できる。なおナップザック暗号には他に低密度攻撃が可能で、低密度攻撃を回避するように公開鍵ベクトルaiの密度diを定めることが好ましい。
【００３２】
図２は３系列で  Z=2, I=J=3  での実施例を示し、乱数平文ベクトルv1,v2,v3からXOR演算により乱数ベクトルr1,r2,r3を生成する。同様に、秘密鍵ベクトルs1,s2,s3の最下位ビットから、XOR演算により公開鍵ベクトルb1,b2,b3を生成する。系列数Iが３以上で、上記の演算は一方向性、即ち逆演算が困難になり、乱数ベクトルr1,r2,r3から乱数平文ベクトルv1,v2,v3を推定することも、公開鍵ベクトルb1,b2,b3から秘密鍵ベクトルs1,s2,s3の最下位ビットを推定することも困難になる。  
【００３３】
図２の公開鍵暗号通信装置40は、特に指摘する点以外は、図1の公開鍵暗号通信装置2と同様で、暗号化装置41と復号装置42とを備えている。乱数発生器45は成分が1ビットの乱数平文ベクトルv1,v2,v3を出力し、AND回路46により公開鍵ベクトルb1,b2,b3との内積を発生させる。またXOR回路４７により乱数平文ベクトルv1,v2,v3を乱数ベクトルr1,r2,r3に変換する。そしてXOR回路47とラッチ回路51とにより、
(b1・ v1 + b2・ v2 + b3・ v3) mod 2  を求め、検査器16により、
m = (b1・ v1 + b2・ v2 + b3・ v3) mod 2                          (20)
が成立するかを検査する。b1・ v1 + b2・ v2 + b3・ v3の最下位ビットと1ビットの平文mとが一致しない場合、例えば乱数平文ベクトルv1,v2,v3を再度生成する。なおmod 2の演算なのでXOR回路47とラッチ回路51とで、2を法とする加算を実現できる。
【００３４】
乗算器48と加算器50により、公開鍵ベクトルa1,a2,a3と乱数ベクトルr1,r2,r3との内積を求めて、暗号文C1,C2,C3とし、通信インターフェース8から他の暗号通信装置の復号器42へ送信する。
【００３５】
復号装置42では、暗号文メモリ32に暗号文C1,C2,C3を記憶し、暗号文C1に乗算器56により秘密鍵e1の法P1に関する逆数e1-1を乗算する。同様に暗号文C2に秘密鍵e2の法P2に関する逆数e2-1を乗算し、暗号文C3に秘密鍵e3の法P3に関する逆数e3-1を乗算する。剰余演算器57により法P1,P2,P3に対する剰余（中間平文M1.M2.M3）を求め、加算器58によりM1,M2,M3を加算して中間平文Mとし、その最下位ビットを平文mとして出力する。
【００３６】
図２の公開鍵暗号通信装置40は以下の暗号を用いる。    
秘密鍵: s1; s2; s3;   P1; P2; P3;   e1; e2; e3
公開鍵: a1; a2; a3;   b1; b2; b3
【００３７】
鍵生成
Step 1: 公開鍵ベクトルai,bjの次元n と正整数N を決める。
Step 2: n次元の秘密鍵ベクトルsi （i=1,2,3で、成分は0〜N-1）をランダムに生成する。
Step 3: 次式を満たす素数Pi をランダムに生成する。
Pi > sum(si)            （sum(si)は秘密鍵ベクトルsiの成分の総和）
sum(si) > Pi／２ を満たすことが好ましいが、これに限らない。
Step 4: 次式を満たす整数ei をランダムに生成する。  ei < Pi (i = 1; 2; 3)
ただしPiが素数でなくても、gcd（ei,Pi）=1  であればよい。
Step 5: 次式により公開鍵ベクトルai を計算する。
ai = ei×si mod Pi   (i = 1; 2; 3)
Step 6: 下記のbj∈{０,１}n   (j = 1; 2; 3) を公開する。
b1 = (s2 + s3) mod 2                                             (21)
b2 = (s3 + s1) mod 2                                             (22)
b3 = (s1 + s2) mod 2                                             (23)
【００３８】
暗号化
Step 1: １ビットの平文をm ∈{０,１} とする。
Step 2: 次式を満たす2 進乱数平文ベクトルv1; v2; v3∈{０,１}nを生成する。
m = (b1・ v1 + b2・ v2 + b3・ v3) mod 2                           (24)
Step 3: 次式により2 進乱数ベクトルr1; r2; r3 ∈{０,１}n を計算する。
r1 = (v2 + v3) mod 2                                              (25)
r2 = (v3 + v1) mod 2                                              (26)
r3 = (v1 + v2) mod 2                                              (27)
Step 4: 暗号文Ci を
Ci = ai・ri (i = 1; 2; 3)                                             (28)
により計算する。
【００３９】
復号
中間平文Mi 及びM を次式で定義する。
Mi = si・ri (i = 1; 2; 3)                                            (29)
M = M1 +M2 +M3                                                 (30)
Step 1: Pi > sum(si) かつ  ai = ei×si mod Pi  なので、中間平文Mi ,M を次式により計算することができる。
Mi = ei-1Ci mod Pi (i = 1; 2; 3)                                    (31)
M = M1 +M2 +M3                                                (32)
Step 2: 平文m を次式により計算する。
m = M mod 2                                                    (33)
【００４０】
復号の正当性は以下のように保証される。
M≡s1・(v2 + v3) + s2・(v3 + v1) + s3・(v1 + v2)
≡ (s2 + s3)・ v1 + (s3 + s1)・ v2 + (s1 + s2)・ v3
≡ m (mod 2)                                                    (34)
【００４１】
別解攻撃への安全性
仮に別解攻撃により、式(29)  Mi = si・ri '(i = 1; 2; 3)  を満たす別解ri'  が求まったとする。これから乱数平文ベクトルv1,v2,v3を推定できると、別解攻撃が成立する。式(25)〜(27)はv1,v2,v3からr1,r2,r3への写像の像空間は狭く、別解攻撃で求めたr1',r2',r3'には大部分原像となるv1,v2,v3が存在しない。これは、r1',r2',r3'からv1,v2,v3を推定できないことを意味している。そして次元数nが増すと、別解攻撃で求めたr1',r2',r3'からv1,v2,v3を推定できない確率は1に漸近する。
【００４２】
図３の公開鍵暗号通信装置60は、図２の公開鍵暗号通信装置40での暗号化装置41を暗号化装置61に置き換えたものである。図3では、乱数ベクトルr1,r2,r3からアンド回路46により、式(35)〜(37)に従って乱数平文ベクトルv1,v2,v3を発生させる。そして公開鍵bjと秘密鍵siとの関係は式(21)〜(23)で与えられて、図２の場合と変わらない。また検査式(24)も図２の場合と同じである。ただし、ベクトルr1,r2,r3は3個の第k成分（k=1〜n）の和が0または2となるように発生させる。
v1=r2＆r3                                                      (35)
v2=r3＆r1                                                      (36)
v3=r1＆r2                                                      (37)
r1+r2+r3≡0 (mod 2)                                             (38)
【００４３】
k番目の成分について、v2k+v3k=(r3k&r1k)+(r1k&r2k)が成立する。r1k=1のとき、右辺は式(38)よりr3k+r2k≡r1k (mod 2)が成立する。また、r1k=0 のとき、右辺は0となる。これらより、式(25)が成立する。同様に、式(26)と式(27)も成立することがわかる。このようにZ=2の場合には、乱数平文ベクトルr1,r2,r3からアンド回路46により乱数平文v1,v2,v3を求めることができることがわかる。すなわち、XOR方式はv1,v2,v3からr1,r2,r3を求めていたが、AND方式では逆にr1,r2,r3からv1,v2,v3を求める点が異なっているにすぎない。
【００４４】
式(24)からbj、vjを消去し、si、riで表すと、次式が成立する。
m≡s1・r1＆（r2+r3）+s2・r2＆（r3+r1）+s3・r3＆（r1+r2）(mod 2)      (39)
式(38)により式(39)を変形すると、
m≡s1・r1＆r1+s2・r2＆r2+s3・r3＆r3 ≡s1・r1+s2・r2+s3・r3 (mod 2)   (40)
となり、式(24)から求めたmと式(31)〜(33)から求めたmとが一致し、復号の正当性が保証される。
【００４５】
別解攻撃への安全性
仮に別解攻撃により、式(28)  Ci=ai・ri' を満たす別解ri'が求められ，別解ri'が式(29)  Mi = si・ri '(i = 1; 2; 3)  を満たしているとする。これから乱数平文ベクトルv1,v2,v3を推定できると、別解攻撃が成立する。式(25)〜(27)はv1,v2,v3からr1,r2,r3への写像の像空間は狭く、別解攻撃で求めたr1',r2',r3'には大部分原像となるv1,v2,v3が存在しない。これは、r1',r2',r3'からv1,v2,v3を推定できないことを意味している。そして次元数nが増すと、別解攻撃で求めたr1',r2',r3'からv1,v2,v3を推定できない確率は1に漸近する。
【００４６】
図4は４系列の公開鍵暗号通信装置70を示し、71は暗号化装置、72は復号装置である。復号装置72では、系列数を3から4に変更したことに伴い、乗算器56と剰余演算器57を追加する。暗号化装置71では、乱数ベクトルr1,r2,r3,r4からアンド回路46により、式(39)〜(42)に基づき、乱数平文ベクトルv1,v2,v3,v4を生成する。
v1=r1＆r2                                                      (41)
v2=r2＆r3                                                      (42)
v3=r3＆r4                                                      (43)
v4=r4＆r1                                                      (44)
ただしベクトルr1,r2,r3,r4のk成分（k=1〜n）は(0,0,0,0), (1,1,0,0), (0,1,1,0), (0,0,1,1), (1,0,0,1) のいずれかとする。これは復号の正当性を保証する条件である。
【００４７】
また秘密鍵s1〜s4から式(45)〜(48)に基づき公開鍵b1〜b4を生成する。
b1 = (s1 + s2) mod 2                                             (45)
b2 = (s2 + s3) mod 2                                             (46)
b3 = (s3 + s4) mod 2                                             (47)
b4 = (s4 + s1) mod 2                                             (48)
【００４８】
公開鍵ベクトルa1〜a4は、式(49)で与えられる。
ai = ei×si mod Pi (i = 1〜4)                                    (49)
1ビットの平文ｍに関する検査式は、式(50)で与えられる。
m = (b1・ v1 + b2・ v2 + b3・ v3＋b4・s4) mod 2                (50)
そして暗号文C1〜C4は、式(51)で与えられる。
Ci＝ai・ri                                                      (51)
【００４９】
3系列の場合と同様に、
Mi=si・ri=ei-1Ci mod Pi  （i=1〜4）                            (52)
M=M1+M2+M3+M4                                             (53)
とし、
m=M mod 2                                                    (54)
により復号する。
【００５０】
復号の正当性を示す。式(50)から、次式が成立する。
m≡(s1+s2)・(r1＆r2)+(s2+s3)・(r2＆r3)+(s3+s4)・(r3＆r4)+(s4+s1)・(r4＆r1)
≡s1・（r4＆r1＋r1＆r2）+s2・（r1＆r2＋r2＆r3）+s3・（r2＆r3＋r3＆r4）
+s4・（r3＆r4＋r4＆r1）(mod 2)                                 (55)
【００５１】
ここでベクトルr1,r2,r3,r4のk成分（k=1〜n）は(0,0,0,0),(1,1,0,0), (0,1,1,0), (0,0,1,1), (1,0,0,1) のいずれかとするので、式(55)から求めた平文mは、式(52)〜(54)から求めたｍと一致し、復号の正当性が保証される。  
【００５２】
別解攻撃への安全性
仮に別解攻撃により、式(51)  Ci=ai・ri'を満たす別解ri'が求められ，別解ri'が式(52)  Mi = si・ri '(i = 1; 2; 3; 4)  を満たしているとする。これから乱数平文ベクトルv1,v2,v3,v4を推定できると、別解攻撃が成立する。式(41)〜(44)はv1,v2,v3,v4からr1,r2,r3,r4への写像の像空間は狭く、別解攻撃で求めたr1',r2',r3',r4'には大部分原像となるv1,v2,v3,v4が存在しない。これは、r1',r2',r3',r4'からv1,v2,v3,v4を推定できないことを意味している。そして次元数nが増すと、別解攻撃で求めたr1',r2',r3',r4'からv1,v2,v3,v4を推定できない確率は1に漸近する。
【００５３】
図５の公開鍵暗号通信装置80の暗号化装置81では、２系統の公開鍵ベクトルbHとbVとを用い、Iは4であるが、Jは２である。図４の暗号化装置71に比べ、秘密鍵s1〜s4に
s1+s2+s3+s4≡0 (mod 2)                                          (56)
との制約がある。また式(45)〜(48)より、公開鍵ベクトルb1〜b4に関し、
b1=b3=bH                                                       (57)
b2=b4=bV                                                       (58)
が成立するため、公開鍵ベクトルの数を２つに減らすことができる。そして4個の乱数ベクトルr00〜r10からアンド演算により中間的な乱数ベクトルr0*〜r*0を生成し、XOR演算により2個の乱数平文ベクトルrH,rVとし、検査式(59)を満たす乱数ベクトルr00〜r10を取り出す。
m≡bH・rH＋bV・rV (mod 2)                                     (59)
検査式(59)を満たす乱数ベクトルr00〜r10と公開鍵ベクトルa00〜a10との内積により、暗号文C00〜C10を生成して送信する。ここでベクトルr00,r01,r11,r10のk成分（k=1〜n）は(0,0,0,0),(1,1,0,0), (0,1,1,0), (0,0,1,1), (1,0,0,1), (1,1,1,1)のいずれかとする．式(56)の条件が付加されたので、図４の方式で用いることができる成分にさらに(1,1,1,1)を使うことができる。
【００５４】
r1=r00, r2=r01, r3=r11, r4=r10, v1=r0*, v2=r*1, v3=r1*,v4=r*0と置けば、復号方法は図4の場合と同じで、復号の正当性は以下のように保証される。
復号の正当性を示す。式(55)から、次式が成立する。
m≡(s1+s2)・(r00＆r01)+(s2+s3)・(r01＆r11)+(s3+s4)・(r11＆r10)+(s4+s1)・(r10＆r00)
≡(s1+s2)・r0*+(s2+s3)・r*1+(s3+s4)・r1*+(s4+s1)・r*0
≡b1(s1+s2)・r0*+ b2・r*1+ b3・r1*+ b4・r*0
≡bH・(r0*+r1*) + bV・(r*1+r*0)
≡bH・rH + bV・rV (mod 2)
【００５５】
式(56)の条件により、b1=b3, b2=b4と置けば、図４の方式の特殊な場合であることがわかる。仮に別解攻撃により、式(51)  C00=a00・r00', C01=a01・r01', C11=a11・r11', C10=a10・r10'を満たす別解r00',r01',r11',r10'が求められたとしても，これらの別解から乱数平文ベクトルr0*,r*1,r1*,r*0を推定できると、rH,rVを求めることができ、式(59)により、別解攻撃が成立する。r0*,r*1,r1*,r*0は図４の方式におけるv1,v2,v3,v4にそれぞれ対応しているため、図４の方式と全く同様の理由により、これらからr00,r01,r11,r10への写像の像空間は狭く、別解攻撃で求めたr00',r01',r11',r10'には大部分原像となるr0*,r*1,r1*,r*0が存在しない。これは、r00',r01',r11',r10'からr0*,r*1,r1*,r*0を推定できないことを意味している。そして次元数nが増すと、別解攻撃で求めたr00',r01',r11',r10'からv0*,v*1,v1*,v*0を推定できない確率は1に漸近する。
【００５６】
図４では、アンド演算を用い、乱数ベクトルを乱数平文ベクトルへ変換した。しかし
r1 = (v4 + v1) mod 2                                            (60)
r2 = (v1 + v2) mod 2                                            (61)
r3 = (v2 + v3) mod 2                                            (62)
r4 = (v3 + v4) mod 2                                            (63)
等により、v1〜v4からr1〜r4を生成しても良い。なお式(41),(44)により、k番目の成分について、  v4k+v1k=(r4k&r1k)+(r1k&r2k)=r1k  が成立するので、式(60)が成立する。同様に式(61)〜(63)も成立する。      
【００５７】
t系列のXOR方式
Z=2で、I=J=t（t≧3）とした場合をt系列と呼ぶ。t系列について、XOR方式とAND方式を改めて定義することにより、相互の関係を明らかにする。
【００５８】
鍵生成
Step 1: 公開鍵ベクトルai,bjの次元n と正整数N を決める。
Step 2: n次元の秘密鍵ベクトルsi （i=1,2,...,tで、成分は0〜N-1）をランダムに生成する。
Step 3: 次式を満たす素数Pi をランダムに生成する。
Pi > sum(si)          (sum(si)は秘密鍵ベクトルsiの成分の総和）
sum(si) > Pi／２ を満たすことが好ましいが、これに限らない。
Step 4: 次式を満たす整数ei をランダムに生成する。  ei < Pi (i = 1; 2; ... ; t)
ただしPiが素数でなくても、gcd（ei,Pi）=1  であればよい。
Step 5: 次式により公開鍵ベクトルai を計算する。
ai = ei×si mod Pi   (i = 1; 2; ... ; t)
Step 6: 下記のbi∈{０,１}n   (i = 1; 2; ... ; t) を公開する。
bi = (s[i+1] + s[i+2]) mod 2                                        (64)
ここで[x]=((x-1)mod t)+1である。
【００５９】
暗号化
Step 1: １ビットの平文をm ∈{０,１} とする。
Step 2: 次式を満たす2 進乱数平文ベクトルv1; v2; ...; vt∈{０,１}nを生成する。
m = (b1・ v1 + b2・ v2 + … + bt・ vt) mod 2                       (65)
Step 3: 次式により2 進乱数ベクトルr1; r2; ...; rt ∈{０,１}n を計算する。
ri = (v[i-1] + v[i-2]) mod 2                                        (66)
Step 4: 暗号文Ci を
Ci = ai・ri (i = 1; 2; ... ; t)                                        (67)
により計算する。
【００６０】
復号
中間平文Mi 及びM を次式で定義する。
Mi = si・ri (i = 1; 2; ... ; t)                                       (68)
M = M1 +M2 + … + Mt                                         (69)
Step 1: Pi > sum(si) かつ  ai = ei×si mod Pi  なので、中間平文Mi ,M を次式により計算することができる。
Mi = ei-1Ci mod Pi (i = 1; 2; ... ; t)                               (70)
M = M1 +M2 + … +Mt                                          (71)
Step 2: 平文m を次式により計算する。
m = M mod 2                                                   (72)
【００６１】
復号の正当性は以下のように保証される。
M≡s1・(vt + vt-1) + s2・(v1 + vt) + … + st・(vt-1 + vt-2)
≡ (s2 + s3)・ v1 + (s3 + s4)・ v2 + … + (s1 + s2)・ vt
≡ m (mod 2)                                                 (73)
【００６２】
t系列のAND方式
t系列のAND方式を説明する。なお鍵生成はt系列のXOR方式と全く同様である。
【００６３】
暗号化
Step 1: １ビットの平文をm ∈{０,１} とする。
Step 2: 式(74)及び式(75)を満たす2 進乱数ベクトルr1; r2; ...; rt ∈{０,１}n を生成する。
rik=0またはr[i-1]k+r[i+1]k=1                                      (74)
m = (b1・ v1 + b2・ v2 + … + bt・ vt) mod 2                      (75)
ここで、vi = r[i+1] & r[i+2] である。
Step 3: 暗号文Ci を
Ci = ai・ri (i = 1; 2; ... ; t)                                        (76)
により計算する。
【００６４】
復号
t系列のXOR方式と全く同様に復号を行う。式(74)を満たすとき、復号の正当性は以下のように保証される。
M≡(s1+s2)・(r1&r2) + (s2+s3)・(r2&r3) + … + (st+s1)・(rt&r1)
≡ s1・(rt&r1 + r1&r2) + s2・(r1&r2 + r2&r3) + … + st・(rt-1 & rt + rt & r1)
≡ s1・r1 + s2・r2 + … + st・rt
≡ m (mod 2)                                                   (77)
【００６５】
式(74)より、rik=0のとき、その両隣りのr[i-1]kとr[i+1]k は0と1のいずれでもよいが、  rik=1のとき、その両隣りのr[i-1]kとr[i+1]k は，いずれか一方が0で他方が1になる必要があることがわかる。要するに、２進乱数ベクトルr[i-1]，ri，r[i+1]のk成分では、"1"は必ず2bit連続する必要があるが、決して3bit連続してはいけないことがわかる。ベクトルriのk成分(k=1〜n)のハミング重みは必ず偶数である必要がある。
【００６６】
例えば、t=4のときを考え、ここでベクトルriのk成分（k=1〜n）は (0,0,0,0), (0,0,1,1), (0,1,1,0),  (1,1,0,0), (1,0,0,1)のいずれかとする。t=5のときは、(0,0,0,0,0)と、(0,0,0,1,1)を巡回シフトした元、すなわち、(0,0,0,0,0), (0,0,0,1,1), (0,0,1,1,0), (0,1,1,0,0), (1,1,0,0,0), (1,0,0,0,1)のいずれかとする。t=6のときは、(0,0,0,0,0,0)と、(0,0,0,0,1,1)及び(0,1,1,0,1,1)を巡回シフトした元、すなわち、(0,0,0,0,0,0), (0,0,0,0,1,1), (0,0,0,1,1,0), (0,0,1,1,0,0), (0,1,1,0,0,0), (1,1,0,0,0,0), (1,0,0,0,0,1), (0,1,1,0,1,1), (1,1,0,1,1,0), (1,0,1,1,0,1)のいずれかとする。
【００６７】
t系列のXOR方式とAND方式の関係
AND方式において、ベクトルriのk成分について次式が成立する。
v[i-1]k = rik & r[i+1]k
v[i-2]k = r[i-1]k & rik
これらを、式(66)の右辺に代入すると、
v[i-1]k + v[i-2]k ≡ (rik & r[i+1]k) + (r[i-1]k & rik)  (mod 2)            (78)
が成立する。rik = 0のとき、
v[i-1]k + v[i-2]k ≡ 0 ≡ rik  (mod 2)                                 (79)
が成立し、r[i-1]k + r[i+1]k = 1のとき、
v[i-1]k + v[i-2]k ≡ r[i+1]k + r[i-1]k k ≡ 1 ≡ rik  (mod 2)              (80)
が成立する。式(74)が成立することから常に式(66)が成立することがわかる。これより、AND方式はXOR方式において特殊な場合であることがわかる。このことから、AND方式は式(74)を満たすriを生成し、これらからviを求める方式であるのに対し、XOR方式は自由に独立な乱数viを生成し，これらからriを求める方式であることがわかる。
【００６８】
図５の方式とAND方式の関係
図５の方式における二桁の添え字00, 01, 11, 10をそれぞれ，t=4の場合のt系列AND方式における一桁の添え字1,2,3,4に対応させれば、図５の方式はAND方式の特殊な場合であることがわかる。両者の変数の対応を示す。
s1=s00, s2=s01, s3=s11, s4=s10,
P1=P00, P2=P01, P3=P11, P4=P10,
e1=e00, e2=e01, e3=e11, e4=e10,
a1=a00, a2=a01, a3=a11, a4=a10,
r1=r00, r2=r01, r3=r11, r4=r10,
v1=r*1, v2=r1*, v3=r*0, v4=r0*
【００６９】
図５の方式はさらに
s00+s01+s10+s11≡s1+s2+s3+s4≡0 (mod 2)                           (81)
を満たすので、b1=b3及びb2=b4が成立する．よってb1=b3=bV、b2=b4=bHの2系列でよい。またriのk成分（k=1〜n）は、t=4のAND方式では (0,0,0,0), (0,0,1,1), (0,1,1,0),  (1,1,0,0), (1,0,0,1)のいずれかとするが、図５の方式では、式(81)を満たすので、これらに加えて(1,1,1,1)も使用することができる。このようにAND方式は単にXOR方式の特殊な場合であり、図５の方式はさらに4系列AND方式の特殊な場合である。
【符号の説明】
【００７０】
2,40,60,70,80     公開鍵暗号通信装置
4,41,61,71,81     暗号化装置
6,42,72          復号装置
８              通信インターフェース
10              公開鍵メモリ
12              演算器
14              演算器
16              検査器
18              演算器
32              暗号文メモリ
34              乗算器
36              剰余演算器
38              演算器
45              乱数発生器
46              AND回路
47              XOR回路
48              乗算器
50              加算器
51              ラッチ回路
56              乗算器
57              剰余演算器
58              加算器
【図１】
2017016048.tif 000003
【図２】
2017016048.tif 000004
【図３】
2017016048.tif 000005
【図４】
2017016048.tif 000006
【図５】
2017016048.tif 000007