Patent US5198650A successfully refreshed from Google Patents.
Patent US2912398A successfully refreshed from Google Patents.
Patent US5245657A successfully refreshed from Google Patents.
US5245657A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Verification method and apparatus
Assignee: Mitsubishi Electric Corp
•
Filing: 1992-07-02
•
Granted: 1993-09-14
•
Expires: 2012-07-02
Abstract
Abstract A prover possessing public information and related secret information sends the public information and an initial message to a verifier. The verifier sends back a random message and an enquiry generated from the initial message and random message. The prover confirms that the enquiry has been correctly generated, then sends the verifier a response created from the enquiry and the secret information and related to the initial message. Using the initial message and public information, the verifier checks whether the response is a valid response to the enquiry. If it is, the verifier stores the public information, initial message, random message, and response as a transcript. If necessary, the transcript can be submitted to an arbitrator to establish that verification has taken place.
Inventors
- 👤 Kouici Sakurai
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 18:54
CPC Classifications
G; G06; G06Q; G06Q20/00; G06Q20/30; G06Q20/36; G06Q20/367; G06Q20/3674; G06Q20/3678; H; H04; H04L; H04L9/00; H04L9/32; H04L9/321; H04L9/3218
Claims Analysis
Total Claims: 53
Claim 1
Independent Claim
240 words
A method of verifying a prover possessing public information ID and related secret information S, comprising the steps of: (a) linking said prover to a verifier by a communication line; (b) generating, in said prover, an initial message X; (c) transmitting said public information ID and said initial message X from said prover to said verifier; (d) generating, in said verifier, a random message M; (e) generating, in said verifier, an enquiry E by application of a function relating said enquiry E to said initial message X and said random message M; (f) transmitting said enquiry E and said random message M from said verifier to said prover; (g) checking, in said prover, that said enquiry E has been correctly generated from said initial message X and said random message M; (h) generating, in said prover, a response Y by application of a function relating said response to said enquiry E, said secret information S related to said public information ID and said function having a known mathematical relationship to said initial message X; (i) transmitting said response Y from said prover to said verifier; (j) checking, in said verifier, whether said response Y was validly generated by computing a function of said enquiry E, said initial message X, and said public information ID; and (k) storing, in said verifier, a transcript T comprising said public information ID, said initial message X, said random message M, and said response Y.
Claim 2
Independent Claim
240 words
A method of verifying a prover possessing public information ID and related secret information S, comprising the steps of: (a) linking said prover to a verifier by a communication line; (b) generating, in said prover, an initial message X; (c) transmitting said public information ID and said initial message X from said prover to said verifier; (d) generating, in said verifier, a random message M; (e) generating, in said verifier, an enquiry E by application of a function relating said enquiry E to said initial message X and said random message M; (f) transmitting said enquiry E and said random message M from said verifier to said prover; (g) checking, in said prover, that said enquiry E has been correctly generated from said initial message X and said random message M; (h) generating, in said prover, a response Y by application of a function relating said response to said enquiry E, said secret information S related to said public information ID and said function having a known mathematical relationship to said initial message X; (i) transmitting said response Y from said prover to said verifier; (j) checking, in said verifier, whether said response Y was validly generated by computing a function of said enquiry E, said initial message X, and said public information ID; and (k) storing, in said verifier, a transcript T comprising said public information ID, said initial message X, said random message M, and said response Y.
Claim 3
Dependent Claim
36 words
The method of claim 1, wherein said public information ID, said secret information S, said initial message X, said random message M, said enquiry E, and said response Y are represented as integers in binary notation.
Claim 4
Dependent Claim
30 words
The method of claim 2, wherein computations are performed modulo a public composite number N with prime factors P and Q not known to either the prover or the verifier.
Claim 5
Dependent Claim
29 words
The method of claim 3, wherein said public information ID and said secret information S are related by a public one-way function F, and S 2 =F(ID) modulo N.
Claim 6
Dependent Claim
69 words
The method of claim 4, wherein said step (b) comprises further steps of: (b1) generating k random numbers R1, . . . , Rk, where k is a certain positive integer; (b2) computing squares X1, . . . , Xk of respective random numbers R1, . . . , Rk modulo N; and (b3) concatenating said squares X1, . . . , Xk to form said initial message X.
Claim 7
Dependent Claim
19 words
The method of claim 5, wherein said enquiry E comprises k binary digits E1, . . . , Ek.
Claim 8
Dependent Claim
35 words
The method of claim 6, wherein said binary digits E1, . . . , Ek are generated by using a public hashing function H to hash said random message M and said initial message X.
Claim 9
Dependent Claim
61 words
The method of claim 6, wherein said binary digits E1, . . . , Ek are generated by: using a digital signature function D to generate a signature J from said random message M and said initial message X; and using a public hashing function H to generate said binary digits E1, . . . , Ek from said signature J.
Claim 10
Dependent Claim
45 words
The method of claim 8, wherein: said signature J is also transmitted to said prover in said step (f); and said prover checks that said signature J has been correctly generated from said random message M and said initial message X in said step (g).
Claim 11
Dependent Claim
22 words
The method of claim 8, wherein said signature J is also stored as part of said transcript T in said step (k).
Claim 12
Dependent Claim
34 words
The method of claim 6, wherein said response Y comprises integers Y1, . . . , Yk and each Yi is equal to Ri×S Ei modulo N, for i=1, . . . , k.
Claim 13
Dependent Claim
32 words
The method of claim 11, wherein said verifier checks whether said response Y is valid in step (k) by checking whether Yi 2 =Xi×F(ID) Ei for i=1, . . . , k.
Claim 14
Dependent Claim
67 words
The method of claim 1, wherein: said prover also transmits a request R to said verifier in said step (c); said verifier uses said request R in generating said enquiry E in said step (e); said prover uses said request R in checking said enquiry E in said step (g); and said verifier stores said request R as part of said transcript T in said step (k).
Claim 15
Dependent Claim
31 words
The method of claim 1, wherein, in step (k), said verifier generates a random message M that does not appear together with said public information ID in any previously stored transcript.
Claim 16
Dependent Claim
20 words
The method of claim 14, wherein said verifier refuses to verify said prover more than a certain number of times.
Claim 17
Dependent Claim
90 words
A method of establishing validity of the transcript T stored in the verifier of claim 1, comprising the steps of: (l) linking the verifier to an arbitrator by a communication line; (m) transmitting said transcript T from said verifier to said arbitrator; (n) generating, in said arbitrator, the enquiry E of claim 1; (o) checking, in said arbitrator, whether the response Y of claim 1 is valid according to the enquiry E of claim 1, the initial message X of claim 1, and the public information ID of claim 1.
Claim 18
Dependent Claim
32 words
The method of claim 16, wherein said transcript T also comprises a signature J obtained by applying a digital signature function D to said random message M and said initial message X.
Claim 19
Dependent Claim
20 words
The method of claim 17, also comprising a step of checking, in said arbitrator, whether said signature J is valid.
Claim 20
Dependent Claim
144 words
Proving apparatus, comprising: a central processing unit for executing programs; a random-number generator coupled to said central processing unit, for generating random numbers; an I/O port coupled to said central processing unit, for transmitting public information ID and an initial message X, receiving an enquiry E and a random message M, then transmitting a response Y; and a memory coupled to said central processing unit, for storing public information ID and secret information S, said memory further containing a first program for using said random numbers to generate said initial message X, a second program for checking whether said enquiry E is related to said initial message X and said random message M according to a predetermined function, and a third program for generating said response Y as a predetermined function of said random numbers, said public information ID, and said secret information S.
Claim 21
Dependent Claim
144 words
Proving apparatus, comprising: a central processing unit for executing programs; a random-number generator coupled to said central processing unit, for generating random numbers; an I/O port coupled to said central processing unit, for transmitting public information ID and an initial message X, receiving an enquiry E and a random message M, then transmitting a response Y; and a memory coupled to said central processing unit, for storing public information ID and secret information S, said memory further containing a first program for using said random numbers to generate said initial message X, a second program for checking whether said enquiry E is related to said initial message X and said random message M according to a predetermined function, and a third program for generating said response Y as a predetermined function of said random numbers, said public information ID, and said secret information S.
Claim 22
Dependent Claim
24 words
The apparatus of claim 19, wherein said secret information S is stored in a protected part of said memory that cannot be accessed externally.
Claim 23
Dependent Claim
17 words
The apparatus of claim 19, wherein said memory also stores an integer N having secret prime factors.
Claim 24
Dependent Claim
21 words
The apparatus of claim 21, wherein said first program generates said initial message X by squaring said random numbers modulo N.
Claim 25
Dependent Claim
24 words
The apparatus of claim 19, wherein said second program applies a public hashing function to said initial message X and said random message M.
Claim 26
Dependent Claim
34 words
The apparatus of claim 21, wherein said third program multiplies said random numbers by said secret information S raised to exponents equal to individual bits of said enquiry E, multiplication being performed modulo N.
Claim 27
Dependent Claim
36 words
The apparatus of claim 19, wherein said I/O port also transmits a request R, and said second program checks said enquiry E according to said initial message X, said request R, and said random message M.
Claim 28
Dependent Claim
37 words
The apparatus of claim 19, wherein said I/O port also receives a signature J and said memory stores a fourth program for checking said signature J according to said initial message X and said random message M.
Claim 29
Dependent Claim
18 words
The apparatus of claim 26, wherein said second program checks said enquiry E according to said signature J.
Claim 30
Dependent Claim
45 words
The apparatus of claim 19, wherein said I/O port also transmits a request R and receives a signature J, and said memory stores a fourth program for checking said signature J according to said initial message X, said request R, and said random message M.
Claim 31
Dependent Claim
18 words
The apparatus of claim 28, wherein said second program checks said enquiry E according to said signature J.
Claim 32
Dependent Claim
140 words
Verifying apparatus, comprising: a central processing unit for executing programs; a random-number generator coupled to said central processing unit, for generating random numbers; an I/O port coupled to said central processing unit, for receiving public information ID and an initial message X, transmitting an enquiry E and a random message M, and receiving a response Y; and a memory coupled to said central processing unit, for storing at least one transcript, said memory further containing a first program for using said random-number generator to generate said random message M, a second program for generating said enquiry E as a function of said initial message X and said random message M, and a third program for checking whether said response Y is related to said public information ID, said initial message X, and said enquiry E according to a predetermined function.
Claim 33
Dependent Claim
140 words
Verifying apparatus, comprising: a central processing unit for executing programs; a random-number generator coupled to said central processing unit, for generating random numbers; an I/O port coupled to said central processing unit, for receiving public information ID and an initial message X, transmitting an enquiry E and a random message M, and receiving a response Y; and a memory coupled to said central processing unit, for storing at least one transcript, said memory further containing a first program for using said random-number generator to generate said random message M, a second program for generating said enquiry E as a function of said initial message X and said random message M, and a third program for checking whether said response Y is related to said public information ID, said initial message X, and said enquiry E according to a predetermined function.
Claim 34
Dependent Claim
26 words
The verifying apparatus of claim 30, wherein said transcript comprises said public information ID, said initial message X, said random message M, and said response Y.
Claim 35
Dependent Claim
29 words
The apparatus of claim 30, wherein said second program generates said enquiry E by applying a public hashing function to said initial message X and said random message M.
Claim 36
Dependent Claim
25 words
The apparatus of claim 30, wherein said enquiry E comprises k bits E1, . . . , Ek where k is a certain positive integer.
Claim 37
Dependent Claim
17 words
The apparatus of claim 33, wherein said memory also stores an integer N having secret prime factors.
Claim 38
Dependent Claim
61 words
The apparatus of claim 34, wherein said third program extracts k values X1, . . . , Xk from said initial message X, extracts k values Y1, . . . , Yk from said response Y, applies a public one-way function F to said public information ID, and checks whether Yi.sup.2 =Xi×F(ID).sup.Ei mod N for i=1, . . . , k.
Claim 39
Dependent Claim
35 words
The apparatus of claim 30, wherein said I/O port also receives a request R, and said second program generates said enquiry E from said initial message X, said request R, and said random message M.
Claim 40
Dependent Claim
37 words
The apparatus of claim 30, wherein said I/O port also transmits a signature J and said memory also stores a fourth program for generating said signature J from said initial message X and said random message M.
Claim 41
Dependent Claim
17 words
The apparatus of claim 37, wherein said second program generates said enquiry E from said signature J.
Claim 42
Dependent Claim
45 words
The apparatus of claim 30, wherein said I/O port also receives a request R and transmits a signature J, and said memory also stores a fourth program for generating said signature J from said initial message X, said request R, and said random message M.
Claim 43
Dependent Claim
17 words
The apparatus of claim 39, wherein said second program generates said enquiry E from said signature J.
Claim 44
Dependent Claim
104 words
Arbitration apparatus comprising: a central processing unit for executing programs; an I/O port coupled to said central processing unit, for receiving a transcript comprising public information ID, an initial message X, a random message M, and a response Y; and a memory coupled to said central processing unit, said memory containing a first program for generating an enquiry E according to a predetermined function of said initial message X and said random message M, and a second program for checking whether said response Y is generated according to a predetermined function of said public information ID, said initial message X, and said enquiry E.
Claim 45
Dependent Claim
104 words
Arbitration apparatus comprising: a central processing unit for executing programs; an I/O port coupled to said central processing unit, for receiving a transcript comprising public information ID, an initial message X, a random message M, and a response Y; and a memory coupled to said central processing unit, said memory containing a first program for generating an enquiry E according to a predetermined function of said initial message X and said random message M, and a second program for checking whether said response Y is generated according to a predetermined function of said public information ID, said initial message X, and said enquiry E.
Claim 46
Dependent Claim
25 words
The apparatus of claim 41, wherein said enquiry E comprises k bits E1, . . . , Ek where k is a certain positive integer.
Claim 47
Dependent Claim
17 words
The apparatus of claim 42, wherein said memory also stores an integer N with secret prime factors.
Claim 48
Dependent Claim
61 words
The apparatus of claim 43, wherein said second program extracts k values X1, . . . , Xk from said initial message X, extracts k values Y1, . . . , Yk from said response Y, applies a public one-way function F to said public information ID, and checks whether Yi.sup.2 =Xi×F(ID).sup.Ei mod N for i=1, . . . , k.
Claim 49
Dependent Claim
34 words
The apparatus of claim 41, wherein said transcript also comprises a request R, and said first program generates said enquiry E from said initial message X, said request R, and said random message M.
Claim 50
Dependent Claim
37 words
The apparatus of claim 41, wherein said transcript also comprises a signature J and said memory also stores a third program for checking said signature J according to said initial message X and said random message M.
Claim 51
Dependent Claim
17 words
The apparatus of claim 46, wherein said first program generates said enquiry E from said signature J.
Claim 52
Dependent Claim
44 words
The apparatus of claim 41, wherein said transcript also comprises a request R and a signature J, and said memory also stores a third program for checking said signature J according to said initial message X, said request R, and said random message M.
Claim 53
Dependent Claim
17 words
The apparatus of claim 48, wherein said first program generates said enquiry E from said signature J.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-09-13 | 1997-03-15 | 1997-09-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-09-13 | 2001-03-15 | 2001-09-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-09-13 | 2005-03-15 | 2005-09-14 | $7700.00 | Window Closed / Lapsed |