Method, apparatus and system for verifying authenticity of an object

• US 8,886,951 B2
• Filed: 07/04/2006
• Issued: 11/11/2014
• Est. Priority Date: 07/07/2005
• Status: Active Grant

• Current Assignee: Intrinsic ID BV
• Original Assignee: Intrinsic ID BV
• Inventors: Tuyls, Pim Theo, Skoric, Boris, Maubach, Stefan Jean, Wolters, Robertus Adrianus Maria
• Primary Examiner(s): CHAO, MICHAEL W
• Application Number:
  US11/993,724
• Publication Number:
  US 20100122093A1
• Time in Patent Office: 3,052 Days
• Field of Search: 713/185
• US Class Current: 713/185
• CPC Class Codes: G06F 21/33 using certificates
• CPC Class Codes: G06F 21/34 involving the use of external additional devices, e.g. dongles or smart cards
• CPC Class Codes: G06F 21/73 by creating or determining hardware identification, e.g. serial numbers
• CPC Class Codes: G07C 9/20 involving the use of a pass
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3234 involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853
• CPC Class Codes: H04L 9/3278 using physically unclonable functions [PUF]
• CPC Class Codes: Y04S 40/20 Information technology specific aspects, e.g. CAD, simulation, modelling, system security

Abstract

The invention relates to a method for proving authenticity of a prover PRV to a verifier VER, the method comprising generating a secret S using a physical token by the prover PRV. Obtaining a public value PV by the verifier, where the public value PV has been derived from the secret S using a function for which the inverse of said function is computationally expensive. The method further comprising a step for conducting a zero knowledge protocol between the prover PRV and the verifier VER in order to prove to the verifier VER, with a pre-determined probability, that the prover PRV has access to the physical token, where the prover PRV makes use of the secret S and the verifier VER makes use of the public value PV. The invention further relates to a system employing the method, and an object for proving authenticity.

Claims

1. A method for proving authenticity of a prover device to a verifier device, the method comprising acts of:

generating, by the prover device, a secret using a physical token, the physical token being challengeable in order to evoke a unique response from the physical token, the physical token is a physical unclonable function and comprises many randomly distributed components in a complex physical system, when challenged complex physics governing the interaction between the physical token and the challenge leads to the response, the secret being generated from said response, generating the secret further comprises acts of;

generating a response using the physical token, combining the response with a helper data, and applying an Error Correcting Code;

obtaining, by the verifier device, a public value in a form of a certificate which has been derived from the secret using a function, and where the function is selected such that it is computationally expensive to establish the secret given the public value; and

conducting a zero knowledge protocol between the prover device and the verifier device in order to prove to the verifier device that the prover device has access to the physical token, where the prover device makes use of the secret and the verifier device makes use of the public value.

2. The method as claimed in claim 1, wherein the function is a one-way function.

3. The method as claimed in claim 1, wherein the function is a trapdoor one-way function.

4. The method as claimed in claim 1, where the secret is generated using the physical token every time that the secret is needed.

5. The method as claimed in claim 1, where the certificate is signed by a Trusted Third Party, and where the method further comprises an act of verifying the signature of the certificate to establish authenticity of the public value.

6. The method as claimed in claim 1, where the zero knowledge protocol is based on the fact that calculating the eth root modulo N is computationally expensive.

7. The method as claimed in claim 1, where the zero knowledge protocol is based on the fact that calculating discrete logarithms is computationally expensive.

8. The method of claim 1, comprising determining for a pre-determined probability the number of iterations, each iteration having a guessing probability, needed to prove to the verifier device, with the pre-determined probability, that the prover device has access to the physical token, and wherein the zero knowledge protocol uses the number of iterations.

9. An object for proving authenticity, the object comprising:

a physical token;

a secret generator configured to generate a secret using the physical token, the physical token being challengeable in order to evoke a unique response from the physical token, the physical token is a physical unclonable function and comprises many randomly distributed components in a complex physical system, when challenged complex physics governing the interaction between the physical token and the challenge leads to the response, the secret being generated from said response, the secret generator being further configured to;

generate a response using the physical token, combine the response with a helper data, and apply an Error Correcting Code;

a storage configured to store a public value in a form of a certificate; and

a first zero knowledge protocol conductor configured to conduct a zero knowledge protocol using the secret, with an apparatus for verifying authenticity, in order to prove to the apparatus for verifying authenticity that the object has access to the physical token, the apparatus for verifying authenticity using the public value.

10. The object as claimed in claim 9, where the object further comprises a function applier configured to apply a function to the secret in order to generate the public value based on the secret, and where the function is selected such that it is computationally expensive to establish the secret given the public value.

11. The object as claimed in claim 10, wherein the function is a one-way function.

12. The object as claimed in claim 10, wherein the function is a trapdoor one-way function.

13. The object as claimed in claim 9, where the secret generator is configured to generate the secret using the physical token every time that the secret is needed.

14. The object as claimed in claim 9, where the object public value is stored as a signed public value.

15. The object as claimed in claim 14, wherein the storage is configured to store helper data.

16. The object as claimed in claim 9, where the object further comprises a first communicator configured to communicate with the apparatus for verifying authenticity.

17. The object as claimed in claim 16, where the first communicator is configured for Near Field Communication.

18. The object as claimed in claim 9, where the first zero knowledge protocol conductor is configured to conduct a zero knowledge protocol that is based on the fact that calculating the eth root modulo N is computationally expensive.

19. The object as claimed in claim 9, where the first zero knowledge protocol conductor is configured to conduct a zero knowledge protocol that is based on the fact that calculating discrete logarithms is computationally expensive.

20. The object as claimed in claim 9, wherein the authenticity is verified to join a network.

21. The object of claim 9, wherein the zero knowledge protocol uses a number of iterations each having a guessing probability, the number of iterations being determined for the pre-determined probability as needed to prove to the apparatus for verifying authenticity, with the pre-determined probability, that a prover has access to the physical token.

22. The object as claimed in claim 9, the certificate comprising a variety of public values corresponding to multiple challenge response pairs of the physical token.

23. The object as claimed in claim 9, wherein the object is an RF ID tag.

24. A system for proving the authenticity of an object to an apparatus for verifying authenticity, the system comprising:

an object comprising;

a physical token,

a secret generator configured to generate a secret using the physical token, the physical token being challengeable in order to evoke a unique response from the physical token, the physical token is a physical unclonable function and comprises many randomly distributed components in a complex physical system, when challenged complex physics governing the interaction between the physical token and the challenge leads to the response, the secret being generated from said response, the secret generator being further configured to;

generate a response using the physical token, combine the response with a helper data, and apply an Error Correcting Code;

a first zero knowledge protocol conductor configured to conduct a zero knowledge protocol with an apparatus for verifying authenticity, in order to prove to the apparatus for verifying authenticity that the object has access to the physical token, using the secret; and

an apparatus for verifying authenticity, wherein the apparatus for verifying authenticity comprises;

an obtainer configured to obtain a public value, in a form of a certificate, which has been derived from the secret,

a second zero knowledge protocol conductor configured to conduct the zero knowledge protocol with the first zero knowledge protocol conductor, in order to verify that the object has access to the physical token, using the public value.

25. The system as claimed in claim 24, wherein the object is delivered together with a software, and the apparatus for verifying authenticity is a computer configured to run an authenticity verification program for conducting a zero knowledge protocol with said object, in order to prove authenticity of said software with the predetermined probability before allowing said software to be installed.

26. The system as claimed in claim 24, wherein the object is embedded in a passport, and the apparatus for verifying authenticity is a passport authentication terminal configured to conduct a zero knowledge protocol with said object, in order to prove authenticity of said passport with the predetermined probability.