Patent US3556154A successfully refreshed from Google Patents.
Patent US4932056A successfully refreshed from Google Patents.
US4932056A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for user identification based on permuted kernels
Assignee: Yeda Research and Development Co Ltd
•
Filing: 1989-03-16
•
Granted: 1990-06-05
•
Expires: 2009-03-16
Abstract
Abstract A method and apparatus for identification of a prover to a verifier in which the prover demonstrates his knowledge of a secret permutation π such that V.sub.π ε K(A) for publicly known A and V where all the arithmetic operations are carried out modulo p. The actual proof does not reveal any knowledge of π, and thus it cannot be misused by dishonest verifiers or eavesdroppers to later misrepresent themselves as the prover. The new scheme is much faster than the RSA and Fiat-Shamir identification schemes.
Inventors
- 👤 Adi Shamir
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 15:04
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/30; H04L9/3006; H04L9/302; G; G07; G07F; G07F7/00; G07F7/08; G07F7/10; G07F7/1016; H04L9/32; H04L9/3218; H04L9/3221
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
190 words
A method for identification of a prover to a verifier comprising the steps of: (a) establishing for the prover a secret key consisting of a permutation π over {1, 2, . . . n}, and a public key consisting of a number p, a m×n matrix A, and an n-vector A such that V.sub.π εK(A) modulo p; (b) sending by the prover to the verifier the cryptographically hashed values of the pairs (σ, AR) and (πσ, R.sub.σ) where R is a random vector and σ is a random permutation, chosen by the prover: (c) sending by the verifier to the prover a randomly chosen value c in o≦c<p; (d) determining by the prover and sending to the verifier W=R.sub.σ +cV.sub.πσ ; (e) revealing by the prover to the verifier either σ or πσ, whichever one is requested by the verifier; (f) determining by the verifier for the case of σ having been revealed that (σ, A.sub.σ W) hashes to the value of the cryptographically hashed pair (σ,AR) and for the case of πσ having been revealed that (πσ, W-cV.sub.πσ) hashes to the value of the cryptographically hashed pair (πσ, R.sub.σ).
Claim 2
Independent Claim
190 words
A method for identification of a prover to a verifier comprising the steps of: (a) establishing for the prover a secret key consisting of a permutation π over {1, 2, . . . n}, and a public key consisting of a number p, a m×n matrix A, and an n-vector A such that V.sub.π εK(A) modulo p; (b) sending by the prover to the verifier the cryptographically hashed values of the pairs (σ, AR) and (πσ, R.sub.σ) where R is a random vector and σ is a random permutation, chosen by the prover: (c) sending by the verifier to the prover a randomly chosen value c in o≦c<p; (d) determining by the prover and sending to the verifier W=R.sub.σ +cV.sub.πσ ; (e) revealing by the prover to the verifier either σ or πσ, whichever one is requested by the verifier; (f) determining by the verifier for the case of σ having been revealed that (σ, A.sub.σ W) hashes to the value of the cryptographically hashed pair (σ,AR) and for the case of πσ having been revealed that (πσ, W-cV.sub.πσ) hashes to the value of the cryptographically hashed pair (πσ, R.sub.σ).
Claim 3
Dependent Claim
37 words
The method for identification according to claim 1 wherein the sequence of steps (b), (c), (d), (e) and (f) are iterated t≧1 times, and accepting the prover's claimed identity only when all the t iterations end successfully.
Claim 4
Dependent Claim
22 words
The method for identification according to claim 2 wherein the steps (b), (c), (d), (e) and (f) are iterated about twenty times.
Claim 5
Dependent Claim
18 words
The method for identification according to claim 2 wherein c is selected from a range smaller than [o,p].
Claim 6
Dependent Claim
17 words
The method for identification according to claim 2 wherein n is selected from the range [32, 64].
Claim 7
Dependent Claim
14 words
The method for identification according to claim 2 wherein p is a prime number.
Claim 8
Dependent Claim
15 words
The method for identification according to claim 2 wherein p is a power of 2.
Claim 9
Dependent Claim
23 words
The method for identification according to claim 2 wherein the arithmetic modulo p is replaced by arithmetic operations over an arbitrary ring structure.
Claim 10
Dependent Claim
12 words
The method for identification according to claim 2 wherein p is 251.
Claim 11
Dependent Claim
21 words
The method for identification according to claim 2 wherein m is a value determined by the approximate equation p m ≈n!.
Claim 12
Dependent Claim
19 words
The method for identification according to claim 2 wherein p is 251, n is 32 and m is 16.
Claim 13
Dependent Claim
19 words
The method for identification according to claim 2 wherein p is 251, n is 64 and m is 37.
Claim 14
Dependent Claim
23 words
The method for identification according to claim 2 wherein the number p and/or the matrix A are universal and common to many users.
Claim 15
Dependent Claim
198 words
Apparatus for identification of a prover to a verifier comprising: (a) means for establishing for the prover a secret key consisting of a permutation π over {1, 2, . . . n}, and a public key consisting of a number p, a m×n matrix A, and an n-vector A such that V.sub.π εK(A) modulo p; (b) means for sending by the prover to the verifier the cryptographically hashed values of the pairs (π, AR) and (πσ, R.sub.σ) where R is a random vector and σ is a random permutation, chosen by the prover; (c) means for sending by the verifier to the prover a randomly chosen value c in o≦c<p. (d) means for determining by the prover and sending to the verifier W=R.sub.σ +cV.sub.πσ ; (e) means for revealing by the prover to the verifier either σ or πσ, whichever one is requested by the verifier; (f) means for determining by the verifier for the case of σ having been revealed that (σ, A.sub.σ W) hashes to the value of the cryptographically hashed pair (σ,AR) and for the case of πσ having been revealed that (πσ, W-cV.sub.πσ) hashes to the value of the cryptographically hashed pair (πσ, R.sub.σ).
Claim 16
Dependent Claim
198 words
Apparatus for identification of a prover to a verifier comprising: (a) means for establishing for the prover a secret key consisting of a permutation π over {1, 2, . . . n}, and a public key consisting of a number p, a m×n matrix A, and an n-vector A such that V.sub.π εK(A) modulo p; (b) means for sending by the prover to the verifier the cryptographically hashed values of the pairs (π, AR) and (πσ, R.sub.σ) where R is a random vector and σ is a random permutation, chosen by the prover; (c) means for sending by the verifier to the prover a randomly chosen value c in o≦c<p. (d) means for determining by the prover and sending to the verifier W=R.sub.σ +cV.sub.πσ ; (e) means for revealing by the prover to the verifier either σ or πσ, whichever one is requested by the verifier; (f) means for determining by the verifier for the case of σ having been revealed that (σ, A.sub.σ W) hashes to the value of the cryptographically hashed pair (σ,AR) and for the case of πσ having been revealed that (πσ, W-cV.sub.πσ) hashes to the value of the cryptographically hashed pair (πσ, R.sub.σ).
Claim 17
Dependent Claim
36 words
Apparatus for identification according to claim 14 wherein the sequence of steps (b), (c), (d), (e) and (f) are iterated t≧1 times, and accepting the prover's claimed identity only when all the t iterations end successfully.
Claim 18
Dependent Claim
21 words
Apparatus for identification according to claim 15 wherein the steps (b), (c), (d), (e) and (f) are iterated about twenty times.
Claim 19
Dependent Claim
17 words
Apparatus for identification according to claim 15 wherein c is selected from a range smaller than [o,p].
Claim 20
Dependent Claim
16 words
Apparatus for identification according to claim 15 wherein n is selected from the range [32, 64].
Claim 21
Dependent Claim
13 words
Apparatus for identification according to claim 15 wherein p is a prime number.
Claim 22
Dependent Claim
14 words
Apparatus for identification according to claim 15 wherein p is a power of 2.
Claim 23
Dependent Claim
22 words
Apparatus for identification according to claim 15 wherein the arithmetic modulo p is replaced by arithmetic operations over an arbitrary ring structure.
Claim 24
Dependent Claim
11 words
Apparatus for identification according to claim 15 wherein p is 251.
Claim 25
Dependent Claim
20 words
Apparatus for identification according to claim 15 wherein m is a value determined by the approximate equation p m ≈n!.
Claim 26
Dependent Claim
18 words
Apparatus for identification according to claim 15 wherein p is 251, n is 32 and m is 16.
Claim 27
Dependent Claim
18 words
Apparatus for identification according to claim 15 wherein p is 251, n is 64 and m is 37.
Claim 28
Dependent Claim
22 words
Apparatus for identification according to claim 15 wherein the number p and/or the matrix A are universal and common to many users.
References Cited (Backward Citations)
US4514592A
Cited
US4759063A
Cited
US4799258A
Cited
US4759064A
Cited
US4799061A
Cited
US4748668A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-06-04 | 1993-12-04 | 1994-06-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-06-04 | 1997-12-04 | 1998-06-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-06-04 | 2001-12-04 | 2002-06-05 | $7700.00 | Window Closed / Lapsed |