図面 (/)

技術 使い捨て変数を用い、処理過程における変数を情報理論的に不確定にすることよって暗号化と秘密鍵の秘匿に関し完全秘匿が成立するようにした暗号処理の装置および方法

出願人 若山裕典株式会社CANDACS株式会社ラピュタ
発明者 若山裕典綿野忠松浦克幸
出願日 2008年5月30日 (11年1ヶ月経過) 出願番号 2008-166552
公開日 2009年12月10日 (9年7ヶ月経過) 公開番号 2009-288758
状態 拒絶査定
技術分野 暗号化・復号化装置及び秘密通信
主要キーワード ベクトル配列 コスト対効果 簡易表記 M系列 因子行列 抜き取り量 アイプ 紛失事故
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2009年12月10日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

本発明の目的は、暗号文が完全秘匿性を持ち、秘密鍵が完全秘匿性若しくは計算量的完全秘匿性を持つ暗号処理の装置及び方法を提供することである。

解決手段

暗号鍵使い捨て変数を用いて生成するに当たり、その過程秘匿するべき変数(秘匿変数)を設け、その秘匿変数を入力値側からは推測不能とし、出力値である暗号鍵側からは情報理論的逆算不能とすることによって完全秘匿することにより、そのために、一様かつ周期性がなく初期値鋭敏性を持つ擬似ランダムビット生成器と、その擬似ランダムビット生成器を用いて作られた非線型置換装置および/または内積による置換装置を用いることによる。

概要

背景

本発明は、共通鍵方式対称鍵とも呼ばれる)に分類される暗号方式である。
その中の所謂「ヴァーナム暗号」であって、それを現実的な系として機能するようにしたものである。

Shannonの安全性に関する情報理論的モデル無条件安全性をもたらす。ヴァーナム暗号の完全秘匿性は計算上の問題の困難さや敵の計算能力限界に依存しない。完全秘匿性はほとんどの実用的な状況では到達可能ではないにもかかわらず、仮定に基づいていない。

即ち、ヴァーナム暗号は理論的には解読不能と言われてきたが、これまで何十年にもわたって、その有効な実現方法が見つからなかった。
その主たる理由は、所謂「鍵の配送コスト問題」である。

鍵の配送コスト問題とは、
ヴァーナム暗号では、平文を暗号化するのに、
(i)暗号化の都度新たな、つまりユニークな値を持ち、
且つ、
(ii)その平文と同じ長さを下回らない長さの真正ランダムビット、即ち少なくとも平文の不確定性を下回らない不確定性(情報理論的エントロピー)を持つビット列からなる暗号鍵
を必要とする。
これが暗号通信として成立するには、つまり、正しい受信者復号できるようにするには、暗号文とは別にその暗号鍵も安全に相手に送られなければならない。
ところが、暗号鍵を安全に送れるのであれば、当然のことながらそれと同じか短い長さの平文も、少なくとも同じ方法で安全に送れるはずである。
すると、ヴァーナム暗号は不要ということになり、その存在自体が矛盾することになる。

そこで、従来技術では、
一つには、生成の都度、真正ランダムビットに近いビット列を作るために擬似ランダムビット生成器を用いたが、計算によって生成されるため、シードの持つ低い不確定性しか実現できず、計算量と計算能力次第で解読可能になり得るという問題があった。現代暗号ではこれを情報理論における完全秘匿の類似として計算量的完全(または暗号的安全)といい、そのような暗号鍵は計算量的完全秘匿性を持つという。
また一つには、公開鍵方式とか二重鍵方式とか非対称鍵方式と呼ばれる毎回暗号鍵を送信しなくても済む方式が考えられたが、結局一つの暗号鍵で複数の平文を暗号化することになるので、情報理論的には解読可能になってしまっているという問題があった。そこで、鍵生成を非線型化することによって計算量によって解読困難とすることになる。
Shannonが指摘した、情報理論でいうところのこのような問題のとらえ方は後述するように計算量的完全の問題から証明されている。
ところが、これは実際には間違い(理論は正しい)で、後述するように、たった二つの暗号文から非対称鍵方式も含め固定的な暗号鍵を用いる方式は極めて容易に解読可能である。
ただし、従来の対称鍵方式や公開鍵方式の優れた点は、公開鍵方式では鍵のサイズが、その計算量からどうしても小さくならざるを得なかったため、ブロック暗号と言われる小さなブロックごとに暗号化するようにしたことであった。小さな秘密鍵は、その暗号化しようとする平文自体を変数としてブロック毎に順次置換され、平文の不確定性を下回らない不確定性を持つ暗号鍵として処理される。
従ってこの暗号化は、もし秘密鍵が暗号化の都度ユニークであるならば完全秘匿が成立することになる。

そこで従来技術では、次に、使い捨て公開鍵暗号という方式が考えられた。
この技術は、ヴァーナム暗号が不完全ながら実現したものである。即ち、生成の都度ユニークな値をとる小さな秘密鍵を生成し、その秘密鍵を使ってブロック方式で暗号/復号処理する。
しかしながら、それでも暗号通信に際しては秘密鍵の送受信が必要で、その送受信される秘密鍵の秘匿ために公開鍵(非対称鍵)暗号が用いられるというところに重大な問題が残った。
もっとも、この使い捨て公開鍵方式では通信時を除けば、つまり暗号文を保管する状態では計算量によらない安全、即ち完全秘匿が成立する。つまり、暗号文あるいは暗号化としては完全秘匿性を持たせるようにすることが可能である。

ところが、そこでまた問題が発生する。つまり、暗号文の保管時においては、暗号文と一対一でそれと対応するそれぞれの秘密鍵つまり暗号鍵も関連付けて管理されなければならない。つまり、どのような形にせよそのような関連付けがなければ、暗号文の所有者自身でさえ復号できないことになるわけである。

そこで、通常はデータベース等で管理することになるのであるが、その際のセキュリティが問題となる。データベースには基本的にはパスワード認証程度しかガードがなく、しかもデータベース管理者からはパスワードは無関係に丸見えである。たとえ暗号化されていたとしても、その暗号鍵を管理しているのがデータベース管理者であればやはり解読可能であることは同じである。
すると、暗号システム以外のところから、そもそもその暗号化が目的としていた情報秘匿崩壊してしまう。つまり、折角のヴァーナム暗号の完全秘匿性がヴァーナム暗号以外のところで崩れ去ってしまうという問題があった。

この問題に対する一つの対策として秘密分散と呼ばれる方式で秘密鍵(暗号鍵)を保管する方式が考えられた。これは登録された秘密鍵情報を完全秘匿の成立する形で秘匿する(つまりシステム管理者でも登録されている情報の内容を知ることはできない)ものの、その管理、つまり暗号文とその秘密鍵の関連付けまで考えると安全のレベルはそこに用いられる認証システム次第であり、何ら根本的な解決には至っていないという問題があった。

概要

本発明の目的は、暗号文が完全秘匿性を持ち、秘密鍵が完全秘匿性若しくは計算量的完全秘匿性を持つ暗号処理の装置及び方法を提供することである。暗号鍵を使い捨て変数を用いて生成するに当たり、その過程に秘匿するべき変数(秘匿変数)を設け、その秘匿変数を入力値側からは推測不能とし、出力値である暗号鍵側からは情報理論的に逆算不能とすることによって完全秘匿することにより、そのために、一様かつ周期性がなく初期値鋭敏性を持つ擬似ランダムビット生成器と、その擬似ランダムビット生成器を用いて作られた非線型の置換装置および/または内積による置換装置を用いることによる。

目的

(通信時における完全秘匿)従来方式では、いずれの暗号化法でも少なくとも通信時における暗号文の秘匿に関し、計算量的完全秘匿性しか実現しえていない。しかも今日、NIST(アメリカ合衆国国立標準技術研究所National Institute of Standardsand Technology)の勧告によって、これまで等価安全性で80ビットを下回らない不確定性が必要とされていた暗号化の強度が、2010年以降は113ビットを下回らない不確定性が必要とされ、暗号の2010年問題として社会問題化しつつある。
従って、保管時における完全秘匿性は当然のことながら、通信時における完全秘匿性の確保は喫緊の課題である。

効果

実績

技術文献被引用数
0件
牽制数
1件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

暗号処理の装置に関する系の全体は、変数ViとM−1000暗号化モデュール平文Miと暗号文EiとM−2000公開変数添付モデュールと送信文Tiとから構成され、M−1000暗号化モデュールは、M−1100暗号鍵生成モデュールと暗号鍵KiとM−1200暗号文生成モデュールとから構成され、M−1100暗号鍵生成モデュールはM−1110秘匿変数生成モデュールとM−1120不可視化処理モデュールとから構成され、成し、その暗号鍵KiをM−1200暗号文生成モデュールに入力して暗号文Eiを生成し、その暗号文EiをM−2000公開変数添付モデュールに入力して送信文Tiを得るようにし、M−1110秘匿変数生成モデュールにおいて秘匿変数を推測不能とし、且つM−1110秘匿変数生成モデュールを非線型化をすることによってM−1110秘匿変数生成モデュールに含まれる秘密鍵を秘匿するか若しくはM−1120不可視化処理モデュールを非線型処理とすることによって秘匿変数そのことによって、暗号化を完全秘匿とすると同時に、変数Viと暗号文Eiとその平文Miを攻撃者入手したとしても秘密鍵について完全秘匿性または計算量的完全秘匿性を持つようにしたことを特徴とする暗号処理の装置。

請求項2

暗号処理の装置のための置換装置において、置換装置(c)は、二つの入力値を持つ擬似ランダムビット生成過程において折畳または抜取または内積を含む演算を行うことによって生成を非線型化するA−004擬似ランダムビット生成器型置換装置(ロ)と、入力値である変数Vと、秘密鍵Sと、出力値Cとから構成され、変数Vと秘密鍵SとをA−004擬似ランダムビット生成器型置換装置(ロ)に入力することに因って非線型化した演算を行って出力値Cを得るようにした暗号処理の方法のための置換処理の装置であるか、または、置換装置(d)は、二つの入力値を素数pを法とする内積によって置換するA−変数Vと、p−1(前記素数pから一を減じた値)を法とする秘密鍵Sと、p−1(前記素数pから一を減じた値)を法とする出力値Cとから構成され、変数Vと内積して法pの出力値Cを得、その出力値Cを法pで各成分から一を減じることで法をp−1(前記素数pから一を減じた値)とする処理を行い、法をp−1(前記素数pから一を減じた値)とする出力値Cを得るようにした暗号処理の方法のための置換処理の装置であるか、または、置換装置(e)は、二つの入力値を自然数Nを法とするベクトル和によって置換鍵Sをベクトル和して出力値Cを得るようにした暗号処理の方法のための置換処理の装置であるか、または、置換装置(f)は、二つの入力値を自然数Nを法とするベクトル和によって置換値C′と、一つの入力値を持つ擬似ランダムビット生成過程において折畳または抜取または内積を含む演算を行うことによって生成を非線型化するA−005擬似ランダムビット生成器型置換装置(ハ)と、出力値Cとから構成され、VAとVBとそのC′をA−005擬似ランダムビット生成器型置換装置(ハ)に入力して置換することによって出力値Cを得るようにした暗号処理の方法のための置換処理の装置であるか、または、置換装置(g)は、二つの入力値を素数pを法とする内積によって置換するA−変数Vと、p−1(前記素数pから一を減じた値)を法とする秘密鍵Sと、置換された値C′と、一つの入力値を持つ擬似ランダムビット生成過程において折畳または抜取または内積を含む演算を行うことによって生成を非線型化するA−005擬似ランダムビット生成器型置換装置(ハ)と、出力値Cとから構成され、VとそのC′をA−005擬似ランダムビット生成器型置換装置(ハ)に入力して置換することによって出力値Cを得るようにした暗号処理の方法のための置換処理の装置であることを特徴とする請求項1に記載の暗号処理の装置。

請求項3

暗号文および秘密鍵について完全秘匿である暗号処理の装置は、使い捨て公開変数riと、M−1110秘匿変数生成モデュールと、秘匿変数K′iと、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、M−1110秘匿変数生成モデュールは、秘密鍵S1と、A−901置換装置Aとから構成され、M−1120不可視化処理モデュールは、秘密鍵S2と、A−902置換装置Bと、から構成され、使い捨て公開変数riと秘密鍵S1とをA−901置換装置Aに入力して置換することによって秘匿変数K′iを生成し、その秘匿変数K′iと秘密鍵S2とをA−902置換装置Bに入力することによって暗号鍵Kiを生成し、その暗号鍵Kiと平文MiをA−903置換装置Γに入力することに因って暗号文Eiを生成するよう処理され、A−901置換装置Aを、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、A−902置換装置Bを、置換装置(d)または置換装置(g)から構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も情報理論的逆算不能とし、A−901置換装置AとA−902置換装置Bを用いるようにしたことに因って秘密鍵S1と秘密鍵S2とを完全秘匿化し、A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにしたことを特徴とする請求項1または請求項2に記載の暗号処理の装置。

請求項4

暗号文および秘密鍵について完全秘匿である暗号処理の装置は、使い捨て公開変数riと、A−301セパレータと、変数Vi1と、変数Vi2と、M−1110秘匿変数生成モデュールと、秘匿変数K′i1と、秘匿変数K′i2と、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、M−1110秘匿変数生成モデュールは、秘密鍵S1と、秘密鍵S2と、A−901置換装置A1と、A−901置換装置A2とから構成され、M−1120不可視化処理モデュールは、A−902置換装置Bから構成され、使い捨て公開変数riをA−301セパレータで分割して変数Vi1と変数Vi2とを生成し、その変数Vi1と秘密鍵S1とをA−901置換装置A1に入力して置換することによって秘匿変数K′i1を生成し、同時に変数Vi2と秘密鍵S2とをA−901置換装置A2に入力して置換することによって秘匿変数K′i2を生成し、その秘匿変数K′i1と秘匿変数K′i2とをA−902置換装置Bに入力することによって置換して暗号鍵Kiを生成し、その暗号鍵Kiと平文MiとをA−903置換装置Γに入力することによって置換して暗号文Eiを生成するよう処理され、A−901置換装置A1およびA−901置換装置A2を、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、A−902置換装置Bを、置換装置(d)、置換装置(e)置換装置(f)、置換装置(g)のいずれかから構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も情報理論的に逆算不能とし、A−901置換装置A1およびA−901置換装置A2とA−902置換装置Bを用いるようにしたことに因って、但し、A−901置換装置A1およびA−901置換装置A2が置換装置(e)であればA−902置換装置Bは置換装置(c)、置換装置(d)、置換装置(f)、置換装置(g)のいずれかとし、A−902置換装置Bが置換装置(e)であればA−901置換装置A1およびA−901置換装置A2は置換装置(c)、置換装置(d)、置換装置(f)、置換装置(g)のいずれかとすることに因って、秘密鍵S1と秘密鍵S2とを完全秘匿化し、A−903置換装置Γを、置換装置(d)または(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにしたことを特徴とする請求項1または請求項2に記載の暗号処理の装置。

請求項5

暗号文について完全秘匿性を持たせると同時に、秘密鍵について暗号文と平文が漏洩することによって暗号鍵の情報が漏洩したとしても計算量的完全秘匿性を持たせる暗号処理の装置は、使い捨て公開変数riと、M−1110秘匿変数生成モデュールと、秘匿変数K′iと、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、M−1110秘匿変数生成モデュールは、秘密鍵S1と、A−901置換装置Aとから構成され、M−1120不可視化処理モデュールは、秘密鍵S2と、A−902置換装置Bと、から構成され、使い捨て公開変数riと秘密鍵S1とをA−901置換装置Aに入力して置換することによって秘匿変数K′iを生成し、その秘匿変数K′iと秘密鍵S2とをA−902置換装置Bに入力することによって暗号鍵Kiを生成し、その暗号鍵Kiと平文MiをA−903置換装置Γに入力することに因って暗号文Eiを生成するよう処理され、A−901置換装置Aを、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、A−902置換装置Bを、置換装置(c)または置換装置(f)から構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も計算量的に逆算不能とし、A−901置換装置AとA−902置換装置Bを用いるようにしたことに因って秘密鍵S1と秘密鍵S2とを計算量的完全秘匿化し、A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにしたことを特徴とする請求項1または請求項2に記載の暗号処理の装置。

請求項6

暗号文について完全秘匿性を持たせると同時に、秘密鍵について暗号文と平文が漏洩することによって暗号鍵の情報が漏洩したとしても計算量的完全秘匿性を持たせる暗号処理の装置は、使い捨て公開変数riと、A−301セパレータと、変数Vi1と、変数Vi2と、M−1110秘匿変数生成モデュールと、秘匿変数K′i1と、秘匿変数K′i2と、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、M−1110秘匿変数生成モデュールは、秘密鍵S1と、秘密鍵S2と、A−901置換装置A1と、A−901置換装置A2とから構成され、M−1120不可視化処理モデュールは、A−902置換装置Bから構成され、使い捨て公開変数riをA−301セパレータで分割して変数Vi1と変数Vi2とを生成し、その変数Vi1と秘密鍵S1とをA−901置換装置A1に入力して置換することによって秘匿変数K′i1を生成し、同時に変数Vi2と秘密鍵S2とをA−901置換装置A2に入力して置換することによって秘匿変数K′i2を生成し、その秘匿変数K′i1と秘匿変数K′i2とをA−902置換装置Bに入力することによって置換して暗号鍵Kiを生成し、その暗号鍵Kiと平文MiとをA−903置換装置Γに入力することによって置換して暗号文Eiを生成するよう処理され、A−901置換装置A1およびA−901置換装置A2を、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、A−902置換装置Bを、置換装置(c)から構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も計算量的に逆算不能とし、A−901置換装置A1およびA−901置換装置A2とA−902置換装置Bを用いるようにしたことに因って、秘密鍵S1と秘密鍵S2とを計算量的完全秘匿化し、A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにしたことを特徴とする請求項1または請求項2に記載の暗号処理の装置。

請求項7

暗号文について完全秘匿性を持たせると同時に、秘密鍵について暗号文と平文が漏洩することによって暗号鍵の情報が漏洩したとしても計算量的完全秘匿性を持たせる暗号処理の装置は、使い捨て公開変数riと、M−1110秘匿変数生成モデュールと、変数Riと、A化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、M−1110秘匿変数生成モデュールは、秘密鍵S1と、A−901置換装置Aとから構成され、M−1120不可視化処理モデュールは、秘密鍵S2と、A−902置換装置Bとから構成され、使い捨て公開変数riと秘密鍵S1とをA−901置換装置Aに入力して置換することによって変数Riを生成し、その変数RiからA−002擬似ランダムビット生成2置換装置Bに入力することによって暗号鍵Kiを生成し、その暗号鍵Kiと平文MiをA−903置換装置Γに入力することに因って暗号文Eiを生成するよう処理され、A−901置換装置Aを、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って使い捨て公開変数riからは秘匿変数K′iを推測不能とし、A−902置換装置Bを、置換装置(c)、置換装置(d)、置換装置(f)、置換装置(g)のいずれかから構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も計算量的に逆算不能とし、A−901置換装置AとA−902置換装置Bを用いるようにしたことに因って秘密鍵S1と秘密鍵S2とを計算量的完全秘匿化し、A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにしたことを特徴とする請求項1または請求項2に記載の暗号処理の装置。

請求項8

暗号文について完全秘匿性を持たせると同時に、秘密鍵について暗号文と平文が漏洩することによって暗号鍵の情報が漏洩したとしても計算量的完全秘匿性を持たせる暗号処理の装置は、使い捨て公開変数riと、A−301セパレータと、変数Vi1と、変数Vi2と、M−1110秘匿変数生成モデュールと、変数Riと、秘匿変数K′i1と、秘匿変数K′i2と、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、M−1110秘匿変数生成モデュールは、秘密鍵S1と、秘密鍵S2と、A−901置換装置A1と、A−901置換装置A2とから構成され、M−1120不可視化処理モデュールは、A−902置換装置Bとから構成され、使い捨て公開変数riをA−301セパレータで分割して変数Vi1と変数Vi2とを生成し、その変数Vi1と秘密鍵S1とをA−901置換装置A1に入力して置換することによって秘匿変数K′i1を生成し、同時に変数Vi2と秘密鍵S2とをA−901置換装置A2に入力して置換することによって変数Riを生成し、その変数Riか秘匿変数K′i1と秘匿変数K′i2とをA−902置換装置Bに入力することによって置換して暗号鍵Kiを生成し、その暗号鍵Kiと平文MiとをA−903置換装置Γに入力することによって置換して暗号文Eiを生成するよう処理され、A−901置換装置A1およびA−901置換装置A2を、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、A−902置換装置Bを、置換装置(c)から構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も計算量的に逆算不能とし、A−901置換装置A1およびA−901置換装置A2とA−902置換装置Bを用いるようにしたことに因って、秘密鍵S1と秘密鍵S2を不確定性がH(S1)+H(S2)で計算量的完全秘匿化し、但し、このときつまり、秘密鍵S1の不確定性H(S1)は変数Vi1の不確定性H(Vi1)を下回らず、かつ秘匿変数K′i1の不確定性H(K′i1)および暗号鍵Kiの不確定性H(Ki)と等しく、且つ、秘密鍵S2の不確定性H(S2)は変数Vi2の不確定性H(Vi2)を下回らず、かつ変数Riの不確定性H(Ri)および秘匿変数K′i2の不確定性H(K′i2)と等しく、かつ暗号鍵Kiの不確定性H(Ki)を下回り、且つ、暗号鍵Kiの不確定性H(Ki)は平文Miの不確定性H(Mi)を下回らないものとし、A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにしたことを特徴とする請求項1または請求項2に記載の暗号処理の装置。

請求項9

シードであるベクトルaと生成するべき成分数|A|を入力値として受け取り、生成に伴って伸長されるベクトルの成分数を監視し、成分数の過不足を判定して不足であれば入力または生成されたベクトルをA−301セパレータに送るようA−203ベクトル配列生成部に指示し、十分であればA−203ベクトル配列生成部に通知してA−203ベクトル配列生成部において生成されたベクトルをA−203ベクトル配列生成部から受け取って外部に戻す働きをするA−201データ長管理部と、受け取ったベクトルを二つのベクトルに分割してA−202表演算部に送出するA−301セパレータと、A−301セパレータから受け取った二つのベクトルを2次元の表の第一列と第一行に配置し、生成値を含む行方向および列方向の複数の成分に和または積の演算を行うことによって演算表を生成するA−202表演算部と、A−202表演算部において生成された表の成分から列ベクトル毎にデータを抜き出し、新たなベクトルとして配列を生成し、データ長管理部からの指示に基づいて送出するA−203ベクトル配列生成部とから構成され、シードであるベクトルaと生成する擬似ランダムビットの成分数|A|をA−201データ長管理部に入力すると、A−201データ長管理部はベクトルaの成分数が|A|を下回れば、つまり、|a|<|A|ならばベクトルaをA−301セパレータに送り、A−301セパレータはベクトルaをベクトルV1とV2に分割(但し|a|=|V1|+|V2|。つまりV1の成分数とV2の成分数を足したものはaの成分数に等しい)してA−202表演算部に送り、(1)A−202表演算部はベクトルV1、V2をそれぞれ二次元の表の第一行と第一列に配置し、表の各成分に対して行方向の複数の成分と列方向の複数の成分を用い(但し、例えば第二行第二列成分ではV1の第一成分とV2の第二成分を用い、第二行第三列成分ではV1の第一成分と第二行第二列成分とV2の第二成分を用いるという風に、一つの成分しか用いることができない場合は一つの成分だけを用いる)自然数Nを法として和または素数pを法として積または積と和を行うことにより二次元の演算表を生成し、例えば、全ての演算を和とするならば、行方向に演算される成分数をψ、列方向に演算される成分数をξとする時、任意の成分をaijとすれば、つまり、aijで表わされる二次元の表の第i行第j列の成分は、自然数Nを法として、aijが属する列のaijの一つ上の行つまり第i−1(iから一を減じた値)行目から上に第ψ番目の行つまり第i−ψ(iからψ(二を下回らない自然数)を減じた値)行目までの全ての成分を足し合わせた値と、aijが属する行のaijの一つ左の列つまり第j−1(jから一を減じた値)列目から左に第ξ番目の列つまり第j−ξ(jからξ(二を下回らない自然数)を減じた値)列目までの全ての成分を足し合わせた値を足し合わせた値に合同その生成結果から第一列成分と第一行成分を除いた成分(生成結果を行列に見立について列ベクトル毎にまたは行ベクトル毎に成分を取り出したベクトル(Bj)j=1,2,...,n−1(但し、Bj=Aj+1)、つまり、任意の成分がBjで表わされるn−1(nから一を減じた値)個の成分からなるベクトルであって、第j番目の成分がベクトルAの第j+1(jに一を加えた値)番目の成分と等しいベクトルを生成してA−203ベクトル配列生成部に送り、(2)A−203ベクトル配列生成部は、その取り出された列ベクトル(Bj)j=1,2,...,n−1=(B1,B2,...,Bn−1)つまり、ベクトル(Bj)j=1,2,...,n−1はベクトルB1からベクトルBn−1までのn−1(nから一を減じた値)個のベクトルを成分とするベクトルの成分を展開してベクトルB=(b1,b2,...,b(m−1)(n−1)−1,b(m−1)(n−1))つまり、b1からb(m−1)(n−1)までの(m−1)(n−1)(mから一を減じた値とnから一を減じた値を掛け合わせた値)個の成分からなるベクトルBを生成し、(3)A−201データ長管理部はこの生成過程を常時チェックし、ベクトルBの成分数|B|が|A|を上回らないならばベクトルBをA−301セパレータに送って、(4)A−301セパレータはベクトルBをベクトルV1とV2に分割(但し|B|=|V1|+|V2|。つまりV1の成分数とV2の成分数を足したものはBの成分数に等しい)してA−202表演算部に送り、成分数|B|が|A|を下回らなくなるまで上記(1)から(4)までの過程を繰り返し、成分数|B|が|A|を下回らなくなったベクトルBを出力値であるベクトルAとして返すようにしたことを特徴とする請求項2から8までのいずれかに記載の暗号処理の装置。

請求項10

複数の入力値であるベクトルA,Bに対して出力値がベクトルCとするとき、A,Bを、二を下回らない自然数Nを法としてベクトル和するか、または三を下回らない素数pを法として内積するかまたはベクトル和および内積してベクトルCとして出力することによって、即ち、入力された二つのベクトルであるA−101A=(ai)i=1,2,...,n、つまり任意の成分がaiで表わされるn個の成分からなるベクトルAおよびA−101B=(bi)i=1,2,...,n、つまり任意の成分がbiで表わされるn個の成分からなるベクトルBに対し、それぞれの成分の内の同じ次元同士の値をは積と和の演算を行い、各成分を次元の順に並べてベクトルA−102C=(ci)i=1,2,...,nつまり任意の成分がciで表わされるn個の成分からなるベクトルCの出力を得、そのことによって、ベクトルAの不確定性H(A)とベクトルBの不確定性H(B)が異H(C)つまりH(B)はH(C)と等しく、且つ、H(B)とH(C)はH(A)を下回らず、即ちベクトルCの不確定性H(C)がベクトルBの不確定性H(B)と等しくなるように置換するようにしたことを特徴とする請求項2から請求項8までのいずれかに記載の暗号処理の装置。

請求項11

入力値であるベクトルA,Bに対して出力値がベクトルCとすると、ベクトルA,Bが共にp−1(pから一を減じた値)を法とするベクトルあるとき、p−1を法とするA−101A=(ai)i=1,2,...,nつまり任意の成分がaiで表わされるn個の成分からなるベクトルAおよびA−101B=(bi)i=1,2,...,nつまり任意の成分がbiで表わされるn個の成分からなるベクトルBの各成分にpを法として一を加えることで、pを法とするベクトルA−103A′=(a′i)i=1,2,...,nつまり任意の成分がa′iで表わされるn個の成分からなるベクトルA′およびA−103B′=(b′i)i=1,2,...,nつまり任意の成分がb′iで表わされるn個の成分からなるベクトルB′(但し、(a′i,b′i)≠(0,0)、つまりベクトルA′およびB′の成分には0は含まれていない)を生成し、ベクトルA−103A′=(a′i)i=1,2,...,nつまり任意の成分がa′iで表わされるn個の成分からなるベクトルA′およびA−103B′=(b′i)i=1,2,...,nつまり任意の成分がb′iで表わされるn個の成分からなるベクトルB′のそれぞれの成分の内の同じ次元同士の値をpを法として積で演算し、演算結果として出力されたベクトルA−103C′=(c′i)i=1,2,...,nつまり任意の成分がc′iで表わされるn個の成分からなるベクトルC′の各成分の値からpを法として一を引いた値を生成することで実質的に法をp−1(pから一を減じた値)とし、法をp−1(pから一を減じた値)とするベクトルA−102C=(ci)i=1,2,...,nつまり任意の成分がciで表わされるn個の成分からなるベクトルCを得るようにしたことを特徴とする請求項2から請求項8、請求項10のいずれかに記載の暗号処理の装置。

請求項12

暗号化が計算量的完全秘匿性を持つための必要条件を満たすA−00一または複数のベクトルと、出力するベクトルの成分数|A|を入力し、入力されるベクトルが複数の場合はA−401連結装置でそれら複数のベクトルを連結して一つのベクトルとし(入力値が二つのベクトルa、bであればそのa、bを連結した一つのベクトル(a‖b)を生成し)、−201データ長管理部で算定し、その連結された一つのベクトル前記(a‖b)をシードとしてA−002擬似ランダその行列A′をA−601一方向置換器(イ)またはA−603折畳置換器からなるA−501置換器に入力して非線型な置換をして成分数|A|を有するベクトルAを得るようにしたことを特徴とする請求項2から請求項8までのいずれかに記載の暗号処理の装置。

請求項13

暗号化が計算量的完全秘匿性を持つための必要条件を満たすA−00(一)一または複数のベクトルと、出力するベクトルの成分数|A|を入力し、(二)入力されるベクトルが複数の場合はA−401連結装置でそれら複数のベクトルを連結して一つのベクトルとし(入力値が二つのベクトルa、bであればそのa、bを連結した一つのベクトル(a‖b)を生成し)、(三)その複数のベクトルが連結された一つのベクトル(前記(a‖b))をシードット生成し、(四)その擬似ランダムビットをA−601一方向置換器(イ)からなるA−501置換器で非線型な置換をして行列A′を生成し、判定し、(ろ)|A|>|A′|であればその行列A′を再びA−002擬似ランダムビット生ことによってベクトルAを得るようにしたことを特徴とする請求項2から請求項8までのいずれかに記載の暗号処理の装置。

請求項14

暗号化が完全秘匿性を持つための必要条件を満たすA−002擬似ラ一または複数のベクトルと、出力するベクトルの成分数|A|を入力し、入力されるベクトルが複数の場合はA−401連結装置でそれら複数のベクトルを連結して一つのベクトルとし(入力値が二つのベクトルa、bであればそのa、bを連結した一つのベクトル(a‖b)を生成し)、−201データ長管理部で算定し、その連結された一つのベクトル前記(a‖b)をシードとしてA−002擬似ランダその行列A′をA−602一方向置換器(ロ)またはA−603折畳置換器またはA−604折畳+抜取置換器からなるA−501置換器に入力して非線型な置換をして成分数|A|を有するベクトルAを得るようにしたことを特徴とする請求項2から請求項8までのいずれかに記載の暗号処理の装置。

請求項15

暗号化が完全秘匿性を持つための必要条件を満たすA−002擬似ラ(一)一または複数のベクトルと、出力するベクトルの成分数|A|を入力し、(二)入力されるベクトルが複数の場合はA−401連結装置でそれら複数のベクトルを連結して一つのベクトルとし(入力値が二つのベクトルa、bであればそのa、bを連結した一つのベクトル(a‖b)を生成し)、(三)その複数のベクトルが連結された一つのベクトル(前記(a‖b))をシードット生成し、(四)その擬似ランダムビットをA−602一方向置換器(ロ)またはA−603折畳置換器またはA−604折畳+抜取置換器からなるA−502置換器で非線型な置換して行列A′を生成し、判定し、Aとして出力し、(ろ)|A|>|A′|であればその行列A′を再びA−002擬似ランダムビット生ことによってベクトルAを得るようにしたことを特徴とする請求項2から請求項8までのいずれかに記載の暗号処理の装置。

請求項16

擬似ランダムビット生成器を用いる置換装置であって、入力値が複数で且つ出力値の成分数が入力値の成分数を下回らない置換装置がA−003擬似ランダムビット生成器型置換装置(イ)であり、入力値が複数で且つ出力値の成分数が入力値の成分数と等しい置換装置が、A−004擬似ランダムビット生成器型置換装置(ロ)であり、入力値が一つで且つ出力値の成分数が入力値の成分数を下回らない置換装置はA−005擬似ランダムビット生成器型置換装置(ハ)であることを特徴とする請求項2から請求項8までのいずれかに記載の暗号処理の装置。

請求項17

弱い非線型性を持つ線型の擬似ランダムビット生成器であるA−00抜き取りによって非線型化させる置換器は、る表(行列)をAとするとき、A−302一方向化エクストラクタ単体から構成され、入力値Aに対し、その成分数が入力値Aの成分数|A|を下回らず且つ非線型化され情報理論的にA−601一方向置換器(イ)と、A−302一方向化エクストラクタとA−303ベーシックエクストラクタから構成され、A−302一方向化エクストラクタ単体から構成され、入力値Aに対し、A−302一方向化エクストラクタがその成分数が入力値Aの成分数|A|を下回らず且つ非線型化され情報理論的に逆算不能な余因子行列をベクトルAとして出力するA−602一方向置換器(ロ)であるようにしたことを特徴とする請求項2から請求項8までのいずれかに記載の暗号処理の装置。

請求項18

弱い非線型性を持つ線型の擬似ランダムビット生成器であるA−00みによって非線型化させる置換器は、の擬似ランダムビットA′を生成し、それをA−301セパレータでn個に分割し、または、擬似ランダムビットA′を生成し、それをA−301セパレータで二つ以上に分割とによって生成した値またはベクトルから、更に成分数を前記A−002擬似ラクストラクタで任意の成分を抜き取り成分数を調整するようにしたことを特徴とする請求項2から請求項8までのいずれかに記載の暗号処理の装置。

請求項19

A−301セパレータとA−001aベクトル和型置換装置によって構成される置換器は、る表(行列)をAとし、その行列Aから生成されたベクトルをA′とするとき、A−301セパレータとA−001aベクトル和型置換装置によって構成され、A′が入力されるとA−301セパレータはA′を等分な二つのベクトルにのベクトルをベクトル和または内積することによって置換してベクトルAを生成し出力するA−603置換器と、A−301セパレータとA−001aベクトル和型置換装置とA−303ベーシックエクストラクタによって構成され、A′が入力されるとA−301セすることによって置換してベクトルA″を生成し、A−303ベーシックエクストラクタがそのA″から任意の成分を|A″|−|A′|つまりベクトルA″の成分数|A″|からA′の成分数|A′|を引いた成分数だけ抜き取ることによって成分数|A′|のベクトルA(3)を生成し、そのA(3)をベクトルAとして出力するA−604折畳+抜取置換器であるようにしたことを特徴とする請求項2から請求項8までのいずれかに記載の暗号処理の装置。

請求項20

A−302一方向化エクストラクタは、のij成分であるaijの演算対象となる成分が、第i−1行目の成分であるai−1,jから列方向に第i−ψ行目の成分であるai−ψ,jまでのψ個と、第j−1列目の成分であるai,j−1から行方向に第j−ξ列目の成分であるai,j−ξまでのξ個とすれば、その第一行と第二行および第2+ψm行(但しm=1,2,...)及び第一列と第二列および第2+ξn列(但し、n=1,2,...)を除いた前記行列の余因子行列を生成し、その余因子行列の各列ベクトルまたは行ベクトルを並べて一つのベクトルとして生成し出力するようにしたことを特徴とする請求項17に記載の暗号処理の装置。

請求項21

暗号処理の方法に関する系の全体は、変数ViとM−1000暗号化モデュールと平文Miと暗号文EiとM−2000公開変数添付モデュールと送信文Tiとから構成され、M−1000暗号化モデュールは、M−1100暗号鍵生成モデュールと暗号鍵KiとM−1200暗号文生成モデュールとから構成され、M−1100暗号鍵生成モデュールはM−1110秘匿変数生成モデュールとM−1120不可視化処理モデュールとから構成され、成し、その暗号鍵KiをM−1200暗号文生成モデュールに入力して暗号文Eiを生成し、その暗号文EiをM−2000公開変数添付モデュールに入力して送信文Tiを得るようにし、M−1110秘匿変数生成モデュールにおいて秘匿変数を推測不能とし、且つM−1110秘匿変数生成モデュールを非線型化をすることによってM−1110秘匿変数生成モデュールに含まれる秘密鍵を秘匿するか若しくはM−1120不可視化処理モデュールを非線型処理とすることによって秘匿変数そのことによって、暗号化を完全秘匿とすると同時に、変数Viと暗号文Eiとその平文Miを攻撃者が入手したとしても秘密鍵について完全秘匿性または計算量的完全秘匿性を持つようにしたことを特徴とする暗号処理の方法。

請求項22

暗号処理の方法ための置換方法は、置換装置(c)は、二つの入力値を持つ擬似ランダムビット生成過程において折畳または抜取または内積を含む演算を行うことによって生成を非線型化するA−004擬似ランダムビット生成器型置換装置(ロ)と、入力値である変数Vと、秘密鍵Sと、出力値Cとから構成され、変数Vと秘密鍵SとをA−004擬似ランダムビット生成器型置換装置(ロ)に入力することに因って非線型化した演算を行って出力値Cを得るようにした暗号処理の方法のための置換処理の装置および/または方法であるか、または、置換装置(d)は、二つの入力値を素数pを法とする内積によって置換するA−変数Vと、p−1(前記素数pから一を減じた値)を法とする秘密鍵Sと、p−1(前記素数pから一を減じた値)を法とする出力値Cとから構成され、変数Vと内積して法pの出力値Cを得、その出力値Cを法pで各成分から一を減じることで法をp−1(前記素数pから一を減じた値)とする処理を行い、法をp−1(前記素数pから一を減じた値)とする出力値Cを得るようにした暗号処理の方法のための置換処理の装置および/または方法であるか、または、置換装置(e)は、二つの入力値を自然数Nを法とするベクトル和によって置換鍵Sをベクトル和して出力値Cを得るようにした暗号処理の方法のための置換処理の装置および/または方法であるか、または、置換装置(f)は、二つの入力値を自然数Nを法とするベクトル和によって置換値C′と、一つの入力値を持つ擬似ランダムビット生成過程において折畳または抜取または内積を含む演算を行うことによって生成を非線型化するA−005擬似ランダムビット生成器型置換装置(ハ)と、出力値Cとから構成され、VAとVBとそのC′をA−005擬似ランダムビット生成器型置換装置(ハ)に入力して置換することによって出力値Cを得るようにした暗号処理の方法のための置換処理の装置および/または方法であるか、または、置換装置(g)は、二つの入力値を素数pを法とする内積によって置換するA−変数Vと、p−1(前記素数pから一を減じた値)を法とする秘密鍵Sと、置換された値C′と、一つの入力値を持つ擬似ランダムビット生成過程において折畳または抜取または内積を含む演算を行うことによって生成を非線型化するA−005擬似ランダムビット生成器型置換装置(ハ)と、出力値Cとから構成され、VとそのC′をA−005擬似ランダムビット生成器型置換装置(ハ)に入力して置換することによって出力値Cを得るようにした暗号処理の方法のための置換処理の装置および/または方法であることを特徴とする請求項21に記載の暗号処理の方法。

請求項23

暗号文および秘密鍵について完全秘匿である暗号処理の方法は、使い捨て公開変数riと、M−1110秘匿変数生成モデュールと、秘匿変数K′iと、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、M−1110秘匿変数生成モデュールは、秘密鍵S1と、A−901置換装置Aとから構成され、M−1120不可視化処理モデュールは、秘密鍵S2と、A−902置換装置Bと、から構成され、使い捨て公開変数riからA−002擬似ランダムビット生成器によって変数Viを生成し、その変数Viと秘密鍵S1とをA−901置換装置Aに入力して置換することによって秘匿変数K′iを生成し、その秘匿変数K′iと秘密鍵S2とをA−902置換装置Bに入力することによって暗号鍵Kiを生成し、その暗号鍵Kiと平文MiをA−903置換装置Γに入力することに因って暗号文Eiを生成するよう処理され、A−901置換装置Aを、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、A−902置換装置Bを、置換装置(d)または置換装置(g)から構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も情報理論的に逆算不能とし、A−901置換装置AとA−902置換装置Bを用いるようにしたことに因って秘密鍵S1と秘密鍵S2とを完全秘匿化し、A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにしたことを特徴とする請求項21または請求項22に記載の暗号処理の方法。

請求項24

暗号文および秘密鍵について完全秘匿である暗号処理の方法は、使い捨て公開変数riと、A−301セパレータと、変数Vi1と、変数Vi2と、M−1110秘匿変数生成モデュールと、秘匿変数K′i1と、秘匿変数K′i2と、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、M−1110秘匿変数生成モデュールは、秘密鍵S1と、秘密鍵S2と、A−901置換装置A1と、A−901置換装置A2とから構成され、M−1120不可視化処理モデュールは、A−902置換装置Bから構成され、使い捨て公開変数riからA−002擬似ランダムビット生成器によって変数Viを生成し、その変数ViをA−301セパレータで分割して変数Vi1と変数Vi2とを生成し、その変数Vi1と秘密鍵S1とをA−901置換装置A1に入力して置換することによって秘匿変数K′i1を生成し、同時に変数Vi2と秘密鍵S2とをA−901置換装置A2に入力して置換することによって秘匿変数K′i2を生成し、その秘匿変数K′i1と秘匿変数K′i2とをA−902置換装置Bに入力することによって置換して暗号鍵Kiを生成し、その暗号鍵Kiと平文MiとをA−903置換装置Γに入力することによって置換して暗号文Eiを生成するよう処理され、A−901置換装置A1およびA−901置換装置A2を、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、A−902置換装置Bを、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も情報理論的に逆算不能とし、A−901置換装置A1およびA−901置換装置A2とA−902置換装置Bを用いるようにしたことに因って、但し、A−901置換装置A1およびA−901置換装置A2が置換装置(e)であればA−902置換装置Bは置換装置(c)、置換装置(d)、置換装置(f)、置換装置(g)のいずれかとし、A−902置換装置Bが置換装置(e)であればA−901置換装置A1およびA−901置換装置A2は置換装置(c)、置換装置(d)、置換装置(f)、置換装置(g)のいずれかとすることに因って、秘密鍵S1と秘密鍵S2とを完全秘匿化し、A−903置換装置Γを、置換装置(d)または(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにしたことを特徴とする請求項21または請求項22に記載の暗号処理の方法。

請求項25

暗号文について完全秘匿性を持たせると同時に、秘密鍵について暗号文と平文が漏洩することによって暗号鍵の情報が漏洩したとしても計算量的完全秘匿性を持たせる暗号処理の方法は、M−1110秘匿変数生成モデュールと、秘匿変数K′iと、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、M−1110秘匿変数生成モデュールは、秘密鍵S1と、A−901置換装置Aとから構成され、M−1120不可視化処理モデュールは、秘密鍵S2と、A−902置換装置Bと、から構成され、を生成し、その変数Viと秘密鍵S1とをA−901置換装置Aに入力して置換することによって秘匿変数K′iを生成し、その秘匿変数K′iと秘密鍵S2とをA−902置換装置Bに入力することによって暗号鍵Kiを生成し、その暗号鍵Kiと平文MiをA−903置換装置Γに入力することに因って暗号文Eiを生成するよう処理され、A−901置換装置Aを、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、A−902置換装置Bを、置換装置(c)または置換装置(f)から構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も計算量的に逆算不能とし、A−901置換装置AとA−902置換装置Bを用いるようにしたことに因って秘密鍵S1と秘密鍵S2とを計算量的完全秘匿化し、A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにしたことを特徴とする請求項21または請求項22に記載の暗号処理の方法。

請求項26

暗号文について完全秘匿性を持たせると同時に、秘密鍵について暗号文と平文が漏洩することによって暗号鍵の情報が漏洩したとしても計算量的完全秘匿性を持たせる暗号処理の方法は、A−301セパレータと、変数Vi1と、変数Vi2と、M−1110秘匿変数生成モデュールと、秘匿変数K′i1と、秘匿変数K′i2と、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、M−1110秘匿変数生成モデュールは、秘密鍵S1と、秘密鍵S2と、A−901置換装置A1と、A−901置換装置A2とから構成され、M−1120不可視化処理モデュールは、A−902置換装置Bから構成され、を生成し、その変数ViをA−301セパレータで分割して変数Vi1と変数Vi2とを生成し、その変数Vi1と秘密鍵S1とをA−901置換装置A1に入力して置換することによって秘匿変数K′i1を生成し、同時に変数Vi2と秘密鍵S2とをA−901置換装置A2に入力して置換することによって秘匿変数K′i2を生成し、その秘匿変数K′i1と秘匿変数K′i2とをA−902置換装置Bに入力することによって置換して暗号鍵Kiを生成し、その暗号鍵Kiと平文MiとをA−903置換装置Γに入力することによって置換して暗号文Eiを生成するよう処理され、A−901置換装置A1およびA−901置換装置A2を、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、A−902置換装置Bを、置換装置(c)から構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も計算量的に逆算不能とし、A−901置換装置A1およびA−901置換装置A2とA−902置換装置Bを用いるようにしたことに因って、秘密鍵S1と秘密鍵S2とを計算量的完全秘匿化し、A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにしたことを特徴とする請求項21または請求項22に記載の暗号処理の方法。

請求項27

暗号文について完全秘匿性を持たせると同時に、秘密鍵について暗号文と平文が漏洩することによって暗号鍵の情報が漏洩したとしても計算量的完全秘匿性を持たせる暗号処理の方法は、使い捨て公開変数riと、M−1110秘匿変数生成モデュールと、変数Riと、A化処理モデュールと、暗号鍵Ki、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、M−1110秘匿変数生成モデュールは、秘密鍵S1と、A−901置換装置Aとから構成され、M−1120不可視化処理モデュールは、秘密鍵S2と、A−902置換装置Bとから構成され、使い捨て公開変数riと秘密鍵S1とをA−901置換装置Aに入力して置換することによって変数Riを生成し、その変数RiからA−002擬似ランダムビット生成2置換装置Bに入力することによって暗号鍵Kiを生成し、その暗号鍵Kiと平文MiをA−903置換装置Γに入力することに因って暗号文Eiを生成するよう処理され、A−901置換装置Aを、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って使い捨て公開変数riからは秘匿変数K′iを推測不能とし、A−902置換装置Bを、置換装置(c)、置換装置(d)、置換装置(f)、置換装置(g)のいずれかから構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も計算量的に逆算不能とし、A−901置換装置AとA−902置換装置Bを用いるようにしたことに因って秘密鍵S1と秘密鍵S2とを計算量的完全秘匿化し、A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにしたことを特徴とする請求項21または請求項22に記載の暗号処理の方法。

請求項28

暗号文について完全秘匿性を持たせると同時に、秘密鍵について暗号文と平文が漏洩することによって暗号鍵の情報が漏洩したとしても計算量的完全秘匿性を持たせる暗号処理の方法は、A−301セパレータと、変数Vi1と、変数Vi2と、M−1110秘匿変数生成モデュールと、変数Riと、秘匿変数K′i1と、秘匿変数K′i2と、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、M−1110秘匿変数生成モデュールは、秘密鍵S1と、秘密鍵S2と、A−901置換装置A1と、A−901置換装置A2とから構成され、M−1120不可視化処理モデュールは、A−902置換装置Bとから構成され、使い捨て公開変数riからA−002擬似ランダムビット生成器によって変数Viを生成し、その変数ViをA−301セパレータで分割して変数Vi1と変数Vi2とを生成し、その変数Vi1と秘密鍵S1とをA−901置換装置A1に入力して置換することによって秘匿変数K′i1を生成し、同時に変数Vi2と秘密鍵S2とをA−901置換装置A2に入力して置換することによって変数Riを生成し、その変数RiからA−002擬似ランダムビット生成器によって秘匿変数K′i2を生成し、その秘匿変数K′i1と秘匿変数K′i2とをA−902置換装置Bに入力することによって置換して暗号鍵Kiを生成し、その暗号鍵Kiと平文MiとをA−903置換装置Γに入力することによって置換して暗号文Eiを生成するよう処理され、A−901置換装置A1およびA−901置換装置A2を、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、A−902置換装置Bを、置換装置(c)から構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も計算量的に逆算不能とし、A−901置換装置A1およびA−901置換装置A2とA−902置換装置Bを用いるようにしたことに因って、秘密鍵S1と秘密鍵S2を不確定性がH(S1)+H(S2)で計算量的完全秘匿化し、但し、このときつまり、秘密鍵S1の不確定性H(S1)は変数Vi1の不確定性H(Vi1)を下回らず、かつ秘匿変数K′i1の不確定性H(K′i1)および暗号鍵Kiの不確定性H(Ki)と等しく、且つ、秘密鍵S2の不確定性H(S2)は変数Vi2の不確定性H(Vi2)を下回らず、かつ変数Riの不確定性H(Ri)および秘匿変数K′i2の不確定性H(K′i2)と等しく、かつ暗号鍵Kiの不確定性H(Ki)を下回り、且つ、暗号鍵Kiの不確定性H(Ki)は平文Miの不確定性H(Mi)を下回らないものとし、A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにしたことを特徴とする請求項21または請求項22に記載の暗号処理の方法。

請求項29

シードであるベクトルaと生成するべき成分数|A|を入力値として受け取り、生成に伴って伸長されるベクトルの成分数を監視し、成分数の過不足を判定して不足であれば入力または生成されたベクトルをA−301セパレータに送るようA−203ベクトル配列生成部に指示し、十分であればA−203ベクトル配列生成部に通知してA−203ベクトル配列生成部において生成されたベクトルをA−203ベクトル配列生成部から受け取って外部に戻す働きをするA−201データ長管理部と、受け取ったベクトルを二つのベクトルに分割してA−202表演算部に送出するA−301セパレータと、A−301セパレータから受け取った二つのベクトルを2次元の表の第一列と第一行に配置し、生成値を含む行方向および列方向の複数の成分に和または積の演算を行うことによって演算表を生成するA−202表演算部と、A−202表演算部において生成された表の成分から列ベクトル毎にデータを抜き出し、新たなベクトルとして配列を生成し、データ長管理部からの指示に基づいて送出するA−203ベクトル配列生成部とから構成され、シードであるベクトルaと生成する擬似ランダムビットの成分数|A|をA−201データ長管理部に入力すると、A−201データ長管理部はベクトルaの成分数が|A|を下回れば、つまり、|a|<|A|ならばベクトルaをA−301セパレータに送り、A−301セパレータはベクトルaをベクトルV1とV2に分割(但し|a|=|V1|+|V2|。つまりV1の成分数とV2の成分数を足したものはaの成分数に等しい)してA−202表演算部に送り、(1)A−202表演算部はベクトルV1、V2をそれぞれ二次元の表の第一行と第一列に配置し、表の各成分に対して行方向の複数の成分と列方向の複数の成分を用い(但し、例えば第二行第二列成分ではV1の第一成分とV2の第二成分を用い、第二行第三列成分ではV1の第一成分と第二行第二列成分とV2の第二成分を用いるという風に、一つの成分しか用いることができない場合は一つの成分だけを用いる)自然数Nを法として和または素数pを法として積または積と和を行うことにより二次元の演算表を生成し、例えば、全ての演算を和とするならば、行方向に演算される成分数をψ、列方向に演算される成分数をξとする時、任意の成分をaijとすれば、つまり、aijで表わされる二次元の表の第i行第j列の成分は、自然数Nを法として、aijが属する列のaijの一つ上の行つまり第i−1(iから一を減じた値)行目から上に第ψ番目の行つまり第i−ψ(iからψ(二を下回らない自然数)を減じた値)行目までの全ての成分を足し合わせた値と、aijが属する行のaijの一つ左の列つまり第j−1(jから一を減じた値)列目から左に第ξ番目の列つまり第j−ξ(jからξ(二を下回らない自然数)を減じた値)列目までの全ての成分を足し合わせた値を足し合わせた値に合同その生成結果から第一列成分と第一行成分を除いた成分(生成結果を行列に見立について列ベクトル毎にまたは行ベクトル毎に成分を取り出したベクトル(Bj)j=1,2,...,n−1(但し、Bj=Aj+1)、つまり、任意の成分がBjで表わされるn−1(nから一を減じた値)個の成分からなるベクトルであって、第j番目の成分がベクトルAの第j+1(jに一を加えた値)番目の成分と等しいベクトルを生成してA−203ベクトル配列生成部に送り、(2)A−203ベクトル配列生成部は、その取り出された列ベクトル(Bj)j=1,2,...,n−1=(B1,B2,...,Bn−1)つまり、ベクトル(Bj)j=1,2,...,n−1はベクトルB1からベクトルBn−1までのn−1(nから一を減じた値)個のベクトルを成分とするベクトルの成分を展開してベクトルB=(b1,b2,...,b(m−1)(n−1)−1,b(m−1)(n−1))つまり、b1からb(m−1)(n−1)までの(m−1)(n−1)(mから一を減じた値とnから一を減じた値を掛け合わせた値)個の成分からなるベクトルBを生成し、(3)A−201データ長管理部はこの生成過程を常時チェックし、ベクトルBの成分数|B|が|A|を上回らないならばベクトルBをA−301セパレータに送って、(4)A−301セパレータはベクトルBをベクトルV1とV2に分割(但し|B|=|V1|+|V2|。つまりV1の成分数とV2の成分数を足したものはBの成分数に等しい)してA−202表演算部に送り、成分数|B|が|A|を下回らなくなるまで上記(1)から(4)までの過程を繰り返し、成分数|B|が|A|を下回らなくなったベクトルBを出力値であるベクトルAとして返すようにしたことを特徴とする請求項22から28までのいずれかに記載の暗号処理の方法。

請求項30

複数の入力値であるベクトルA,Bに対して出力値がベクトルCとするとき、A,Bを、二を下回らない自然数Nを法としてベクトル和するか、または三を下回らない素数pを法として内積するかまたはベクトル和および内積してベクトルCとして出力することによって、即ち、入力された二つのベクトルであるA−101A=(ai)i=1,2,...,n、つまり任意の成分がaiで表わされるn個の成分からなるベクトルAおよびA−101B=(bi)i=1,2,...,n、つまり任意の成分がbiで表わされるn個の成分からなるベクトルBに対し、それぞれの成分の内の同じ次元同士の値をは積と和の演算を行い、各成分を次元の順に並べてベクトルA−102C=(ci)i=1,2,...,nつまり任意の成分がciで表わされるn個の成分からなるベクトルCの出力を得、そのことによって、ベクトルAの不確定性H(A)とベクトルBの不確定性H(B)が異H(C)つまりH(B)はH(C)と等しく、且つ、H(B)とH(C)はH(A)を下回らず、即ちベクトルCの不確定性H(C)がベクトルBの不確定性H(B)と等しくなるように置換するようにしたことを特徴とする請求項22から請求項28までのいずれかに記載の暗号処理の方法。

請求項31

入力値であるベクトルA,Bに対して出力値がベクトルCとすると、ベクトルA,Bが共にp−1(pから一を減じた値)を法とするベクトルあるとき、p−1を法とするA−101A=(ai)i=1,2,...,nつまり任意の成分がaiで表わされるn個の成分からなるベクトルAおよびA−101B=(bi)i=1,2,...,nつまり任意の成分がbiで表わされるn個の成分からなるベクトルBの各成分にpを法として一を加えることで、pを法とするベクトルA−103A′=(a′i)i=1,2,...,nつまり任意の成分がa′iで表わされるn個の成分からなるベクトルA′およびA−103B′=(b′i)i=1,2,...,nつまり任意の成分がb′iで表わされるn個の成分からなるベクトルB′(但し、(a′i,b′i)≠(0,0)、つまりベクトルA′およびB′の成分には0は含まれていない)を生成し、ベクトルA−103A′=(a′i)i=1,2,...,nつまり任意の成分がα′iで表わされるn個の成分からなるベクトルA′およびA−103B′=(b′i)i=1,2,...,nつまり任意の成分がb′iで表わされるn個の成分からなるベクトルB′のそれぞれの成分の内の同じ次元同士の値をpを法として積で演算し、演算結果として出力されたベクトルA−103C′=(c′i)i=1,2,...,nつまり任意の成分がc′iで表わされるn個の成分からなるベクトルC′の各成分の値からpを法として一を引いた値を生成することで実質的に法をp−1(pから一を減じた値)とし、法をp−1(pから一を減じた値)とするベクトルA−102C=(ci)i=1,2,...,nつまり任意の成分がciで表わされるn個の成分からなるベクトルCを得るようにしたことを特徴とする請求項22から請求項28、請求項30のいずれかに記載の暗号処理の方法。

請求項32

暗号化が計算量的完全秘匿性を持つための必要条件を満たすA−00一または複数のベクトルと、出力するベクトルの成分数|A|を入力し、入力されるベクトルが複数の場合はA−401連結装置でそれら複数のベクトルを連結して一つのベクトルとし(入力値が二つのベクトルa、bであればそのa、bを連結した一つのベクトル(a‖b)を生成し)、−201データ長管理部で算定し、その連結された一つのベクトル前記(a‖b)をシードとしてA−002擬似ランダその行列A′をA−601一方向置換器(イ)またはA−603折畳置換器からなるA−501置換器に入力して非線型な置換をして成分数|A|を有するベクトルAを得るようにしたことを特徴とする請求項22から請求項28までのいずれかに記載の暗号処理の方法。

請求項33

暗号化が計算量的完全秘匿性を持つための必要条件を満たすA−00(一)一または複数のベクトルと、出力するベクトルの成分数|A|を入力し、(二)入力されるベクトルが複数の場合はA−401連結装置でそれら複数のベクトルを連結して一つのベクトルとし(入力値が二つのベクトルa、bであればそのa、bを連結した一つのベクトル(a‖b)を生成し)、(三)その複数のベクトルが連結された一つのベクトル(前記(a‖b))をシードット生成し、(四)その擬似ランダムビットをA−601一方向置換器(イ)からなるA−501置換器で非線型な置換をして行列A′を生成し、判定し、(ろ)|A|>|A′|であればその行列A′を再びA−002擬似ランダムビット生ことによってベクトルAを得るようにしたことを特徴とする請求項22から請求項28までのいずれかに記載の暗号処理の方法。

請求項34

暗号化が完全秘匿性を持つための必要条件を満たすA−002擬似ラ一または複数のベクトルと、出力するベクトルの成分数|A|を入力し、入力されるベクトルが複数の場合はA−401連結装置でそれら複数のベクトルを連結して一つのベクトルとし(入力値が二つのベクトルa、bであればそのa、bを連結した一つのベクトル(a‖b)を生成し)、−201データ長管理部で算定し、その連結された一つのベクトル前記(a‖b)をシードとしてA−002擬似ランダその行列A′をA−602一方向置換器(ロ)またはA−603折畳置換器またはA−604折畳+抜取置換器からなるA−501置換器に入力して非線型な置換をして成分数|A|を有するベクトルAを得るようにしたことを特徴とする請求項22から請求項28までのいずれかに記載の暗号処理の方法。

請求項35

暗号化が完全秘匿性を持つための必要条件を満たすA−002擬似ラ(一)一または複数のベクトルと、出力するベクトルの成分数|A|を入力し、(二)入力されるベクトルが複数の場合はA−401連結装置でそれら複数のベクトルを連結して一つのベクトルとし(入力値が二つのベクトルa、bであればそのa、bを連結した一つのベクトル(a‖b)を生成し)、(三)その複数のベクトルが連結された一つのベクトル(前記(a‖b))をシードット生成し、(四)その擬似ランダムビットをA−602一方向置換器(ロ)またはA−603折畳置換器またはA−604折畳+抜取置換器からなるA−502置換器で非線型な置換して行列A′を生成し、判定し、Aとして出力し、(ろ)|A|>|A′|であればその行列A′を再びA−002擬似ランダムビット生ことによってベクトルAを得るようにしたことを特徴とする請求項22から請求項28までのいずれかに記載の暗号処理の方法。

請求項36

擬似ランダムビット生成器を用いる置換装置であって、入力値が複数で且つ出力値の成分数が入力値の成分数を下回らない置換装置がA−003擬似ランダムビット生成器型置換装置(イ)であり、入力値が複数で且つ出力値の成分数が入力値の成分数と等しい置換装置が、A−004擬似ランダムビット生成器型置換装置(ロ)であり、入力値が一つで且つ出力値の成分数が入力値の成分数を下回らない置換装置はA−005擬似ランダムビット生成器型置換装置(ハ)であることを特徴とする請求項22から請求項28までのいずれかに記載の暗号処理の方法。

請求項37

弱い非線型性を持つ線型の擬似ランダムビット生成器であるA−00抜き取りによって非線型化させる置換器は、る表(行列)をAとするとき、A−302一方向化エクストラクタ単体から構成され、入力値Aに対し、その成分数が入力値Aの成分数|A|を下回らず且つ非線型化され情報理論的にA−601一方向置換器(イ)と、A−302一方向化エクストラクタとA−303ベーシックエクストラクタから構成され、A−302一方向化エクストラクタ単体から構成され、入力値Aに対し、A−302一方向化エクストラクタがその成分数が入力値Aの成分数|A|を下回らず且つ非線型化され情報理論的に逆算不能な余因子行列をベクトルAとして出力するA−602一方向置換器(ロ)であるようにしたことを特徴とする請求項22から請求項28までのいずれかに記載の暗号処理の方法。

請求項38

弱い非線型性を持つ線型の擬似ランダムビット生成器であるA−00みによって非線型化させる置換器は、の擬似ランダムビットA′を生成し、それをA−301セパレータでn個に分割しまたは、擬似ランダムビットA′を生成し、それをA−301セパレータで二つ以上に分割とによって生成した値またはベクトルから、更に成分数を前記A−002擬似ラクストラクタで任意の成分を抜き取り成分数を調整するようにしたことを特徴とする請求項22から請求項28までのいずれかに記載の暗号処理の方法。

請求項39

A−301セパレータとA−001aベクトル和型置換装置によって構成される置換器は、る表(行列)をAとし、その行列Aから生成されたベクトルをA′とするとき、A−301セパレータとA−001aベクトル和型置換装置によって構成され、A′が入力されるとA−301セパレータはA′を等分な二つのベクトルにのベクトルをベクトル和または内積することによって置換してベクトルAを生成し出力するA−603置換器と、A−301セパレータとA−001aベクトル和型置換装置とA−303ベーシックエクストラクタによって構成され、A′が入力されるとA−301セすることによって置換してベクトルA″を生成し、A−303ベーシックエクストラクタがそのA″から任意の成分を|A″|−|A′|つまりベクトルA″の成分数|A″|からA′の成分数|A′|を引いた成分数だけ抜き取ることによって成分数|A′|のベクトルA(3)を生成し、そのA(3)をベクトルAとして出力するA−604折畳+抜取置換器であるようにしたことを特徴とする請求項22から請求項28までのいずれかに記載の暗号処理の方法。

請求項40

A−302一方向化エクストラクタは、のij成分であるaijの演算対象となる成分が、第i−1行目の成分であるai−1,jから列方向に第i−ψ行目の成分であるai−ψ,jまでのψ個と、第j−1列目の成分であるai,j−1から行方向に第j−ξ列目の成分であるai,j−ξまでのξ個とすれば、その第一行と第二行および第2+ψm行(但しm=1,2,...)及び第一列と第二列および第2+ξn列(但し、n=1,2,...)を除いた前記行列の余因子行列を生成し、その余因子行列の各列ベクトルまたは行ベクトルを並べて一つのベクトルとして生成し出力するようにしたことを特徴とする請求項37に記載の暗号処理の方法。

技術分野

0001

以下に述べる暗号処理装置および方法は、
二を下回らない自然数を法とする剰余群および/または三を下回らない素数を法とする剰余群において、
使い捨ての変数で少なくとも二つの秘密鍵置換して暗号鍵を生成することによって、毎回新たな暗号鍵を使用して暗号化処理復号処理を行えるようにし、その暗号鍵の生成過程において生成される変数を、入力側からは推測不能とし、且つ出力側からは数学的かつ情報理論的逆算不能とすることによってその暗号化が完全秘匿であると同時に、複数の暗号文攻撃者の手に渡ったとしても、あるいは暗号文とその平文およびその使い捨て変数が攻撃者の手に渡ったとしても秘密鍵の秘匿の完全性に関し完全秘匿または計算量的完全秘匿であるようにし、それによって使い捨て変数が公開可能となることから、使い捨て変数を暗号文に添付して送受信および/または保管することによって、暗号鍵と秘密鍵と暗号文の関連付けを完全に秘匿した状態で管理できるようにした
暗号処理の装置および方法に関する技術である。

背景技術

0002

本発明は、共通鍵方式対称鍵とも呼ばれる)に分類される暗号方式である。
その中の所謂「ヴァーナム暗号」であって、それを現実的な系として機能するようにしたものである。

0003

Shannonの安全性に関する情報理論的モデル無条件安全性をもたらす。ヴァーナム暗号の完全秘匿性は計算上の問題の困難さや敵の計算能力限界に依存しない。完全秘匿性はほとんどの実用的な状況では到達可能ではないにもかかわらず、仮定に基づいていない。

0004

即ち、ヴァーナム暗号は理論的には解読不能と言われてきたが、これまで何十年にもわたって、その有効な実現方法が見つからなかった。
その主たる理由は、所謂「鍵の配送コスト問題」である。

0005

鍵の配送コスト問題とは、
ヴァーナム暗号では、平文を暗号化するのに、
(i)暗号化の都度新たな、つまりユニークな値を持ち、
且つ、
(ii)その平文と同じ長さを下回らない長さの真正ランダムビット、即ち少なくとも平文の不確定性を下回らない不確定性(情報理論的エントロピー)を持つビット列からなる暗号鍵
を必要とする。
これが暗号通信として成立するには、つまり、正しい受信者復号できるようにするには、暗号文とは別にその暗号鍵も安全に相手に送られなければならない。
ところが、暗号鍵を安全に送れるのであれば、当然のことながらそれと同じか短い長さの平文も、少なくとも同じ方法で安全に送れるはずである。
すると、ヴァーナム暗号は不要ということになり、その存在自体が矛盾することになる。

0006

そこで、従来技術では、
一つには、生成の都度、真正ランダムビットに近いビット列を作るために擬似ランダムビット生成器を用いたが、計算によって生成されるため、シードの持つ低い不確定性しか実現できず、計算量と計算能力次第で解読可能になり得るという問題があった。現代暗号ではこれを情報理論における完全秘匿の類似として計算量的完全(または暗号的安全)といい、そのような暗号鍵は計算量的完全秘匿性を持つという。
また一つには、公開鍵方式とか二重鍵方式とか非対称鍵方式と呼ばれる毎回暗号鍵を送信しなくても済む方式が考えられたが、結局一つの暗号鍵で複数の平文を暗号化することになるので、情報理論的には解読可能になってしまっているという問題があった。そこで、鍵生成を非線型化することによって計算量によって解読困難とすることになる。
Shannonが指摘した、情報理論でいうところのこのような問題のとらえ方は後述するように計算量的完全の問題から証明されている。
ところが、これは実際には間違い(理論は正しい)で、後述するように、たった二つの暗号文から非対称鍵方式も含め固定的な暗号鍵を用いる方式は極めて容易に解読可能である。
ただし、従来の対称鍵方式や公開鍵方式の優れた点は、公開鍵方式では鍵のサイズが、その計算量からどうしても小さくならざるを得なかったため、ブロック暗号と言われる小さなブロックごとに暗号化するようにしたことであった。小さな秘密鍵は、その暗号化しようとする平文自体を変数としてブロック毎に順次置換され、平文の不確定性を下回らない不確定性を持つ暗号鍵として処理される。
従ってこの暗号化は、もし秘密鍵が暗号化の都度ユニークであるならば完全秘匿が成立することになる。

0007

そこで従来技術では、次に、使い捨て公開鍵暗号という方式が考えられた。
この技術は、ヴァーナム暗号が不完全ながら実現したものである。即ち、生成の都度ユニークな値をとる小さな秘密鍵を生成し、その秘密鍵を使ってブロック方式で暗号/復号処理する。
しかしながら、それでも暗号通信に際しては秘密鍵の送受信が必要で、その送受信される秘密鍵の秘匿ために公開鍵(非対称鍵)暗号が用いられるというところに重大な問題が残った。
もっとも、この使い捨て公開鍵方式では通信時を除けば、つまり暗号文を保管する状態では計算量によらない安全、即ち完全秘匿が成立する。つまり、暗号文あるいは暗号化としては完全秘匿性を持たせるようにすることが可能である。

0008

ところが、そこでまた問題が発生する。つまり、暗号文の保管時においては、暗号文と一対一でそれと対応するそれぞれの秘密鍵つまり暗号鍵も関連付けて管理されなければならない。つまり、どのような形にせよそのような関連付けがなければ、暗号文の所有者自身でさえ復号できないことになるわけである。

0009

そこで、通常はデータベース等で管理することになるのであるが、その際のセキュリティが問題となる。データベースには基本的にはパスワード認証程度しかガードがなく、しかもデータベース管理者からはパスワードは無関係に丸見えである。たとえ暗号化されていたとしても、その暗号鍵を管理しているのがデータベース管理者であればやはり解読可能であることは同じである。
すると、暗号システム以外のところから、そもそもその暗号化が目的としていた情報秘匿崩壊してしまう。つまり、折角のヴァーナム暗号の完全秘匿性がヴァーナム暗号以外のところで崩れ去ってしまうという問題があった。

0010

この問題に対する一つの対策として秘密分散と呼ばれる方式で秘密鍵(暗号鍵)を保管する方式が考えられた。これは登録された秘密鍵情報を完全秘匿の成立する形で秘匿する(つまりシステム管理者でも登録されている情報の内容を知ることはできない)ものの、その管理、つまり暗号文とその秘密鍵の関連付けまで考えると安全のレベルはそこに用いられる認証システム次第であり、何ら根本的な解決には至っていないという問題があった。

発明が解決しようとする課題

0011

(通信時における完全秘匿)従来方式では、いずれの暗号化法でも少なくとも通信時における暗号文の秘匿に関し、計算量的完全秘匿性しか実現しえていない。しかも今日、NIST(アメリカ合衆国国立標準技術研究所National Institute of Standardsand Technology)の勧告によって、これまで等価安全性で80ビットを下回らない不確定性が必要とされていた暗号化の強度が、2010年以降は113ビットを下回らない不確定性が必要とされ、暗号の2010年問題として社会問題化しつつある。
従って、保管時における完全秘匿性は当然のことながら、通信時における完全秘匿性の確保は喫緊の課題である。

0012

そうした状況下において、暗号方式が完全秘匿であるヴァーナム暗号の実用化即ち情報理論の確立は必須の課題であると考えられる。

0013

また、暗号文の保管時における秘密鍵との関連付けにおいて情報漏洩の危険が発生している点についても、暗号システム全体の根幹を揺るがす問題であり、喫緊の解決が求められている。

0014

鍵管理容易性だけでなく、秘密情報のやり取りの方法や暗号処理/復号処理における操作の容易性などについて、一般ユーザが使用することを前提とした場合、従来方式ではその操作性に問題を持つものが多く見られ、そのことは情報漏洩や鍵の紛失事故を誘発する問題であり、システムの基本においてカヴァーされるべき課題である。

0015

所謂ヴァーナム暗号の考え方によって、単純な完全秘匿を、変数を用いて作ることは至って簡単である。しかしながら複数の暗号文が存在する場合や暗号文とその平文が同時に攻撃者の手に渡った場合における秘密鍵の完全秘匿に関しては別の技術が必要になる。
攻撃の内、
●一つの暗号文だけで解読される場合というのは、暗号文を直接的に暗号化する暗号鍵の不確定性に問題がある場合である。即ち計算量的に解読可能な状態である。暗号鍵の不確定性が平文の不確定性を下回らなければ情報理論に言う所謂完全秘匿が成立する。
●複数の暗号文から秘密鍵が解読される状態というのは、秘密鍵の取り扱い方、あるいは暗号化における最終的な暗号文生成処理の手法に問題がある場合である。単純な線型のベクトル和(法が二の場合は特にXORあるいは排他的論理和と呼ばれる)では、二つの暗号文から容易に解読される。
●暗号化に伴う入力値の内の変数と、最終的な暗号化に用いる暗号鍵とがわかれば解読される状態というのは、秘密鍵の秘匿に問題がある状態であり、それは一つには暗号鍵を生成する変数の不確定性の問題であり、一つには入力値である変数から不確定性を拡張する件に関する問題及び推測不能性に関する問題である。
●変数の不確定性拡張に関する問題には、置換の問題と、擬似ランダムビット生成における一様性非周期性初期値鋭敏性確保の問題が含まれる。
●推測不能性に関する問題には置換の問題が含まれる。
以上の問題が解決されることによって、生成の都度ユニークな値をとる小さなシードを公開鍵として用いて暗号化を完全秘匿とし、且つ、秘密鍵の秘匿の完全性に関しても完全秘匿若しくは従来技術とは比較にならないほど巨大な計算量的完全秘匿性を得ることが可能となる。
ここで、秘密鍵の秘匿に関し、本来完全秘匿が成立すれば不要であるはずなのに、計算量的安全までも含める件については、秘密鍵の秘匿に関する使い勝手の問題からセキュリティの面で現実的にはあったほうが良いと考えられるので、敢えてここに含めるものである。

発明を解決するための手段

0016

本発明は、図1を用いて説明すると、
暗号処理の装置および方法に関する系の全体は、
変数ViとM−1000暗号化モデュール
平文Miと
暗号文Eiと
M−2000公開変数添付モデュールと
送信文Tiと
から構成され、
M−1000暗号化モデュールは、
M−1100暗号鍵生成モデュールと
暗号鍵Kiと
M−1200暗号文生成モデュールと
から構成され、
M−1100暗号鍵生成モデュールは
M−1110秘匿変数生成モデュールと

M−1120不可視化処理モデュールと
から構成され、

成し、その暗号鍵KiをM−1200暗号文生成モデュールに入力して暗号文Eiを生成し、その暗号文EiをM−2000公開変数添付モデュールに入力して送信文Tiを得るようにし、
M−1110秘匿変数生成モデュールにおいて秘匿変数を推測不能とし、
且つ
M−1110秘匿変数生成モデュールを広い意味での非線型化をすることによってM−1110秘匿変数生成モデュールに含まれる秘密鍵を秘匿するか
若しくは
M−1120不可視化処理モデュールを広い意味での非線型処理とすることによ

そのことによって、暗号化を完全秘匿とすると同時に、変数Viと暗号文Eiとその平文Miを攻撃者が入手したとしても秘密鍵について完全秘匿性または計算量的完全秘匿性を持つようにした暗号処理の装置および方法である。

0017

図2はヴァーナム暗号の基本的な構造を示す図であり、完全秘匿が成立する暗号化の基本形であるとともに、その暗号化における暗号鍵生成の基本形である。

和)
または

但し、積の場合は入力値は0を含まない。内積の場合は、入力値であるベクトルの成分に0を含まない
演算を行うことによって置換してKiを生成する。
図の中でSiが第i回目の暗号化に用いる暗号鍵でViが第i回日の暗号化における平文であれば、Kiは第i回目の暗号化における暗号文ということになり、
回異なる暗号鍵で平文を暗号化するわけであるから、情報理論によればこの暗号

回異なる暗号鍵で平文を暗号化するわけであるから、情報理論によればこの暗号化は完全秘匿である。
但し、出力値である暗号文が公開されており、且つ入力値である暗号鍵と平文の内のいずれか一つの値が秘匿されていないときには、残りの一つの値は引くか割るかするだけで容易に解読される。従って、この暗号化は、平文と暗号文が共に秘匿される限りにおいて暗号鍵は完全秘匿性を持つ。
図1のM−1100暗号鍵生成モデュールにおいても暗号鍵をこの方法で生成すれば、暗号化の都度、毎回異なる暗号鍵を生成することができる。そこで、Viを第i回目の暗号化における変数、M−1110秘匿変数生成モデュールに含まれ

おける暗号鍵とする。すると、暗号鍵Kiと変数Viが秘匿される限りにおいて変数

暗号鍵Kiについて推測すら成立しないので平文を解読することはできず、やはり暗号化に関し完全秘匿が成立する。
ところが、暗号文とともにその平文が攻撃者の手に渡ると、暗号鍵Kiは容易に解読される。更に、変数Viは公開されているわけであるから、M−1110秘匿変数生成モデュールおよびM−1120不可視化処理モデュールが単なるXORや

読されれば、変数鍵Siが秘密鍵Sを変数υiで置換して生成されたものであるとすれば、その秘密鍵Sも容易に解読されてしまう。これを図5に示す

0018

図5の説明の前に、暗号鍵の不確定性に関わるランダムビットの不確定性の問題について一言触れておく。
ここで秘密鍵Sはその不確定性H(S)が、法を二を下回らない自然数N(2

H(S)=log2N|S|
つまり秘密鍵Sの不確定性H(S)は二を底とするNの[秘密鍵Sの成分数|S|]乗の対数(場合の数(確率の逆数)N|S|のビット表記
でなければならないから、本来真正ランダムであることが求められる。しかしながら、情報理論的には暗号鍵の不確定性はその暗号化しようとする平文の不確定性を下回らなければ良いわけであるから、任意の平文または任意の平文を任意の変数で置換した値を秘密鍵あるいは暗号鍵として用いても良いことになる。つまり、物理学的な意味での真正ランダムまでは要求されない。
更に言えば、後述するように、任意の値(擬似ランダムビットでもよい)で置換された平文は文字からなる平文であったとしても、文字そのものの不確定性ではなく、つまり文字コードの数によって生ずる不確定性ではなく、その文字コードの定義によって定められた不確定性、例えばその文字コードが二百五十六ビットであれば一つの文字について二百五十六ビットの不確定性(つまり、二の二百五十六乗通りの可能性、ヴァリエーション)を持つ。従って真正ランダム同等となる。
ヘッダー部やフッター部には定型句が多いことから解読の可能性が生ずる危険があるとか、データフォーマットから類推可能になるという可能性に関しては、一つには本来何を秘密鍵とするかについて秘匿するから秘密鍵なのであり、また、どのような種類のデータを秘密鍵として用いているか分かったとしても、秘密鍵を都度異なる任意の値で置換して暗号鍵として用いることから、任意の平文を秘密鍵として用いたとしても、そのことによって部分的にせよ解読される可能性は全く存在しえない。

0019

図3は、図2におけるような単純な和または積ではなく、A−003擬似ランダムビット生成器型置換装置(イ)を用いて、二つ以上の入力値を絡めることによって同様の効果を実現しようとするものである。二つ以上のシードからそれらを伸長したベクトルを生成するわけであるから、暗号鍵Kiを生成するには、データ長(成分数)を調整しなければならない。但し、この擬似ランダムビット生成が線型であれば二つの入力値を秘匿したとしても成分調整の方法によっては部分的に逆算される可能性がある。擬似ランダムビット生成が非線型であれば完全非可逆が成立する。
二つ以上のシードによる擬似ランダムビット生成は、そのような専用の擬似ランダムビット生成器を用いてもよいし、また従来方式の一つのシードから生成する擬似ランダムビット生成器の場合は、それら複数のベクトルをつなげて一つのシードとするようにしても良い。つまり、それら入力値である複数のベクトルをa1,a2,...,anとするとき、このベクトルからなるベクトルを生成してA=(a1,a2,...,an)(ベクトルAはa1からanまでのn個のベクトルを成分とするベクトル)とし、このベクトルAを新たなシードとする。
情報理論ではAが行列ではないことを明示するためと思われるが、A=(a1‖a2‖・・・‖an)(ベクトルAはa1からanまでのn個のベクトルを連結したベクトル)のように記述することもある。
但し、入力値の成分数と出力値の成分数を等しくする際に、成分の抜き取りが行われるわけであるが、単純な抜き取りの場合には出力値の不確定性が入力値の不確定性の最大値を下回り得るという問題がある。

0020

図4は、図3の擬似ランダムビット生成器が完全非可逆な擬似ランダムビット生成器であるA−004擬似ランダムビット生成器型置換装置(ロ)による場合を示したもので、擬似ランダムビット生成が線型である場合においても完全一方向(非可逆)となるよう処理を施したものである。
擬似ランダムビット生成器を使った非可逆化(一方向化)には三通りやり方がある。
一つは、生成の過程の中に積の演算が含まれる場合である。未知数の積は非線型となることから処理は非線型化され一方向化(非可逆化)される。
また、一つは全ての生成処理が和によって行われる場合、つまり線型の場合であ

ベクトルをn個に分割してその内の少なくとも二つをベクトル和するものである。この処理は「折りたたむ」という表現で表わされることもある。図の変数鍵Siの不確定性H(Si)が平文の不確定性を下回らないとするとき、変数Viの不確定性

H(Vi)を下回らないのであれば、暗号鍵Kiの不確定性H(Ki)はH(Ki)=H(Si)つまり、暗号鍵Kiの不確定性H(Ki)は変数鍵Siの不確定性H(Si)に等しい。そこで、変数Viと変数鍵Siをn倍に伸長したベクトルをn個に分割してその内の少なくとも二つをベクトル和すると、その不確定性はやはりH(Si)に等しい。従って、この擬

とするとき、変数鍵Siの各成分の値に対し、変数Viと変数鍵Siをn倍に伸長したベクトルをn個に分割してその内の少なくとも二つをベクトル和して生成されたベクトルの各成分の値に対する変数Viと変数鍵Siの各成分の値の組み合わせはN通り存在することになり、従って、生成値からシードを求めることは情報理論的に不可能である。
いま一つは、やはり全ての生成処理が和によって行われる場合であって、擬似ランダムビット生成された値から、少なくとも逆算の要となる値を抜き取ることで情報量的、情報理論的に不確定性を確保して完全非可逆化するものである。
これら3通りのやり方は全て、広い意味での非線型性を持つと言える。また、入力値の不確定性の最大値と出力値の不確定性は等しい。従って、完全秘匿が成立する方式には図3のA−003擬似ランダムビット生成器型置換装置(イ)ではなく、このA−004擬似ランダムビット生成器型置換装置(ロ)が用いられることになる。
完全非可逆化に関し、詳しくは後述する。また、演算における不確定性の転移や拡張についても詳しくは後述する。

0021

号鍵Kiと平文Miと暗号文Eiから構成され、
変数鍵Siが秘密鍵Sを変数υiで置換して生成され、その変数鍵Siを変数Viで置換して暗号鍵Kiを生成し、その暗号鍵Kiで平文Miを置換することによって暗号化し、暗号文Eiを生成している。ここで、

れば、変数鍵Siの不確定性H(Si)はH(Si)=H(S)、つまり、変数鍵Siの不確定性H(Si)は秘密鍵Sの不確定性H(S)に等しく、変数υiが秘匿されていなくても秘密鍵Sが秘匿される限りにおいて推測不能であり、
暗号鍵Kiの不確定性H(Ki)はH(Ki)=H(Si)、つまり、暗号鍵Kiの不確定性H(Ki)は変数鍵Siの不確定性H(Si)に等しく、変数Viが秘匿されていなくても変数鍵Siが秘匿される限りおいて推測不能であり、

確定性H(Ei)は暗号鍵Kiの不確定性と等しく且つ暗号文Eiの不確定性H(Ei)は秘密鍵Sの不確定性と等しく且つ暗号文Eiの不確定性H(Ei)は平文Miの不確定性を下回らないことから、
この暗号化は完全秘匿である。
ところが、暗号文Eiとともにその平文Miが攻撃者の手に渡ると
EiとMiからKiが求まり、
KiとViからSiが求まり、
Siとυiから秘密鍵Sが求まり、
その結果、それ以降の暗号化は全て攻撃者によって解読されてしまうことになる。
暗号システムの通常使用において、暗号文とその平文が同時に存在することはままある。従って、暗号文とともにその平文が漏洩しても逆算できないシステムが必須である。
そこでそのような事態を防ぐには、
変数Viを秘匿する機構を備えるか、
または
暗号鍵Kiを暗号文とその平文からは解読できない機構を備える必要がある。
ところが後者に関し、暗号文の生成は復号されることが前提であるから情報量を操作して不確定性を確保するような形での完全非可逆(完全一方向関数)とすることはできない。また、もし単なる非可逆(一方向関数)であれば計算量的に解読可能となる。従ってこの部分は情報量によらない情報理論的な解読不能性をもつものとなり、即ち、和または積による置換処理となる。従って、暗号部と同時に攻撃者によって入手されれば、暗号鍵Kiは解読されることが前提となる。そこで、
暗号鍵Kiが解読されても、変数鍵Siを解読されないような秘匿機構を備える必要がある
ということになる。

0022

図6は変数Viを秘匿する機構としてM−1110秘匿変数生成モデュールを備えた暗号鍵生成モデュールを表す。
全体は、
入力値である使い捨て公開変数riと
M−1100暗号鍵生成モデュールと
暗号鍵Ki
から構成され、
M−1100暗号鍵生成モデュールは、
M−1110秘匿変数生成モデュールと
変数Viと
変数鍵Siと

から構成され、
使い捨て変数riを秘匿変数生成モデュールに入力し、変数Viを生成し、その変数

このモデュールに要求される性能は、入力値であるriが漏洩しても変数Viが推測不能であり、その不確定性が変数鍵Siの不確定性を下回らないことである。
そのような構造が成立すれば、変数Viと変数鍵Siは秘匿されるので暗号鍵Kiは完全秘匿性を持つ。また、暗号鍵Kiが漏洩したとしても変数鍵Siが解読されることはなく、従って変数鍵Siの元となる秘密鍵Sも完全秘匿性を持つ。

0023

図7は暗号鍵Kiの生成を非可逆処理する機構としてM−1130非可逆化処理モデュールを備えた暗号鍵生成モデュールである。
全体は、
入力値である変数Viと
M−1100暗号鍵生成モデュールと
M−1130非可逆処理モデュールと
暗号鍵Kiと
から構成され、
M−1100暗号鍵生成モデュールは、

から構成され、

た値をM−1130非可逆処理モデュールで処理して暗号鍵Kiを生成する。
暗号鍵Kiと変数Viが攻撃者によって入手されたとしても、暗号鍵Kiから情報理論的に非可逆であれば、変数鍵Siは計算量的完全秘匿性を持ち、従って変数鍵Siの元となる秘密鍵Sも計算量的に完全秘匿される。

Nの|S|乗に等しい。ここで|Si|は変数鍵Siの成分数であり、|S|は秘密鍵Sの成分数)通りの暗号鍵Kiの候補を生成し、その一つ一つを入手した暗号鍵Kiと比較して変数Viと変数鍵Siを置換して生成した値を決定することができる。即ち、この時、変数鍵Siは計算量的な完全秘匿性を持ち、従って変数鍵Siの元となる秘密鍵Sも計算量的な完全秘匿性を持つ。

0024

図8は、図6に示した構造をM−1000暗号化モデュールに関しより具体的に記述した図である。
全体は、
入力値であり平文Miの不確定性を下回る不確定性を有する使い捨て公開変数riと
M−1000暗号化モデュールと
平文Miと
出力値である暗号文Ei
から構成され、
M−1000暗号化モデュールは、

とによって生成された変数Riと
M−1100暗号鍵生成モデュールと
暗号鍵Kiと
M−1200暗号文生成モデュール
から構成され、
M−1100暗号鍵生成モデュールは、
M−1110秘匿変数生成モデュールと
変数Viと

から構成され、
M−1200暗号文生成モデュールは、

から構成され、
M−1110秘匿変数生成モデュールは、

から構成され、

置換して暗号鍵Kiを生成し、その暗号鍵Kiと平文MiをM−1200暗号文生成

ここで、使い捨て公開変数riは擬似ランダムビットのシードであるから、
H(ri)=H(Ri)<H(S1)、
即ち、使い捨て公開変数riの不確定性H(ri)は変数Riの不確定性H(Ri)と等し

も短い、別の言い方をすれば、使い捨て公開変数riの成分数|ri|は変数鍵


つまり、平文Miの不確定性を下回らない不確定性を有する変数Viを生成する値であるから、

成分数を持ち、

暗号文Eiがわかったとしても、暗号鍵Kiと平文Miは変数であるから、この暗号化は完全秘匿である。また、使い捨て公開変数riと暗号文Eiがわかったとしても

持ち解読されることはない。
ところが、暗号文Eiと共にその平文Miが漏洩すると容易に暗号鍵Kiが求まるので、秘密鍵を秘匿するには少なくともM−1100暗号鍵生成モデュールの出力

何故なら、

つまり、二を下回らない自然数Nを法とする世界で、生成の都度ユニ

したベクトルに合同なベクトルであると定義する
とするとき、

ベクトルに法Nで合同なベクトルであり、それは変数Riとベクトル

う一つの固定値からなるベクトルのベクトル和の形に書き表せる
であり、
ここでM−1100暗号鍵生成モデュールの出力側のA−001置換装置

クトルに法Nで合同なベクトルであり、

秘密鍵S1をベクトル和したベクトルに法Nで合同なベクト

ル和したベクトルに法Nで合同なベクトルであると定義されたベクトルであるから、

ある一つのベクトルと、秘密鍵S1という一つの固定値からなる

トルに合同なベクトルという形に書き表すことができ、従って

したベクトルと、秘密鍵S1と秘密鍵S2をベクトル和したベクトルをベクトル和したベクトルに合同なベクトルという形に書き表され、

ル和したベクトルに法Nで合同であると定義し、ベクトルS3は秘密鍵S1と秘密鍵S2をベクトル和したベクトルに法Nで合同であると定義する
とおくと、

クトルと書き表すことができる
となる。

回らなければ、置換がこの一回限りにおいて、暗号鍵Kiの秘匿に関し完全

を下回り、且つ、その不確定性が計算量的に解読困難なレベルであれば暗号鍵Kiは計算量的完全秘匿性を持つ。
ところが、一つの変数と一つの固定値の和で表せることから、たった二つの暗号鍵Kiが攻撃者によって入手されるだけで、たったN通りでS3は解読され得、
何故なら、上記(1)式において

したベクトル

したベクトル

つまり、従って、暗号鍵K1と暗号鍵K2を法二でベクトル和

クトルと合同

つまり、暗号鍵K1と暗号鍵K2のマイナス一倍を法Nでベク

Nでベクトル和したベクトルと合同
(2)式と(3)式を足すと

したベクトルと合同

実質的に一つの暗号鍵と同じことであるから、秘密鍵S1と秘密鍵S2の値がわからなくても、それ以降暗号文は容易に解読されることになる。

ける演算が積であれば、

して内積したベクトルと合同であり、

密鍵S1をベクトル和したベクトルに合同なベクトルであり、

トルに合同なベクトルであると定義されたベクトルであるから、

一つのベクトルと秘密鍵S1という一つの固定値からなるベクトル

トル和したベクトルを内積したベクトルに法pで合同なベクトルという形に書き表すことができ、従って、

したベクトルと、秘密鍵S1と秘密鍵S2を内積したベクトルをベクトル和したベクトルに法pで合同なベクトルという形に書き表すことができる
となって、二つの未知数(秘密鍵S1と秘密鍵S2)の積が現れることから処理は非線型となり、

鍵Kiから逆算によって秘密鍵を求めることはできない。

基づく計算量で解読可能つまり計算量的完全秘匿となる。■

ることはできず、従って、使い捨て公開変数riは暗号文Eiよりもはるかに小さくすることができるので、ヴァーナム暗号における鍵の配送コスト問題が解消されることになる。
尚、ここで、M−1100暗号鍵生成モデュールの出力側のA−001置換装置

S1、秘密鍵S2としても良い。
また、使い捨て公開変数riは、秘密鍵で置換して用いられることから、秘密鍵が秘匿される限りにおいて、使い捨て公開変数riが秘匿されなくても暗号化の秘匿性に影響を与えない。従って、使い捨て公開変数riは生成の都度ユニークでありさえすれば良いので、例えばミリ秒単位の時刻データを用いるなどしても良い。

0025

図9は、図7に示した構造をM−1000暗号化モデュールに関しより具体的に記述した図である。
全体は、入力値である変数ViとM−1000暗号化モデュールと平文Miと出力値である暗号文Eiから構成され、
M−1000暗号化モデュールは、

モデュールと暗号鍵KiとM−1200暗号文生成モデュールから構成され、
M−1100暗号鍵生成モデュールは

M−1130非可逆処理モデュールは

M−1200暗号文生成モデュールは

成し、その暗号鍵Kiと平文MiをM−1200暗号文生成モデュールの中のA−

開変数riから変数Riを生成する工程を除けばモデュール分けを無視した場合、図8と全く同じ形をしている。

0026

そこで図8図9をまとめてM−1000暗号文生成モデュールを図10で表わすと、
全体は、入力値である使い捨て公開変数riとM−1000暗号化モデュールと平文Miと出力値である暗号文Eiから構成され、
M−1000暗号化モデュールは、
M−1100暗号鍵生成モデュールと暗号鍵KiとM−1200暗号文生成モデュールから構成され、
M−1100暗号鍵生成モデュールは、

され、
M−1200暗号文生成モデュールは、

M−1110秘匿変数生成モデュールは、

似ランダムビット置換装置から構成され、
M−1120不可視化処理モデュールは、

換した値をA−005擬似ランダムビット生成器型置換装置(ハ)で置換して秘


この装置及び方法は完全秘匿が成立すると同時に、秘密鍵の秘匿に関しても完全秘匿性を持つ。M−1120不可視化処理モデュールの置換装置は図8図9

しても良い。
ここで、M−1120不可視化処理モデュールの置換装置がA−001aベクト

つまり、完全秘匿および秘密鍵の秘匿という点からすれば、このような構造では完全秘匿は成立しているものの、基本的に、M−1110秘匿変数生成モデュールは入力値の一つである変数は公開された値が元になっていることから攻撃者に

洩してしまう。つまり、M−1110秘匿変数生成モデュールは線型でも非線型でも良く、且つ、M−1120不可視化処理モデュールが広い意味での非線型で

尚、ここでA−005擬似ランダムビット生成器型置換装置(ハ)は図3のA−004擬似ランダムビット生成器型置換装置(ロ)における入力値を一つとした擬似ランダムビット生成器である。

0027

図10の検討結果から、M−1120不可視化処理モデュールの置換装置が

することができることが分かった。
その全体は、使い捨て公開変数riから擬似ランダムビット生成する過程をまとめて変数Viに置き換えて省略して表すと、図11に示すように、
変数ViとM−1100暗号鍵生成モデュールと暗号鍵Kiから構成され、
M−1100暗号鍵生成モデュールは、

処理モデュールから構成され、
M−1110秘匿変数生成モデュールは

Miの不確定性を下回らない不確定性を有する秘密鍵S1とA−001aベクト

M−1120不可視化処理モデュールは、

Miの不確定性を下回らない不確定性を有する秘密鍵S2とA−001b内積型

M−1110秘匿変数生成モデュールの置換装置がA−001aベクトル和型置

密鍵S1をベクトル和したベクトル]と[秘密鍵S2]を内積したベクトルに合同であり、従ってこれを展開すると[変数Viと秘密鍵S2の内積]と[秘密鍵S1と秘密鍵S2の内積]のベクトル和となり2つの未知数の積が現れ非線型であることから、

鍵S1の不確定性H(S1)が平文Miの不確定性H(Mi)を下回らず、且つ、秘密鍵S2の不確定性H(S2)が平文Miの不確定性H(Mi)を下回らず、且つ、秘密鍵S1の不

性H(S2)が暗号鍵Kiの不確定性H(Ki)に等しい関係が成立するとき完全秘匿が成

が盗まれたとしても完全秘匿される。
M−1110秘匿変数生成モデュールの置換装置がA−001b内積型置換装置

したものと秘密鍵S2を内積したベクトルであり、即ち変数Viと秘密鍵S1と秘密鍵S2を内積したベクトルであるから未知数の積が現れ、やはり非線型となる。
また、ここで当然のことながら、M−1120不可視化処理モデュールのA−0

よく、またその時、M−1110秘匿変数生成モデュールの置換装置はA−00

0028

図12は再び擬似ランダムビット生成から記載したものであるが、図11のM−1110秘匿変数生成モデュールのA−001置換装置をA−004擬似ランダムビット生成器型置換装置(ロ)置き換えたものである。A−004擬似ランダムビット生成器型置換装置(ロ)は広い意味での非線型な変換をする装置で

特にここで重要な点は、A−004擬似ランダムビット生成器型置換装置(ロ)

0029

図13は、更にM−1120不可視化処理モデュールのA−001b内積型

ものである。A−004擬似ランダムビット生成器型置換装置(ロ)は広い意味での非線型な変換をする装置であるから、秘匿の完全性に対しA−001b内積

ダムビット生成器型置換装置(ロ)では不確定性H(S2)による計算量的完全秘匿性を持つ点である。

0030

図14において、M−1120不可視化処理モデュールの置換装置には二つ以上の値が入れば良い訳であるから、M−1110秘匿変数生成モデュールで二つ以上の秘匿変数を生成し、それをM−1120不可視化処理モデュールに入力するようにすることが考えられる。
そこで、暗号鍵生成に関する装置および方法に関する系の全体が
使い捨て公開変数riとM−1100暗号鍵生成モデュールと暗号鍵Kiから構成され、
M−1100暗号鍵生成モデュールは

M−1110秘匿変数生成モデュールと

M−1120不可視化処理モデュール
から構成され、
M−1110秘匿変数生成モデュールは
二つのM−1110秘匿変数生成モデュール、
M−1110秘匿変数生成モデュール(A)と
M−1110秘匿変数生成モデュール(B)
から構成され、
M−1120不可視化処理モデュールは

から構成され、
生成の都度ユニークな値を採る使い捨て公開変数riをA−002擬似ランダム

変数RiをM−1110秘匿変数生成モデュールのM−1110秘匿変数生成モデ

出力し、

このとき、
M−1110秘匿変数生成モデュールまたはM−1120不可視化処理モデュールの少なくともいずれか一方の処理を非線型とし

不確定性を下回らないようにすることによって、
暗号化は完全秘匿性を持つと同時に秘密鍵に関しても完全秘匿性を持つ
暗号化とすることができる。
この形では、M−1120不可視化処理モデュールに入力される値はいずれも変数であるから、M−1110秘匿変数生成モデュールにおける処理が非線型であ

つ秘密鍵も完全秘匿される。
逆に、図13までに述べた通り、M−1120不可視化処理モデュールのA−0

0秘匿変数生成モデュールにおける処理は線型でも完全秘匿が成立し、且つ秘密鍵も完全秘匿される。

0031

図15図14のM−1110秘匿変数生成モデュールをA−001aベク

ランダムビット生成器型置換装置(ハ)としたものである。M−1110秘匿変数生成モデュールにおける処理が非線型となるので、M−1120不可視化処理モデュールにおける処理は線型でも非線型でも完全秘匿が成立し、且つ秘密鍵も完全秘匿で完全秘匿される。尚、ここで秘密鍵S1、S2は共に平文Miの不確定性を下回らない不確定性を有する。

0032

のであり、M−1110秘匿変数生成モデュールの置換装置がA−001b内積

とを表している。尚、ここで秘密鍵S1、S2は共に平文Miの不確定性を下回らない不確定性を有する。

0033

図17図16におけるM−1120不可視化処理モデュールの置換装置をA−004擬似ランダムビット生成器型置換装置(ロ)に置き換えたものである。
A−004擬似ランダムビット生成器型置換装置(ロ)は非線型処理を行うから、M−1110秘匿変数生成モデュールの置換装置は線型のA−001aベクトル

下回らない不確定性を有する。

0034

図18図14のM−1110秘匿変数生成モデュールにおける置換装置を非線型の擬似ランダムビット生成器であるA−004擬似ランダムビット生成器型置換装置(ロ)に置き換えたものである。M−1110秘匿変数生成モデュールの処理が非線型となることから、M−1120不可視化処理モデュールの置換

文Miの不確定性を下回らない不確定性を有する。
またここで、M−1120不可視化処理モデュールの置換装置がA−001b内

置はA−004擬似ランダムビット生成器型置換装置(ロ)でなくても、例えば、

を後述するA−303エクストラクタで単に調整するだけの擬似ランダムビット生成器としても良い。

0035

図19図15から図18までに記載の全ての置換装置をA−004擬似ランダムビット生成器型置換装置(ロ)に置き換えたものである。
全ての置換装置が同じ処理モデュールから構成されることによって、コンピュータ処理の上では効率的である。このように全ての置換装置を同じ処理方式で揃える場合は、非線型のタイプであればどれでも同様である。即ち、A−001b内積型置換装置pでも良いし、A−004擬似ランダムビット生成器型置換装置(ロ)でも良いし、A−005擬似ランダムビット生成器型置換装置(ハ)でも良い。尚、ここで秘密鍵S1、S2は共に平文Miの不確定性を下回らない不確定性を有する。

0036

図20は秘密鍵のサイズが異なる場合のものである。

全体は、
使い捨て公開変数riとM−1100暗号鍵生成モデュールと暗号鍵Kiから構成され、
M−1100暗号鍵生成モデュールは、

れ、
M−1110秘匿変数生成モデュールは

擬似ランダムビット生成器型置換装置(ロ)から構成され、
M−1120非可逆処理モデュールは、

擬似ランダムビット生成器型置換装置(ロ)から構成され、

力して置換することによって暗号鍵Kiを得る。
成分数(データ長)について

その不確定性は

成分数(データ長)について

その不確定性は

成分数(データ長)について
|ri|<|Ri|
つまり使い捨て公開変数riの成分数|ri|は変数Riの成分数|Ri|を下回るから

従ってその不確定性は

A−004擬似ランダムビット生成器型置換装置(ロ)は広い意味での非線型で

−004擬似ランダムビット生成器型置換装置(ロ)の演算が法Nであるとすれ


通りに置換したものであるから、変数Riがわからない限り、どれが正しい変数鍵

置(ロ)の処理がわかっているとして、入力値が一つであれば、攻撃者の計算能力に制限がないとした時、総当たり攻撃でKiとなる入力値を唯一に特定することが可能であるが、入力値が複数なのでその組み合わせを特定できない。

の暗号化は完全秘匿である。
ところが、複数の暗号鍵Kiが入手されれば、総当たり攻撃によって唯一の変数鍵

を持つ。もし、その中にたった一つの組み合わせしか持たない値(暗号鍵Kiの成

とになる。
少しややこしいかもしれないので、もっと具体的に数字を入れて説明すると、

トルではないとする。例えば、Riが十七と二十一と二十八の三つの値しかと

六の内のいずれかである。次に入手されたKiが三十であれば、それに対応す

従って、この装置および方法では暗号化に関し完全秘匿であり、秘密鍵の秘匿に関し計算量的完全秘匿性を持つ。
秘密鍵の秘匿に関し、計算量的完全秘匿性しか持たないものの、この装置および方法の良い点は、秘密鍵S1を小さくできることで、媒体等に搭載して持ち歩くことなく、パスワードや生体情報キーボードあるいはバイオメトリクス読み取り装置から入力して使うこともできることから、秘密鍵の管理が悪いことで秘密鍵情報が漏洩する危険を多少でも減じられることである。
但し、計算量的完全秘匿といっても従来方式では実現不可能なほど巨大な完全性を持つことができる。たとえば秘密鍵S2のデータ長が壱MBであれば単純に八百三十八万八千六百八ビットを超える不確定性、つまり計算量的完全秘匿性を持つことになる。

よりも二ビット不確定性が低くなるだけ)である。また置換装置について、非線

(ハ)を組み合わせたものであっても同じである。

0037

以上からM−1110秘匿変数生成モデュールとM−1120不可視化処理モデュールにおける置換装置について整理すると、
図21はM−1110秘匿変数生成モデュールの構成と充当可能な置換装置を示したもので、秘密鍵または変数鍵をS1で表わしている。

変数Viと、
M−1110秘匿変数生成モデュールと、

から構成され、
M−1110秘匿変数生成モデュールは、
秘密鍵または変数鍵であるS1と、
置換装置(A)と
から構成され、

生成の都度ユニークな値をとる変数であり、成分数が|ri|(但し、|ri|<|Vi|つまり|ri|は|Vi|を下回る)であるシードriから擬似ランダムビット生成された数値または数ベクトルで、その不確定性がシードriの不確定性に等しい

つまり、H(Vi)は二を底とするNの|ri|乗の対数(場合の数(確率の逆数)Nの|ri|乗のビット表記)で表わされる値
を持つものであるか、
または、
生成の都度ユニークな値をとる変数であり、成分数が|Vi|であり、その不確

つまり、H(Vi)は二を底とするNの|Vi|乗の対数(場合の数(確率の逆数)Nの|Vi|乗のビット表記)で表わされる値
を持つ数値または数ベクトル
であって、
秘密鍵または変数鍵であるS1は、法をNとする時、

つまり、H(S1)は二を底とするNの|S1|乗の対数(場合の数(確率の逆数)Nの|S1|乗のビット表記)で表わされる値
を持つ数値または数ベクトルである秘密鍵S1
または
生成の都度ユニークな値である任意の変数で前記秘密鍵S1を置換した数値または数ベクトルであって、成分数|S1|であり、その不確定性H(S1)が

つまり、H(S1)は二を底とするNの|S1|乗の対数(場合の数(確率の逆数)Nの|S1|乗のビット表記)で表わされる値

であって、
置換装置(A)は、
二つ以上の入力値をベクトル和することによって置換するA−001aベク

または、二つ以上の入力値を内積することによって、またはベクトル和およ

または、二つ以上の入力値から擬似ランダムビット生成器を使って完全非可逆化した擬似ランダムビットを生成するA−004擬似ランダムビット生成器型置換装置(ロ)か、
または、一つの入力値から擬似ランダムビット生成器を使って完全非可逆化した擬似ランダムビットを生成するA−005擬似ランダムビット生成器型

換装置
であり、
変数Viと一つ以上の秘密鍵または変数鍵であるS1を置換装置(A)に入力して一

を出力する。

H(S1)はH(Vi)を下回らないから、変数Viよりも不確定性の大きい値で置換して

りにおいてH(S1)に等しい。

0038

図22はM−1120不可視化処理モデュールの構成と充当可能な置換装置

M−1120不可視化処理モデュールと、
暗号鍵Kiと
から構成され、
M−1120不可視化処理モデュールは、
秘密鍵または変数鍵S2と、
置換装置(B)と
から構成され、

M−1110秘匿変数生成モデュールによって入力値である変数Vi側からは秘匿された数値または数ベクトルであって、
法をNとする時、
生成の都度ユニークな値をとるriから生成された変数であることから秘匿変

り、その不確定性が秘密鍵または変数鍵S1の不確定性に等しい不確定性

数)Nの|S1|乗のビット表記)
に等しい不確定性を持つもの
であって、

成分数|S2|(但し、|S2|=|S1|つまり|S2|は|S1|に等しい)であり、その不確

つまり、H(S2)は二を底とするNの|S2|乗の対数(場合の数(確率の逆数)Nの|S2|乗のビット表記)
を持つ数値または数ベクトルである秘密鍵S2
または
生成の都度ユニークな値である任意の変数で前記秘密鍵S2を置換した数値または数ベクトルであって、成分数|S2|であり、その不確定性H(S2)が

つまり、H(S2)は二を底とするNの|S2|乗の対数(場合の数(確率の逆数)Nの|S2|乗のビット表記)

であって、
置換装置(B)は、
二つ以上の入力値を和またはベクトル和することによって置換するA−00

または、二つ以上の入力値を積または内積することによって置換するA−001b内積型置換装置pか、
または、二つ以上の入力値から擬似ランダムビット生成器を使って完全非可逆化した擬似ランダムビットを生成するA−004擬似ランダムビット生成器型置換装置(ロ)か、
または一つの入力値から擬似ランダムビット生成器を使って完全非可逆化した擬似ランダムビットを生成するA−005擬似ランダムビット生成器型置

装置
であり、

置換することによって秘匿暗号鍵Kiを出力する。

ともにM−1110秘匿変数生成モデュールの秘密鍵または変数鍵S1の不確定性

モデュールによって秘匿された変数であるから、暗号鍵Kiは完全秘匿である。
次に、置換装置(B)が数学的に線型の処理をするものであり、且つ、秘密鍵または変数鍵S2が固定値若しくは固定値と変数の組み合わせに変換可能な値であれば、入力値がたとえ全て秘匿されていたとしても、前述した通り、高々二つの暗

号鍵Kと任意のjをiに加えたi+j番目の暗号鍵Kの二つの暗号鍵によって固定値若しくは固定値に還元される秘密鍵または変数鍵S2は容易に解読される。
秘密鍵または変数鍵S2を完全秘匿とするには、
秘密鍵または変数鍵S2が固定値若しくは固定値と変数の組み合わせに変換可能な値であれば、置換装置(B)は非線型の処理をする装置とするか、
または
置換装置(B)が線型の処理をする装置であれば、秘密鍵または変数鍵S2が固定値若しくは固定値と変数の組み合わせに変換できない値とする
ようにしなければならない。
そこで、秘密鍵または変数鍵S2が固定値若しくは固定値と変数の組み合わせに変換可能な値である処理は、図10から図13までに示した処理を典型とする処理である。この時、
M−1120不可視化処理モデュールの置換装置の処理が線型であれば、秘密鍵または変数鍵S2は解読可能であり、
M−1120不可視化処理モデュールの置換装置の処理が非線型であれば、秘密鍵または変数鍵S2は完全秘匿性を持つ。
秘密鍵または変数鍵S2が固定値着しくは固定値と変数の組み合わせに変換できない値とする処理は、
秘密鍵S2と、秘密鍵S2の不確定性と等しい不確定性を有する変数を非線型処理をする置換装置によって置換する
ことにより、これが図14から図19にまで示した処理を典型とする処理となる。
M−1120不可視化処理モデュールの置換装置の処理が線型でも非線型でも、

暗号鍵Kiの不確定性を下回らない限りにおいて、秘密鍵または変数鍵S2は完全秘匿である。
以上をまとめると図22
M−1120不可視化処理モデュールにおいて秘密鍵または変数鍵S2が固定値若しくは固定値と変数の組み合わせに変換可能な処理である時、
置換装置(B)の処理が線型であれば、

秘密鍵または変数鍵S2は高々二つの暗号鍵Kiを入手することで容易に解読可能であることから、
置換装置(B)の処理を非線型とすることによって、

またはA−004擬似ランダムビット生成器型置換装置(ロ)、
またはA−005擬似ランダムビット生成器型置換装置(ハ)とA−0

とすることによって、
秘密鍵または変数鍵S2を完全秘匿とするか、
または、
秘密鍵または変数鍵S2が固定値若しくは固定値と変数の組み合わせに変換できない値とする処理とすることによって、即ち
秘密鍵または変数鍵S2が、秘密鍵S2と、秘密鍵S2の不確定性と等しい不確定性を有する変数を非線型処理をする置換装置、

ダムビット生成器型置換装置(ロ)、またはA−005擬似ランダムビット生成器型置換装置(ハ)とA−001aベクトル和型置換装

によって置換して生成されるもの
とすることによって、
M−1120不可視化処理モデュールの置換装置の処理が線型でも非線型でも、

はA−005擬似ランダムビット生成器型置換装置(ハ)とA−001

として使っても、
秘密鍵または変数鍵S2を完全秘匿とする

0039

上記の全体ををまとめて整理しなおすと、
置換装置の基本形は、ベクトル和または内積によって置換する装置と、擬似ランダムビット生成器を用いて置換する装置とがあり、
擬似ランダムビットを用いて置換する装置には、擬似ランダムビットを折畳若しくは抜取によって非線型化して置換するものと、擬似ランダムビット生成において内積の演算を含むことによって非線型化して置換するものとがある。
この内、擬似ランダムビットによって置換する方式の基本的な性能は、図41(a)に示すように、一つの入力値AとA−005擬似ランダムビット生成器型置換装置(ハ)と出力値Cからなり、関数fをAからCへの写像とするとき、AからCは容易に算出されるが、その逆写像であるCからAへの写像は不確定性H(A)の計算量的完全秘匿である。
入力値が二つの場合は、図41(b)に示すように、二つの入力値A、BとA−004擬似ランダムビット生成器型置換装置(ロ)と出力値Cからなり、関数fを(A,B)からCへの写像とするとき、(A,B)からCは容易に算出されるが、その逆写像であるCから(A,B)への写像は不確定性H(A)またはH(B)の計算量的完全秘匿である。また、関数gをAからCへの写像とし、関数g′をBからCへの写像とするとき、関数gおよび関数g′は完全秘匿であり、それぞれの逆写像g−1およびg′−1は不確定性H(A)+H(B)つまりH(A)にH(B)を加えた値の計算量的完全秘匿である。
また、(A,C)からBへの写像を関数hとするとき、関数hは不確定性H(A)またはH(B)の計算量的完全秘匿である。

0040

そこで、暗号処理の装置のための置換装置および置換方法は、図41(c)から(g)までに示す構造をとり、
置換装置(c)は、二つの入力値を持つ擬似ランダムビット生成過程において折畳または抜取または内積を含む演算を行うことによって生成を非線型化するA−004擬似ランダムビット生成器型置換装置(ロ)と、入力値である変数Vと、秘密鍵Sと、出力値Cとから構成され、変数Vと秘密鍵SとをA−004擬似ランダムビット生成器型置換装置(ロ)に入力することに因って非線型化した演算を行って出力値Cを得るようにした暗号処理の方法のための置換処理の装置および/または方法であるか、または、
置換装置(d)は、二つの入力値を素数pを法とする内積によって置換するA−

変数Vと、p−1(前記素数pから一を減じた値)を法とする秘密鍵Sと、p−1(前記素数pから一を減じた値)を法とする出力値Cとから構成され、変数Vと

内積して法pの出力値Cを得、その出力値Cを法pで各成分から一を減じることで法をp−1(前記素数pから一を減じた値)とする処理を行い、法をp−1(前記素数pから一を減じた値)とする出力値Cを得るようにした暗号処理の方法のための置換処理の装置および/または方法であるか、または、
置換装置(e)は、二つの入力値を自然数Nを法とするベクトル和によって置換

鍵Sをベクトル和して出力値Cを得るようにした暗号処理の方法のための置換処理の装置および/または方法であるか、または、
置換装置(f)は、二つの入力値を自然数Nを法とするベクトル和によって置換

値C′と、一つの入力値を持つ擬似ランダムビット生成過程において折畳または抜取または内積を含む演算を行うことによって生成を非線型化するA−005擬似ランダムビット生成器型置換装置(ハ)と、出力値Cとから構成され、VAとVBと

そのC′をA−005擬似ランダムビット生成器型置換装置(ハ)に入力して置換することによって出力値Cを得るようにした暗号処理の方法のための置換処理の装置および/または方法であるか、または、
置換装置(g)は、二つの入力値を素数pを法とする内積によって置換するA−

変数Vと、p−1(前記素数pから一を減じた値)を法とする秘密鍵Sと、置換された値C′と、一つの入力値を持つ擬似ランダムビット生成過程において折畳または抜取または内積を含む演算を行うことによって生成を非線型化するA−005擬似ランダムビット生成器型置換装置(ハ)と、出力値Cとから構成され、Vと

そのC′をA−005擬似ランダムビット生成器型置換装置(ハ)に入力して置換することによって出力値Cを得るようにした暗号処理の方法のための置換処理の装置および/または方法である。

0041

それぞれの置換装置の性能は、
図41(c)に示す置換装置は、擬似ランダムビットを用いて置換する装置と、入力値である変数Vと秘密鍵Sと出力値Cからなり、関数f:(V,S)→Cは容易に算出されるが、その逆写像f−1:(V,S)←Cは計算量的完全秘匿である。VからCへの写像gおよびSからCへの写像g′はそれぞれ完全秘匿性を持ち、それぞれの逆写像g−1およびg′−1は不確定性H(V)+H(S)の計算量的完全秘匿である。更に、(V,C)からSへの写像h:(V,C)→Sは不確定性H(V)またはH(S)の計算量的完全秘匿である。
図41(d)に示す置換装置は、二つの入力値を内積によって置換する装置であって、関数f:(V,S)→Cは容易に算出される。VからCへの写像gおよびSからCへの写像g′はそれぞれ完全秘匿性を持ち、それぞれの逆写像g−1およびg′−1も完全秘匿である。但し、(V,C)からSへの写像h:(V,C)→Sは容易に算出される。
図41(e)に示す置換装置は、二つの入力値VA、VBをベクトル和によって置換して出力値Cを出力する装置であって、関数f:(VA,VB)→Cは容易に算出される。
VAからCへの写像gおよびVBからCへの写像g′はそれぞれ完全秘匿であり、それぞれの逆写像g−1およびg′−1も完全秘匿である。但し、(VA,C)からVBへの写像h:(VA,C)→VBは容易に算出される。
図41(f)に示す置換装置は、二つの入力値VA、VBをベクトル和によって置換した値C′を更に擬似ランダムビット生成器を用いる方式で置換して出力値Cを出力するようにした装置であって、関数f:(VA,VB)→Cは容易に算出され、その逆写像f−1:(VA,VB)←Cは計算量的完全秘匿である。また、VAからCへの写像gおよびVBからCへの写像g′はそれぞれ完全秘匿であり、それぞれの逆写像g−1およびg′−1も完全秘匿である。更に、(VA,C)からVBへの写像h:(VA,C)→VBは不確定性H(C′)の計算量的完全秘匿である。
図41(g)に示す置換装置は、二つの入力値V、Sを内積によって置換した値C′を更に擬似ランダムビット生成器を用いる方式で置換して出力値Cを出力するようにした装置であって、関数f:(V,S)→Cは容易に算出され、その逆写像f−1:(V,S)←Cは計算量的完全秘匿である。また、VからCへの写像gおよびSからCへの写像g′はそれぞれ完全秘匿であり、それぞれの逆写像g−1およびg′−1も完全秘匿である。更に、(V,C)からSへの写像h:(V,C)→Sは不確定性H(C′)の計算量的完全秘匿である。
ここで重要な点はが二つある。一つは、全ての置換装置が二つ(複数)の入力値を持つ点である。置換装置(c)の場合を除いていずれの場合も、ベクトル和または内積が絡んでおり、出力値からはそれら二つの入力値を特定することができない(法Nとすれば入力値、出力値とも各成分がN通りずつ存在する)構造となっている。一つの入力値から一つの出力値を得る装置では、出力値が得られれば、計算量的に入力値を特定することが可能となることと対照的である。但し、ベクトル和のみの場合で、入力値の一つが固定値である場合は、もう一方の入力値が変数であっても二つの出力値から容易に全ての入力値を求めることができる。
また一つは、擬似ランダムビット生成器の絡んだ置換装置、つまり、置換装置(c)、置換装置(f)、置換装置(g)は、出力値と一つの入力値が漏洩したとしても、もう一つの入力値が計算量的に解読不能である(すべての擬似ランダムビットを生成してみなければ値を特定できない)点である。

0042

上記の置換装置を用いて、暗号文Eiについて完全秘匿性を持たせると同時に、秘密鍵Sについて暗号文Eiと平文Miが漏洩することによって暗号鍵Kiの情報が漏洩したとしても完全秘匿性を持たせる暗号処理の装置および方法には図41に示す装置および方法と図42に示す装置及び方法があり、
図42に示す暗号文および秘密鍵について完全秘匿である暗号処理の装置および方法は、
使い捨て公開変数riと、M−1110秘匿変数生成モデュールと、秘匿変数K′iと、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Гと、暗号文Eiとから構成され、
M−1110秘匿変数生成モデュールは、秘密鍵S1と、A−901置換装置Aとから構成され、
M−1120不可視化処理モデュールは、秘密鍵S2と、A−902置換装置Bと、から構成され、

を生成し、その変数Viと秘密鍵S1とをA−901置換装置Aに入力して置換することによって秘匿変数K′iを生成し、その秘匿変数K′iと秘密鍵S2とをA−902置換装置Bに入力することによって暗号鍵Kiを生成し、その暗号鍵Kiと平文MiをA−903置換装置Гに入力することに因って暗号文Eiを生成するよう処理され、
A−901置換装置Aを、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、
A−902置換装置Bを、置換装置(d)または置換装置(g)から構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も情報理論的に逆算不能とし、
A−901置換装置AとA−902置換装置Bを用いるようにしたことに因って秘密鍵S1と秘密鍵S2とを完全秘匿化し、
A−903置換装置Гを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにした暗号処理の装置及び方法である。

開変数riとA−901置換装置Aの間に入れるようにしても良い。擬似ランダムビット生成がブロック暗号よりも高速であることから、そのようにすることで暗号化の処理全体を高速化するとができ、
また同時に生成する変数に大きな不確定性を付与することが可能となり、秘密鍵を一つ漏洩した場合でも巨大な計算量を確保することで解読不能とすることができる。

定性は平文Miの不確定性を下回らないから暗号文Eiは完全秘匿である。またこ

捨て公開変数riの不確定性を下回らないことから、riからはK′iを推測できず、また、暗号鍵Kiからは法pによる内積((ai,bi)≠(0,0)つまり、入力値の成分にが含まれない演算とする)の非線型性と演算結果の一様性により演算結果の成分の不確定性が演算する成分の不確定性を下回らないことから情報理論的にK′iを求めることができず、そのことによって、秘密鍵S1およびS2は暗号文Eiとその平文Miが漏洩したとしても完全秘匿となる。
尚、暗号鍵Kiからの逆算において、ベクトル和による場合も演算結果に一様性が

回らない自然数)の連立方程式によって容易に差分が求まり、その結果、秘密鍵S2がN通りで解読されてしまうので使えない。
また、この方式ではいずれか一つの秘密鍵が漏洩すれば、もう一つの秘密鍵も解読可能となる。S1が漏洩すればS2の置換装置が置換装置(d)であればS2は容易に求まり、S2の置換装置が置換装置(g)であれば計算量的完全秘匿である。S2が漏洩したとき、S1の置換装置が置換装置(e)または置換装置(d)であれば容易にS1は求まり、S2の置換装置が置換装置(c)、置換装置(f)、置換装置(g)のいずれかであればS1は計算量的完全秘匿である。また秘密鍵の計算量的完全秘匿が成立している間は、暗号文は尚も完全秘匿である。
当然ここで、生成過程をもう一段階増やして、秘密鍵を3つ用いるようにすれば、いずれか一つの秘密鍵が漏洩したり若しくはその秘密鍵を用いる置換装置が故障しても尚完全秘匿とすることも可能である。

0043

図43に示す暗号処理の装置および方法は、
使い捨て公開変数riと、A−301セパレータと、変数Vi1と、変数Vi2と、M−1110秘匿変数生成モデュールと、秘匿変数K′i1と、秘匿変数K′i2と、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、
M−1110秘匿変数生成モデュールは、秘密鍵S1と、秘密鍵S2と、A−901置換装置A1と、A−901置換装置A2とから構成され、
M−1120不可視化処理モデュールは、A−902置換装置Bから構成され、
使い捨て公開変数riをA−301セパレータで分割して変数Vi1と変数Vi2とを生成し、その変数Vi1と秘密鍵S1とをA−901置換装置A1に入力して置換することによって秘匿変数K′i1を生成し、同時に変数Vi2と秘密鍵S2とをA−901置換装置A2に入力して置換することによって秘匿変数K′i2を生成し、その秘匿変数K′i1と秘匿変数K′i2とをA−902置換装置Bに入力することによって置換して暗号鍵Kiを生成し、その暗号鍵Kiと平文MiとをA−903置換装置Γに入力することによって置換して暗号文Eiを生成するよう処理され、
A−901置換装置A1およびA−901置換装置A2を、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、
A−902置換装置Bを、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も情報理論的に逆算不能とし、
A−901置換装置A1およびA−901置換装置A2とA−902置換装置Bを用いるようにしたことに因って、
但し、A−901置換装置A1およびA−901置換装置A2が置換装置(e)であればA−902置換装置Bは置換装置(c)、置換装置(d)、置換装置(f)、置換装置(g)のいずれかとし、A−902置換装置Bが置換装置(e)であればA−901置換装置A1およびA−901置換装置A2は置換装置(c)、置換装置(d)、置換装置(f)、置換装置(g)のいずれかとすることに因って、
秘密鍵S1と秘密鍵S2とを完全秘匿化し、
A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにした暗号処理の装置及び方法である。

開変数riとA−301セパレータの間に入れるようにしても良い。そのようにすることで送信する使い捨て公開変数riのサイズをより小さく(概ね半分に)することができる。
図43においてM−1110秘匿変数生成モデュールの置換装置は図42の場合と同じであるが、M−1120不可視化処理モデュールの置換装置は選択の幅が広がっている。但し、M−1110秘匿変数生成モデュール、M−1120不可視化処理モデュールの置換装置が両者ともベクトル和である場合、つまり置換装置(e)である場合には、一つの変数と一つの秘密鍵の組み合わせとなるため、2つの暗号鍵から容易に秘密鍵が解読されてしまう。また、いずれかの秘密鍵が漏洩すると他の秘密鍵も解読可能となることは図42の場合と同じであり、そのときM−1110秘匿変数生成モデュールの置換装置が置換装置(c)、置換装置(f)、置換装置(g)のいずれかであればもう一方の秘密鍵は計算量的完全秘匿であり、暗号化は尚も完全秘匿である。
当然ここで、生成過程をもう一段階増やして、秘密鍵を3つ用いるようにすれば、いずれか一つの秘密鍵が漏洩したり若しくはその秘密鍵を用いる置換装置が故障しても尚完全秘匿とすることも可能である。

0044

また、暗号文Eiについて完全秘匿性を持たせると同時に、秘密鍵Sについて暗号文Eiと平文Miが漏洩することによって暗号鍵Kiの情報が漏洩したとしても計算量的完全秘匿性を持たせる暗号処理の装置および方法には図41に示す装置および方法と図42に示す装置及び方法と図43に示す装置及び方法と図44に示す装置及び方法があり、
図42に示す装置および方法において暗号文について完全秘匿性を持たせると同時に、秘密鍵について暗号文と平文が漏洩することによって暗号鍵の情報が漏洩したとしても計算量的完全秘匿性を持たせる暗号処理の装置および方法は、使い捨て公開変数riと、M−1110秘匿変数生成モデュールと、秘匿変数K′iと、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、
M−1110秘匿変数生成モデュールは、秘密鍵S1と、A−901置換装置Aとから構成され、
M−1120不可視化処理モデュールは、秘密鍵S2と、A−902置換装置Bと、から構成され、
使い捨て公開変数riと秘密鍵S1とをA−901置換装置Aに入力して置換することによって秘匿変数K′iを生成し、その秘匿変数K′iと秘密鍵S2とをA−902置換装置Bに入力することによって暗号鍵Kiを生成し、その暗号鍵Kiと平文MiをA−903置換装置Γに入力することに因って暗号文Eiを生成するよう処理され、
A−901置換装置Aを、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、
A−902置換装置Bを、置換装置(c)または置換装置(f)から構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も計算量的に逆算不能とし、
A−901置換装置AとA−902置換装置Bを用いるようにしたことに因って秘密鍵S1と秘密鍵S2とを計算量的完全秘匿化し、
A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにした暗号処理の装置及び方法である。

Viを使い捨て公開変数riとA−901置換装置Aの間に入れるようにしても良い。
この方式は図42のM−1120不可視化処理モデュールの置換装置を置換装置(d)または置換装置(g)から、置換装置(c)または置換装置(f)に替えたものである。このとき、暗号鍵Kiがわかれば擬似ランダムビット型置換装置の特性によって、攻撃者の計算能力に制限がないとすれば計算量的に一つの入力値を求めることが可能であることから、置換装置(c)の場合はそこから容易にK′iとS2が求まり、置換装置(f)の場合でも二つの暗号鍵が入手されれば容易にK′iとS2が求まる。従って、秘密鍵に関し計算量的完全秘匿性しかない。
また、この方式では一方の秘密鍵が漏洩してももう一方の秘密鍵は必ず計算量的完全秘匿である。但し、この時、例えば秘密鍵が一メガバイトであれば、八百三十八万八千六百八ビットの不確定性(即、情報理論的エントロビー)となる。
当然ここで、生成過程をもう一段階増やして、秘密鍵を3つ用いるようにすれば、いずれか一つの秘密鍵が漏洩したり若しくはその秘密鍵を用いる置換装置が故障しても尚完全秘匿とすることも可能である。

0045

図43に示す装置および方法において暗号文について完全秘匿性を持たせると同時に、秘密鍵について暗号文と平文が漏洩することによって暗号鍵の情報が漏洩したとしても計算量的完全秘匿性を持たせる暗号処理の装置および方法は、使い捨て公開変数riと、A−301セパレータと、変数Vi1と、変数Vi2と、M−1110秘匿変数生成モデュールと、秘匿変数K′i1と、秘匿変数K′i2と、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、
M−1110秘匿変数生成モデュールは、秘密鍵S1と、秘密鍵S2と、A−901置換装置A1と、A−901置換装置A2とから構成され、
M−1120不可視化処理モデュールは、A−902置換装置Bから構成され、
使い捨て公開変数riをA−301セパレータで分割して変数Vi1と変数Vi2とを生成し、その変数Vi1と秘密鍵S1とをA−901置換装置A1に入力して置換することによって秘匿変数K′i1を生成し、同時に変数Vi2と秘密鍵S2とをA−901置換装置A2に入力して置換することによって秘匿変数K′i2を生成し、その秘匿変数K′i1と秘匿変数K′i2とをA−902置換装置Bに入力することによって置換して暗号鍵Kiを生成し、その暗号鍵Kiと平文MiとをA−903置換装置Γに入力することによって置換して暗号文Eiを生成するよう処理され、
A−901置換装置A1およびA−901置換装置A2を、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、
A−902置換装置Bを、置換装置(c)から構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も計算量的に逆算不能とし、A−901置換装置A1およびA−901置換装置A2とA−902置換装置Bを用いるようにしたことに因って、
秘密鍵S1と秘密鍵S2とを計算量的完全秘匿化し、
A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにした暗号処理の装置及び方法である。

数Viを使い捨て公開変数riとA−301セパレータの間に入れるようにしても良い。
これはM−1120不可視化処理モジュールの置換装置を置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから、置換装置(c)に替えたものであって、攻撃者の計算能力に制限がないとすれば計算量的に一つの入力値を求めることが可能であり、そこから置換装置(c)の場合は容易にK′iとK″iが求まる。次に、M−1110秘匿変数生成モジュールが置換装置(e)または置換装置(d)の場合は容易にS1とS2が求まり、置換装置(c)、置換装置(f)、置換装置(g)のいずれかの場合には計算量的にS1とS2を求めることが可能である。
この方式でも、一方の秘密鍵が漏洩してももう一方の秘密鍵は少なくとも秘密鍵の不確定性による計算量的完全秘匿である。この時、例えば秘密鍵が一メガバイトであれば、少なくとも八百三十八万八千六百八ビットの不確定性(即、情報理論的エントロピー)となる。当然、M−1120不可視化処理モジュールが置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかであれば完全秘匿となる。
当然ここで、生成過程をもう一段階増やして、秘密鍵を3つ用いるようにすれば、いずれか一つの秘密鍵が漏洩したり着しくはその秘密鍵を用いる置換装置が故障しても尚完全秘匿とすることも可能である。

0046

図44に示す装置および方法において暗号文について完全秘匿性を持たせると同時に、秘密鍵について暗号文と平文が漏洩することによって暗号鍵の情報が漏洩したとしても計算量的完全秘匿性を持たせる暗号処理の装置および方法は、使い捨て公開変数riと、M−1110秘匿変数生成モデュールと、変数Riと、A

化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、
M−1110秘匿変数生成モデュールは、秘密鍵S1と、A−901置換装置Aとから構成され、
M−1120不可視化処理モデュールは、秘密鍵S2と、A−902置換装置Bとから構成され、
使い捨て公開変数riと秘密鍵S1とをA−901置換装置Aに入力して置換することによって変数Riを生成し、その変数RiからA−002擬似ランダムビット生成

2置換装置Bに入力することによって暗号鍵Kiを生成し、その暗号鍵Kiと平文MiをA−903置換装置Γに入力することに因って暗号文Eiを生成するよう処理され、
A−901置換装置Aを、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って使い捨て公開変数riからは秘匿変数K′iを推測不能とし、
A−902置換装置Bを、置換装置(c)、置換装置(d)、置換装置(f)、置換装置(g)のいずれかから構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も計算量的に逆算不能とし、
A−901置換装置AとA−902置換装置Bを用いるようにしたことに因って秘密鍵S1と秘密鍵S2とを計算量的完全秘匿化し、
A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにした暗号処理の装置及び方法である。
当然ここで、生成過程をもう一段階増やして、秘密鍵を3つ用いるようにすれば、いずれか一つの秘密鍵が漏洩したり若しくはその秘密鍵を用いる置換装置が故障しても尚完全秘匿とすることも可能である。

0047

図45に示す装置および方法において暗号文について完全秘匿性を持たせると同時に、秘密鍵について暗号文と平文が漏洩することによって暗号鍵の情報が漏洩したとしても計算量的完全秘匿性を持たせる暗号処理の装置および方法は、使い捨て公開変数riと、A−301セパレータと、変数Vi1と、変数Vi2と、M−1110秘匿変数生成モデュールと、変数Riと、秘匿変数K′i1と、秘匿変数K′i2と、M−1120不可視化処理モデュールと、暗号鍵Kiと、平文Miと、A−903置換装置Γと、暗号文Eiとから構成され、
M−1110秘匿変数生成モデュールは、秘密鍵S1と、秘密鍵S2と、A−901置換装置A1と、A−901置換装置A2とから構成され、
M−1120不可視化処理モデュールは、A−902置換装置Bとから構成され、
使い捨て公開変数riをA−301セパレータで分割して変数Vi1と変数Vi2とを生成し、その変数Vi1と秘密鍵S1とをA−901置換装置A1に入力して置換することによって秘匿変数K′i1を生成し、同時に変数Vi2と秘密鍵S2とをA−901置換装置A2に入力して置換することによって変数Riを生成し、その変数Riか

秘匿変数K′i1と秘匿変数K′i2とをA−902置換装置Bに入力することによって置換して暗号鍵Kiを生成し、その暗号鍵Kiと平文MiとをA−903置換装置Γに入力することによって置換して暗号文Eiを生成するよう処理され、
A−901置換装置A1およびA−901置換装置A2を、置換装置(c)、置換装置(d)、置換装置(e)、置換装置(f)、置換装置(g)のいずれかから構成したことに因って変数Viからは秘匿変数K′iを推測不能とし、
A−902置換装置Bを、置換装置(c)から構成するようにしたことに因って暗号鍵Kiからは秘匿変数K′iも秘密鍵S2も計算量的に逆算不能とし、
A−901置換装置A1およびA−901置換装置A2とA−902置換装置Bを用いるようにしたことに因って、
秘密鍵S1と秘密鍵S2を不確定性がH(S1)+H(S2)で計算量的完全秘匿化し、
但し、このとき

つまり、秘密鍵S1の不確定性H(S1)は変数Vi1の不確定性H(Vi1)を下回らず、かつ秘匿変数K′i1の不確定性H(K′i1)および暗号鍵Kiの不確定性H(Ki)と等しく、
且つ、秘密鍵S2の不確定性H(S2)は変数Vi2の不確定性H(Vi2)を下回らず、かつ変数Riの不確定性H(Ri)および秘匿変数K′i2の不確定性H(K′i2)と等しく、かつ暗号鍵Kiの不確定性H(Ki)を下回り、
且つ、暗号鍵Kiの不確定性H(Ki)は平文Miの不確定性H(Mi)を下回らないものとし、
A−903置換装置Γを、置換装置(d)または置換装置(e)から構成するようにしたことに因って暗号文Eiを完全秘匿化するようにした暗号処理の装置及び方法である。

開変数riとA−301セパレータの間に入れるようにしても良い。そのようにすることで送信する使い捨て公開変数riのサイズをより小さくすることができる。
当然ここで、生成過程をもう一段階増やして、秘密鍵を3つ用いるようにすれば、いずれか一つの秘密鍵が漏洩したり若しくはその秘密鍵を用いる置換装置が故障しても尚完全秘匿とすることも可能である。

0048

上記の装置及び方法を成立させるための擬似ランダムビット生成器を含む置換装置の論理および構成と処理は、

回らない素数)を法として積または内積することによって置換し、まったく異なる数値または全く異なる値からなる成分を持つ数ベクトルとして出力するものである。

0049

何故ならば、

つまり、零を含む任意の自然数a,b,cがあり、法が二を下回らない自然数Nであるときa+b≡cつまり、aにbを加えたものはcに合同であることが成り立つならば、cの不確定性はlog2Nつまり、二を底とするNの対数(場合の数(確率の逆数)Nのビット表記)であり、かつaの不確定性H(a)とbの不確定性H(b)は、それぞれ全てlog2Nつまり二を底とするNの対数(場合の数(確率の逆数)Nのビット表記)に写される。
また、任意の自然数a,b,cがあり、法を三を下回らない素数pとするとき
a×b≡cつまり、aにbをかけたものがcに合同)が成り立つならば、cの不確定性はlog2(p−1)つまり二を底とするpから一を減じた値の対数(場合の数(確率の逆数)p−1(pから一を減じた値)のビット表記)であり(法pの場合については、零を含む積の演算では演算結果が零に偏り一様分布にならないため、一からpまでのp−1(pから一を減じた値)個の値を演算対象としなければならない。従ってその不確定性はlog2(p−1)つまり二を底とするpから一を減じた値の対数(場合の数(確率の逆数)p−1(pから一を減じた値)のビット表記)となり、かつaの不確定性H(a)とbの不確定性H(b)は、それぞれ全てlog2(p−1)つまり二を底とするpから一を減じた値の対数(場合の数(確率の逆数)p−1(pから一を減じた値)のビット表記)に写されることによる。つまり、N通りの入力値に対してN通りの出力値が得られ、p−1(pから一を減じた値)通りの入力値からはp−1(pから一を減じた値)通りの出力値が得られる。

0050

但し、二つの入力値であるベクトルの成分数が同じであっても、その不確定性が異なる場合、少なくとも不確定性の大きな方のベクトルが秘匿される限りにおいて、出力されたベクトルの不確定性は、その大きな不確定性に等しくなる。
このことを図23を使って説明すると、
Aはシードの集合。Bは秘密鍵の集合。Cは暗号鍵の見かけの集合。DはシードAから生成された擬似ランダムビット列の集合。Eは秘密鍵をシードで置換したベクトルの集合であって暗号鍵の実際の集合。とする。この時、それぞれの集合に含まれる成分(黒い点)の数は、それぞれの集合の成分が取りうる場合の数であり、それぞれの集合の成分の不確定性に対数で比例している(点がN個あれば、その不確定性はlog2N(二を底とするNの対数。場合の数(確率の逆数)Nのビット表記))ものとする。
集合Dにおいて、擬似ランダムビット列生成器が全単写であれば、当然、生成される成分数はシードである集合Aの成分数に等しいので、集合Dの成分の不確定性は集合Aの成分の不確定性に等しく、この不確定性は集合Aのベクトルの二進の成分数に等しい。ところが、集合Dの成分であるベクトルの成分数は秘密鍵Bの成分であるベクトルの成分数を下回らない。
集合Eは、集合Aの各成分が集合Bの成分φを置換することによって作られる写像である。従って、集合Eの成分数と集合Aの成分数は等しく、また、集合Aと集合Dの間の関係と同様に、集合Eの成分の不確定性と集合Aの成分の不確定性は等しい。ところが、集合Bにおいて成分φ以外の任意の成分φ′をとってきて置換による集合Aの写像E’(Eプライム)を考えると、E’(Eプライム)はEとは別の新しい集合を作る。すると、集合Bの成分数がnであれば、それらの置換によって生成される集合はE(0)(Eの零プライム)からE(n−1)(Eのn−1(nから一を減じた値)プライム)までn個存在することになる。今、集合Aの成分数をmとすれば、集合Cの成分数はmn(mにnを掛けた値)ということになるが、任意の数Nを法とする世界では集合Bを置換した集合Cの不確定性は集合Bの不確定性を上回ることはないので、結局その成分数は集合Bの成分数と等しくnとなる(つまり、(mn−n)=(m−1)n(mにnを掛けた値からnを減じた値はmから一を減じた値にnを掛けた値に等しい)個は重複した成分)。そうであるならば、集合Bが秘匿される限りにおいて集合Eの成分を計算量的に特定することはできず(完全秘匿)、従って、その時に限り集合Eの成分の不確定性は集合Bの成分の不確定性を下回らない。
従って、ここで置換という操作を考えると、集合Bが真正ランダムであれば、それを集合Aで置換した集合Eは、やはり真正ランダムということになる。
つまり、ある擬似ランダムビット列である秘密鍵を置換することによって生成されたベクトルの不確定性は、その秘密鍵が秘匿される限りにおいてその秘密鍵の不確定性に等しい。

0051

そこで置換装置について図24を使って説明すると、
入力されたベクトルA,Bに対し、それぞれの成分の内の同じ次元の値を法N(N

は内積または和またはベクトル和を行うことにより、ベクトルCを生成する装置であると言える。この時、ベクトルCの不確定性は、法Nのときlog2Nつまり二を底とするNの対数(場合の数(確率の逆数)Nのビット表記)となり、法pのときはlog2(p−1)つまり二を底とするpから一を減じた値の対数(場合の数(確率の逆数)p−1(pから一を減じた値)のビット表記)であることは前述したとおりである。

0052

図24において、
複数の入力値であるベクトルA,Bに対して出力値がベクトルCとするとき、
A,Bを、
二を下回らない自然数Nを法として
ベクトル和
するか、
または三を下回らない素数pを法として
内積するか
またはベクトル和および内積して
ベクトルCとして出力することによって、
即ち、入力された二つのベクトルである
A−101A=(ai)i=1,2,...,n、つまり任意の成分がaiで表わされるn個の成分からなるベクトルA
およびA−101B=(bi)i=1,2,...,n、つまり任意の成分がbiで表わされるn個の成分からなるベクトルB
に対し、
それぞれの成分の内の同じ次元同士の値を

積と和の演算を行い、
各成分を次元の順に並べてベクトルA−102C=(ci)i=1,2,...,nつまり任意の成分がciで表わされるn個の成分からなるベクトルCの出力を得、
そのことによって、ベクトルAの不確定性H(A)とベクトルBの不確定性H(B)が異

H(C)つまりH(B)はH(C)と等しく、且つ、H(B)とH(C)はH(A)を下回らず、即ちベクトルCの不確定性H(C)がベクトルBの不確定性H(B)と等しくなる
ように置換する装置である。

0053

ここで、特に積または内積の演算は、図37で説明すると、

入力値であるベクトルA,Bに対して出力値がベクトルCとすると、
ベクトルA,Bが共にp−1(pから一を減じた値)を法とするベクトルあるとき、

p−1を法とするA−101A=(ai)i=1,2,...,n
つまり任意の成分がaiで表わされるn個の成分からなるベクトルA
およびA−101B=(bi)i=1,2,...,n
つまり任意の成分がbiで表わされるn個の成分からなるベクトルB
の各成分にpを法として一を加えることで、pを法とするベクトルA−103
A′=(a′i)i=1,2,...,n
つまり任意の成分がa′iで表わされるn個の成分からなるベクトルA′
およびA−103B′=(b′i)i=1,2,...,n
つまり任意の成分ががbiで表わされるn個の成分からなるベクトルB′
(但し、(a′i,b′i)≠(0,0)、つまりベクトルA′およびB′の成分には0は含まれていない)を生成し、
ベクトルA−103A′=(a′i)i=1,2,...,n
つまり任意の成分がa′iで表わされるn個の成分からなるベクトルA′
およびA−103B′=(b′i)i=1,2,...,n
つまり任意の成分がb′iで表わされるn個の成分からなるベクトルB′
のそれぞれの成分の内の同じ次元同士の値をpを法として積で演算し、演算結果として出力されたベクトルA−103C′=(c′i)i=1,2,...,n
つまり任意の成分がc′iで表わされるn個の成分からなるベクトルC′
の各成分の値からpを法として一を引いた値を生成することで実質的に法をp−1(pから一を減じた値)とし、
法をp−1(pから一を減じた値)とするベクトルA−102C=(ci)i=1,2,...,n
つまり任意の成分がciで表わされるn個の成分からなるベクトルC
を得る
という演算を行うと定義される。

尚、本発明で「素数pを法とする積」または「素数pを法とする内積」または「素数pを法とする積または内積」というときは、このような演算法を指す。

0054

但し、この方法は法の変換方法としては全く正確ではない。つまり、あるp−1進法(法p−1(pから一を減じた値))の値をp進法(法p)に変換する方法としては数学的に妥当ではない。しかしながら、このような方法をとる目的は法の変換ではなく、法を素数とすることで積における演算結果における値の分布の一様性を確保することが目的なので何ら問題はない。しかも、このような方法であってもp進法の成分から一を減じてp−1進法(法p−1(pから一を減じた値))に戻した時に、正しい値となるので、更に問題はない。
数学的には、零からp−2(pから二を減じた値)までの成分数p−1(pから一を減じた値)の整数からなる順序集合を一からp−1(pから一を減じた値)までの成分数p−1(pから一を減じた値)の整数からなる順序集合に順序どおりに全単写で写像している。
例えば法を二百五十七とするとき、法を二百五十六とする二つの値、二百四十と百四十六があるとする。この値を法二百五十六で演算すれば二百四十×百四十六≡二百二十四であるが、法二百五十七で演算すれば二百四十一×百四十七≡二百十八となり、そこから一を引いても二百二十四にはならない。
ところが、この二百十八に百四十七の逆数である七を掛けると二百十八×七≡二百四十一となり、そこから一を引けば元の法を二百五十六とする値二百四十が得られる。つまり、法とする世界のこのような変換を通しても積の演算が成立する。これは、たまたまそうなったのではなく、計算技術的にはごく当然のことで、法二百五十七での演算の合同式左辺の値は二つとも法二百五十六の値に一加えたものであるから、その採りうる値は一から二百五十六の間の数値であり、その結果、右辺の採りうる値の範囲も一から二百五十六となり、その右辺の値にその逆数である自然数(やはり値の採りうる範囲は一から二百五十六)を掛けてもその演算結果の採りうる値の範囲は一から二百五十六となる。そこから一を引けば、元の法二百五十六の値に戻るわけである。もっとあからさまな言い方をすれば、素数を法として演算する必要があることから形式的に素数二百五十七を法としているだけであって、上記のような演算の実質は法二百五十六というわけである。
つまりここでは、演算処理の結果として得たいのは法を二百五十六とする値であって、法を素数二百五十七とする値ではないという点がポイントとなる。
もう一つ良い点は、演算する値にそれぞれ一を加えることで、成分における値の出現率が完全に一様になる点である。例えば、法二百五十七で演算する場合、零から二百五十六までの値で積の演算を行うと演算結果は零に大きく偏るが、一か

算結果がN通りとなるのと同様に、演算結果は一から二百五十六までの値で完全に一様になる。
これら二点は、例えばN=六(Nは六に等しい)とp=七(pは七に等しい)やN=十二(Nは十二に等しい)とp=十三(pは十三に等しい)あるいはN=十八(Nは十八に等しい)とp=十九(pは十九に等しい)など多くの数の間でも

たは二または三または四とするとき、二の二乗のk乗に等しく、

るとき、二の二乗のk乗に一を加えた値に等しいとすると、より面白い処理あるいは軽量化した処理が可能なる。現在のコンピュータ二進法で構成されており、特に文字列がバイナリーコードの形で十六ビットまたは二百五十六ビットの単位で処理されていることから、暗号処理システムとしての値の取扱いがきわめて容易になる。

とき、二の二乗のk乗に等しいNと

二の二乗のk乗に一を加えた値に等しい素数pではこの自然数と素数の関係が五段階で設定できることから、整数体、有理数体、あるいは累乗根などの一部の実数のほかに多重複素数体(例えば自乗して虚数になる数など)を自然数で扱えるなど、より複雑な構造を簡単な演算で処理することが可能となる点は極めて重要と考えられる。
更にこのような積の演算は擬似ランダムビット生成においても利用できる。
また例えば、こうした置換や擬似ランダムビット生成のほかにDiffie−Hellmanの指数鍵交換(Exponential Key Exchange)方式がベクトルで小さな値を使って容易に扱えるようになることから、この方式で大きな不確定性が少ない計算量で容易に得られるようになるなど、

二の二乗のk乗に一を加えた値に等しい素数pのメリットは大きい。

は二または三または四とするとき、二の二乗のk乗に一を加えた値に等しい素数pに限定して

あるベクトルA,Bに対して出力値がベクトルCとすると、
ベクトルA,Bが共にp−1(pから一を減じた値)を法とするベクトルあるとき、

たは三または四とするとき、二の二乗のk乗に一を加えた値に等しいとき、pを法としてA−101A=(ai)i=1,2,...,nつまり任意の成分がaiで表わされるn個の成分からなるベクトルAおよびA−101B=(bi)i=1,2,...,nつまり任意の成分がbiで表わされるn個の成分からなるベクトルBの各成分に一を加えることで、pを法とするベクトルA−103A′=(a′i)i=1,2,...,nつまり任意の成分がa′iで表わされるn個の成分からなるベクトルA′およびA−103B′=(b′i)i=1,2,...,nつまり任意の成分がb′iで表わされるn個の成分からなるベクトルB′(但し、(a′i,b′i)≠(0,0)つまりベクトルA′およびB′の成分には零は含まれていない)を生成し、
ベクトルA′,B′のそれぞれの成分の内の同じ次元同士の値をpを法として積で演算し、演算結果として出力されたA−103C′=(c′i)i=1,2,...,nつまり任意の成分がc′iで表わされるn個の成分からなるベクトルC′の各成分の値からpを法として一を引いた値を生成することで実質的に法をp−1とし、
各成分を次元の順にならべて法をp−1(pから一を減じた値)とする数ベクトルA−102C=(ci)i=1,2,...,nつまり任意の成分がciで表わされるn個の成分からなるベクトルCを得る。
という演算を行う。
という風に定義することもできる。

0055

更に、この積の演算の面白い点は、一言でいえば二つまたはそれ以上の未知数の積となることから、演算が非線型化するので生成値からは逆算不能であることである。即ち、入力値の一つが秘匿された固定値であっても逆算は不能であり、このことが和の置換との大きな違いである。
つまり、入力される固定値をx、入力される変数をy1,y2、出力値をそれぞれc1,c2とし、xy1:=c1,xy2:=c2、つまりxにy1を掛けた値はc1に等しく、xにy2を

割った値に等しくなり、y1,y2,c1,c2がそれぞれ一様かつ周期性のないランダムビット若しくは擬似ランダムビットからなるベクトルであれば、いずれの値も情報理論的に不確定である。

y2=ky1であるからp−1(pから一を減じた値)通りのy2に対してp−1(pから一を減じた値)通りのy1となることによって情報理論的に値を確定させることができない。
法pにおける積の演算結果が一様であることの証明は、

つまり、零を上回り素数pを下回る、つまり一を下回らず素数pから一を減じた値を上回らない任意の値a,b,cと任意の整数mとzがあるとき
a×b≡c mod.p,a×b=z,z=cx−mpが成り立っているとする。
つまり、aにbをかけた値が法pでcに合同であり、aにbをかけた値がzに等しく、zはcにxをかけた値からmとpをかけた値を減じた値に等しいとする
x=0のとき、z=−mp≡0であるからz≡0
つまり、xが零に等しい時、zはmとpをかけた値にマイナス一を掛けた値に等しく、その値は零に合同であり、従ってzは零に合同
x=1のとき、z=c−mp≡c mod.pであるから
つまり、xが一に等しい時、zはcからmとpをかけた値を減じた値に等しく、その値はcに合同であるから
c=1のとき、z=1
つまり、cが一に等しい時、zは一に等しい
c=2のとき、z=2
つまり、cが二に等しい時、zは二に等しい

c=p−1のとき、z=p−1
つまり、cがpから一を減じた値に等しい時、zはpから一を減じた値に等しい
x=2のとき、z=2c−mp≡2c mod.pであるから
つまり、xが二に等しい時、zはcを二倍した値からmとpをかけた値を減じた値に等しく、その値はcを二倍した値に合同であるから
c=1のとき、z=2
つまり、cが一に等しい時、zは二に等しい
c=2のとき、z=4
つまり、cが二に等しい時、zは四に等しい

つまり、cがpから一を減じた値を二で割った値に等しい時、zはpから一を減じた値に等しい

つまり、cがpから一を減じた値を二で割った値に更に一を加えた値に等しい時、zはpに一を加えた値に等しく、その値は一に合同である

つまり、cがpから一を減じた値を二で割った値に更に二を加えた値に等しい時、zはpに三を加えた値に等しく、その値は三に合同である

c=p−1のとき、z=2(p−1)≡p−2 mod.p
つまり、cがpから一を減じた値に等しい時、zはpから一を減じた値に二を掛けた値に等しく、その値はpから二を減じた値に合同である

x=p−1のとき、z≡(p−1)c mod.pであるから、
つまり、xがpから一を減じた値に等しい時、zはcにpから一を減じた値を掛けた値に合同であるから
c=1のとき、z≡p−1 mod.p
つまり、cが一に等しい時、zはpから一を減じた値に合同
c=2のとき、z=2(p−1)≡p−2 mod.p
つまり、cが二に等しい時、zはpから一を減じた値に二を掛けた値に等しく、その値はpから二を減じた値に合同

c=p−2のとき、z=(p−1)(p−2)≡2 mod.p
つまり、cがpから二を減じた値に等しい時、zはpから一を減じた値とpから二を減じた値の積に等しく、その値は二に合同
c=p−1のとき、z=(p−1)2≡1 mod.p
つまり、cがpから一を減じた値に等しい時、zはpから一を減じた値の二乗に等しく、その値は一に合同
よって、a,bが一からp−1までのp−1通りの値をとるとき、cも一からp−1までのp−1通りの値をとり、且つ(a,b)とcの関係は全単写、即ち置換である■
そこで、x,y1,y2がp−1(pから一を減じた値)を法とする値であり、このとき演算にあたってx,y1,y2の各成分に法pで一を加えることで零を消し、法pで積の演算を行えば、演算結果はやはり零を含まず、且つ一からp−1(pから一を減じた値)までの値を一様に出現させることができる。
因って、このような置換では演算は完全に一方向(非可逆)となる。
Shannonの情報理論では複数の平文を一つの暗号鍵で暗号化すれば情報理論的に解読可能になるとされている。
何故なら、例えば二つの平文MiとMjを一つの暗号鍵Kで暗号化するということは、単純に|Mi|+|Mj|のデータ長を持つ平文を暗号化することに等

定性は平文の不確定性を下回ることになり、暗号化は計算量的完全性しか持ち得ない。即ち情報理論では解読可能ということになる。
暗号化(暗号文生成処理)がXORを含むベクトル和による場合は理屈としては確かにその通りであるが、
実際には更に悪いことに、計算量によらず、高々二つの暗号文を法二と法Nにおいて連立方程式で処理することによって暗号鍵Kが差分において求まることから極めて容易に解読されてしまうという問題がある。つまり、P≠N予想(P対NP問題)の問題とは無関係に、つまり計算量の問題とは全く無関係に解読できてしまうということである。
このことによって、全ての非対称鍵暗号つまり二重鍵暗号は鍵を固定値として用いる限りにおいて、どんなに逆算困難な形で暗号鍵が生成されたとしても、そのこととは全く無関係に容易に解読することが可能であると言える。
ところが、積(内積)による場合は解読不能であることになる。
また、もしそうであるならば、たとえ公開鍵(非対称鍵)方式であっても、この積による置換を用いることで完全秘匿で解読不能とすることができることになる。

0056

次に、擬似ランダムビット生成器を用いて置換装置を構成する場合、生成された擬似ランダムビットは変数として用いられるわけであり、他の値、n個の成分数を有するベクトルであって法Nにおいてその不確定性HがH=log2Nn
つまり不確定性Hが底を二とするNのn乗の対数
である値を置換するために用いられるわけであるから、一様性や周期性に関しては、暗号化の完全秘匿という点ではさほど気にする必要はないはずである。つまり、真正ランダムのビット列にどのようなビット列をベクトル和あるいは内積しても真正ランダムであることには全く影響を与えない。

0057

ところが、折り畳む方式でも元になる擬似ランダムビットに周期性があれば、周期性のあるもの同士を足し合わせる若しくは掛け合わせるわけであるから、生成値にも周期性が生じることになり、従って暗号鍵生成モデュールにおける置換装置にそのような擬似ランダムビット生成器が使われると、その周期スパンの計算量によって攻撃可能となる。周期のスパンをλとすれば、法Nのとき、log2Nλの不確定性となる。当然、一つの周期に含まれる成分数は全体の成分数よりも少ない訳であるから、その場合、計算量的完全秘匿または、解読可能となる。

0058

抜き取る方式でも、抜き取りをランダムに行えば、もし元の擬似ランダムビットに周期性があったとしてもその周期性を消せるかも知れないが、今度は非線型性を持たせることが困難になる。従って、やはり生成結果に周期性が残ることになる。また、元の擬似ランダムビットに一様性がなければ、抜き取りの結果、更に一様性が失われる危険性がある。いずれにしても計算量的完全秘匿、または解読可能である。

0059

擬似ランダムビットの生成そのものが非線型な擬似ランダムビット生成器であっても、生成値に周期性があれば、やはり、log2Nλ
つまり二を底とするNのλ乗の対数
の不確定性しかなく、計算量的完全秘匿または計算量的に解読可能である。

0060

従って、元になる擬似ランダムビットは、周期性がなく、且つ、一様性のあるものでなければならない。
また、入力値であり変数であるシードriとして、時間データのような連続的に変化するデータを用いる場合には、当然のことながら初期値鋭敏性が要求される。

0061

そこで以下では、周期性がなく、一様性があり、且つ初期値鋭敏性のある擬似ランダムビット生成器とその非線型化について述べる。

0062

図25は本発明の擬似ランダムビット生成器、A−002擬似ランダムビッ

擬似ランダムビット生成器は、
シードであるベクトルaと生成するべき成分数|A|を入力値として受け取り、生成に伴って伸長されるベクトルの成分数を監視し、成分数の過不足を判定して不足であれば入力または生成されたベクトルをA−301セパレータに送るようA−203ベクトル配列生成部に指示し、十分であればA−203ベクトル配列生成部に通知してA−203ベクトル配列生成部において生成されたベクトルをA−203ベクトル配列生成部から受け取って外部に戻す働きをする
A−201データ長管理部と、
受け取ったベクトルを二つのベクトルに分割してA−202表演算部に送出する
A−301セパレータと、
A−301セパレータから受け取った二つのベクトルを2次元の表の第一列と第一行に配置し、生成値を含む行方向および列方向の複数の成分に和または積の演算を行うことによって演算表を生成する
A−202表演算部と、
A−202表演算部において生成された表の成分から列ベクトル毎にデータを抜き出し、新たなベクトルとして配列を生成し、データ長管理部からの指示に基づいて送出する
A−203ベクトル配列生成部と
から構成され、

0063

シードであるベクトルaと生成する擬似ランダムビットの成分数|A|をA−201データ長管理部に入力すると、A−201データ長管理部はベクトルaの成分数が|A|を下回れば、つまり、|a|<|A|ならばベクトルaをA−301セパレータに送り
A−301セパレータはベクトルaをベクトルV1とV2に分割(但し|a|=|V1|+|V2|。
つまりV1の成分数とV2の成分数を足したものはaの成分数に等しい)してA−202表演算部に送り、
(1)A−202表演算部はベクトルV1、V2をそれぞれ二次元の表の第一行と第一列に配置し、表の各成分に対して行方向の複数の成分と列方向の複数の成分を用い(但し、例えば第二行第二列成分ではV1の第一成分とV2の第二成分を用い、第二行第三列成分ではV1の第一成分と第二行第二列成分とV2の第二成分を用いるという風に、一つの成分しか用いることができない場合は一つの成分だけを用いる)自然数Nを法として和または素数pを法として積または積と和を行うことにより二次元の演算表を生成し、
例えば、全ての演算を和とするならば、行方向に演算される成分数をψ、列方向に演算される成分数をξとする時、任意の成分をaijとすれば、

つまり、aijで表わされる二次元の表の第i行第j列の成分は、自然数Nを法として、aijが属する列のaijの一つ上の行つまり第i−1(iから一を減じた値)行目から上に第ψ番目の行つまり第i−ψ(iからψ(二を下回らない自然数)を減じた値)行目までの全ての成分を足し合わせた値と、aijが属する行のaijの一つ左の列つまり第j−1(jから一を減じた値)列目から左に第ξ番目の列つまり第j−ξ(jからξ(二を下回らない自然数)を減じた値)列目までの全ての成分を足し合わせた値を足し合わせた値に合同
その生成結果から第一列成分と第一行成分を除いた成分(生成結果を行列に見立

について列ベクトル毎にまたは行ベクトル毎に成分を取り出したベクトル
(Bj)j=1,2,...,n−1(但し、Bj=Aj+1)、
つまり、任意の成分がBjで表わされるn−1(nから一を減じた値)個の成分からなるベクトルであって、第j番目の成分がベクトルAの第j+1(jに一を加えた値)番目の成分と等しいベクトル
を生成してA−203ベクトル配列生成部に送り、
(2)A−203ベクトル配列生成部は、その取り出された列ベクトル
(Bj)j=1,2,...,n−1=(B1,B2,...,Bn−1)
つまり、ベクトル(Bj)j=1,2,...,n−1はベクトルB1からベクトルBn−1までのn−1
(nから一を減じた値)個のベクトルを成分とするベクトルの成分を展開してベクトル
B=(b1,b2,...,b(m−1)(n−1)−1,b(m−1)(n−1))
つまり、b1からb(m−1)(n−1)までの(m−1)(n−1)(mから一を減じた値とnから一を減じた値を掛け合わせた値)個の成分からなるベクトルB
を生成し、
(3)A−201データ長管理部はこの生成過程を常時チェックし、ベクトルBの成分数|B|が|A|を上回らないならばベクトルBをA−301セパレータに送って、
(4)A−301セパレータはベクトルBをベクトルV1とV2に分割(但し|B|=|V1|+|V2|。つまりV1の成分数とV2の成分数を足したものはBの成分数に等しい)してA−202表演算部に送り、
成分数|B|が|A|を下回らなくなるまで上記(1)から(4)までの過程を繰り返し、成分数|B|が|A|を下回らなくなったベクトルBを出力値であるベクトルAとして返すようにして擬似ランダムビットを生成することによって、実際の使用において用いられる程度(少なくとも数百メガバイト程度)のデータ長では全く周期性が認められず、且つ生成値は一様であり、初期値鋭敏性を持つ擬似ランダムビット生成器となる。

0064

従来の擬似ラングムビット生成方式と比較した場合の本発明における擬似ランダムビット生成器の最大の特徴は、シードが複数の成分からなるベクトルであり、そのベクトル成分を二次元に配置することで、二次元の漸化式を構成し、指数的に成分数を増やしていく点にある。生成値の一様性を確保するには、演算に自然数を法とする場合は和のみ、素数を法とする場合は和および積が使えるが、和のみの演算が高速である。そこで以下では煩雑になるのを避けるため和のみの場合について説明する。
尚、生成過程に積の演算がある場合は非線型の擬似ランダムビット生成器となる。
また、和のみの場合でも演算段階ごとに生成値の組み換えが行われることから弱い非線型性がある(法をNとする時、一つの演算段階ごとにlog2Nビット(二を底とするNの対数。場合の数(確率の逆数)Nのビット表記))の不確定性が生まれる)。

0065

その前に、二次元の表による演算と高次元の表による演算について若干補足する。本発明の擬似ランダムビット生成器による方式では、表演算部における演算処理をn次元の表から二次元の表に還元して処理し、その生成値を再利用して次のシードとして順次n次元まで高次元空間を生成していく。ところが、同じようにベクトルを用いて指数的に成分数を増加させる方式として、最初からn次元の表を一気に作る(一括処理する)方式がある。これは、シードのベクトルをn個に分割して、n個のうちの最初の二つの成分から二次元の表を作成し、この表を配列生成部でベクトルに変換して次の演算表の一つの次元(第一行成分)とし、n個のうちの三番目のベクトルをもう一つの次元(第一列成分)として追加して再び二次元の表を作成し、以下同様にして第n次元でそのまま順次演算処理するのと数学的な構造は同じである。つまり、そうした方式でも演算表は二次元の表の演算に還元することができる。

0066

尚、この場合、上記セパレータは入力されたベクトルをV1からVnまでn個に分割して表演算部に送り、表演算部で順次消費されることになる。その結果、そのような方式では前の段階の生成値を再びシードとして利用するような利用の仕方ができないので、伸長されるデータサイズにシードサイズによる限界があることから、本発明の擬似ランダムビット生成器のように一つのシードから理論上無限に擬似ランダムビットを生成し続けるということはできない。

0067

からなるベクトル)の二つに分割して二次元の表のそれぞれ第一列と第一行に配

m1行n1列からなる表)を作る。ここでaijはψ、ξをそれぞれ行方向、列方向で

分がaijで表わされる二次元の表の第i行第j列の成分は自然数Nを法として、aijが属する列のaijの一つ上の行つまり第i−1行目から上第i−ψ行目までの全ての成分を足し合わせた値と、aijが属する行のaijの一つ左の列つまり第j−1列目から左第j−ξ列目までの全ての成分を足し合わせた値を足し合わせた値に合同)とし、ここまでを演算の第一段階とする。次に、表A1から第一行と第一列を除い

ル)の二つに分割し、二次元の表のそれぞれ第一列と第一行に配置して表

これを演算の第二段階とする。この第二段階の演算を必要なデータ長が得られるまで、または処理するコンピュータの処理能力において可能な範囲まで繰り返すことで擬似ランダムビットを生成する。

0068

ここで、各段階における生成値からそのシードを逆算することを考えると、本発明の擬似ランダムビット生成器にはそのままでも弱い一方向性があることがわかる。即ち、今、a22成分について見ると、a22成分はa21とa12の法をN∈

になる。従って、演算の一段階ごとにN通りの組み合わせが存在し、N=28(Nは二の八乗に等しい)ならば演算一段階について八ビットの不確定性(エントロピー)が生じ、演算十段階では八十ビットの不確定性となる。つまり280(二の八十乗)個の全ての可能な組み合わせを作ったとして、そのうちの一つが本当に使われたシードである。
そこで、N=28(Nは二の八乗に等しい)でシードの成分数を三十二とし、n1=n2=…=3(n1もn2も全部三に等しい)、ξ=ψ=3(ξもψも三に等しい)で生成する場合を考えると、演算十段階で百六十二万三千八百五十二バイト(約一.五五メガバイト)の擬似ランダムビットが生成される。生成速度は演算をベクトルとして扱うことによって法を小さくできる(但し、XORではなく法N>2(Nは三を下回らない)のベクトル和)ことから、一般的な従来技術と比べて格段に処理を軽量化できる(従来技術ではこの法の値を極力大きく設定するようにしていた)。例えば三十二バイトのシードから十メガバイト生成にかかる生成時間では、Java言語によるプログラムで、2007年において標準的と考えられる二.三ギガヘルツ動作のパーソナルコンピュータでほぼ三百ミリ秒である。速く

とき、n×n=n2(n×nはnの二乗に等しい)とすることが最も効率的であるが、演算段階数が減ることから不確定性が小さくなるという問題が生ずる。

0069

一方向性を強化するには、単純には表を三次元化する形が考えられる。そこでa222成分について見ると、a211、a121、a112成分の組み合わせはN2(Nの二乗)通りとなるから、演算十段階でN20(Nの二十乗)通り、N=28(Nは二の八乗に等しい)ならば百六十ビットの不確定性となる。ところが、三次元化すると演算五段階で百四十九万九百九十四バイト(−.四二メガバイト)生成されるので、結局その辺りのサイズでは不確定性は八十ビットしか生成されない。

0070

生成値の周期性に関しては、所謂M系列を単に二次元化したような形であるにも関わらず、生成の手続き自体が演算段階ごとにシードとなる成分の組み換えを行うものであり、さらに二次元の演算処理の中で値の入念な攪拌が行われ、更に、二次元で生成された成分を列ベクトルまたは行ベクトル毎に抽出して生成するものであることから、周期性は少なくとも実用の範囲において全く存在しないと考えられる。実際、法N=28、シードサイズ三十二バイトで十メガバイトの擬似ランダムビットを生成し、生成値の先頭のビット列が生成値の中に現れる頻度をとってみても、先頭二バイトのデータと一致する成分の並びが現れる頻度は一千回の試行で1つの生成値について百五十〜百七十個出現したが、これは理論値の百六十(百六十=十×千二十四の二乗÷二百五十六の二乗、つまり百六十は十に千二十四の二乗を掛けて、それを二百五十六の二乗で割ったものに等しい)にほぼ等しく、先頭四バイトでは稀にしか出現せず(理論値は一つの生成値に零.零零二四四一回、検査では一千回の生成で二回出現)、先頭5バイト以上では実際上ほとんど出現せず(一千回の試行では一度も出現せず)、期待値(理論値)通りである。

0071

一様性に関しては、シードの成分が全て零でない限りにおいて、演算四段階目から五段階目で法Nにおけるすべての値の出現率(数)がほぼ一様になる。つまり、例えばシードサイズが三十二バイトのとき、一キロバイト程度を生成するだけでほぼ一様な擬似ランダムビットが得られる。

0072

初期値鋭敏性に関し、本発明の擬似ランダムビット生成器は行方向、列方向共に長い腕を持つことから、シードであるベクトルの成分の値を何重にも取り込むことによって成分の小さな値の変化を増幅して敏感に反映し、その変化を演算段階ごとの組み換えが更に増幅し、一つの成分の値が一違うだけでも全く異なる擬似ランダムビットを生成する。

0073

次に、擬似ランダムビット生成器の一方向化(非可逆化)について説明する。
抜き取り方式は、
そもそも本発明の擬似ランダムビット生成器ではa22成分に関し、a21とa12の組み合わせがN通り存在することによってナチュラルに不完全ながら非可逆性を生じていたわけであるが、これを全てのシードの成分についても成立するよう、

値は確定しないことになる。
但し、この抜き取り処理をするための負荷と、生成される成分数そのものが減少することによって、生成速度を含む生成効率がかなり大幅に低下することになる具体的には、生成においてaijを算出するための少なくとも二つの成分が未知数となれば良いわけであるが、いずれにしてもN通りのa21とa12の組み合わせを決めると、第二行目の成分と第二列目の成分だけからシードの部分ベクトル(a12,a13,...,a1,ξ+1)つまり、a12,a13,...,a1,ξ+1のξ個の成分からなるベクトルと(a21,a31,...,aψ+1,1)つまり、a21,a31,...,aψ+1,1のψ個の成分からなるベクトルが差分で求まってしまう。従って他のどの成分を抜き取ったとしても、このままでは一つの演算段階の不確定性はlog2Nビットつまり二を底とするNの対数(場合の数(確率の逆数)のビット表記)であって、つまりN通りのままである。

0074

そこで、図26を使って説明すると、
図26はa11成分のない行列A=(aij)の一部左上隅の部分を抜き取って表した図である。
Aから第一列に加えて第二列と第一行に加えて第二行を抜き取ることを考え、こ

み合わせはN通り。これにa31を加えた組み合わせはN2(Nの二乗)通り。更にa13を加えた組み合わせはN3(Nの三乗)通り。以下同様にして、行方向、列方向にN(未知数の個数)−1(Nの[未知数の個数から一を減じた値]乗)通りの組み合わせが実現し、第一列目と第一行目だけでシードの不確定性を下回らない不確定性が実現すると考えられる。

0075

ところが図27は前記の行列A=(aij)の左端を含む部分の成分の配列を表したものであるが、
aijは、ψ、ξをそれぞれ行方向、列方向で足し合わせる成分数とするとき、

つまり、任意の成分がaijで表わされる二次元の表の第i行第j列成分は、全ての演算が和であるならば、aijが属する列のaijの一つ上の行つまり第i−1(iから一を減じた値)行目から上に第ψ番目の行つまり第i−ψ(iからψ(二を下回らない自然数)を減じた値)行目までの全ての成分を足し合わせた値と、aijが属する行のαijの一つ左の列つまり第j−1(jから一を減じた値)列目から左に第ξ番目の列つまり第j−ξ(jからξ(二を下回らない自然数)を減じた値)列目までの全ての成分を足し合わせた値を足し合わせた値に合同

成分)についてみるとai,j−1≡(ai2+…+αi,j−2)+(ai−ψ,j−1+…+ai−1,j−1)であるから、容易にai2(aijが含まれる行の第二列目の成分)が求まってしまう。すると同様にai1(aijが含まれる行の第一列目の成分)が求まり、従って、i行目以下の全ての未知数成分が求まることになる。
列方向についても同様に、j列目以降の全ての未知数成分が求まる。つまり部分解読される。これでは複数の演算段階を持ったとしても、計算量的な完全性しか持ち得ない。

0076

との成分とξ+1列ごとの成分が抜き取られる必要がある。今、αi,j−1(αijの左隣の成分)についてai−ψ,j−1(aijの左隣にあって、ψ行上の成分)が未知数であれば、ai2(aijが含まれる行の第二列目の成分)はN通りとなる。

行を除き、且つ、ψ+1行ごとの行成分とξ+1列ごとの列成分を除いた余因

ij成分がBijで表わされる成分からなる行列である。この時、Bij自身も行列。
つまり(Bij)は、行列Aから第一行と第二行および2+ψm行(但しm=1,2,...)及び第一列と第二列および2+ξn列(但し、n=1,2,...)を除いた行列Aの余因子行列である。

0077

このような成分の抜き取り処理を行う装置が図29から図31に記載のA−302一方向化エクストラクタであって、
A−302一方向化エクストラクタは、

のij成分であるaijの演算対象となる成分が、
第i−1行目の成分であるai−1,jから列方向に第i−ψ行目の成分であるai−ψ,jまでのψ個と、
第j−1列目の成分であるai,j−1から行方向に第j−ξ列目の成分であるai,j−ξまでのζ
とすれば、

その第一行と第二行および第2+ψm行(但しm=1,2,...)
及び第一列と第二列および第2+ξn列(但し、n=1,2,...)
を除いた前記行列の余因子行列を生成し、その余因子行列の各列ベクトルまたは行ベクトルを並べて一つのベクトルとして生成し出力する装置である。

0078

演算段階毎にこのような処理を行うか、または少なくとも演算の最終段階においてこのような処理を行うことにより、全ての演算が和であっても二次元の線型漸化式による非線型な擬似ランダムビット生成が実現する。
ソフトウェアによる処理の場合は演算の最終段階でのみこうした処理を行うようにすることで生成効率の面で処理の高速化が図れ、
また、LSI等、専用のハードウェアで処理する場合はコスト対効果の問題があることから演算の各段階で処理するようにしても良い。

0079

て、シードと同じサイズにするようにすれば、完全非可逆(一方向)な置換となり、演算段階毎にこのような処理を行うかまたは少なくとも演算の最終段階においてこのような処理を行うことにより、全ての演算が和であっても二次元の線型漸化式による非線型な擬似ランダムビット生成による置換が実現する。
ソフトウェアによる処理の場合は演算の最終段階でのみこうした処理を行うようにすることで生成効率の面で処理の高速化が図れ、専用のハードウェアで処理する場合はコスト対効果の問題があることから演算の各段階で行うようにしても良い。
しかしながら、置換の場合、何段階も擬似ランダムビット生成を繰り返しても無駄であるから通常は一段階だけの擬似ランダムビット生成になると考えられ、従ってその一段階の演算によって生成された擬似ランダムビットから抜き取り処理を行うことによって置換が成立することになる。

0080

演算に積が含まれれば二次元の非線型漸化式となり、成分の抜き取りがなくてもやはり擬似ランダムビット生成に非可逆性が付与される。
また更に抜き取り量を増やし均一に抜き取るあるいは折りたたむようにすれば完全非可逆(一方向)のハッシュ関数とすることも可能である。

0081

そこで、A−302一方向化エクストラクタによって構成される置換器は、図29および図30の構成図に示す構造を持つ。即ち、
弱い非線型性を持つ線型の擬似ランダムビット生成器であるA−002擬似ラン

よって非線型化させる置換器は、

る表(行列)をAとするとき、
A−302一方向化エクストラクタ単体から構成され、入力値Aに対し、その成分数が入力値Aの成分数|A|を下回らず且つ非線型化され情報理論的に

A−601一方向置換器(イ)と、
A−302一方向化エクストラクタとA−303ベーシックエクストラクタから構成され、A−302一方向化エクストラクタ単体から構成され、入力値Aに対し、A−302一方向化エクストラクタがその成分数が入力値Aの成分数|A|を下回らず且つ非線型化され情報理論的に逆算不能な余因子行列

をベクトルAとして出力する
A−602一方向置換器(ロ)である。

0082

折りたたみ方式は、擬似ランダムビットを、目的とするデータ長よりも長く生成し、それいくつか(任意)の成分数毎に等分に分割して、分割したそれぞれのベクトルをベクトル和若しくは内積することによって一方向性を持たせるようにする置換器であって、
図31に示すように、
弱い非線型性を持つ線型の擬似ランダムビット生成器であるA−002擬似ラン

非線型化させる置換器は、

log2N|Mi|、つまりViの不確定性H(Vi)はNの[Miの成分数乗]の二を底とする対数

の擬似ランダムビットA′を生成し、それをA−301セパレータでn個に分割し、

または、図32に示すように、

擬似ランダムビットA′を生成し、それをA−301セパレータで二つ以上に分割

とによって生成した値またはベクトルから、更に成分数を前記A−002擬似ラ

クストラクタで任意の成分を抜き取り成分数を調整するようにした置換器である。
尚、この方式における擬似ランダムビット生成器は、A−002擬似ランダムビ

トを生成するものであれば、擬似ランダムビット生成器であれば、その生成方法は線型でも非線型でも良い。
この定義は理論上の話であって、実際の運用では、入力値と同じ成分数を有する出力値を得るには、何倍にしてもその不確定性は変わらないので、最少である二倍の成分数を擬似ランダムビット生成し、それを二つに分けて、その二つに分けられたベクトル同士をベクトル和若しくは内積する形で用いることが最も効率的である。従って、他に特別な理由がない限り、n=2(nは二に等しい)で用いることになる。

0083

A−301セパレータとA−001aベクトル和型置換装置によって構成される置換器は、図31および図32の構成図に示す構造を持つ。即ち、

る表(行列)をAとし、その行列Aから生成されたベクトルをA′とするとき、
A−301セパレータとA−001aベクトル和型置換装置によって構成され、A′が入力されるとA−301セパレータはA′を等分な二つのベクトルに

のベクトルをベクトル和または内積することによって置換してベクトルAを生成し出力する
A−603置換器と、
A−301セパレータとA−001aベクトル和型置換装置とA−303ベーシックエクストラクタによって構成され、A′が入力されるとA−301セ

することによって置換してベクトルA″を生成し、A−303ベーシックエクストラクタがそのA″から任意の成分を|A″|−|A′|つまりベクトルA″の成分数|A″|からA′の成分数|A′|を引いた成分数だけ抜き取ることによって成分数|A′|のベクトルA(3)を生成し、そのA(3)をベクトルAとして出力する
A−604折畳+抜取置換器である。

0084

上記の擬似ランダムビット生成器を用いる置換装置を暗号化に用いた場合、入力値A′の不確定性が暗号化しようとする平文の不確定性を下回らないとするとき、
図29のA−302一方向化エクストラクタのみから構成される場合は計算量的完全秘匿性を持つ暗号化の必要条件を満たし、
図31の場合は、
|A′|<|A|、つまり出力値Aの成分数|A|が入力値A′の成分数|A′|を下回らず且つ出力値Aの成分数|A|が入力値A′の成分数|A′|が等しくないとき、少なくとも計算量的完全秘匿性を持つ暗号化の必要条件を満たし、
|A′|>|A|、つまり出力値Aの成分数|A|が入力値A′の成分数|A′|を上回らず且つ出力値Aの成分数|A|が入力値A′の成分数|A′|が等しくないとき、計算量的完全秘匿性を持つ暗号化の必要条件を満たし、
|A′|=|A|、つまり出力値Aの成分数|A|が入力値A′の成分数|A′|と等しいとき、完全秘匿である暗号化の必要条件を満たし、
図30および図32の場合は完全秘匿である暗号化の必要条件を満たす。

0085

図33はA−501置換装置として図29のA−601一方向置換器(イ)または図31のA−603折畳置換器を用いた計算量的完全秘匿性の必要条件を満たす処理の流れを示す図であり、
暗号化が計算量的完全秘匿性を持つための必要条件を満たすA−002擬似ラン

一または複数のベクトルと、出力するベクトルの成分数|A|を入力し、
入力されるベクトルが複数の場合はA−401連結装置でそれら複数のベクトルを連結して一つのベクトルとし(入力値が二つのベクトルa、bであればそのa、bを連結した一つのベクトル(α‖b)を生成し)、

−201データ長管理部で算定し、
その連結された一つのベクトル前記(a‖b)をシードとしてA−002擬似ランダ

その行列A′をA−601一方向置換器(イ)またはA−603折畳置換器からなるA−501置換器に入力して非線型な置換をして成分数|A|を有するベクトルAを得る。
このとき、A−501置換装置が
A−603折畳置換器であって、入力値である複数のベクトルの内の少なくともいずれか一つのベクトルが暗号化しようとする平文の不確定生成を下回らない不確定性を有し、且つ、出力値の成分数が入力値の内の暗号化しようとする平文の不確定生成を下回らない不確定性を有するベクトルの成分数と等しければ、この置換装置による暗号化は完全秘匿であることの必要条件を満たし、
A−603置換装置であって、入力値である複数のベクトルの内の少なくともいずれか一つのベクトルが暗号化しようとする平文の不確定生成を下回らない不確定性を有さず、および/または、出力値の成分数が入力値の内の暗号化しようとする平文の不確定生成を下回らない不確定性を有するベクトルの成分数と等しくなければ、この置換装置による暗号化は計算量的完全(暗号的安全)であることの必要条件を満たし、
A−601一方向置換器(イ)である場合は計算量的完全(暗号的安全)であることの必要条件を満たしている。

0086

過程の各演算段階において成分の抜き取りを行う処理の流れを示す図であって、A−501置換装置として図29のA−601一方向置換器(イ)を用いるもので、
暗号化が計算量的完全秘匿性を持つための必要条件を満たすA−002擬似ラン

(一)一または複数のベクトルと、出力するベクトルの成分数|A|を入力し、
(二)入力されるベクトルが複数の場合はA−401連結装置でそれら複数のベクトルを連結して一つのベクトルとし(入力値が二つのベクトルa、bであればそのa、bを連結した一つのベクトル(a‖b)を生成し)、
(三)その複数のベクトルが連結された一つのベクトル(前記(a‖b))をシード

ット生成し、
(四)その擬似ランダムビットをA−601一方向置換器(イ)からなるA−501置換器で非線型な置換をして行列A′を生成し、

判定し、

(ろ)|A|>|A′|であればその行列A′を再びA−002擬似ランダムビット生

ことによってベクトルAを得る。
このとき、この装置を用いた暗号化は計算量的完全であることの必要条件を満たしている。

0087

図35図33のA−501置換装置をA−602一方向置換器(ロ)またはA−603折畳置換器またはA−604折畳+抜取置換器からなるA−502置換装置に置き換えた図であって、
暗号化が完全秘匿性を持つための必要条件を満たすA−002擬似ランダムビッ

一または複数のベクトルと、出力するベクトルの成分数|A|を入力し、
入力されるベクトルが複数の場合はA−401連結装置でそれら複数のベクトルを連結して一つのベクトルとし(入力値が二つのベクトルa、bであればそのa、bを連結した一つのベクトル(a‖b)を生成し)、

−201データ長管理部で算定し、
その連結された一つのベクトル前記(a‖b)をシードとしてA−002擬似ランダ

その行列A′をA−602一方向置換器(ロ)またはA−603折畳置換器またはA−604折畳+抜取置換器からなるA−501置換器に入力して非線型な置換をして成分数|A|を有するベクトルAを得る。
このとき、入力値であるベクトルの内の少なくともいずれか一つのベクトルが暗号化しようとする平文の不確定生成を下回らない不確定性を有し、且つ、出力値の成分数が入力値の内の暗号化しようとする平文の不確定生成を下回らない不確定性を有するベクトルの成分数と等しければ、この置換装置による暗号化は完全秘匿であることの必要条件を満たす。

0088

図36図34のA−501置換装置をA−602一方向置換器(ロ)からなるA−502置換装置に置き換えた図であって、A−002擬似ランダムビッ

を行う処理の流れを示す図である。
暗号化が完全秘匿性を持つための必要条件を満たすA−002擬似ランダムビッ

(一)一または複数のベクトルと、出力するベクトルの成分数|A|を入力し、
(二)入力されるベクトルが複数の場合はA−401連結装置でそれら複数のベクトルを連結して一つのベクトルとし(入力値が二つのベクトルa、bであればそのa、bを連結した一つのベクトル(a‖b)を生成し)、
(三)その複数のベクトルが連結された一つのベクトル(前記(a‖b))をシード

ット生成し、
(四)その擬似ランダムビットをA−602一方向置換器(ロ)またはA−603折畳置換器またはA−604折畳+抜取置換器からなるA−502置換器で非線型な置換して行列A′を生成し、

判定し、

Aとして出力し、
(ろ)|A|>|A′|であればその行列A′を再びA−002擬似ランダムビット生

ことによってベクトルAを得る。
このとき、入力値であるベクトルの内の少なくともいずれか一つのベクトルが暗号化しようとする平文の不確定生成を下回らない不確定性を有すれば、この置換装置による暗号化は完全秘匿であることの必要条件を満たす。

0089

上記の擬似ランダムビット生成器を用いる置換装置であって、図33から図36までの処理の流れ図において
入力値が複数で且つ出力値の成分数が入力値の成分数を上回る置換装置がA−003擬似ランダムビット生成器型置換装置(イ)
であり、
入力値が複数で且つ出力値の成分数が入力値の成分数と等しい置換装置が、A−004擬似ランダムビット生成器型置換装置(ロ)
であり、
入力値が一つで且つ出力値の成分数が入力値の成分数と等しい置換装置はA−005擬似ランダムビット生成器型置換装置(ハ)
である。

発明の効果

0090

暗号化が完全秘匿であり、秘密鍵が完全秘匿または計算量的完全秘匿であるならば、使い捨て公開変数riを暗号文に添付して送受信および/または保管することが可能となる。つまり、今本発明の暗号化を関数fとするならば、秘密鍵は装置またはシステムの一部と看做すことができ、暗号鍵は処理の過程の一つと看做されるから、
暗号化fはf(ri,Mi)≡Ei(つまり、暗号文Eiは使い捨て公開変数riと平文Miを関数に入力して得られる値に合同)という形で書き表され、
本発明の暗号化では入力値である変数が漏洩しても暗号文は完全秘匿即ち解読不能であり且つ秘密鍵も完全秘匿性を持つわけであるから、
送受信および/または保管される送信文TiはTi=(ri‖Ei)=(ri‖f(ri,Mi))(つまり、送信文Tiは使い捨て公開変数riと暗号文Eiを連結したベクトル)という形で使い捨て公開変数riを暗号文Eiに添付可能となる。
従って攻撃者によって送信文Tiを盗まれても解読されることはなく、また保管時において従来方式のデータベースで送信文Tiを特に暗号化を必要としないデータと同様に管理しても、データベース管理者あるいはシステム管理者によってさえ、その暗号化によって秘匿すべきとされた情報が漏洩することはなく、暗号をかけた本人は少なくとも二つの秘密鍵を秘匿管理すれば足りる。

0091

また、少なくとも二つの秘密鍵を用い、万が一一つの秘密鍵が漏洩しても残りの秘密鍵による計算量的完全秘匿性が働くことから、ユーザの秘密鍵の管理が容易になる。たとえば、秘密鍵を別々の媒体に保管するようにしても良いし、あるいは一つの秘密鍵に指静脈などの生体情報を用いることによって、秘密鍵の秘匿管理および使い勝手の容易性を格段に高めることができる。

発明を実施するための最良の形態

0092

本発明は特定の使用目的に対して発明された暗号処理の装置および方法に関するものではなく、暗号化に関し完全秘匿であり且つ秘密鍵の秘匿に関し計算量的完全秘匿もしくは完全秘匿である暗号処理の装置および方法に関するものであり、技術は使用目的に対して最良か否か判断されるものであるから、本発明の「実施するための」最良の形態は、その使用目的やユーザの能力あるいはユーザのニーズ等によって異なり、従って一つに絞り込むことは不可能若しくは無意味または非論理的である。

0093

暗号化が完全秘匿であると同時に、秘密鍵の秘匿の完全性に関しても完全秘匿であることが全ての暗号処理に関する装置および方法の本来の目的であると考えられるが、
実施場面においては、必ずしもそのような装置及び方法が最良とは言い切れない。

0094

例えば、図10から図19に示したような装置および方法、つまり秘密鍵がいずれもその暗号化しようとする平文の不確定性を下回らない不確定性を有する装置と方法では、暗号化および秘密鍵の秘匿に関し完全秘匿であるが、いずれの秘密鍵も平文の不確定性を下回らないとすれば、大きな秘密鍵であるから必ず媒体等に保管する必要があり、その保管が悪ければそこから機密情報の漏洩を起こすことになってしまう。あまり機密性の高くない情報を扱う一般ユーザにはあまり適さない装置及び方法である。しかしながら、極めて高い機密性を要求される情報の秘匿には最良の装置および方法であると考えられる。しかも構造的にはシンプルである。

0095

そこで図20に示したように一つの秘密鍵を小さくし、秘密鍵の秘匿に関しては計算量的完全秘匿性を持たせるようにすれば、その小さな秘密鍵を短いテキストデータあるいは生体情報とすることが可能となり、毎回入力するようにすることで、もし平文の不確定性を下回らない大きな秘密鍵が盗まれたとしても、小さな秘密鍵の不確定性によって計算量的完全で機密情報を守ることができる。モニタリングスパイウェアによって短いテキストデータあるいは生体情報として入力される秘密鍵の情報が盗まれない限り、今日的には機密情報が解読されることはない。さほど機密性の高くない情報を扱う一般ユーザには最良の装置および方法であると考えられる。
但し、図20のような装置および方法であっても、更にもう一つ秘密鍵を追加して、置換装置を追加することによって、図38から図40に示すように(図38から図40に示すものに限らず、同じ構造を持ちながら置換装置の多数の組み合わせ(置換装置のヴァリエーションを除いても、少なくとも六の二乗かける五かける二通り、つまり少なくとも三百六十通り)が存在する)、暗号化と秘密鍵の秘匿に関し完全秘匿である装置および方法とすることも可能である。しかしながら、更に秘密鍵が増えることで、一般ユーザのレベルでは秘密鍵の管理が煩雑化し、そのことで却って機密情報の管理に穴が開きやすいという問題がある。但しプロユースにおいては望ましい装置および方法である。

0096

次に、装置及び方法としての技術的な立場から最良の方法を探れば、
この装置および方法がプログラムであっても、カスタムLSIのようなハードウェアであっても、その部品(モデュール)の種類、点数が少ないほど資源効率が高く、一般的には処理速度も速くなる。従って、全ての置換装置を一つの種類で

またはA−004擬似ランダムビット生成器型置換装置(ロ)、またはA−002

(ハ)を組み合わせた置換装置を用いることが考えられる。
ところがM−1200暗号文生成モデュールでは、A−004擬似ランダムビット生成器型置換装置(ロ)やA−004擬似ランダムビット生成器型置換装置

ビット生成器型置換装置(ハ)を組み合わせた置換装置のようにA−302エクストラクタを用いる方式では情報量の欠落が起こることから、復号できなくなってしまうので、この部分に用いることができない。従って、全体を一つの置換装

る。

0097

処理速度から見れば、積の演算よりも和の演算の方が圧倒的に処理速度が速

用いるようにすることが考えられる。また、A−004擬似ランダムビット生成器型置換装置(ロ)であっても、A−301セパレータとA−001aベクトル

全体としてもきわめて高速な処理が可能である。
そこで、資源効率をある程度考慮した装置及び方法であって処理速度的に最良の装置および方法には、
一つには、M−1110秘匿変数生成モデュールとM−1200暗号文生成モデ

またはA−004擬似ランダムビット生成器型置換装置(ロ)、またはA−002

(ハ)を組み合わせた置換装置を用いる装置および方法があり、
また一つには、M−1110秘匿変数生成モデュールの全ての置換装置に非線型のA−004擬似ランダムビット生成器型置換装置(ロ)、またはA−002擬似

を組み合わせた置換装置を用い、M−1120不可視化モデュールの置換装置とM−1200暗号文生成モデュールの置換装置を全てA−001aベクトル和型

上記二つの装置及び方法の内、いずれの装置および方法が速いかについては、プログラム言語やハードウェアにもよるので、一概には決められない。より詳細な設計が必要であり、その結果更なるテューンナップも可能であると考えられる。

間のかかる処理は特に復号処理であって、復号において逆数をループ処理または逆数の一覧表の中から検索で見つけ出す処理負荷がきわめて大きい訳であるが、この処理を何らかの装置および/または方法によって高速化できるのであれば、

良の選択となる。

0098

上記の中からいずれか一つを採り上げて実施例を示すならば、シンプル且つ使い勝手もまずまずであると考えられ、暗号化および秘密鍵の秘匿の完全性が完全秘匿である図39の装置および方法を図1とともに用いて説明する。

0099

使用に当たってユーザは最初に秘密鍵S1、S2、S3とするデータを決める。ここで、秘密鍵S1は三十二バイトつまり二百五十六ビットを下回らないデータ長を持つテキストデータ、または指静脈などの生体情報または生体情報を複数組み合わせたデータとし、秘密鍵S2およびS3は一メガバイトを下回らないデータ長を持つデータであって、スキャナで読み込むことでディジタル化したデータ、あるいは趣味写真データ、あるいはディジタルデータ化された音楽などとする。
ここで、ユーザによる秘密鍵の設定がそれぞれに定義されたデータ長を下回らないものであれば、処理にあたってシステムがデータ長をそれぞれのデータ長、つまり秘密鍵S1は三十二バイトつまり二百五十六ビットに、秘密鍵S2およびS3は一メガバイトに、データ長を調整して用いるものとする。

0100

ユーザが暗号化処理を開始すると、
システムは使い捨て公開変数riをミリ秒単位の時刻データから取得または生成し、M−1110秘匿変数生成モデュールにおいてA−001aベクトル和型置換装

ガバイトまで伸長して変数Riを生成し、

ことによって暗号鍵Kiを生成する。

0101

そこでユーザが暗号化しようとする平文Miを指定すると、
システムはその平文Miと前記暗号鍵KiをM−1200暗号文生成モデュールで

その暗号文EiにM−2000公開変数添付モデュールにおいてA−401連結装置を使って使い捨て公開変数riを添付して送信文Tiを得る。
ここで、平文Miが秘密鍵S2およびS3のデータ長一メガバイトを下回らない場合は、一メガバイトの単位でブロック暗号処理されることになる。

0102

ユーザが復号処理を開始すると、
システムは送信文Tiから使い捨て公開変数riと暗号文Eiを抽出し、
M−1110秘匿変数生成モデュールにおいてA−001aベクトル和型置換装

ガバイトまで伸長して変数Riを生成し、

ことによって暗号鍵Kiを生成し、

マイナス一倍したベクトルとをベクトル和することによって置換して平文Miを得る。

0103

送信文Tiが送受信される場合であって、復号処理を行うユーザが暗号化処理を行うユーザと異なる場合、その送信文Tiの受信者側での保管に当たっては、そのままの状態で保管することも可能であるが、特に社内文書として保管する場合は、社内専用の秘密鍵で暗号化することが望ましい。秘密鍵を秘密分散や多重分散などの方法で分散保管し、分散認証などを用いた認証システムでアクセスパーミッションを与えるようにして管理することによってユーザ自身は秘密鍵の情報を一切知ることなく、会社内で統一的に用いることが可能となる。

0104

また最初の秘密鍵の交換についても、上記の秘密分散や多重分散を用いた方法でパーミッションを設定することで鍵交換不要とすることが可能である。

0105

鍵交換を行う場合は、秘密鍵とする情報を一メガバイトを上回らないデータ長に圧縮して暗号化し送受信することで、直接受け渡しすることなく、完全秘匿に鍵交換することが可能となる。

0106

つまり、送信者A受信者Bがともに本発明のいずれかの暗号処理の装置および方法を用い、AはAの秘密鍵を使ってこれから共有しようとする秘密鍵を暗号化して送信し、それを受信したBはBの秘密鍵でその暗号文を暗号化してAに送信し、AはAの秘密鍵を使ってそれを復号してBに送信し、BはBの秘密鍵を使って復号することによって共有しようとする秘密鍵を得ることができる。
但し、この方法では秘密鍵のサイズを超える対象を暗号化するにはブロック暗号となるため、正確な復号が行われず、従って、対象である共有しようとする秘密鍵の情報はAおよびBの秘密鍵のサイズ(上記の例では一メガバイト)を下回らなければならない。また、AとBの秘密鍵のサイズ(上記の例では一メガバイト)が異なっても処理は正確に行われないことから、全く同じ装置および方法を用いる必要がある。

0107

また、継続的な通信を行わない場合、例えば契約書の送受信などにおいて、ほぼ一回限りの送受信を秘密鍵の交換をすることなく完全秘匿に暗号通信することが可能である。その装置および方法は上記鍵交換とまったく同じ方法による。

図面の簡単な説明

0108

本発明における暗号処理の装置および方法の全体的な構成と処理の流れを示す図である。 本発明における暗号処理の装置および方法の基本的な構造単位の構成と処理の流れを示す図である。 本発明における暗号処理の装置および方法の内、擬似ランダムビット生成器型置換装置(イ)の処理の流れを示す図である。 本発明における暗号処理の装置の内、擬似ランダムビット生成器型置換装置(ロ)の処理の流れを示す図である。
本発明における暗号処理に関し、暗号鍵生成モデュールに秘匿変数生成モデュールを組み込んだ場合の構成と処理の流れを示す図である。 本発明における暗号処理に関し、暗号鍵生成モデュールと暗号鍵との間に非可逆処理モデュールを組み込んだ場合の構成と処理の流れを示す図である。図6をやや具体化し、且つ暗号文生成モデュールまで構成と処理の流れを示した図である。図7をやや具体化し、且つ暗号文生成モデュールまで構成と処理の流れを示した図である。図8図9をまとめた図である。 本発明における暗号処理に関し、暗号文と秘密鍵に関し完全秘匿である装置の基本的構成と処理の流れを示す図である。図11の変数Viを擬似ランダムビット生成されたものに置き換え、秘匿変数生成モデュールの置換装置を擬似ランダムビット生成器型置換装置(ロ)に置き換えた装置の構成と処理の流れを示す図である。図12の不可視化処理モデュールの置換装置を擬似ランダムビット生成器型置換装置(ロ)に置き換えた装置の構成と処理の流れを示す図である。 本発明における暗号処理に関し、二つの秘匿変数を用いる装置および方法の基本的な装置の構成と処理の流れを示す図である。

図16の不可視化処理モデュールの置換装置を擬似ランダムビット生成器型置換装置(ロ)に置き換えた装置の構成と処理の流れを示す図である。図14の秘匿変数生成モデュールの置換装置を二つとも擬似ランダムビット生成器型置換装置(ロ)に置き換えた装置の構成と処理の流れを示す図である。図18の不可視化処理モデュールの置換装置を擬似ランダムビット生成器型置換装置(ロ)に置き換えた装置の構成と処理の流れを示す図である。 本発明における暗号処理の暗号鍵生成モデュールに関し、二つの秘密鍵の内、秘匿変数生成モデュールの置換装置で置換されるもについて暗号鍵の不確定性を下回る不確定性を持つ場合の装置の構成と処理の流れを示す図である。 本発明における暗号処理の秘匿変数生成モデュールの基本的な構成と処理の流れを示す図である。 本発明における暗号処理の不可視化処理モデュールの基本的な構成と処理の流れを示す図である。 置換における不確定性の拡張もしくは転移を示す図である。

本発明における擬似ランダムビット生成器の表演算部における左上隅のデータの配列と成分の抜き取りによる非線型化を示す図である。 本発明における擬似ランダムビット生成器の表演算部における中ほどの行のデータの配列と成分の抜き取りによる非線型化を示す図である。 本発明における擬似ランダムビット生成器の表演算部における成分の配列と成分の抜き取りによる非線型化を示す図である。 本発明における擬似ランダムビット生成器の非線型化のための成分抜き取りのための一方向化エクストラクタを用いた一方向置換器(イ)の構成と働きを示す図である。 本発明における擬似ランダムビット生成器の非線型化のための成分抜き取りのための一方向化エクストラクタを用いた一方向置換器(ロ)の構成と働きを示す図である。 本発明における擬似ランダムビット生成器の非線型化のための折り畳みのためのセパレータを用いた折畳置換器の構成と働きを示す図である。 本発明における擬似ランダムビット生成器の非線型化のための折り畳みのためのセパレータを用いた折畳置換器+抜取置換器の構成と働きを示す図である。 本発明における置換装置であって、処理の最終工程で一方向化の処理を行うもので、暗号化が計算量的完全秘匿であるための必要条件を満たす処理の流れを示す図である。 本発明における置換装置であって、処理の各工程で一方向化の処理を行うもので、暗号化が計算量的完全秘匿であるための必要条件を満たす処理の流れを示す図である。 本発明における置換装置であって、処理の最終工程で一方向化の処理を行うもので、暗号化が完全秘匿であるための必要条件を満たす処理の流れを示す図である。 本発明における置換装置であって、処理の各工程で一方向化の処理を行うもので、暗号化が完全秘匿であるための必要条件を満たす処理の流れを示す図である。
本発明における、暗号処理の装置および方法であって、秘密鍵を三つ使って暗号文および秘密鍵について完全秘匿性を持つ装置及び方法の内、全ての置換装置を擬似ランダムビット生成器型置換装置(ロ)とした場合の構成と処理の流れを示す図である。

本発明における置換処理装置の一覧である。 本発明における暗号処理の装置および方法を示す図の内、暗号文および秘密鍵について完全秘匿である装置および方法の一つを示す図。 本発明における暗号処理の装置と方法を示す図の内、暗号文および秘密鍵について完全秘匿である装置および方法の一つを示す図。 本発明における暗号処理の装置と方法を示す図の内、暗号文について完全秘匿であり、秘密鍵について計算量的完全秘匿である装置および方法の一つを示す図である。 本発明における暗号処理の装置と方法を示す図の内、暗号文について完全秘匿であり、秘密鍵について計算量的完全秘匿である装置および方法の一つを示す図である。

符号の説明

0109

M−1000 : 暗号化モデュール
M−1100 :暗号鍵生成モデュール
M−1110 :秘匿変数生成モデュール
M−1120 :不可視化処理モデュール
M−1130 :非可逆処理モデュール
M−1200 :暗号文生成モデュール
M−2000 :公開変数添付モデュール


つ線型の置換装置。擬似ランダムビット生成器型置換装置(イ)。

持つ非線型の置換装置。擬似ランダムビット生成器型置換装置(ロ)。

である非線型の置換装置。擬似ランダムビット生成器型置換装置(ハ)。
A−101 :入力値であるベクトル
A−102 :出力値であるベクトル
A−103 :素数を法とするベクトルであって、成分に零を含まないベクトル。その素数から一を減じた値を法とするベクトルの各成分に対して、一を加えることで生成され、そのようにして生成されたベクトルの各成分から一を減じることで、その素数から一を減じた値を法とするベクトルとなる。

成要素の一つ。

器およびA−604置換器等に用いられるセパレータ。ベクトルを二つに分割する、または二つに分割したベクトルの一方を抜き取る働きをする。
A−302 : 一方向化エクストラクタ
A−303 :ベーシックエクストラクタ
A−401 : ベクトルの連結装置
A−501 : 置換器
A−502 : 置換器
A−601 : 一方向置換器(イ)
A−602 : 一方向置換器(ロ)
A−603 :折畳置換器
A−604 : 折畳+抜取置換器
A−901 : 置換装置A
A−902 : 置換装置B
A−903 : 置換装置Γ
A :行列Aまたは表A


A′ : 行列A′または表A′。
|A| : 行列Aの成分数
|A′| : 行列A′の成分数
A : ベクトルA
A′ : ベクトルA′(ベクトルAプライム)
A″ : ベクトルA″(ベクトルAトゥープライム)
A(3) : ベクトルA(3)(ベクトルAスリープライム
|A| : ベクトルAの成分数
|A′| : ベクトルA′の成分数
a :スカラー
a : ベクトルa
aij : 行列Aのij(アイジェイ)成分。つまり、第i(アイ)行第j(ジェイ)列の成分
(aij) : aij(但し、i=1,2,...,m j=1,2,...,n、つまりi(アイ)は一からm(エム)までの連続する自然数、j(ジェイ)は一からn(エヌ)までの連続する自然数)を成分とする行列A
(ai)i=1,2,...,n : n個の成分からなるベクトルAの成分表記における簡易表記
(ai)i=1,2,...,n : n個の成分からなるベクトルaiを成分とするベクトルAの成分表記の簡易表記
(a1,a2,...,an) : n個の成分からなるベクトルAの成分表記
(a1,a2,...,an) : n個の成分からなるベクトルaiを成分とするベクトルAの成分表記。
ベクトルa1,a2,...,anからなるベクトル。
(a,b,c)≠(0,0,0) : aは零に等しくなく、bは零に等しくなく、cは零に等しくないことを表す式
(B1,B2,...,Bn) : n個のベクトルB1,B2,...,Bnからなるベクトルまたは行列。特

いて生成された行列Aの列ベクトルをB1,B2,...,Bnで表わしている。

Ei : 第i回目の暗号文
H :不確定性(情報理論的エントロピー)
H(a) : ベクトルaの不確定性(情報理論的エントロピー)。確率の逆数、つまり場合の数を二を底とする対数で表したもの。場合の数のビット表記で単位はビット。等価安全性とも呼ばれる。
Ki : 第i回目の暗号化に暗号鍵として用いる変数

Viから計算によって生成された秘匿変数。ケーアイプライム。この変数が秘匿されることによって暗号化および秘密鍵の秘匿に関し完全秘匿が成立する。

Viから計算によって生成された秘匿変数。ケーアイトゥープライム。この変数が秘匿されることによって暗号化および秘密鍵の秘匿に関し完全秘匿が成立する。
Mi : 第i回目の暗号化処理で暗号化する対象となる平文
N : 和またはベクトル和において法とする値。二を下回らない自然数

p : 積または内積において法とする値。三を下回らない素数
p−1 素数pから一を減じた値。

Pi : 第i回目の暗号化処理に用いる使い捨て公開変数riまたは変数Viから計算によって生成された第i回目の暗号化に用いる

Ri : 第i回目の暗号化処理に用いる使い捨て公開変数riまたは変数Viから計算によって生成された第i回目の暗号化に用いる
ri : 第i回目の暗号化処理に用いる使い捨て公開変数
S 秘密鍵
Si : 秘密鍵Sを変数νiによって置換した第i回目の暗号化処理に用いる変数鍵

いる変数鍵

いる変数鍵

いる変数
S1 : 秘密鍵
S2 : 秘密鍵
S3 : 秘密鍵
Ti :送信文。Ti=(ri‖Ei)
Vi : 第i回目の暗号化処理に用いる変数

νi : 第i回目の暗号化処理に用いる変数であって、秘密鍵を置換するための変数

鍵S1を置換する変数

鍵S2を置換する変数

∈ :集合論における演算記号。左辺に成分、右辺に集合を入れ、左辺の成分は右辺の集合に属することを表す。
≡ :合同を表す演算記号。左辺と右辺は合同であることを表す。

= : 等しいことを表す演算記号。等号。左辺と右辺は等しいことを表す。

≠ : 左辺と右辺が等しくないことを表す演算記号。不等号

< : 右辺の値が左辺の値を上回ることを表す演算記号。
∀ : 「全て(forall)」を表す論理記号

「自然数に属する任意の(つまり自然数から適当にとってきた値)a」を表す。
f:A→B :関数fによるAからBへの写像、またはAからBへの写像f

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ