JP2000115157A - 紛失通信方法 - Google Patents

Abstract

(57)【要約】 【課題】 計算量及び通信量を削減する。 【解決手段】 送信装置１００で送信したい情報の組ｍ
_i （ｉ＝０，…，ｋ−１）を暗号化して（１１０）、暗
号文ｃ_i を乱数ｕで撹乱して（１３０）予備情報ｖ_i と
して受信装置２００へ送る。装置２００は受信したｖ_i
から受信したいｊ個のｖ_ij（ｊ＝０，…，ｆ−１）（１
＜ｆ＜ｋ）を選択し（２１０）、これらを、生成した乱
数ｒ_j で撹乱して（２３０）質問情報ｘ_j として装置１
００へ送る。装置１００ではｘ_j からｕを除し（１４
０）、その出力ｗ_j を復号して（１５０）の回答情報ｙ
_j として装置２００へ送る。装置２００ではｙ_j からｒ
_j を除去してｍ_ijを得る（２４０）。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、同時契約，配達
証明等で必要となる段階的秘密交換法に必要な１−ｏｕ
ｔ−ｏｆ−２紛失通信方法に関して、安全性を保証しつ
つ、同時に通信量を削減できる、効率のよい通信方法を
提案するものである。

【０００２】

【従来の技術】１−ｏｕｔ−ｏｆ−２紛失通信方法の代
表的な例として、ＥＧＬ法（Even,S.etal. “A Randomi
zed Protocol for Signing Contracts ”，Communicati
ons of the ACM,Vol.28,No.6,pp.637-647,(1985))を利
用したものがある。１−ｏｕｔ−ｏｆ−２紛失通信と
は、送信者が二つの情報ｍ₀ ，ｍ₁ を受信者に送信する
際に、受信者にはｍ₀ ，ｍ₁ の一方しか受信されず、も
う一方は通信路にて紛失してしまうものであり、送信情
報の同時受信不能性と送達確認不能性を備えるものであ
る。ここで、同時受信不能性とは、受信者が、送信され
た情報ｍ₀ ，ｍ₁ の両方を受信できないことであり、送
達確認不能性とは、送信者が、送信する情報ｍ₀ ，ｍ₁
のどちらが受信者に送信されたかを確認することができ
ないことである。

【０００３】ＥＧＬ法は、以下の通りである。まず前提
として、送信者は、公開鍵暗号方式を利用し、自分の公
開鍵暗号の鍵をＰ、対応する秘密鍵をＳとしているもの
とする。このとき、暗号化関数、復号化関数をそれぞれ
Ｅ_P ，Ｄ_S とすると、Ｄ_S （Ｅ_P （ｍ））＝ｍとなる。
ここでは、簡単のため、Ｅ_P ：Ｚ_N →Ｚ_M （Ｚ_N ，Ｚ_M
は整数環）とする。つまりＥ_Pは集合Ｚ_N の要素を集合
Ｚ_M の要素に変換する。

【０００４】Ｓｔｅｐ１ 送信装置は、乱数ｒ₀ とｒ₁
（ｒ₀ ，ｒ₁ ∈Ｚ_M ）を選び、これを受信装置に送る。
Ｓｔｅｐ２ 受信装置は、ランダムにｂ∈｛０，１｝を
選び、さらに乱数ｘ∈Ｚ_N を生成する。受信装置は、 ｑ＝Ｅ_P （ｘ）＋ｒ_b mod Ｍ を送信装置に送る。ここで、ａmod ｂは、ａをｂで割っ
たときの余りを表す。

【０００５】Ｓｔｅｐ３送信装置は、 ｙ₀ ＝Ｄ_S （ｑ−ｒ₀ mod Ｍ） ｙ₁ ＝Ｄ_S （ｑ−ｒ₁ mod Ｍ） を計算する。送信装置は、 ｃ₀ ＝ｍ₀ ＋ｙ₀ mod Ｎ ｃ₁ ＝ｍ₁ ＋ｙ₁ mod Ｎ を計算し、ｃ₀ とｃ₁ を受信装置に送る。

【０００６】Ｓｔｅｐ４ 受信装置は、 ｍ_b ＝ｃ_b −ｘmod Ｎ を得る。つまりランダムに選んだｂ＝０又はｂ＝１と対
応してｍ₀ ＝ｃ₀ −ｘmod Ｎ又はｍ₁ ＝ｃ₁ −ｘmod Ｎ
の何れかを得る。この方法が同時受信不能性を満たすこ
とは、以下のように示される。

【０００７】まず、明らかに、受信装置は所望の情報ｍ
_b を得ることができる。一方、選択された以外の情報ｍ
_d （ｄはｂ＝０の場合は１、ｂ＝１の場合は０、つまり
ｂと１との排他的論理和）を求めることは Ｄ_S （ｑ−ｒ_d mod Ｍ）＝Ｄ_S （Ｅ_P （ｘ）＋ｒ_b −ｒ
_d mod Ｍ） を求めることと等価である。したがって、Ｅ_P （ｘ）が
ランダムな値をとると仮定すると、この公開鍵暗号が安
全であればｍ_d を求めることは困難となる。

【０００８】次に、送達確認不能性は、送信装置にとっ
ては乱数ｘを予測できないために、受信装置が選択した
値（ｂ）を送られてきたｑから推定することは難しく、
よって、どちらのｍ_i を受信したかを判定するのは困難
であることから導かれる。このＥＧＬ法を１−ｏｕｔ−
ｏｆ−ｋ紛失通信（ｋ＞２）に拡張することは容易に行
なえる。すなわち、Ｓｔｅｐ１で送る乱数の数をｋ個に
拡張（ｒ_i （ｉ＝０，…，ｋ−１））し、Ｓｔｅｐ３で
そのすべての乱数についてｙ_i （ｉ＝０，…，ｋ−１）
を求め、 ｙ_i ＝Ｄ_S （ｑ−ｒ_i mod Ｍ）（ｉ＝０，…，ｋ−１） このｙ_i から同様にｃ_i （ｉ＝０，…，ｋ−１）を ｃ_i ＝ｍ_i ＋ｙ_i mod Ｎ（ｉ＝０，…，ｋ−１） と計算して送信すれば、受信装置は、ｋ個の情報ｍ
_i （ｉ＝０，…，ｋ−１）の中から所望の情報ｍ_j （０
＜ｊ＜ｋ）を得ることができる。

【０００９】また、さらにｆ−ｏｕｔ−ｏｆ−ｋ紛失通
信（ｋ＞２，１＜ｆ＜ｋ）に拡張するには、先と同様に
Ｓｔｅｐ１で送る乱数の数をｋ個に拡張し、Ｓｔｅｐ２
では、ｆ個の乱数ｘ_j （ｊ＝０，…，ｆ−１）より、ｑ
_j （ｊ＝０，…，ｆ−１）を ｑ_j ＝Ｅ_P （ｘ_j ）＋ｒ_j mod Ｍ と計算して、送信装置に送り、Ｓｔｅｐ３にて、ｑ
_j （ｊ＝０，…，ｆ−１）と送信装置が生成した乱数ｒ
_i （ｉ＝０，…，ｋ−１）からｙ_ij（ｉ＝０，…，ｋ−
１，ｊ＝０，…，ｆ−１）を ｙ_ij＝Ｄ_S （ｑ_j −ｒ_i mod Ｍ）（ｉ＝０，…，ｋ−
１，ｊ＝０，…，ｆ−１） として、さらに、ｃ_ij（ｉ＝０，…，ｋ−１，ｊ＝０，
…，ｆ−１）を ｃ_ij＝ｍ_i ＋ｙ_ij modＮ（ｉ＝０，…，ｋ−１，ｊ＝
０，…，ｆ−１） と求めて送信すれば、受信装置は、ｋ個の情報ｍ_i （ｉ
＝０，…，ｋ−１）の中から所望の情報ｍ_ij（ｊ＝０，
…，ｆ−１）を得ることができる。

【００１０】ここで用いられたような公開鍵暗号方式の
代表的な例として、ＲＳＡ暗号法（Rivest,R.L. etal.
“A Method for Obtaining Digital Signatures and Pu
blic-Key Cryptosystems”，Communications of the AC
M,Vol.21,No.2,pp.120-126,(1978) ）があげられる。Ｒ
ＳＡ暗号法は、以下の通りである。利用者は、復号用鍵
Ｐ（ｄ，Ｎの組）と暗号用鍵Ｓ（ｅ，Ｎの組）を Ｎ＝ｐ×ｑ ｅ×ｄ≡１（mod Ｌ） ただし、Ｌ＝ＬＣＭ｛（ｐ−１），（ｑ−１）｝ をみたすように生成し、暗号用鍵Ｐを公開し、暗号用鍵
Ｓを秘密に管理する。ここで、ｐとｑは相異なる２つの
大きな素数とし、ＬＣＭ｛ａ，ｂ｝は整数ａとｂの最小
公倍数を示している。また、ａ≡ｂ（mod Ｌ）は、ａ−
ｂがＬの倍数であることを表す。

【００１１】暗号化関数Ｅ_P と復号化関数Ｄ_S を Ｅ_P （ｍ）＝ｍ^e mod Ｎ Ｄ_S （ｃ）＝ｃ^d mod Ｎ で定義すると、ｍ∈Ｚ_N となる整数ｍに対して Ｄ_S （Ｅ_P （ｍ））＝ｍ となる。

【００１２】このように、ＲＳＡ暗号法を利用した場
合、Ｅ_P ：Ｚ_N →Ｚ_N となるため、Ｍ＝Ｎとして、紛失
通信方法を実現することとなる。

【００１３】

【発明が解決しようとする課題】前述のＥＧＬ法では、
送信装置が（Ｓｔｅｐ３において）受信装置から送られ
てきたｑと送信装置自らが生成した乱数ｒ_i を組合せ
て、ｃ_i を計算しなくてはならず、しかも、その計算は
受信装置が選択した情報ｍ_j には依存していなかった。
そのため、１−ｏｕｔ−ｏｆ−２紛失通信をｆ−ｏｕｔ
−ｏｆ−ｋ紛失通信に拡張した際には、送信装置は、送
信される情報の個数がｆであるにもかかわらず、すべて
の情報の個数ｋに依存した形で（ｋ×ｆ個の）送信デー
タを作成しなくてはならなかった。

【００１４】紛失通信が応用される同時契約，配達証明
などでは、実際に送られる通信量や送受信装置の計算量
を削減したいという要求があり、そのためＥＧＬ法では
非常に非効率である。この発明の目的は、送受信装置の
計算量と通信量を削減した効率のよい紛失通信方法を実
現することにある。

【００１５】

【課題を解決するための手段】そこで、送信装置が送信
すべきデータ量を削減することから、このデータが受信
装置が選択した情報のみに依存するように方式を設計す
ればよい。ＲＳＡ暗号法の鍵を先と同様に、暗号化鍵
（ｅ，Ｎ），復号化鍵（ｄ，Ｎ）とし、暗号化関数Ｅ_P
と復号化関数Ｄ_S を Ｅ_P （ｍ）＝ｍ^e mod Ｎ Ｄ_S （ｃ）＝ｃ^d mod Ｎ とする。今、平文ｍを暗号化した暗号文をｃとした時
に、このｃに対して乱数ｒ（ｒ∈Ｚ_N ）を用いて、 ｘ＝ｃｒ^e mod Ｎ と撹乱したとする。このとき、このｘはｘ≡（ｍｒ）^e
（mod Ｎ）なる関係を満たすため、ｘ＝Ｅ_P （ｍｒ）と
して考えることができる。よって、このｘを復号したも
のをｙ（＝Ｄ_S （ｘ））とすると、 ｙ≡ｘｒ（mod Ｎ) となり、このｙより乱数成分ｒを除去する（この場合は
ｒで法Ｎ上の除算を行なう）ことにより、ｍを求めるこ
とができる。乱数ｒをランダムに選んだ場合に、情報ｘ
からｃを推定することは不可能である。

【００１６】また、平文ｍを暗号化した暗号文をｃとし
た時に、このｃに対して乱数ｕ（ｕ∈Ｚ_N ）を用いて、 ｖ＝ｃｕ modＮ と撹乱したとする。このとき、このｖをさらにｘ＝ｖ
（ｒ）^e （mod Ｎ）のように撹乱したとしても、 ｗ＝ｘｕ^-1 modＮ としてｗを求めてみると、明らかにｗ＝Ｅ_P （ｍｒ）と
いう関係を満たしている。

【００１７】このような性質は、例えば、暗号化関数が
準同型性を満たし、かつ、暗号文空間が可換群であるよ
うな暗号方式に備わっているものである（すなわち、Ｒ
ＳＡ暗号法もこれらの性質を満たす暗号方式である）。
まず、いくつかの集合を定義する。Йを可算無限集合と
する。Ｎ∈Йに対して、｜Ｎ｜をＮの適切な表現の長さ
とし、また、Ｎ∈Йに対して、Ｘ_N ，Ｙ_N を有限集合と
する。ここで、Ｘ_N を暗号文空間、Ｙ_N を平文空間と考
えるとする。

【００１８】いま、暗号化関数Ｅ_P が準同型性を満たす
とは、任意のｙ，ｙ′∈Ｙ_N に対し、それぞれ、暗号文
ｘ＝Ｅ_P （ｙ），ｘ′＝Ｅ_P （ｙ′）を考えた場合に、 ｘ○ｘ′＝Ｅ_P （ｙ●ｙ′） を満たす演算○と●が定義できることである。また、暗
号化空間Ｘ_N が可換群であるとは、任意のｘ，ｘ′∈Ｘ
_N に対し、ｘ○ｘ′＝ｘ′○ｘを満たすことである。

【００１９】以下、暗号文ｃを乱数ｒで撹乱する関数を
χ_P （ｃ，ｒ）と表記し、撹乱されたｙから乱数ｒによ
る影響を除去する関数をδ_P （ｙ，ｒ）で表すものとす
る。また、暗号文ｃを乱数ｕで撹乱する関数をξ
_P （ｃ，ｕ）と表記し、情報ｘから乱数ｕによる影響を
除去する関数をψ_P （ｘ，ｕ）で表すものとする。これ
らの関数χ_P （ｃ，ｒ），δ_P （ｙ，ｒ），ξ_P （ｃ，
ｕ），ψ_P （ｘ，ｕ）を、例えば暗号化関数Ｅ_P が準同
型性を満たし、かつ、暗号文空間が演算○に対し可換群
を満たすような暗号方式の場合は、次のように定義する
ことができる（ここで、ｃ＝Ｅ_P （ｍ）として、平文ｍ
の暗号文をｃとし、ｒ^-1は、演算●におけるｒの逆元、
ｕ^-1は、演算○におけるｕの逆元とする）。

【００２０】χ_P （ｃ，ｒ）＝ｃ○Ｅ_P （ｒ） δ_P （ｙ，ｒ）＝ｙ●ｒ^-1 ξ_P （ｃ，ｕ）＝ｃ○ｕ ψ_P （ｘ，ｕ）＝ｘ○ｕ^-1 まず、ｃ＝Ｅ_P （ｍ）であるから、χ_P （ｃ，ｒ）は χ_P （ｃ，ｒ）＝ｃ○Ｅ_P （ｒ）＝Ｅ_P （ｍ）○Ｅ
_P （ｒ）＝Ｅ_P （ｍ●ｒ） となりｃを撹乱できている。よって、これを復号した結
果ｙはｍ●ｒとなり、δ _P （ｙ，ｒ）よりｍを得ること
ができる。

【００２１】また、ξ_P （ｃ，ｕ）で撹乱された値ｖを
さらにχ_P （ｖ，ｒ）として撹乱しても、 χ_P （ｖ，ｒ）＝ｖ○Ｅ_P （ｒ）＝ξ_P （ｃ，ｕ）○Ｅ
_P （ｒ）＝ｃ○ｕ○Ｅ _P （ｒ）＝ｃ○Ｅ_P （ｒ）○ｕ となるので、この値ｘと関数ψ_P （ｘ，ｕ）からｃ○Ｅ
_P （ｒ）を得ることができる。

【００２２】いま、暗号文空間は演算○に対して群をな
すので、ｕをランダムに選んだ場合、ξ_P （ｃ，ｕ）の
出力もランダムとなる。また、Ｅ_P は暗号化関数である
ので、ｒをランダムに選んだ場合、Ｅ_P （ｒ）の結果も
十分にランダムとなり、上と同様にχ_P （ｃ，ｒ）の出
力もランダムとなる。

【００２３】

【発明の実施の形態】以下、図面と共にこの発明の実施
例を詳細に説明する。図１はこの発明の原理を示す機能
構成図である。送信装置１００は、受信装置２００と通
信路３００を介して結合されているとする。また、送信
装置１００には、送信したい情報ｍ_i （ｉ＝０，…，ｋ
−１）が入力され、受信装置２００には、受信したいｍ
_ijに対応する情報の組ｉ_j （ｊ＝０，…，ｆ−１）が入
力されると、ｍ_ij（ｊ＝０，…，ｆ−１）が出力される
ものとする。

【００２４】図２に、この発明の通信シーケンス例を、
図３に送信装置１００のブロック図を、図４に受信装置
２００のブロック図を示す。この発明の第一の実施例の
紛失通信方法を説明する。Ｓｔｅｐ１ 送信装置１００
には外部より送信したい情報の組ｍ_i （ｉ＝０，…，ｋ
−１）が入力される。この情報を暗号器１１０により暗
号化 ｃ_i ＝Ｅ_P （ｍ_i ）（ｉ＝０，…，ｋ−１） を行ない、この暗号文ｃ_i （ｉ＝０，…，ｋ−１）と、
乱数生成器１２０で生成されたｕを撹乱器１３０を用い
て ｖ_i ＝ξ_P （ｃ_i ，ｕ）（ｉ＝０，…，ｋ−１） と撹乱し、出力された予備情報ｖ_i （ｉ＝０，…，ｋ−
１）を受信装置２００へ送信する（つまり、従来技術の
Ｓｔｅｐ３に相当することを行なっている）。

【００２５】Ｓｔｅｐ２ 受信装置２００には、入力と
して、受信したい情報の識別情報の組ｉ_j （ｊ＝０，
…，ｆ−１）が与えられ、受信した予備情報ｖ_i （ｉ＝
０，…，ｋ−１）から選択器２１０を用いて、選択され
た予備情報の組ｖ_ij（ｊ＝０，…，ｆ−１）を求め、乱
数生成器２２０を用いて乱数ｒ_j （ｊ＝０，…，ｆ−
１）を生成して、撹乱器２３０を用いて質問情報ｘ
_j （ｊ＝０，…，ｆ−１）を ｘ_j ＝χ_P （ｖ_ij，ｒ_j ）（ｊ＝０，…，ｆ−１） と計算して、送信装置１００に送信する（つまり、従来
は受信装置が乱数ｑを送信し、これを受信して送信装置
がｃ_i が送信したが、この実施例では受信装置２００は
受信したいｍ_i に依存したｘ_j を送信している）。

【００２６】Ｓｔｅｐ３ 送信装置１００は、受信した
質問情報ｘ_j （ｊ＝０，…，ｆ−１）と先に生成した乱
数ｕを乱数成分除去器１４０に入力して ｗ_j ＝ψ_P （ｘ_j ，ｕ）（ｊ＝０，…，ｆ−１） を計算し、この出力ｗ_j （ｊ＝０，…，ｆ−１）を復号
器１５０を用いて復号し、回答情報ｙ_j （ｊ＝０，…，
ｆ−１）を ｙ_j ＝Ｄ_S （ｗ_j ）（ｊ＝０，…，ｆ−１） と計算し、受信装置２００へ送信する。

【００２７】Ｓｔｅｐ４ 受信装置２００は、受信した
回答情報ｙ_j （ｊ＝０，…，ｆ−１）と、撹乱器２３０
で用いた乱数ｒ_j （ｊ＝０，…，ｆ−１）を乱数成分除
去器２４０に入力し、受信したい情報ｍ_ij（ｊ＝０，
…，ｆ−１）を得る。 ｍ_ij＝δ_P （ｙ_j ，ｒ_j ）（ｊ＝０，…，ｋ−１） 次に、図５に送信情報長を可変にした場合の送信装置４
００の機能構成を、図６に送信情報長を可変にした場合
の受信装置５００の機能構成を示す。つまり送信情報ｍ
_i のビット数が少ないと安全性に問題があるためｍ_i に
乱数を連結するようにする。

【００２８】以下、この発明の第二の実施例の紛失通信
方式を説明する。Ｓｔｅｐ１ 送信装置４００には外部
より送信したい情報の組ｍ_i （ｉ＝０，…，ｋ−１）が
入力される。この情報と乱数生成器４１０で生成した乱
数ｔ_i （ｉ＝０，…，ｋ−１）を連結器４２０で連結
し、連結された情報ｓ_i （ｉ＝０，…，ｋ−１）を暗号
器４３０により暗号化を行ない、暗号文ｃ_i （ｉ＝０，
…，ｋ−１）と、乱数生成器４４０で生成されたｕを撹
乱器４５０を用いて撹乱し、出力された予備情報ｖ
_i （ｉ＝０，…，ｋ−１）を受信装置５００へ送信す
る。ここで、ｍ_i のビット数とｍ_i に対しどのようにｔ
_i を連結するかは送信側と受信側であらかじめ決められ
ているものとする。

【００２９】Ｓｔｅｐ２ 受信装置５００には、入力と
して、受信したい情報の識別情報の組ｉ_j （ｊ＝０，
…，ｆ−１）が与えられ、受信した予備情報ｖ_i （ｊ＝
０，…，ｋ−１）から選択回路５１０を用いて、選択さ
れた予備情報の組ｖ_ij（ｊ＝０，…，ｆ−１）を求め、
乱数生成器５２０を用いて乱数ｒ_j （ｊ＝０，…，ｆ−
１）を生成して、撹乱器５３０を用いて質問情報ｘ
_j （ｊ＝０，…，ｆ−１）を計算して、送信装置４００
に送信する。

【００３０】Ｓｔｅｐ３ 送信装置４００は、受信した
質問情報ｘ_j （ｊ＝０，…，ｆ−１）と先に生成した乱
数ｕを乱数成分除去器４６０に入力して、出力ｗ_j （ｊ
＝０，…，ｆ−１）を復号器４７０を用いて復号し、回
答情報ｙ_j （ｊ＝０，…，ｆ−１）を受信装置５００へ
送信する。Ｓｔｅｐ４ 受信装置５００は、受信したｙ
_j （ｊ＝０，…，ｋ−１）と、撹乱器５３０で用いた乱
数ｒ_j （ｊ＝０，…，ｆ−１）を乱数成分除去器５４０
に入力し、出力ｓ_ij（ｊ＝０，…，ｆ−１）を計算し、
これを乱数成分分離器５５０に入力することにより、受
信したい情報ｍ_ij（ｊ＝０，…，ｆ−１）を得る。

【００３１】なお、ｘ_P （ｃ，ｒ），δ_P （ｙ，ｒ）と
しては、暗号文ｃを乱数ｒを撹乱し、その撹乱された質
問情報ｘを復号し、その復号情報ｙから乱数ｒを除去で
き、また、乱数ｕによる撹乱による影響を受けないよう
な撹乱であればどのような手法でもよい。この発明で
は、暗号文ｃ_i を乱数ｕで撹乱したｖｉを受信装置へ送
信することにより、当紛失通信方法を複数回実行したと
しても、受信装置が先の通信で紛失した情報を不正に入
手することは不可能である。

【００３２】

【発明の効果】ここでは、ｆ−ｏｕｔ−ｏｆ−ｋ紛失通
信として、通信量をＥＧＬ法と比較する。ともに公開鍵
暗号方式にＲＳＡ暗号法を利用とするものとし（Ｚ_M ＝
Ｚ_N 、すなわち、Ｍ＝Ｎ）、この発明における送信装置
が行なう撹乱、および、乱数除去と受信装置が行なう乱
数除去は、Ｚ_N 上の乗除算で行なうものとする。また、
法Ｎ上での加算と乗除算に必要な計算量は、乱数生成や
暗号・復号操作に必要な計算量に比べて無視できるもの
とし、受信装置が行なう撹乱に必要な計算量は、暗号操
作に必要な計算量と同じであるとする。 （１）送信装置の処理量 まず、ＥＧＬ法において、送信装置は、ｒ_i （ｉ＝０，
…，ｋ−１）の生成にｋ回の乱数生成、ｃ_i,j （ｉ＝
０，…，ｋ−１，Ｊ＝０，…，ｆ−１）の計算ｋｆ回の
復号操作を必要とする。

【００３３】ｋ回 ： 乱数生成 ｋｆ回： 復号操作 一方、この発明方法では、送信装置はｃ_i （ｉ＝０，
…，ｋ−１）の計算にｋ回の暗号操作、ｙ_j （ｊ＝０，
…，ｆ−１）の計算にｆ回の復号操作を必要としてい
る。

【００３４】１回 ： 乱数生成 ｋ回 ： 暗号操作 ｆ回 ： 復号操作 ＥＧＬ法は、ｋｆ回の暗号・復号操作が必要なのに対
し、この発明の方法は、ｋ＋ｆ回の暗号・復号操作です
み、ｋ≫ｆの場合（ｋ＝１の場合を除く）に非常に効率
的であると言える。また、ｆ＝１の場合で比較しても、
暗号・復号操作の回数は一つしか違っていないので、送
信装置の処理量はほぼ同程度であると言える。

【００３５】また、ＥＧＬ法では、ｋ回の送信装置の乱
数生成が必要であるのに対して、この発明方法ではｋに
依存せず１回の乱数生成だけで十分である。 （２）受信装置の処理量 まず、ＥＧＬ法において、受信装置は、ｑ_j （ｊ＝０，
…，ｆ−１）の生成にｆ回の乱数生成、ｆ回の暗号操作
を必要とする。

【００３６】ｆ回 ： 乱数生成 ｆ回 ： 暗号操作 一方、この発明方法では、受信装置はｘ_j （ｊ＝０，
…，ｆ−１）の計算にｆ回の乱数生成、ｆ回の暗号操作
を必要としている。 ｆ回 ： 乱数生成 ｆ回 ： 暗号操作 よって、受信装置の処理量は同程度であると言える。 （３）システム内の通信量 まず、ＥＧＬ法では、送信装置からｒ_i （ｉ＝０，…，
ｋ−１）が、受信装置からｑ_j （ｊ＝０，…，ｆ−１）
が、さらに送信装置からＣ_i,j （ｉ＝０，…，ｋ−１，
ｊ＝０，…，ｆ−１）が送られるため、その通信量は （ｋ＋ｆ＋ｋｆ）×｜Ｎ｜bits で与えられる（ただし、｜Ｎ｜は法Ｎのビット長）。

【００３７】一方、この発明方法では、送信装置からｃ
_i （ｉ＝０，…，ｋ−１）が、受信装置からｘ_j （ｊ＝
０，…，ｆ−１）が、さらに送信装置からｙ_j （ｊ＝
０，…，ｆ−１）が送られるため、その通信量は （ｋ＋２ｆ）×｜Ｎ｜bits で与えられる。

【００３８】よって、ｋ＝２、ｆ＝１のときには、約２
０％の通信量の削減が可能であり、ｋ≫ｆの場合により
顕著に通信量が削減されることになる。

【図面の簡単な説明】

【図１】この発明の原理の機能構成を示すブロック図。

【図２】この発明の紛失通信における送信装置と受信装
置の通信文の交信の様子を示す図。

【図３】この発明の第一の実施例における送信装置の機
能構成を示すブロック図。

【図４】その受信装置の機能構成を示すブロック図。

【図５】送信情報長を可変にした実施例の送信装置の機
能構成を示すブロック図。

【図６】送信情報長を可変にした実施例の受信装置の機
能構成を示すブロック図。

Claims (2)

【特許請求の範囲】
1. 【請求項１】 送信装置がｋ個（ｋ＞２）の情報の中か
   らｆ個（１＜ｆ＜ｋ）を受信装置へ送信する通信方法に
   おいて、 送信装置は、複数の情報ｍ_i （ｉ＝０，…，ｋ−１）を
   暗号化し、暗号文ｃ_i（ｉ＝０，…，ｋ−１）を、生成
   した乱数ｕにより撹乱して予備情報ｖ_i （ｉ＝０，…，
   ｋ−１）を生成し、これを受信装置に送信し、 受信装置は、受信した予備情報ｖ_i （ｉ＝０，…，ｋ−
   １）から受信したい情報に対応（ｉ_j （ｊ＝０，…，ｆ
   −１））するｆ個の予備情報を選択し、選択された予備
   情報の組ｖ_ij（ｊ＝０，…，ｆ−１）を、生成した乱数
   ｒ_j （ｊ＝０，…，ｆ−１）で撹乱して質問情報ｘ
   _j （ｊ＝０，…，ｆ−１）を生成し、これを送信装置に
   送信し、 送信装置は、受信した質問情報ｘ_j （ｊ＝０，…，ｆ−
   １）から乱数成分ｕを除去して、この出力ｗ_j （ｊ＝
   ０，…，ｆ−１）を復号して回答情報ｙ_j （ｊ＝０，
   …，ｆ−１）を生成し、これを受信装置に送信し、 受信装置は、受信した回答情報ｙ_j （ｊ＝０，…，ｆ−
   １）から乱数成分ｒ_j（ｊ＝０，…，ｋ−１）を除去し
   て、選択した情報ｍ_ij（ｊ＝０，…，ｆ−１）を得るこ
   とを特徴とする紛失通信方法。
2. 【請求項２】 送信装置は、乱数ｔ_i （ｉ＝０，…，ｋ
   −１）を生成し、乱数ｔ_i を上記情報ｍ_i （ｉ＝０，
   …，ｋ−１）と連結し、その連結された情報ｓ _i （ｉ＝
   ０，…，ｋ−１）を暗号化して上記暗号文ｃ_i （ｉ＝
   ０，…，ｋ−１）とし、 受信装置は、受信した回答情報ｙ_j （ｊ＝０，…，ｋ−
   １）から乱数成分ｒ_iを除去して情報ｓ_ij（ｊ＝０，
   …，ｆ−１）を得、その情報ｓ_ijから送信装置が連結し
   た乱数成分ｔ_ij（ｊ＝０，…，ｆ−１）を分離して選択
   した情報ｍ_ij（ｊ＝０，…，ｋ−１）を得ることを特徴
   とする請求項１記載の紛失通信方法。