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

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.