Method and apparatus for pseudonym generation and authentication

• US 8,683,209 B2
• Filed: 10/13/2009
• Issued: 03/25/2014
• Est. Priority Date: 10/14/2008
• Status: Expired due to Fees

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips N.V.
• Inventors: Li, Hui, Qu, Jin
• Primary Examiner(s): Kim, Jung
• Assistant Examiner(s): Wilcox, James J
• Application Number:
  US13/123,918
• Publication Number:
  US 20110202767A1
• Time in Patent Office: 1,624 Days
• Field of Search: None
• US Class Current: 713/182
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/88 Medical equipments
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority

Abstract

The invention provides a method and apparatus for pseudonym generation and authentication. The method comprises the steps of: transmitting a user identity ID_user to a Personal Identity Manager (PIM); receiving a set of public parameters and a prime pseudonym P_prime corresponding to the ID user from the PIM; and selecting at least two random parameters, and generating a sub-pseudonym P_pseu with the at least two random numbers, the set of public parameters, and the prime pseudonym P_prime.

Claims

1. A method for pseudonym generation in a Personal Identity Manager (PIM), the method comprising:

with a computer hardware processor, determining a set of public parameters {g,g^∂

,G₁,G₂,ê

,H₂,p} in which;

G₁ and G₂ are two selected groups of order q modulo p, in which q is a prime number;

ê

is a bilinear map and ê

;

G₁×

G₁→

G₂,

g is a random generator selected from the group G₁,

H₂ is a one-way hash function and H₂;

G₂→

{0,1}*, and

H₁;

{0,1}*→

G₁;

with the computer hardware processor, receiving a user identity ID_user from a user device;

with the computer hardware processor, generating a prime pseudonym P_prime=<

H₁(ID_user),H₁^∂

(ID_user)>

based on the determined set of private parameters and the ID_user, in which H₁ is a one-way hash function, ∂

is a random number selected from a domain Z_p, and p is a selected prime number;

with the computer hardware processor, transmitting the prime pseudonym P_prime and the set of public parameters to the user device;

with the computer hardware processor, receiving a sub-pseudonym P_pseu=<

Q_A,Q_B,c_A>

from a third-party device;

with the computer hardware processor, calculating a query parameter Ver=ê

(g^∂

,Q_A)c_A with the sub-pseudonym P_pseu and the set of public parameters;

with the computer hardware processor, searching for a user identity ID′

_user in stored user identities based on the query parameter V_er such that ê

(Q_B,H^∂

(ID′

_user))=Ver;

with the computer hardware processor, transmitting the ID′

_user to the third-party device as a user identity corresponding to the P_pseu.

2. The method as set forth in claim 1, further comprising the steps of:

receiving an acquisition request from the third-party device; and

transmitting the set of public parameters to the third-party device in response to the acquisition request.

3. The method as set forth in claim 1, further comprising with the computer hardware processor:

receiving a sub-pseudonym P_pseu from the user device; and

authenticating a validation of the sub-pseudonym P_pseu by interacting with the user device.

4. A method for pseudonym generation, the method comprising:

with a computer hardware processor, receiving a user identity ID_user and calculating a prime pseudonym P_prime corresponding to the user ID with a computer hardware processor of a Personal Identity Manager (PIM) system;

with the computer hardware processor, receiving a set of public parameters is {g,g^∂

,G₁,G₂,ê

,H₂,p}, from the PIM system in which;

p is a prime number and ∂

is a random number selected from a domain Z_p;

G₁ and G₂ are two groups of order q modulo p, in which q is a prime number;

ê

is a bilinear map and ê

;

G₁×

G₁→

G₂;

g is a random generator in the group G₁; and

H₂ is a one-way hash function and H₂;

G₂→

{0,1}*;

and the prime pseudonym is P_prime=<

H₁(ID_user),H1^∂

(ID_user)>

,

in which H₁ is a one-way hash function and H₁;

G₁→

{0,1}*;

with the computer hardware processor, generating a sub-pseudonym P_pseu with the at least two random parameters, the set of public parameters, and the prime pseudonym P_prime including;

selecting two random numbers k₁ and k₂ from the domain Z_p based on the set of public parameters; and

with the selected random numbers k₁ and k₂, the set of public parameters and the prime pseudonym P_prime, calculating parameters;

Q_A=H₁^k12k2(ID);

Q_B=g^k12;

c_A=ê

(Q_C,Q_D), in which Q_C=g^k1k2, Q_D=H₁<sup>∂

k1(k2−

1−

1)</sup>(ID), and k₂k₂<sup>−

1</sup> mod p=1; and

with the computer hardware processor, generating a sub-pseudonym P_pseu=<

Q_A,Q_B,c_A>

based on the calculated parameters.

5. The method as set forth in claim 4, further comprising with the computer hardware processor:

transmitting the sub-pseudonym P_pseu and an identifier ID_server for identifying the PIM to a third-party device; and

authenticating the sub-pseudonym P_pseu by interacting with the third-party device as an authenticator.

6. The method as set forth in claim 5, wherein the step of authenticating comprises:

authenticating a validation of the sub-pseudonym P_pseu by exchanging zero-knowledge proofs with the authenticator.

7. The method as set forth in claim 6, wherein the step of exchanging zero-knowledge proofs with the authenticator comprises:

receiving a query message from the authenticator, the query message being generated in accordance with the set of public parameters and the sub-pseudonym P_pseu, and being represented as <

g^t,K_ses⊕

H₂(O_B^tc_A^t),Enc(K_ses,N_a)>

;

in which t is a random number selected by the authenticator from Z_p;

O_B=ê

(g^∂

,Q_A);

K_ses is an original session key selected by the authenticator;

N_a is a query content selected by the authenticator randomly; and

Enc(K_ses,N_a) represents an encrypted content obtained by encrypting the query content N_a with the original session key K_ses;

calculating a session key K*_ses with K*_ses=K_ses⊕

H₁(O_B^tc_A^t)⊕

H₁(ê

(g^t,(H₂^∂

(ID_user))^k12t)) based on the query message and the prime pseudonym P_prime;

decrypting the encrypted content Enc(K_ses,N_a) with the session key K*_ses so as to obtain a decrypted content N_a*;

selecting a response content N_b corresponding to the decrypted content N_a* in accordance with a predetermined rule, and encrypting the response content N_b with the session key K*_ses so as to obtain a response message Enc(K*_ses,N_b); and

transmitting the response message Enc(K*_ses,N_b) to the authenticator.

8. The method as set forth in claim 4, further comprising, with the computer hardware processor:

transmitting the sub-pseudonym P_pseu to the PIM; and

authenticating the sub-pseudonym P_pseu using the PIM system as an authenticator.

9. A method for pseudonym authentication in a third-party device, the method comprising the steps of:

with a computer hardware processor of the third-party device, receiving a sub-pseudonym P_pseu and an identifier ID_server for identifying a Personal Identity Manager (PIM) from a user device;

with the third-party device computer hardware processor, obtaining a set of public parameters {g,g^∂

,G₁,G₂,ê

,H₂,p} from the PIM system based on the identifier ID_server in which;

p is a prime number and ∂

is a random number selected from a domain Z_p,

G₁ and G₂ are two groups of order q modulo p, in which q is a prime number,

ê

is a bilinear map and ê

;

G₁×

G₁→

G₂,

g is a random generator in the group G₁, and

H₂ is a one-way hash function and H₂;

G₂→

{0,1}*; and

with the third-party device computer hardware processor, authenticating a validation of the sub-pseudonym P_pseu by exchanging zero-knowledge proofs with a computer hardware processor of the user device on the basis of the set of public parameters, exchanging the zero-knowledge proofs including;

selecting a random number t from a domain Z_p,

selecting an original session key K_ses and a query content N_a, and encrypting the query content N_a with the original session key K_ses to obtain an encrypted content Enc(K_ses,N_a),

generating a query message <

g^t,K_ses⊕

H₂(O_B^tc_A^t),Enc(K_ses,N_a)>

with the random number t, the set of public parameters, the sub-pseudonym P_pseu, and the encrypted content Enc(K_ses,N_a), in which O_B=ê

(g^∂

,Q_A);

transmitting the query message to the user device,

receiving a response message Enc(K*_ses,N_b) from the user device, in which K*_ses is a session key calculated with a computer hardware processor of the user device from the query message, and N_b is a response content selected by the user device computer hardware processor in accordance with a predetermined rule based on a query content decrypted from Enc(K_ses,N_a),

decrypting the response message with the original session key K_ses; and

determining whether the predetermined rule is met between the decrypted response content N_b* and the query content N_a so as to authenticate the validation of the sub-pseudonym P_pseu.

10. The method as set forth in claim 9, wherein:

the sub-pseudonym P_pseu is transmitted to the PIM system; and

a user identity ID′

_user is received from the PIM system as the user identity ID_user corresponding to the sub-pseudonym P_pseu.

11. A Personal Identity Manager (PIM) system, comprising:

a PIM system computer hardware processor programmed to;

determine a set of public parameters {g,g^∂

,G₁,G₂,ê

,H₂,p} and a set of private parameters in which;

p is a prime number and ∂

is a random number selected from a domain Z_p,

G₁ and G₂ are two groups of order q modulo p, in which q is a prime number,

ê

is a bilinear map and ê

;

G₁×

G₁→

G₂,

g is a random generator in the group G₁, and

H₂ is a one-way hash function and H₂;

G₂→

{0,1}*,

receive a user identity ID_user and a sub-pseudonym P_pseu=<

Q_A,Q_B,c_A>

from a third-party device;

generate a prime pseudonym P_prime=<

H₁(ID_user),H₁^∂

(ID_user)>

based on the set of private parameters and the ID_user, in which H₁ is a one-way hash function, ∂

is a random number selected from a domain Z_p, and p is a selected prime number and H₁;

G₁→

{0,1}*;

calculate a query parameter Ver=ê

(g^∂

,Q_A)c_A with the sub-pseudonym P_pseu and the set of public parameters; and

search for a user identity ID′

_user in a storage unit storing the ID_user based on the query parameter such that ê

(Q_B,H^∂

(ID′

_user))=Ver ;

control a transmitter to transmit the prime pseudonym P_prime to a user device and transmit the ID′

_user as a user identity corresponding to the sub-pseudonym P_pseu to the third-party device.

12. A user device comprising:

a transmitting unit configured to transmit a user identity ID_user to a Personal Identity Manager (PIM) system;

a receiving unit configured to receive a set of public parameters {g,g^∂

,G₁,G₂,ê

,H₂,p} and a prime pseudonym P_prime corresponding to the ID_user from the PIM system, wherein;

p is a prime number and ∂

is a random number selected from a domain Z_p,

G₁ and G₂ are two groups of order q modulo p, in which q is a prime number,

ê

is a bilinear map and ê

;

G₁×

G₁→

G₂,

g is a random generator in the group G₁,

H₂ is a one-way hash function and H₂;

G₂→

{0,1 }*,

and the prime pseudonym P_prime=<

H₁(ID_user),H₁^∂

(ID_user)>

,

H₁ is a one-way hash function, and

H₁;

G₁→

{0,1}*; and

a user computer hardware processor configured to;

select at least two random numbers k₁ and k₂, and

calculate a sub-pseudonym P_pseu with the selected random numbers k₁ and k₂, the public parameters, and the prime pseudonym P_prime, in which;

Q_A=H₁^k12k2(ID);

Q_B=g^k12; and

c_A=ê

(Q_C,Q_D), in which Q_C=g^k1k2, Q_D=H₁<sup>∂

k1(k2−

1−

1)</sup>(ID), and

k₂k₂<sup>−

1</sup> mod p=1.

13. The user device as set forth in claim 12, wherein:

the transmitting unit is further configured to transmit the sub-pseudonym P_pseu and an identifier ID_server for identifying the PIM system to a third-party device; and

the user computer hardware processor is configured to authenticate the sub-pseudonym P_pseu by interacting with the third-party device via the transmitting unit and the receiving unit.

14. The user device as set forth in claim 13, wherein the authenticating includes exchanging zero-knowledge proofs with the third-party device.

15. The user device as set forth in claim 14, wherein the authenticating by the user computer hardware processor includes:

receiving a query message from the third-party device via the receiving unit, the query message being generated by a third-party computer hardware processor in accordance with the set of public parameters and the sub-pseudonym P_pseu, and being represented as <

g^t,K_ses⊕

H₂(O_b^tc_A^t), Enc(K_ses,N_a)>

, in which

t is a random number in the domain Z_p, that is, tε

Z_p;

O_B=ê

(g^∂

,Q_A);

K_ses is an original session key selected by the third-party device;

N_a is a query content selected by the third-party device randomly; and

Enc(K_ses,N_a) is an encrypted content obtained by encrypting the query content N_a with the original session key K _ses; and

calculating a session key K*_ses with an equation K*_ses=K_ses⊕

H₁(O_B^tc_A^t)⊕

H₁(ê

(g^t,(H₂^∂

(ID_user))^k12t)) based on the received query message;

decrypting the encrypted content Enc(K_ses, N_a) with the session key K*_ses so as to obtain a decrypted content N_a*; and

selecting a response content N_b corresponding to the decrypted content N_a* in accordance with a predetermined rule, and to encrypt the selected response content N_b with the session key K*_ses, so as to obtain a response message Enc(K*_ses,N_b);

and controlling the transmitting unit to transmit the response message Enc(K*_ses,N_b) to the third-party device.

16. A third-party device from which a user requests a service, the third-party device comprising:

a receiving unit configured to receive a sub-pseudonym P_pseu and an identifier ID_server for identifying a Personal Identity Manager (PIM) system from a user device;

a transmitting unit configured to transmit information to the user device;

a computer hardware processor configured to;

acquire a set of public parameters {g,g^∂

,G₁,G₂,ê

,H₂,p}from the PIM system based on the identifier ID_server in which;

p is a prime number and ∂

is a random number selected from a domain Z _p ,

G₁ and G₂ are two groups of order q modulo p, in which q is a prime number,

ê

is a bilinear map and ê

;

G₁×

G₁→

G₂,

g is a random generator in the group G₁, and

H₂ is a one-way hash function and H₂;

G₂→

{0,1}*;

select a random number t from the domain Z _p ,

select an original session key K_ses and a query content N_a, and encrypt the query content N_a with the original session key K_ses so as to obtain an encrypted content Enc(K_ses,N_a);

generate a query message <

g^t,K_ses⊕

H₂(O_B^tc_A^t),ENC(K_ses,N_a)>

with the random number t, the set of public parameters, the sub-pseudonym P_pseu, and the encrypted content Enc(K_ses,N_a) in which O_B=ê

(g<sup>∂

,Q</sup>_A) , and to control the transmitting unit to transmit the query message to the user device;

decrypt a response message Enc(K*_ses,N_b) received from the user device via the receiving unit with the original session key K_ses , in which K*_ses is a session key calculated by the user device from the query message, and N_b is a response content selected by the user device in accordance with a predetermined rule based on a query content decrypted from Enc(K_ses,N_a); and

determine whether the predetermined rule is met between the decrypted response content N_b* and the query content N_a, and to authenticate the sub-pseudonym P_pseu to be valid when the predetermined rule is met.

17. The third-party device as set forth in claim 16, wherein:

the transmitting unit is further configured to transmit the sub-pseudonym P_pseu to the PIM system; and

the receiving unit is further configured to receive a user identity corresponding to the sub-pseudonym P_pseu from the PIM system.

18. The third-party device as set forth in claim 16, wherein the third-party device is a medical system in a hospital.