Method of Authentication Based on Polyomials

• US 20080209214A1
• Filed: 09/27/2005
• Published: 08/28/2008
• Est. Priority Date: 09/30/2004
• Status: Active Grant

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Kevenaar, Thomas Andreas Maria, Schrijen, Geert Jan
• Granted Patent: US 8,645,694 B2
• Time in Patent Office: Days
• US Class Current: 713/169
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/083 involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]
• CPC Class Codes: H04L 9/0866 involving user or device identifiers, e.g. serial number, physical or biometrical information, DNA, hand-signature or measurable physical characteristics
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• 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/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC
• CPC Class Codes: H04L 9/3273 for mutual authentication network architectures or network communication protocols for achieving mutual authentication in a packet data network H04L63/0869

Abstract

There is provided an authentication method for a system (10) comprising several devices (30). The method involves: a) providing each device (30) with an identity value (pi: i=1, . . . , n) and a polynomial (P) for generating a polynomial key; (b) including a verifier device (p₁) and a prover device (P₂)amongst said devices (30); (c) arranging for the prover device (p₂) to notify its existence to the verifier device (P₁); (d) arranging for the verifier device (p_i) to challenge the prover device (p₂) to encrypt a nonce using the prover (P₂)device'"'"'s polynomial (P) key and communicate the encrypted nonce as a response to the verifier device (p₁); (e) arranging for the verifier device (p₁) to receive the encrypted nonce as a further challenge from the prover device (p_Z) and: (i ) encrypt the challenge using the polynomial keys generated from a set of stored device identities; or (ii) decrypt the challenge received using the set of polynomial keys; until said verifier device (p₁) identifies an authentication match.

Claims

1. A method of authentication based on polynomials for a system (10) comprising a plurality of devices (30) operable to mutually communicate, said method comprising steps of:

(a) providing (20) each of said plurality of devices (30) with a corresponding identity value (p_i;

i=1, n) together with an associated polynomial (P) for generating a polynomial key;

(b) arranging for the plurality of devices (30) to include a verifier device (p₁) and a prover device (p₂);

(c) arranging for the prover device (p₂) to notify its existence to the verifier device (p₁);

(d) arranging for the verifier device (p₁) to issue a first challenge to the prover device (p₂) to encrypt a nonce using the prover (p₂) device'"'"'s polynomial (P) key and communicate the encrypted nonce as a response back to the verifier device (p₁);

(e) arranging for the verifier device (p₁) to receive the encrypted nonce as the response from the prover device (p₂) and;

(i) to encrypt the first challenge using the polynomial keys generated from a set of stored device identities;

or

(ii) to decrypt the response received from the prover device (p₂) using the polynomial keys;

until said verifier device (p₁) identifies a match for said response, said match being indicative of authentication.

2. A method as claimed in claim 1, wherein issuance of the identity values (p₁) and associated polynomials is undertaken via a trusted third party (20).

3. A method as claimed in claim 1, including a further step of applying said method of authentication in general mutual authenticated key establishment protocols in said system for providing mutual authentication for said plurality of devices, said mutual protocols providing privacy to at least one of said plurality of devices.

4. A method as claimed in claim 1, wherein a random value is additionally created by the prover device and encrypted together with the response from the verifier device for sending back to the verifier device, said random value being operable to function as a session key.

5. A method as claimed in claim 1, wherein the first challenge from the verifier device (p₁) to the prover device (p₂) is implemented such that the nonce is a random number.

6. A method as claimed in claim 1, said method further including a step of configuring the system so that said plurality of devices includes multiple prover devices and multiple verifier devices, said multiple prover devices including a subset of prover devices operable to authenticate to a particular verifier device of the multiple verifier devices.

7. A method as claimed in claim 1, wherein said prover devices are implemented as smart cards or tags enabling access to services related to and/or coupled to a given verifier device.

8. A method as claimed in claim 1, wherein the prover device is operable to apply a hash function or keyed hash function to create a response to the first challenge from the verifier device.

9. A system operable according to the method as claimed in claim 1.

10. A system as claimed in claim 9, the system being adapted for providing at least one of:

(a) authentication associated with financial transactions executed within banking systems;

(b) controlling access, for example personnel access, by way of tags or similar portable identifiers authenticating within a system operable according to the method.

11. Software on a data carrier executable on computing hardware to implement the method as claimed in claim 1.

12. A smart card or tag for undertaking authentication in an authentication system, the system being arranged to be operable according to a method as claimed in claim 1.