JPH032953A - 使用者識別装置 - Google Patents
使用者識別装置Info
- Publication number
- JPH032953A JPH032953A JP2066715A JP6671590A JPH032953A JP H032953 A JPH032953 A JP H032953A JP 2066715 A JP2066715 A JP 2066715A JP 6671590 A JP6671590 A JP 6671590A JP H032953 A JPH032953 A JP H032953A
- Authority
- JP
- Japan
- Prior art keywords
- test
- verification
- identification method
- identification device
- identification
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000000034 method Methods 0.000 title claims abstract description 48
- 239000013598 vector Substances 0.000 claims abstract description 34
- 239000011159 matrix material Substances 0.000 claims abstract description 14
- 238000012360 testing method Methods 0.000 claims description 28
- 238000012795 verification Methods 0.000 claims description 12
- 238000004891 communication Methods 0.000 abstract description 3
- 238000006467 substitution reaction Methods 0.000 abstract description 3
- 238000005516 engineering process Methods 0.000 abstract 1
- 230000006870 function Effects 0.000 description 4
- 230000009467 reduction Effects 0.000 description 4
- 238000013459 approach Methods 0.000 description 3
- 238000010586 diagram Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 230000003993 interaction Effects 0.000 description 2
- 238000012545 processing Methods 0.000 description 2
- LZZYPRNAOMGNLH-UHFFFAOYSA-M Cetrimonium bromide Chemical compound [Br-].CCCCCCCCCCCCCCCC[N+](C)(C)C LZZYPRNAOMGNLH-UHFFFAOYSA-M 0.000 description 1
- 101100130497 Drosophila melanogaster Mical gene Proteins 0.000 description 1
- 101100345589 Mus musculus Mical1 gene Proteins 0.000 description 1
- 230000008901 benefit Effects 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 230000008030 elimination Effects 0.000 description 1
- 238000003379 elimination reaction Methods 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 230000002452 interceptive effect Effects 0.000 description 1
- 239000007788 liquid Substances 0.000 description 1
- 229940050561 matrix product Drugs 0.000 description 1
- 239000012528 membrane Substances 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000005192 partition Methods 0.000 description 1
- 230000004044 response Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
- H04L9/302—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
-
- G—PHYSICS
- G07—CHECKING-DEVICES
- G07F—COIN-FREED OR LIKE APPARATUS
- G07F7/00—Mechanisms actuated by objects other than coins to free or to actuate vending, hiring, coin or paper currency dispensing or refunding apparatus
- G07F7/08—Mechanisms actuated by objects other than coins to free or to actuate vending, hiring, coin or paper currency dispensing or refunding apparatus by coded identity card or credit card or other personal identification means
- G07F7/10—Mechanisms actuated by objects other than coins to free or to actuate vending, hiring, coin or paper currency dispensing or refunding apparatus by coded identity card or credit card or other personal identification means together with a coded signal, e.g. in the form of personal identification information, like personal identification number [PIN] or biometric data
- G07F7/1016—Devices or methods for securing the PIN and other transaction-data, e.g. by encryption
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
- H04L9/3218—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
- H04L9/3221—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs interactive zero-knowledge proofs
Landscapes
- Engineering & Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Computing Systems (AREA)
- Theoretical Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Storage Device Security (AREA)
- Magnetic Ceramics (AREA)
- Seal Device For Vehicle (AREA)
- Heterocyclic Carbon Compounds Containing A Hetero Ring Having Oxygen Or Sulfur (AREA)
- Control Of Driving Devices And Active Controlling Of Vehicle (AREA)
- Measuring Volume Flow (AREA)
- Financial Or Insurance-Related Operations Such As Payment And Settlement (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
（産業上の利用分野）
本発明は、順列液に基づく使用者識別及びアクセス制御
用の新規な方法及び装置に関するが、本発明の手法は、
暗号化及び秘密化には関連していない。
用の新規な方法及び装置に関するが、本発明の手法は、
暗号化及び秘密化には関連していない。
（従来の技術）
Ｇｏｌｄｗａｓｓｅｒ、 Ｍｉｃａｌｉ 及びＲａｃ
ｋｏｆｆは、正当性を除いたいかなる主張についての知
識を明らかにしない相互証明システムの新規な形態を提
案している。これらの証明の実際の重要性はＦｉａｔ及
びＳｈａｍｉｒｕによって１９８６年によって成されて
いる。これは、零知識証明を使用して使用者識別を達成
し且つメツセージをデジタル的に示す仕方を示している
（米国特許第４．７４８．６６８号参照）。
ｋｏｆｆは、正当性を除いたいかなる主張についての知
識を明らかにしない相互証明システムの新規な形態を提
案している。これらの証明の実際の重要性はＦｉａｔ及
びＳｈａｍｉｒｕによって１９８６年によって成されて
いる。これは、零知識証明を使用して使用者識別を達成
し且つメツセージをデジタル的に示す仕方を示している
（米国特許第４．７４８．６６８号参照）。
Ｆｉａｔ及びＳｈａｍｉｒによって提案された特定の証
明システムは平方根モジュロ複合数を導出するという困
難さに基づいており、これは公知のＲ８Ａ手法（米国特
許第４．４０５．８２９号）よりも早く且つ安全性は劣
るというものである。
明システムは平方根モジュロ複合数を導出するという困
難さに基づいており、これは公知のＲ８Ａ手法（米国特
許第４．４０５．８２９号）よりも早く且つ安全性は劣
るというものである。
（発明の要約）
本発明に従って、零知識識別手法の新たな形態を達成す
るための方法及び装置が開示される。膨大な（５１２ビ
ツト）数を操作するＲ８Ａ及びＦｉａｔ−３ｈａｍｉｒ
法とは異なって、本発明の新たな手法は小さな（８ビツ
ト）数を使用する。本発明は、従って厳しく制限された
ＲＡＭＳＲＯＭ及び処理電力を有する小さなカード上で
実施出来、従来技術よりもより高速である。本発明の新
たな手法安全性は、因数分解と言うよりもＮＰ完備算術
問題に依存しており、従って、パブリックキー暗号の基
礎を広げるが、他方で成る単一問題の困難さに依存する
危険がある。
るための方法及び装置が開示される。膨大な（５１２ビ
ツト）数を操作するＲ８Ａ及びＦｉａｔ−３ｈａｍｉｒ
法とは異なって、本発明の新たな手法は小さな（８ビツ
ト）数を使用する。本発明は、従って厳しく制限された
ＲＡＭＳＲＯＭ及び処理電力を有する小さなカード上で
実施出来、従来技術よりもより高速である。本発明の新
たな手法安全性は、因数分解と言うよりもＮＰ完備算術
問題に依存しており、従って、パブリックキー暗号の基
礎を広げるが、他方で成る単一問題の困難さに依存する
危険がある。
本発明の以下の記述を通して、大文字はベクトル及びマ
トリックスを示すのに使用され、小文字は値を示すのに
使用される。ギリシャ文字は（１゜・・・、ｎｌ に渡
っての置換を示し、ｎ−ベクトルＶ上の効果Ｖπはｌ≦
ｊ≦ｎに対してｗｊ＝ｖπ（、）の様なベクトルＷとし
て定義される。マトリックスにおける置換の効果は列置
換Ａπ＝〔ａ１π、１．〕として決められており、全て
のマトリックスＡ及びベクトルＶに対して、ＡπＶπ＝
〔Σ＋−１ａ＋πｆ＋１Ｖ７ｒ ｆＨ） ＝ ＣΣｊｌ
ａ＋ ＋Ｖｔ〕＝ Ａ Ｖ。
トリックスを示すのに使用され、小文字は値を示すのに
使用される。ギリシャ文字は（１゜・・・、ｎｌ に渡
っての置換を示し、ｎ−ベクトルＶ上の効果Ｖπはｌ≦
ｊ≦ｎに対してｗｊ＝ｖπ（、）の様なベクトルＷとし
て定義される。マトリックスにおける置換の効果は列置
換Ａπ＝〔ａ１π、１．〕として決められており、全て
のマトリックスＡ及びベクトルＶに対して、ＡπＶπ＝
〔Σ＋−１ａ＋πｆ＋１Ｖ７ｒ ｆＨ） ＝ ＣΣｊｌ
ａ＋ ＋Ｖｔ〕＝ Ａ Ｖ。
置換は関数からなる。従ってＶπσはｌ≦ｊ≦ｎに対し
てｗｌ・■π（σ（ｊ））である様なベクトルＷとして
定義される。全ての算術演算はモジュロｐを対して実効
される。ここでｐは小さい数であり、必要ではないが好
ましくは素数である。矩形ｍｘｎのマトリックスＡの核
Ｋ （Ａ）はＡＷ＝０（ｍｏｄ ｐ） （ここで０は零
のｍベクトルであり）である様な一組のｎベクトルとし
て決められる。
てｗｌ・■π（σ（ｊ））である様なベクトルＷとして
定義される。全ての算術演算はモジュロｐを対して実効
される。ここでｐは小さい数であり、必要ではないが好
ましくは素数である。矩形ｍｘｎのマトリックスＡの核
Ｋ （Ａ）はＡＷ＝０（ｍｏｄ ｐ） （ここで０は零
のｍベクトルであり）である様な一組のｎベクトルとし
て決められる。
前述から、Ｋ （Ａ）はＺ２の線型空間であり、Ｋ （
Ａσ）・（Ｋ （Ａ） ）σであることが容易に分かる
。
Ａσ）・（Ｋ （Ａ） ）σであることが容易に分かる
。
本発明の方法及び装置で使用される置換核問題（ＰＫＰ
）は以下のようにして表現することができる。
）は以下のようにして表現することができる。
既知 ｍＸｎマトリックスＡ、ｎベクトルＶ及び数ｐ
目標 Ｖπ∈Ｋ （Ａ）の様な置換π
Ｋ （Ａ）内の幾つかの、全ての又は乱雑に選ばれたベ
クトルを見出す関連する問題は線型代数の直裁的な技法
により解決することができる。与えられたＶ（及びＫ
（Ａ）の特に小さい非零ベクトル）に対するＫ （Ａ）
の良好な近似を見出す問題はより複雑な（しかし多項式
の）格子減少技術により解くことができる。置換核を難
しくするのは、特定のエントリーの組を有する核ベクト
ルを選ばねばならないからである。実際、ｍ＝１及びＶ
＝（＋１．＋１．・・・、 ＋１．−１．−１．・・・
、−１）に対するでさえ問題はＮＰ完備であることが容
易に分かる。つまりＡにおける重みに対する分割問題で
あるからである。Ｇａｒｅｙ及びＪｏｈｏｎｓｏｎによ
って示されるように３分割問題からの若干込み入った還
元は、ＰＫＰが強い意味でＮＰ完備であることを示して
いる（即ち、適当な仮定の基では、困難性はｌｏｇ（ｐ
）よりｐで指数関数的に増大する）。これは提案された
識別技法で小さい数を使用することを可能にし、単純性
と速度を大幅に増大する。
クトルを見出す関連する問題は線型代数の直裁的な技法
により解決することができる。与えられたＶ（及びＫ
（Ａ）の特に小さい非零ベクトル）に対するＫ （Ａ）
の良好な近似を見出す問題はより複雑な（しかし多項式
の）格子減少技術により解くことができる。置換核を難
しくするのは、特定のエントリーの組を有する核ベクト
ルを選ばねばならないからである。実際、ｍ＝１及びＶ
＝（＋１．＋１．・・・、 ＋１．−１．−１．・・・
、−１）に対するでさえ問題はＮＰ完備であることが容
易に分かる。つまりＡにおける重みに対する分割問題で
あるからである。Ｇａｒｅｙ及びＪｏｈｏｎｓｏｎによ
って示されるように３分割問題からの若干込み入った還
元は、ＰＫＰが強い意味でＮＰ完備であることを示して
いる（即ち、適当な仮定の基では、困難性はｌｏｇ（ｐ
）よりｐで指数関数的に増大する）。これは提案された
識別技法で小さい数を使用することを可能にし、単純性
と速度を大幅に増大する。
本発明の方法及び装置は、以下の方法の識別手法で置換
核問題を実行する。使用者が普遍Ａ及び数ｐに同意する
と、各使用者はランダム置換π（シークレットキーとし
て機能する）及びＶπ∈Ｋ （Ａ）の様なランダムベク
トルＶ（パブリックキーとして機能する）を選択する。
核問題を実行する。使用者が普遍Ａ及び数ｐに同意する
と、各使用者はランダム置換π（シークレットキーとし
て機能する）及びＶπ∈Ｋ （Ａ）の様なランダムベク
トルＶ（パブリックキーとして機能する）を選択する。
使用者は今シークレット置換πの知識を与えることによ
り識別が達成される。零知識証明を使用することにより
、試験体（プローバー）は、盗聴者及び不正な検証体（
ペリファイヤー）がπについて何も学ばないことを補償
できる。πは後で試験体が他人に行うのと同様にして虚
報することを可能にする。
り識別が達成される。零知識証明を使用することにより
、試験体（プローバー）は、盗聴者及び不正な検証体（
ペリファイヤー）がπについて何も学ばないことを補償
できる。πは後で試験体が他人に行うのと同様にして虚
報することを可能にする。
ＮＰに於ける問題に対しても零知識証明が存在すること
がＧｏｌｄｒｅｉｃｈ、 Ｍｉｃａｌｉ及びＷｉｇｄｅ
ｒｓｏｎ（１９８６）によって示されたが、彼等の証明
は全く実用的では無かった。これは、試験体と検証体と
の間に極めて多くの相互関係を必要としてからである。
がＧｏｌｄｒｅｉｃｈ、 Ｍｉｃａｌｉ及びＷｉｇｄｅ
ｒｓｏｎ（１９８６）によって示されたが、彼等の証明
は全く実用的では無かった。これは、試験体と検証体と
の間に極めて多くの相互関係を必要としてからである。
Ｂｌｕｍ （出版されていない記述による）は数個の相
互関係しか必要とせず、各相互関係が膨大な数の連絡ビ
ットを（試験体が独立したビットに関連させることを可
能にするために）必要とするより単純な証明を発展させ
た。このＦｉａｔ−３ｈａｍｉｒの証明（Ｆｉｓｃｈｅ
ｒ及びＭｉｃａｌ ｉによる２次残余の出版されていな
い初期の証明の改良）は数個の相互関係及び少数の連絡
ビットを必要とするが、比較的計算が複雑になる。これ
は、少ないとも５１２ビツト数のｌＯモジュラ乗算を必
要とするからである。本発明の主な寄与は、数個の相互
関係、数個の連絡ビット、単純な８ビツト算術演算、及
びコンパクトなパブリック及びプライベットキーを必要
とする真に実用的な零知識証明技法を構築することを可
能にすることにある。
互関係しか必要とせず、各相互関係が膨大な数の連絡ビ
ットを（試験体が独立したビットに関連させることを可
能にするために）必要とするより単純な証明を発展させ
た。このＦｉａｔ−３ｈａｍｉｒの証明（Ｆｉｓｃｈｅ
ｒ及びＭｉｃａｌ ｉによる２次残余の出版されていな
い初期の証明の改良）は数個の相互関係及び少数の連絡
ビットを必要とするが、比較的計算が複雑になる。これ
は、少ないとも５１２ビツト数のｌＯモジュラ乗算を必
要とするからである。本発明の主な寄与は、数個の相互
関係、数個の連絡ビット、単純な８ビツト算術演算、及
びコンパクトなパブリック及びプライベットキーを必要
とする真に実用的な零知識証明技法を構築することを可
能にすることにある。
従って、本発明の主要な目的は零知識識別手法をより実
用的にし且つより有効にする新規な方法及び装置を提供
することにある。
用的にし且つより有効にする新規な方法及び装置を提供
することにある。
（実施例）
第１図は本発明の方法及び装置が新規の零知識識別手法
を実行する仕方を示すブロック図である。
を実行する仕方を示すブロック図である。
各使用者はＩｌｏ、ＣＰＵ及びメモリーを含む小型カー
ドを有している。
ドを有している。
使用者が、識別を行う目的で、別の使用者又は好適に設
けられた中央エントリー（ここでは検証体と呼ばれる）
と通信することを望む時、使用者試験体は、ランダム置
換πであるシークレットキー及び数ｐ１マトリックスＡ
及びＶπεＫ （Ａ）の様なベクトルＶであるパブリッ
クキーを既に選択していなればならない。これはボック
ス２０内の第１図に示されている。識別手法を開始する
ために、使用者試験体はランダムベクトルＲ及びランダ
ム置換σを選択する（ボックス２６）。そして、（σ、
ＡＲ）及び（πσ、Ｒσ）対の暗号化のためにハツシュ
（ｈａｓｈ）された値を計算して検証器へ送る（ボック
ス３０）。検証体はそれを受信しくボックス３２）、ラ
ンダム値０≦ｃ≦ｐを選び、試験体にＷ＝Ｒσ＋ｃＶπ
σを送る様頼む（ボックス３６）。使用者−試験体は、
応答して、Ｗを計算して、検証体に送る。検証体は試験
体にσ又はπσを明らかにする様要求する（ボックス４
０）。試験体はこの要求を受取り、そして要求されたよ
うにしてσ又はπσのいずれかを送る。
けられた中央エントリー（ここでは検証体と呼ばれる）
と通信することを望む時、使用者試験体は、ランダム置
換πであるシークレットキー及び数ｐ１マトリックスＡ
及びＶπεＫ （Ａ）の様なベクトルＶであるパブリッ
クキーを既に選択していなればならない。これはボック
ス２０内の第１図に示されている。識別手法を開始する
ために、使用者試験体はランダムベクトルＲ及びランダ
ム置換σを選択する（ボックス２６）。そして、（σ、
ＡＲ）及び（πσ、Ｒσ）対の暗号化のためにハツシュ
（ｈａｓｈ）された値を計算して検証器へ送る（ボック
ス３０）。検証体はそれを受信しくボックス３２）、ラ
ンダム値０≦ｃ≦ｐを選び、試験体にＷ＝Ｒσ＋ｃＶπ
σを送る様頼む（ボックス３６）。使用者−試験体は、
応答して、Ｗを計算して、検証体に送る。検証体は試験
体にσ又はπσを明らかにする様要求する（ボックス４
０）。試験体はこの要求を受取り、そして要求されたよ
うにしてσ又はπσのいずれかを送る。
第１の場合、検証体は（σ、ＡσＷ）が第１の所与の値
にハツシュされたことをチエツクし、第２の場合、検証
器は（πσ、Ｗ−ｃＶπσ）が第２の１直にハツシュさ
れたことをチエツクする（ボックス５０）。検証体は試
験が成功した場合宣言を受は取る（ボックス５２）。
にハツシュされたことをチエツクし、第２の場合、検証
器は（πσ、Ｗ−ｃＶπσ）が第２の１直にハツシュさ
れたことをチエツクする（ボックス５０）。検証体は試
験が成功した場合宣言を受は取る（ボックス５２）。
πを知る本物の試験体はこの試験を常にバスする。これ
は、ＡσＷ＝Ａσ（Ｒσ十ＣＶπσ）＝Ａ ＣＲ＋ｃＶ
π）＝ＡＲ＋ｃＡＶπ＝ＡＲ且つ定義により’ｖＶ−ｅ
Ｖπσ＝Ｒσであるからである。
は、ＡσＷ＝Ａσ（Ｒσ十ＣＶπσ）＝Ａ ＣＲ＋ｃＶ
π）＝ＡＲ＋ｃＡＶπ＝ＡＲ且つ定義により’ｖＶ−ｅ
Ｖπσ＝Ｒσであるからである。
贋の試験体が関連する値、提示された対のハツシュされ
た値を選択しようとする場合、贋の試験体は２ｐの可能
な質問に答える準備をする必要がある。ｐが素数である
時ｐ＋２の質問に正確に答えることができ場合、同じ関
連する（σ、Ｘ）及び（τ、Ｙ）に対して、対応するベ
クトルＷ′Ｗ”が両方の条件を満足する少なくとも二つ
の異なる値Ｃ′Ｃ”が存在する。これは、以下の一連の
式％式％ ＡσＷ” ＝Ｘ Ｗ’ −ｃ’ Ｖτ＝Ｙ Ｗ″−ｃ”Ｖτ＝Ｙ これは、（ｗ’ −ｗ”）ＥＫ （Ａσ）及び（Ｗ’−
Ｗ”） ＝ （ｃ’−ｃ”）Ｖτを意味する。Ｃ−Ｃ″
≠０．Ｖｒａ”−’ＦＥＫ （Ａ）であるから、シーク
レット置換π＝τσ−１はいかなるｐ＋２の正しい答え
から引くことができる。結果として、この様なπが既知
でない時の成功の確率が最大で（ｐ＋１）／２ｐである
。この値は本質的にｌ／２であり、２０のみの相互関係
が要求されて、各虚報の試みに対してｌ／１，０００，
０００の実際の安全性しきい値以下に詐欺の確率を減少
することが要求される。
た値を選択しようとする場合、贋の試験体は２ｐの可能
な質問に答える準備をする必要がある。ｐが素数である
時ｐ＋２の質問に正確に答えることができ場合、同じ関
連する（σ、Ｘ）及び（τ、Ｙ）に対して、対応するベ
クトルＷ′Ｗ”が両方の条件を満足する少なくとも二つ
の異なる値Ｃ′Ｃ”が存在する。これは、以下の一連の
式％式％ ＡσＷ” ＝Ｘ Ｗ’ −ｃ’ Ｖτ＝Ｙ Ｗ″−ｃ”Ｖτ＝Ｙ これは、（ｗ’ −ｗ”）ＥＫ （Ａσ）及び（Ｗ’−
Ｗ”） ＝ （ｃ’−ｃ”）Ｖτを意味する。Ｃ−Ｃ″
≠０．Ｖｒａ”−’ＦＥＫ （Ａ）であるから、シーク
レット置換π＝τσ−１はいかなるｐ＋２の正しい答え
から引くことができる。結果として、この様なπが既知
でない時の成功の確率が最大で（ｐ＋１）／２ｐである
。この値は本質的にｌ／２であり、２０のみの相互関係
が要求されて、各虚報の試みに対してｌ／１，０００，
０００の実際の安全性しきい値以下に詐欺の確率を減少
することが要求される。
本発明の方法を実施するのに使用される装置はここで教
示される特別にプログラムされた通常の装置であり、こ
の装置は当業者に知られている。
示される特別にプログラムされた通常の装置であり、こ
の装置は当業者に知られている。
本発明の実施はＣを０又はｌに制限することにより概念
的により単純にすることができる。しかしながら、これ
は詐欺の成功の確率を各繰り返し毎に３／４に且つ所望
の安全性しきい値に到達するのに要求される繰り返し数
の２倍以上に増加する。記述された実施例に対する詐欺
の確率（ｐ＋１）／２ｐは実際に到達可能であり、その
境界は厳しい。
的により単純にすることができる。しかしながら、これ
は詐欺の成功の確率を各繰り返し毎に３／４に且つ所望
の安全性しきい値に到達するのに要求される繰り返し数
の２倍以上に増加する。記述された実施例に対する詐欺
の確率（ｐ＋１）／２ｐは実際に到達可能であり、その
境界は厳しい。
零知識で実行可能な手法が直観的に極めて単純であると
言う技術的証明、即ち、Ｒのランダム性がベクトルＷ、
ＡＲ及びＲσを完全にランダム化する。そしてσのラン
ダム性が置換πσを完全にランダムにする。試験体によ
って送られる個々のメツセージは知識を運ばない。試験
体が真正であると検証体を確信させる全ての可能なＣに
対しての両方の質問に答えるのは試験体の意志のみであ
る。
言う技術的証明、即ち、Ｒのランダム性がベクトルＷ、
ＡＲ及びＲσを完全にランダム化する。そしてσのラン
ダム性が置換πσを完全にランダムにする。試験体によ
って送られる個々のメツセージは知識を運ばない。試験
体が真正であると検証体を確信させる全ての可能なＣに
対しての両方の質問に答えるのは試験体の意志のみであ
る。
ｎの推奨される最小の大きさは低い安全性の適用に対し
ては最小３２であり、高い安全性に対して最小６４であ
る。これらのｎに対して、置換πの数は３２！＝２１２
０及び６４１＝２２９６の間に広がるり、最速処理の場
合２３２・１６！＝２７６及び２６４・３２１．２１４
の間に広がる。素数ｐは小さすぎてはならず（Ｖ（ｍｏ
ｄｐ）に於ける値が多重に発生すると異なる置換の数を
減少するから）、そして大きすぎてもいけない（多重精
度演算は低速であるので）。８ビツトマイクロプロセツ
サ用ｐの最適な選択はｐ＝２５−５＝２５３のようであ
る。ｍの選択は近似式ｐｍ″＝、ｎ！に基づくべきであ
り、この近似式はパラメータの組み合わせを記述してお
り、この時ＰＫＰの場合にランダムに選択されたものは
単一解を有する可能性がある（ｐ″＞ｎｊはＡのｍ行の
幾つを疑似回答を加えることなしに捨てることができる
ことを意味する。ｐ ｎ’ｌ ＜ ｎ ｌはπの入力の
幾つかが全てのＰＫＰの回答を失うことなしに任意に固
定することができることを意味する）。ｐ−２５１及び
ｎ＝３２に対して、ｍは約１６でなくてはならず、ｎ＝
２５１及びｎ＝６４に対してｍは約３７である必要があ
る。
ては最小３２であり、高い安全性に対して最小６４であ
る。これらのｎに対して、置換πの数は３２！＝２１２
０及び６４１＝２２９６の間に広がるり、最速処理の場
合２３２・１６！＝２７６及び２６４・３２１．２１４
の間に広がる。素数ｐは小さすぎてはならず（Ｖ（ｍｏ
ｄｐ）に於ける値が多重に発生すると異なる置換の数を
減少するから）、そして大きすぎてもいけない（多重精
度演算は低速であるので）。８ビツトマイクロプロセツ
サ用ｐの最適な選択はｐ＝２５−５＝２５３のようであ
る。ｍの選択は近似式ｐｍ″＝、ｎ！に基づくべきであ
り、この近似式はパラメータの組み合わせを記述してお
り、この時ＰＫＰの場合にランダムに選択されたものは
単一解を有する可能性がある（ｐ″＞ｎｊはＡのｍ行の
幾つを疑似回答を加えることなしに捨てることができる
ことを意味する。ｐ ｎ’ｌ ＜ ｎ ｌはπの入力の
幾つかが全てのＰＫＰの回答を失うことなしに任意に固
定することができることを意味する）。ｐ−２５１及び
ｎ＝３２に対して、ｍは約１６でなくてはならず、ｎ＝
２５１及びｎ＝６４に対してｍは約３７である必要があ
る。
行列Ａはランダムに選択されるべきであり、そのランク
は殆どｍであるは確かである。従って、Ｋ （Ａ）のサ
イズは殆どｐ”−１であることか確かである（これは、
前述されたパラメータの選択に対して２１２８及び２！
１６の間で変化する）。−膜性を失うことなし、Ａはブ
ロック形態Ａ−［Ａ’■〕で与えられる。ここで、Ａｏ
はｍＸ （ｎ −ｍ）マトリックスであり、■はｍＸｍ
識別マトリックスである。使用者及び対抗者の両方かが
ウス消去を、核を変化することなしに公表されたＡに適
用することができる。ＡＲ（又はＡσＷ）の計算は、こ
の表現で特に容易である。これは、ＡＲ＝Ａ’ Ｒ’
＋Ｒ”でありからであり、Ｒｏ及びＲ″はそれぞれ
第１のｎ −ｍ及びＲへの最後のｍ入力である。
は殆どｍであるは確かである。従って、Ｋ （Ａ）のサ
イズは殆どｐ”−１であることか確かである（これは、
前述されたパラメータの選択に対して２１２８及び２！
１６の間で変化する）。−膜性を失うことなし、Ａはブ
ロック形態Ａ−［Ａ’■〕で与えられる。ここで、Ａｏ
はｍＸ （ｎ −ｍ）マトリックスであり、■はｍＸｍ
識別マトリックスである。使用者及び対抗者の両方かが
ウス消去を、核を変化することなしに公表されたＡに適
用することができる。ＡＲ（又はＡσＷ）の計算は、こ
の表現で特に容易である。これは、ＡＲ＝Ａ’ Ｒ’
＋Ｒ”でありからであり、Ｒｏ及びＲ″はそれぞれ
第１のｎ −ｍ及びＲへの最後のｍ入力である。
同一性に関するこの新規な零知識証明の実時間に対する
複雑性を示すために、［Ａ’１１）及びｎ＝２５１で表
示される１６Ｘ３２マトリツクスＡの具体的場合を考え
る。置換の適用及びサイズ３２のベクトルの追加は殆ど
時間を必要としない。
複雑性を示すために、［Ａ’１１）及びｎ＝２５１で表
示される１６Ｘ３２マトリツクスＡの具体的場合を考え
る。置換の適用及びサイズ３２のベクトルの追加は殆ど
時間を必要としない。
更に、試験体は繰り返し毎に一度のマトリックスベクト
ル乗算を達成する。検証体は（平均）２度の繰り返し毎
に一度のマトリックスーベクトル乗算を達成する。単純
化された１６Ｘ１６マトリツクス一ベクトル乗算は２５
６単一バイト乗算を要求する。この乗算は今日のマイク
ロプロセ、ソサでミリ秒で実行することができる。これ
は数値論理的手法と比較すると極めて有利である。数値
論理手法においては、２つの５１２ビツト数の積の計算
が４０９６の単一バイト乗算を要求する（多精度算術に
おけるキャリー伝播及びモジュラ還元によって引き起こ
されるオーバーへ・ソドが更に加わる）。
ル乗算を達成する。検証体は（平均）２度の繰り返し毎
に一度のマトリックスーベクトル乗算を達成する。単純
化された１６Ｘ１６マトリツクス一ベクトル乗算は２５
６単一バイト乗算を要求する。この乗算は今日のマイク
ロプロセ、ソサでミリ秒で実行することができる。これ
は数値論理的手法と比較すると極めて有利である。数値
論理手法においては、２つの５１２ビツト数の積の計算
が４０９６の単一バイト乗算を要求する（多精度算術に
おけるキャリー伝播及びモジュラ還元によって引き起こ
されるオーバーへ・ソドが更に加わる）。
パラメータの同じ選択に対して、プロトコールの通信の
複雑性を決定することができる。各ベクトルは２５６ビ
ツトを含み、 （１，２，・・・ ３２）に渡る各順列
は約１２０ビツトで記述され、各暗号化するためにハツ
シュされた値は約６４ビ・ソトを必要とする。一方はベ
クトルであり他方は順列である２つのハツシュされた値
は、各置換で送られるので、全情報はラウンド（ｒｏｕ
ｎｄ）毎に約５００ビツトであり、これはＦｉａｔ−３
ｂａｍｉｒ手法の一ラウンドで使用されるビット数より
も少ない。
複雑性を決定することができる。各ベクトルは２５６ビ
ツトを含み、 （１，２，・・・ ３２）に渡る各順列
は約１２０ビツトで記述され、各暗号化するためにハツ
シュされた値は約６４ビ・ソトを必要とする。一方はベ
クトルであり他方は順列である２つのハツシュされた値
は、各置換で送られるので、全情報はラウンド（ｒｏｕ
ｎｄ）毎に約５００ビツトであり、これはＦｉａｔ−３
ｂａｍｉｒ手法の一ラウンドで使用されるビット数より
も少ない。
（カードでの適用で特に重要な）本新規な方法の別の利
点は、極めて安価であるということである。各使用者の
パブリックキーＶは２５６ビツトで記憶することかでき
る。各使用者のシークレットキーπは１２０ビツトで記
憶することができる。
点は、極めて安価であるということである。各使用者の
パブリックキーＶは２５６ビツトで記憶することかでき
る。各使用者のシークレットキーπは１２０ビツトで記
憶することができる。
普遍マトリックスＡ° は、明示マトリックスではなく
、ｉ及びｊの疑似ランダム関数として記憶することがで
きる。最大Ａ°が利用できるので、極めて単純な疑似ラ
ンダム関数が充分実用となる。
、ｉ及びｊの疑似ランダム関数として記憶することがで
きる。最大Ａ°が利用できるので、極めて単純な疑似ラ
ンダム関数が充分実用となる。
Ａ゛の要素は、この関数を適当な項とともに呼び出すこ
とにより（元の又は置換された順序で）要求に応じて発
生することができる。従って、マトリックス−ベクトル
積の計算は数バイトの作業領域のみを要求する。
とにより（元の又は置換された順序で）要求に応じて発
生することができる。従って、マトリックス−ベクトル
積の計算は数バイトの作業領域のみを要求する。
本発明は、種々の方法で拡張したり変形したりすること
ができる。整数モジュロ素数ｐの基礎体Ｚ、はいかなる
環構造でも置き換えることができる。特に、環２２ｋを
使用することができ、モジュラ還元を切断によって置き
換えることができる。
ができる。整数モジュロ素数ｐの基礎体Ｚ、はいかなる
環構造でも置き換えることができる。特に、環２２ｋを
使用することができ、モジュラ還元を切断によって置き
換えることができる。
しかしながら、この異なる方法は対抗者が中間モジユリ
（ｍｏｄｕｌｉ） ２． ４． ８． ・・・、 ２
’−’でこの線型方程式に挑むことを可能にする。これ
は安全性を減少する。
（ｍｏｄｕｌｉ） ２． ４． ８． ・・・、 ２
’−’でこの線型方程式に挑むことを可能にする。これ
は安全性を減少する。
置換π及びσは公知のサブグループ、特に、（１，２，
・・・ｎ）内のあるブロックを安定するサブグループか
ら選ぶことができる。
・・・ｎ）内のあるブロックを安定するサブグループか
ら選ぶことができる。
同次線型方程式Σａ ＋＋Ｖ ｙｒ ＋＋＋ □ ０
（ｍｏｄ ｐ）は非同時方程式Σａ、、ｖπｍ ＝ｕ＋
（ｍｏｄ ｐ）によって置き換えることができる。こ
の場合、Ｕ＝（ｕ＋、 ・・・ｓｕｍ）が既知ベクトル
である。しかしながら、これらの式はＡの最終行である
ベクトルＵを加え、■の最後の入力とじて−ｌを加え、
そして置換をＶ内の最後の入力を安定にするサブグルー
プに限定する。この結果、この拡張は基本的な同時手法
の特別の場合として実際に見ることができる。
（ｍｏｄ ｐ）は非同時方程式Σａ、、ｖπｍ ＝ｕ＋
（ｍｏｄ ｐ）によって置き換えることができる。こ
の場合、Ｕ＝（ｕ＋、 ・・・ｓｕｍ）が既知ベクトル
である。しかしながら、これらの式はＡの最終行である
ベクトルＵを加え、■の最後の入力とじて−ｌを加え、
そして置換をＶ内の最後の入力を安定にするサブグルー
プに限定する。この結果、この拡張は基本的な同時手法
の特別の場合として実際に見ることができる。
非同次場合のベクトルＵは置換形態で同様に与えられる
ことができる。その結果、この問題は、与えられたＡ、
Ｖ及びＵでΣａ、ｖπ＋ｉｌＵτ（Ｂ （ｍｏｄ ｐ
）の様な２つの順列π及びτを見出すことにある。−■
付加的ブロックとしてＡに加え、ＶとＵを連結し、そし
て（Ｖ５．・・・Ｖｎ＋ＬＩ＋、・・・ｕｍ）内の最初
のｎ及び最後のｍ入力を安定にするサブグループに置換
を制限することによって、この拡張を、基本的な手法の
特別の場合と見ることが出来る。
ことができる。その結果、この問題は、与えられたＡ、
Ｖ及びＵでΣａ、ｖπ＋ｉｌＵτ（Ｂ （ｍｏｄ ｐ
）の様な２つの順列π及びτを見出すことにある。−■
付加的ブロックとしてＡに加え、ＶとＵを連結し、そし
て（Ｖ５．・・・Ｖｎ＋ＬＩ＋、・・・ｕｍ）内の最初
のｎ及び最後のｍ入力を安定にするサブグループに置換
を制限することによって、この拡張を、基本的な手法の
特別の場合と見ることが出来る。
非同次の場合において、Ａ及び■の両方を普遍にするこ
とが可能である。前第２章に記述される変体に対しては
、各使用者がシークレットキーとしてランダム置換πを
選択し、そしてパブリックキーとしてＵ＝ＡＶπを公表
する。前章で記述された変体に対しては、各使用者がシ
ークレットキーとして二つのランダム置換π及びτを選
択し、Ｗ−ＡＶπを計算し、そしてパブリックキーとし
てＵ＝Ｗτ−１を公表する。これらの変体はパブリック
キー登録簿がより小さいことである（ｎ＝３２に対して
使用者毎に２５６の代わりに１２８である）。
とが可能である。前第２章に記述される変体に対しては
、各使用者がシークレットキーとしてランダム置換πを
選択し、そしてパブリックキーとしてＵ＝ＡＶπを公表
する。前章で記述された変体に対しては、各使用者がシ
ークレットキーとして二つのランダム置換π及びτを選
択し、Ｗ−ＡＶπを計算し、そしてパブリックキーとし
てＵ＝Ｗτ−１を公表する。これらの変体はパブリック
キー登録簿がより小さいことである（ｎ＝３２に対して
使用者毎に２５６の代わりに１２８である）。
置換核問題におけるマトリックス−ベクトルは、マトリ
ックス−マトリックス積又はより高次のテンソルーテン
ソル積に置き換えることができる。
ックス−マトリックス積又はより高次のテンソルーテン
ソル積に置き換えることができる。
計算を高速化するために、試験体は種々のＰＫＰシーク
レットを同時に知ることを論証することができ、又逐次
零知識の証明を並行して数回繰り返す。並列コンピュー
タが対数時間でマトリックス−ベクトル積を計算するこ
とができる。これは問題が並列複雑クラスＮＣにあるか
らである。
レットを同時に知ることを論証することができ、又逐次
零知識の証明を並行して数回繰り返す。並列コンピュー
タが対数時間でマトリックス−ベクトル積を計算するこ
とができる。これは問題が並列複雑クラスＮＣにあるか
らである。
相互作用識別手法は、Ｆｉａｔ及びＳｈａｍｉｒ（１９
８６）で導入された一般解法を使用することにより非相
互作用識別特徴手法に変更することができる。米国特許
第４．７４８．６６８号を参照されたい。しかしながら
、ＰＫＰに基づく特徴は、Ｆｉａｔ−３ｈａｍｉｒ特徴
よりも充分に長く、実用的な意義は不明瞭である。
８６）で導入された一般解法を使用することにより非相
互作用識別特徴手法に変更することができる。米国特許
第４．７４８．６６８号を参照されたい。しかしながら
、ＰＫＰに基づく特徴は、Ｆｉａｔ−３ｈａｍｉｒ特徴
よりも充分に長く、実用的な意義は不明瞭である。
特定の実施例及びその変形例に基づいて本発明が示され
、記述されたが、それ以外に本発明の技術を具現化する
変形及び改良が明らかである。この様なものは特許請求
の範囲に記載された本発明の範囲に入るものと見做され
る。
、記述されたが、それ以外に本発明の技術を具現化する
変形及び改良が明らかである。この様なものは特許請求
の範囲に記載された本発明の範囲に入るものと見做され
る。
第１図は本発明の方法及び装置が新規の零知識識別手法
をどの様にして実施するのかを示すブロック図である。
をどの様にして実施するのかを示すブロック図である。
Claims (26)
- （１）（ａ）試験体に対して、｛１、２、・・・ｎ｝に
渡る順列πから成るシークレットキー、及びＶπ∈Ｋ（
Ａ）の如き数ｐ、ｍ×ｎマトリックスＡ、及びｎベクト
ルＶからなるパブリックキーを制定し、 （ｂ）Ｒがランダムベクトルであり、σがランダム順列
である、（σ、ＡＲ）及び（πσ、Ｒσ）対の暗号化の
ためにメャメャされた値を試験体が検証体に送り、 （ｃ）検証体に０≦ｃ＜ｐであるランダムに選択された
値を試験体に送り、 （ｄ）試験体によって決定されたＷ＝Ｒσ＋ｃＶπσを
検証体におくり、 （ｅ）試験体が検証体に、何れかが検証者により要求さ
れるσ又はπσを明らかにし、 （ｄ）検証体は、σが明らかにされている場合、（σ、
ＡσＷ）が暗号的にハッシュされた対（σ、Ａσ）の値
にハッシュされたことを決定し、そしてπσが明らかに
されている場合、（πσ、Ｗ−ｃＶπσ）が暗号的にハ
ッシュされた対（πσ、Ｒσ）にハッシュされたことを
決定するステップから成る検証体に対して試験体を識別
するための方法。 - （２）一連の前記ステップ（ｂ）、（ｃ）、（ｄ）、（
ｅ）及び（ｆ）がｔ≧１回繰り返され、全を繰り返しが
成功して終了した場合のみ試験体が要求した同一性を受
入ことを特徴とする請求項１記載の識別方法。 - （３）前記ステップ（ｂ）、（ｃ）、（ｄ）、（ｅ）及
び（ｆ）が約２０回繰り返されることを特徴とする請求
項２記載の識別方法。 - （４）ｃが〔ｏ、ｐ〕よりも小さい範囲から選択される
ことを特徴とする請求項２記載の識別方法。 - （５）ｎが範囲〔３２、６４〕から選択されることを特
徴とする請求項２記載の識別方法。 - （６）ｐが素数であることを特徴とする請求項２記載の
識別方法。 - （７）ｐが２の幕であることを特徴とする請求項２記載
の識別方法。 - （８）算術モジュロｐが任意のリング構造に渡る算術演
算によって置き換えられることを特徴とする請求項２記
載の識別方法。 - （９）ｐが２５１であることを特徴とする請求項２記載
の識別方法。 - （１０）ｍが近似式ｐ＾ｍ≒ｎ！で決められる値である
ことを特徴とする請求項２記載の識別方法。 - （１１）ｐが２５１、ｎが３２及びｍが１６であること
を特徴とする請求項２記載の識別方法。 - （１２）ｐが２５１、ｎが６４及びｍが３７であること
を特徴とする請求項２記載の識別方法。 - （１３）数ｐ及び／又はマトリックスＡは普遍であり、
多くの使用者に共通であることを特徴とする請求項２記
載の識別方法。 - （１４）（ａ）試験体に対して、｛１、２、・・・ｎ｝
に渡る順列πから成るシークレットキー、及びＶπ∈Ｋ
（Ａ）の如き数ｐ、ｍ×ｎマトリックスＡ、及びｎベク
トルＶからなるパブリックキーを制定する手段、 （ｂ）Ｒがランダムベクトルであり、σがランダム順列
である、（σ、ＡＲ）及び（πσ、Ｒσ）対の暗号化の
ためにメャメャされた値を試験体が検証体に送る手段、 （Ｃ）検証体に０≦ｃ＜ｐであるランダムに選択された
値を試験体に送る手段、 （ｄ）試験体によって決定されたＷ＝Ｒσ＋ｃＶπσを
検証体におくる手段、 （ｅ）試験体が検証体に、何れかが検証者により要求さ
れるσ又はπσを明らかにする手段、（ｄ）検証体は、
σが明らかにされている場合、（σ、ＡσＷ）が暗号的
にハッシュされた対（σ、Ａσ）の値にハッシュされた
ことを決定し、そしてπσが明らかにされている場合、
（πσ、Ｗ−ｃＶπσ）が暗号的にハッシュされた対（
πσ、Ｒσ）にハッシュされたことを決定する手段から
成る検証体に対して試験体を識別するための装置。 - （１５）一連の前記ステップ（ｂ）、（ｃ）、（ｄ）、
（ｅ）及び（ｆ）がｔ≧１回繰り返され、全を繰り返し
が成功して終了した場合のみ試験体が要求した同一性を
受入れることを特徴とする請求項１４記載の識別装置。 - （１６）前記ステップ（ｂ）、（ｃ）、（ｄ）、（ｅ）
及び（ｆ）が約２０回繰り返されることを特徴とする請
求項１５記載の識別装置。 - （１７）ｃが〔ｏ、ｐ〕よりも小さい範囲から選択され
ることを特徴とする請求項１５記載の識別装置。 - （１８）ｎが範囲〔３２、６４〕から選択されることを
特徴とする請求項１５記載の識別装置。 - （１９）ｐが素数であることを特徴とする請求項１５記
載の識別装置。 - （２０）ｐが２の幕であることを特徴とする請求項１５
記載の識別装置。 - （２１）算術モジュロｐが任意のリング構造に渡る算術
演算によって置き換えられることを特徴とする請求項１
５記載の識別装置。 - （２２）ｐが２５１であることを特徴とする請求項１５
記載の識別装置。 - （２３）ｍが近似式ｐ＾ｍ≒ｎ！で決められる値である
ことを特徴とする請求項１５記載の識別装置。 - （２４）ｐが２５１、ｎが３２及びｍが１６であること
を特徴とする請求項１５記載の識別装置。 - （２５）ｐが２５１、ｎが６４及びｍが３７であること
を特徴とする請求項１５記載の識別装置。 - （２６）数ｐ及び／又はマトリックスＡは普遍であり、
多くの使用者に共通であることを特徴とする請求項１５
記載の識別装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US324508 | 1989-03-16 | ||
| US07/324,508 US4932056A (en) | 1989-03-16 | 1989-03-16 | Method and apparatus for user identification based on permuted kernels |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH032953A true JPH032953A (ja) | 1991-01-09 |
| JPH0746260B2 JPH0746260B2 (ja) | 1995-05-17 |
Family
ID=23263902
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2066715A Expired - Lifetime JPH0746260B2 (ja) | 1989-03-16 | 1990-03-16 | 使用者識別装置 |
Country Status (8)
| Country | Link |
|---|---|
| US (1) | US4932056A (ja) |
| EP (1) | EP0389895B1 (ja) |
| JP (1) | JPH0746260B2 (ja) |
| AT (1) | ATE100985T1 (ja) |
| DE (1) | DE69006241T2 (ja) |
| DK (1) | DK0389895T3 (ja) |
| ES (1) | ES2050860T3 (ja) |
| IL (1) | IL93739A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6018114A (en) * | 1996-09-19 | 2000-01-25 | Yamaha Corporation | Rotary valve of brass instrument |
| US6678665B1 (en) * | 1997-05-28 | 2004-01-13 | Fujitsu Siemens Computer | Computer system for protecting software and a method for protecting software |
Families Citing this family (31)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5214704A (en) * | 1989-10-04 | 1993-05-25 | Teledyne Industries, Inc. | Nonlinear dynamic substitution devices and methods for block substitutions |
| US5038376A (en) * | 1989-10-04 | 1991-08-06 | Teledyne Industries, Inc. | Block substitution based encryption by a modulo 2 addition method and apparatus |
| US5647001A (en) * | 1989-10-04 | 1997-07-08 | Litton Systems, Inc. | Nonlinear dynamic substitution devices and methods for block substitutions employing coset decompositions and direct geometric generation |
| US5317639A (en) * | 1989-10-04 | 1994-05-31 | Teledyne Industries, Inc. | Non-linear block substitution devices derived by constructive corruption |
| JP3145116B2 (ja) * | 1991-01-18 | 2001-03-12 | トムソン マルチメデイア ソシエテ アノニム | アクセスコントロールおよび／または識別方法および装置 |
| US5148479A (en) * | 1991-03-20 | 1992-09-15 | International Business Machines Corp. | Authentication protocols in communication networks |
| US5204901A (en) * | 1991-08-01 | 1993-04-20 | General Electric Company | Public key cryptographic mechanism |
| US5418854A (en) * | 1992-04-28 | 1995-05-23 | Digital Equipment Corporation | Method and apparatus for protecting the confidentiality of passwords in a distributed data processing system |
| US5345549A (en) * | 1992-10-30 | 1994-09-06 | International Business Machines Corporation | Multimedia based security systems |
| US5375170A (en) * | 1992-11-13 | 1994-12-20 | Yeda Research & Development Co., Ltd. | Efficient signature scheme based on birational permutations |
| US5263085A (en) * | 1992-11-13 | 1993-11-16 | Yeda Research & Development Co. Ltd. | Fast signature scheme based on sequentially linearized equations |
| FR2700430B1 (fr) * | 1992-12-30 | 1995-02-10 | Jacques Stern | Procédé d'authentification d'au moins un dispositif d'identification par un dispositif de vérification et dispositif pour sa mise en Óoeuvre. |
| US5491752A (en) * | 1993-03-18 | 1996-02-13 | Digital Equipment Corporation, Patent Law Group | System for increasing the difficulty of password guessing attacks in a distributed authentication scheme employing authentication tokens |
| US5432852A (en) * | 1993-09-29 | 1995-07-11 | Leighton; Frank T. | Large provably fast and secure digital signature schemes based on secure hash functions |
| FR2714780B1 (fr) * | 1993-12-30 | 1996-01-26 | Stern Jacques | Procédé d'authentification d'au moins un dispositif d'identification par un dispositif de vérification. |
| US5787172A (en) * | 1994-02-24 | 1998-07-28 | The Merdan Group, Inc. | Apparatus and method for establishing a cryptographic link between elements of a system |
| ATE189570T1 (de) * | 1994-02-24 | 2000-02-15 | Merdan Group Inc | Verfahren und einrichtung zum aufbau einer kryptographischen verbindung zwischen elementen eines systems |
| EP0697687A4 (en) * | 1994-03-07 | 2000-09-20 | Nippon Telegraph & Telephone | ZERO KNOWLEDGE AUTHENTICATION PROTOCOL-BASED METHOD AND SYSTEM FOR MESSAGE TRANSMISSION |
| US5504817A (en) * | 1994-05-09 | 1996-04-02 | Yeda Research And Development Co. Ltd. At The Weizmann Institute Of Science | Method and apparatus for memory efficient variants of public key encryption and identification schemes for smart card applications |
| US5530758A (en) * | 1994-06-03 | 1996-06-25 | Motorola, Inc. | Operational methods for a secure node in a computer network |
| US5606609A (en) * | 1994-09-19 | 1997-02-25 | Scientific-Atlanta | Electronic document verification system and method |
| US5838794A (en) * | 1996-01-11 | 1998-11-17 | Teledyne Electronic Technologies | Method and apparatus for inter-round mixing in iterated block substitution systems |
| US5737425A (en) * | 1996-05-21 | 1998-04-07 | International Business Machines Corporation | Cryptosystem employing worst-case difficult-to solve lattice problem |
| DE19703928A1 (de) | 1997-02-04 | 1998-08-06 | Deutsche Telekom Ag | Verfahren zum Verschlüsseln einer als Zahlenwert dargestellten Nachricht |
| US6373948B1 (en) * | 1997-08-15 | 2002-04-16 | Lucent Technologies Inc. | Cryptographic method and apparatus for restricting access to transmitted programming content using program identifiers |
| US6735313B1 (en) | 1999-05-07 | 2004-05-11 | Lucent Technologies Inc. | Cryptographic method and apparatus for restricting access to transmitted programming content using hash functions and program identifiers |
| US20030220880A1 (en) * | 2002-01-17 | 2003-11-27 | Contentguard Holdings, Inc. | Networked services licensing system and method |
| FR2822002B1 (fr) * | 2001-03-12 | 2003-06-06 | France Telecom | Authentification cryptographique par modules ephemeres |
| US6962530B2 (en) | 2002-04-25 | 2005-11-08 | Igt | Authentication in a secure computerized gaming system |
| GB2434472A (en) * | 2005-12-01 | 2007-07-25 | Jonathan Geoffrey Milt Craymer | Verification using one-time transaction codes |
| US7522723B1 (en) * | 2008-05-29 | 2009-04-21 | Cheman Shaik | Password self encryption method and system and encryption by keys generated from personal secret information |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4326098A (en) * | 1980-07-02 | 1982-04-20 | International Business Machines Corporation | High security system for electronic signature verification |
| US4514592A (en) * | 1981-07-27 | 1985-04-30 | Nippon Telegraph & Telephone Public Corporation | Cryptosystem |
| US4759064A (en) * | 1985-10-07 | 1988-07-19 | Chaum David L | Blind unanticipated signature systems |
| US4759063A (en) * | 1983-08-22 | 1988-07-19 | Chaum David L | Blind signature systems |
| US4799258A (en) * | 1984-02-13 | 1989-01-17 | National Research Development Corporation | Apparatus and methods for granting access to computers |
| US4625076A (en) * | 1984-03-19 | 1986-11-25 | Nippon Telegraph & Telephone Public Corporation | Signed document transmission system |
| US4799061A (en) * | 1985-11-18 | 1989-01-17 | International Business Machines Corporation | Secure component authentication system |
| US4748668A (en) * | 1986-07-09 | 1988-05-31 | Yeda Research And Development Company Limited | Method, apparatus and article for identification and signature |
-
1989
- 1989-03-16 US US07/324,508 patent/US4932056A/en not_active Expired - Lifetime
-
1990
- 1990-03-14 IL IL93739A patent/IL93739A/xx not_active IP Right Cessation
- 1990-03-16 AT AT90105041T patent/ATE100985T1/de active
- 1990-03-16 DE DE90105041T patent/DE69006241T2/de not_active Expired - Lifetime
- 1990-03-16 JP JP2066715A patent/JPH0746260B2/ja not_active Expired - Lifetime
- 1990-03-16 ES ES90105041T patent/ES2050860T3/es not_active Expired - Lifetime
- 1990-03-16 EP EP90105041A patent/EP0389895B1/en not_active Expired - Lifetime
- 1990-03-16 DK DK90105041.9T patent/DK0389895T3/da active
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6018114A (en) * | 1996-09-19 | 2000-01-25 | Yamaha Corporation | Rotary valve of brass instrument |
| US6678665B1 (en) * | 1997-05-28 | 2004-01-13 | Fujitsu Siemens Computer | Computer system for protecting software and a method for protecting software |
Also Published As
| Publication number | Publication date |
|---|---|
| IL93739A0 (en) | 1990-12-23 |
| DE69006241D1 (de) | 1994-03-10 |
| EP0389895A1 (en) | 1990-10-03 |
| ATE100985T1 (de) | 1994-02-15 |
| IL93739A (en) | 1992-01-15 |
| DE69006241T2 (de) | 1994-05-11 |
| JPH0746260B2 (ja) | 1995-05-17 |
| US4932056A (en) | 1990-06-05 |
| EP0389895B1 (en) | 1994-01-26 |
| DK0389895T3 (da) | 1994-06-06 |
| ES2050860T3 (es) | 1994-06-01 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH032953A (ja) | 使用者識別装置 | |
| Shamir | An efficient identification scheme based on permuted kernels | |
| Poupard et al. | Security analysis of a practical “on the fly” authentication and signature generation | |
| Ioannidis et al. | An efficient protocol for Yao's millionaires' problem | |
| Orman et al. | Determining strengths for public keys used for exchanging symmetric keys | |
| KR100499433B1 (ko) | 의사 난수 발생 방법 | |
| Feige | Alternative models for zero knowledge interactive proofs | |
| Kumar et al. | A construction of post quantum secure and signal leakage resistant authenticated key agreement protocol for mobile communication | |
| KR101107565B1 (ko) | 영 지식 증명 암호화 방법 및 장치 | |
| Hossain et al. | A Verifiable Multi-Secret Sharing Scheme Based on ℓ-Intersection Pair of Cyclic Codes | |
| Landau | Zero knowledge and the Department of Defense | |
| US6320966B1 (en) | Cryptographic methods for demonstrating satisfiable formulas from propositional logic | |
| US5737425A (en) | Cryptosystem employing worst-case difficult-to solve lattice problem | |
| Harari | A new authentication algorithm | |
| Boyar et al. | On the communication complexity of zero-knowledge proofs | |
| JP4598269B2 (ja) | 楕円曲線上の高速有限体演算 | |
| Dawson et al. | Key agreement scheme based on generalised inverses of matrices | |
| Chilakala et al. | Advanced Hill Cipher Hybrid Cryptography Model | |
| Tiwari | Quantum key distribution simulation using entangled bell states | |
| Mackenzie et al. | Hard bits of the discrete log with applications to password authentication | |
| Zhou et al. | A simple provably secure AKE from the LWE problem | |
| JP4288341B2 (ja) | キーアグリーメントプロトコルを用いた通信方法 | |
| Chevalier et al. | Security Models and Cryptographic Protocols in a Quantum World | |
| Christ | An Exploration of Secure Circular Multi-Party Quantum Computation | |
| Qin | Isogeny-Based Cryptographic Protocols with Advanced Functionalities |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090517 Year of fee payment: 14 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100517 Year of fee payment: 15 |
|
| EXPY | Cancellation because of completion of term |