Method for zero-knowledge authentication of a prover by a verifier providing a user-selectable confidence level and associated application devices

• US 7,363,492 B2
• Filed: 02/25/2005
• Issued: 04/22/2008
• Est. Priority Date: 02/25/2005
• Status: Expired due to Fees

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Dabbish, Ezzat A., Kuhlman, Douglas A., Puhl, Larry C.
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): Tran; Tongoc
• Application Number:
  US11/066,639
• Publication Number:
  US 20060195692A1
• Time in Patent Office: 1,152 Days
• Field of Search: 713/155, 713/161, 713/168, 713/169, 713/170, 713/171, 713/156, 713/175, 713/176, 713/166, 380/232, 380/30, 726 2- 5, 726/39, 726/12, 726/14
• US Class Current: 713/166
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs

Abstract

Authentication is performed to a confidence level (CL) desired by a verifier (220). A prover (210) picks and sends certain same size, square matrices to the verifier (220). A random request bit is sent (234) from the verifier (220) to the prover (210) after the receipt of a certain square matrix. Depending on the request bit, calculations are made (244, 264) by the verifier (220) to determine if the matrices sent from the prover are verifiable. The prover (210) is iteratively authenticated by the verifier (220). Iterations are continued until (320) a count of the iterations (IL) reaches a number sufficient to achieve the desired confidence level (CL). After a delay, more iterations can achieve a higher confidence level by building on previous result of authentication without having to begin at zero. During this delay, the verifier (220) can perform tasks in reliance on the result of authentication. Digital logic can perform the authentication.

Claims

1. An authentication method having a selectable confidence level, comprising the steps of:

(a) iteratively interacting between a prover and a verifier, wherein the prover and verifier are electronic devices that perform calculations and pass values between themselves that result from the calculations;

(b) determining from at least one of the values whether each iteration yields one of a pass and fail result, wherein each iteration that yields a pass result establishes an authentication confidence level that is greater than an authentication level from a previous iteration, and wherein a fail result stops the iterations;

(c) continuing to perform iterations, so long as each iteration achieves a pass result, until a count of iterations reaches a number sufficient to achieve a first authentication confidence level desired by the verifier;

(d) allowing performance of a first task by the verifier in reliance on the first authentication confidence level;

(e) continuing to perform iterations, so long as each iteration achieves a pass result, until a count of iterations reaches a number sufficient to achieve a second authentication confidence level desired by the verifier;

(f) allowing performance of a second task by the verifier in reliance on the second authentication confidence level desired by the verifier; and

(g) disallowing performance of the at least one task by the verifier when an iteration achieves a fail result before the second authentication confidence level is met.

2. An authentication method having a selectable confidence level according to claim 1, wherein each iteration reduces doubt in the result by essentially half.

3. An authentication method having a selectable confidence level according to claim 1, wherein the number sufficient to achieve the first authentication confidence level desired by the verifier in said step (c) is a number chosen by the verifier sufficient to satisfy the security requirements of an environment of at least the verifier.

4. An authentication method having a selectable confidence level according to claim 1, wherein the method is performed among an ad-hoc network of the prover and at least one verifier.

5. An authentication method having a selectable confidence level according to claim 1, wherein the prover is an automobile component and the verifier is an automobile system controller.

6. A verifier device comprising digital logic for performing the steps of claim 1.

7. An authentication method having a selectable confidence level according to claim 1, wherein said step (a) of iteratively interacting between a prover and a verifier uses same size, square matrices.

8. An authentication method having a selectable confidence level according to claim 7, wherein entries of binary digits fill the same size, square matrices used in said step (a) of iteratively authenticating a prover by a verifier.

9. An authentication method having a selectable confidence level according to claim 7,

wherein said step (a) comprises the substeps of:

(a)(a) establishing a private key matrix K, wherein the private key matrix K is a square matrix of a predetermined size;

(a)(b) choosing a base matrix N of the same size as the private key matrix K;

(a)(c) calculating a same-size, masked matrix M;

(a)(d) picking by the prover a same-size, square matrix S for this iteration;

(a)(e) calculating by the prover a same-size, commitment matrix C after the picking of the square matrix S in said step (a)(d) and sending the commitment matrix C from the prover to the verifier; and

(a)(f) sending a request from the verifier to the prover after the receipt of the commitment matrix C in said step (a)(e), wherein the request comprises at least first and second request states;

wherein said step (b) comprises the substeps of;

(b)(g) on a first request state of the request, (b)(g)(1) the prover sending the square matrix S to the verifier, and (b)(g)(2) the verifier using received matrix S and the masked matrix M to verify the commitment matrix C, if not verifiable, then authentication fails, otherwise go to step (c)(i); and

(b)(h) on a second request state of the request, (b)(h)(1) the prover calculating a same-size, masked key matrix V from the square matrix S and the private key matrix K and sending the masked key matrix V to the verifier, and (b)(h)(2) the verifier using received masked key matrix V and the base matrix N to verify the commitment matrix C, if not verifiable, then authentication fails, otherwise go to step (c)(i); and

wherein said step (c) comprises the substeps of;

(c)(i) determining whether to make another iteration to improve confidence and, if so, returning to step (a)(d) to make an additional iteration, otherwise issuing a pass decision.

10. A method in a prover of authenticating a prover using same-size square matrices, wherein the prover has a private key matrix K and a base matrix N, wherein the private key matrix K is a square matrix of a predetermined size, and wherein the base matrix N is of the same size as the private key matrix K, and wherein the prover has a masked matrix M, wherein the masked matrix M is of the same size as the base matrix N, the method comprising the steps of:

(a) picking a square matrix S of the same size as the private key matrix K;

(b) calculating a same-size, commitment matrix C based on the square matrix S and the masked matrix M and sending the commitment matrix C to at least one verifier;

(c) receiving a request from the verifier, wherein the request comprises at least first and second request states;

(d) on a first request state of the request, sending the square matrix S to the verifier; and

(e) on a second request state of the request, calculating a same-size, masked key matrix V from the square matrix S and the private key matrix K and sending the masked key matrix V to the verifier, wherein the prover and verifier are electronic devices.

11. A method according to claim 10, wherein the masked matrix M is calculated based on the private key matrix K and the base matrix N.

12. A method according to claim 11, wherein M=KNK^T.

13. A method according to claim 11, wherein the masked key matrix V calculated in said step (e) as V=SK.

14. A method according to claim 10, wherein the square matrix S picked in said step (a) is a matrix with random entries.

15. A method according to claim 10, wherein the calculating of the commitment matrix C in said step (b) calculates the commitment matrix C based on C=SMS^T for this iteration.

16. A method according to claim 10, wherein the private key matrix K, the base matrix N, the masked matrix M, the square matrix S, the commitment matrix C, and the masked key matrix V have each entry being a binary digit.

17. A method according to claim 16, wherein the size of the private key matrix K, the base matrix N, the masked matrix M, the square matrix S, the commitment matrix C, and the masked key matrix V are of no less then about 24×

24.

18. A prover device comprising digital logic for performing the steps of claim 10.

19. A method in a verifier of deciding whether or not to authenticate a prover using same-size matrices, wherein the prover provides a base matrix N and a masked matrix M, wherein both the base matrix N and the masked matrix M are square matrices of a predetermined size, the method comprising the steps of:

(a) receiving a same-size, commitment matrix C from the prover;

(b) choosing one of at least first and second request states and sending the chosen request state to the prover;

(c) on a first request state of the request, receiving from the prover a same-size, square matrix S and using the square matrix S and the masked matrix M to verify the commitment matrix C;

(d) on a second request state of the request, receiving a same-size, masked key matrix V from the prover and using the received masked key matrix V and the base matrix N to verify the commitment matrix C; and

(e) if the commitment matrix C is unverifiable, then authentication fails, wherein the prover and verifier are electronic devices.

20. A method according to claim 19, further comprising the step of (f) determining whether to make another iteration to improve confidence and, if so, repeating from said step (a), otherwise issuing a pass decision.

21. A method according to claim 20, wherein said step (f) of determining whether to make another iteration to improve confidence continues iterations until a count of the iterations reaches a number sufficient to achieve a confidence level desired by the verifier.

22. A method according to claim 19, wherein the request sent from the verifier to the prover in said step (c) is unpredictable from the perspective of the prover.

23. A method according to claim 19,

wherein the verification of the commitment matrix C in said step (c) verifies SMS^T=C;

and

wherein the verification of the commitment matrix C in said step (d) verifies VNV^T=C.

24. A method according to claim 19, wherein the base matrix N, the masked matrix M, the square matrix S, the commitment matrix C, and the masked key matrix V have each entry being a binary one or zero.

25. A method according to claim 24, wherein the size of the base matrix N, the masked matrix M, the square matrix S, the commitment matrix C, and the masked key matrix V are of no less then about 24×

24.

26. A verifier device comprising a digital logic for performing the steps of claim 19.

27. A method of deciding whether or not to authenticate a prover using same-size square matrices, the method comprising the steps of:

(a) establishing a private key matrix K, wherein the private key matrix K is a square matrix of a predetermined size;

(b) choosing a base matrix N of the same size as the private key matrix K;

(c) calculating a same-size, masked matrix M;

(d) picking by the prover a same-size, square matrix S for this iteration;

(e) calculating by the prover a same-size, commitment matrix C after the picking of the square matrix S in said step (d) and sending the commitment matrix C from the prover to the verifier;

(f) sending a request from the verifier to the prover after the receipt of the commitment matrix C in said step (e), wherein the request comprises at least first and second request states;

(g) on a first request state of the request, (g)(1) sending the square matrix S from the prover to the verifier, and (g)(2) the verifier using received matrix S and the masked matrix M to verify the commitment matrix C, if not verifiable, then authentication fails, otherwise go to step (i);

(h) on a second request state of the request, (h)(1) the prover calculating a same-size, masked key matrix V from the square matrix S and the private key matrix K and sending the masked key matrix V to the verifier, and (h)(2) the verifier using received masked key matrix V and the base matrix N to verify the commitment matrix C, if not verifiable, then authentication fails, otherwise go to step (i); and

(i) determining whether to make another iteration to improve confidence and, if so, returning to step (d) to make an additional authentication iteration, otherwise issuing a pass decision, wherein the prover and verifier are electronic devices.

28. A method according to claim 27, wherein said step (i) of determining whether to make another iteration to improve confidence continues iterations until a count of the iterations reaches a number sufficient to achieve a confidence level desired by the verifier.