METHOD, APPARATUS AND SYSTEM FOR VERIFYING AUTHENTICITY OF AN OBJECT

• US 20100122093A1
• Filed: 07/04/2006
• Published: 05/13/2010
• Est. Priority Date: 07/07/2005
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Maubach, Stefan Jean, Skoric, Boris, Tuyls, Pim Theo, Wolters, Robertus Andrianus Maria
• Granted Patent: US 8,886,951 B2
• Time in Patent Office: Days
• US Class Current: 713/180
• 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 PRV to a verifier VER, the method comprising the following steps:

generating, by the prover PRV, a secret S using a physical token PUF,

obtaining, by the verifier VER, a public value PV which has been derived from the secret S using a function F, and where the function F is selected such that it is computationally expensive to establish the secret S given the public value PV, and

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 PUF, where the prover PRV makes use of the secret S and the verifier VER makes use of the public value PV.

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

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

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

5. The method as claimed in claim 1, where the step to generate the secret S further comprises a sub-step to:

generate a response R using the physical token PUF, and

combine the response R with a helper data H and apply an Error Correcting Code.

6. The method as claimed in claim 1, where the public value PV is obtained from a certificate CERT signed by a Trusted Third Party TTP, and where the method further comprises a step in which the signature of the certificate CERT is verified to establish authenticity of the public value PV.

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

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

23. Use of the method of claim 1 in a method of authenticating a device WDEV that attempts to join a network WLAN.

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

a secret generation means SGM arranged to generate a secret S using a physical token PUF,

the object further characterized in that it comprises;

a first zero knowledge protocol means ZKPM1 arranged to conduct a zero knowledge protocol with an apparatus for verifying authenticity VERF, in order to prove to the apparatus for verifying authenticity VERF, with a pre-determined probability, that the object PRVR has access to the physical token PUF, using the secret S.

10. The object PRVR as claimed in claim 9, where the object PRVR further comprises a function means FM for applying a function F to the secret S in order to generate a public value PV based on the secret S, and where the function F is selected such that it is computationally expensive to establish the secret S given the public value PV.

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

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

13. The object PRVR as claimed in claim 9, where the secret generation means SGM is arranged to generate the secret S using the physical token PUF every time that the secret S is needed.

14. The object PRVR as claimed in claim 9, where the secret generation means SGM is arranged to:

generate a response R using the physical token PUF, and

combine the response R with a helper data H, and apply an Error Correcting Code.

15. The object PRVR as claimed in claim 9, where the object PRVR further comprises a storage means STM for storing a certificate CERT comprising the public value PV.

16. The object PRVR as claimed in claim 9, where the object PRVR further comprises a first communication means CM1 for communicating with the apparatus for verifying authenticity VERF.

17. The object PRVR as claimed in claim 16, where the first communication means CM1 is a means for Near Field Communication.

18. The object PRVR as claimed in claim 9, where the first zero knowledge protocol means ZKPM1 is arranged to conduct a zero knowledge protocol that is based on the fact that calculating the e^th root modulo N is computationally expensive.

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

20. A system SYS for proving the authenticity of an object to an apparatus for verifying authenticity, the system comprising;

an object PRVR according to claim 9 and an apparatus for verifying authenticity VERF, wherein the apparatus for verifying authenticity VERF comprises;

an obtaining means OB arranged to obtain a public value PV which has been derived from the secret S,

a second zero knowledge protocol means ZKPM2 arranged to conduct the zero knowledge protocol with the first zero knowledge protocol means ZKPM1, in order to verify, with the predetermined probability, that the object PRVR has access to the physical token PUF, using the public value PV.

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

22. The system as claimed in claim 20, wherein the object PRVR is embedded in a passport PSSP, and the apparatus for verifying authenticity VERF is a passport authentication terminal TRM arranged to conduct a zero knowledge protocol with said object PRVR, in order to prove authenticity of said passport PSSP with a predetermined probability.