DISTRIBUTED SINGLE SIGN ON TECHNOLOGIES INCLUDING PRIVACY PROTECTION AND PROACTIVE UPDATING

• US 20100131755A1
• Filed: 11/24/2008
• Published: 05/27/2010
• Est. Priority Date: 11/24/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhu, Bin Benjamin, Feng, Min
• Granted Patent: US 8,151,333 B2
• Time in Patent Office: Days
• US Class Current: 713/155
• CPC Class Codes: H04L 63/0435 wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06
• CPC Class Codes: H04L 63/0815 providing single-sign-on or federations
• CPC Class Codes: H04L 63/083 using passwords cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226
• CPC Class Codes: H04L 63/10 for controlling access to devices or network resources
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• 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/3226 using a predetermined code, e.g. password, passphrase or PIN network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083

Abstract

Technologies for distributed single sign-on operable to provide user access to a plurality of services via authentication to a single entity. The distributed single sign-on technologies provide a set of authentication servers and methods for privacy protection based on splitting secret keys and user profiles into secure shares and periodically updating shares among the authentication servers without affecting the underlying secrets. The correctness of the received partial token or partial profiles can be verified with non-interactive zero-knowledge proofs.

Claims

1. A distributed single sign-on system comprising a plurality of n authentication servers associated with a service provider operable to provide a service to a user, wherein a secret key K_S associated with the service provider is split into n distinct secret key shares, each distinct secret key share K_Sⁱ associated with authentication server A_i of the plurality of n authentication servers where 1≦

i≦

n, and wherein each distinct secret key share K_Sⁱ is sent to its associated authentication server A_i along with a service provider identifier SID, and wherein each authentication server A_i stores the distinct secret key share K_Sⁱ in association with the service provider identifier SID.

2. The system of claim 1 wherein each authentication server A_i verifies the distinct secret key share K_Sⁱ before storing it.

3. The system of claim 1 wherein the splitting of the secret key K_S is based on a random polynomial f(x) of order t−

1, where 1≦

t≦

n, the random polynomial f(x) having random coefficients and a constant wherein the constant is set to K_S, and where any t secret key shares of the secret key K_S can be used to reconstruct the secret key K_S.

4. The system of claim 3 wherein the random polynomial f(x)=K_S′

α

₁x+ . . . +α

<sub>t−

1</sub>x<sup>t−

1</sup> mod q where the random coefficients {α

_i ∈

Z_q}, and where q is a large prime number that divides the Euler totient function of a large prime p, and where Z_q represents integers from 0 to q−

1, and where K_Sⁱ=f(x_i) for a set of n distinctive values {x_i ∈

Z_q\{0}}.

5. The system of claim 1 wherein a user profile mapping P_f associated with the user is split into n distinct user profile shares, each distinct user profile share P_f,Γ

ⁱ associated with authentication server A_i of the plurality of n authentication servers, and wherein each distinct user profile share P_f,Γ

ⁱ is sent to its associated authentication server A_i along with the identifier of the user, UID, and wherein each authentication server A_i verifies the distinct user profile share P_f,Γ

ⁱ and stores the distinct use profile share P_f,Γ

ⁱ in association with the user identifier UID.

6. The system of claim 1 wherein P_f is an encryption key used to encrypt a user profile associated with the user with a symmetric encryption, and the encrypted profile is sent to each authentication server A_i of the plurality of n authentication servers, and to the service provider during authentication service.

7. The system of claim 5 wherein the splitting of the user profile mapping P_f is further based on a secret number Γ

_U and a random polynomial w(x) of order t−

1, where 1≦

t≦

n, the random polynomial w(x) having random coefficients and a constant wherein the constant is set to Γ

_U, and where any t user profile shares of the user profile P_f can be used to reconstruct the user profile P_f.

8. The system of claim 7 wherein w(x)=Γ

_U+b₁x+ . . . +b<sub>−

1</sub>x<sup>t−

1</sup> mod q where the random coefficients {b_i ∈

Z_q}, q is a large prime number that divides the Euler totient function of a large prime p, and where Z_q represents integers from 0 to q−

1, where P_Uⁱ=w(x_i) for a set of n distinctive values {x_i ∈

Z_q\{0}}, and where P_f,Γ

=(P_f)<sup>Γ

U1</sup> and P_f,Γ

ⁱ=P_f,Γ

^PUi

9. The system of claim 1 wherein each authentication server A_i of the plurality of n authentication servers receives a user identifier UID and an authentication password K_Uⁱ, both associated with the user.

10. The system of claim 9 wherein each authentication password K_Uⁱ is generated from a user password and the unique identifier associated with the authentication server.

11. The system of claim 10 wherein each authentication password K_Uⁱ is generated with a hash function Hash( ):

K_Uⁱ=Hash(UID, Password, AID_i, N_salt) where Password is a user-generated password, and where AID_i is a unique identifier for the i-th authentication server A_i, and where N_salt is a random number.

12. The system of claim 11 wherein each authentication server A_i stores authentication password K_Uⁱ in associated with user identifier UID.

13. The system of claim 1 wherein the service provider, responsive to a request from the user, directs the user to a list of at least t authentication severs {A_dj, 1≦

j≦

t} of the plurality of n authentication servers, where 1≦

t≦

n, for authentication service.

14. The system of claim 13 wherein the service provider receives an authentication token from the user, the authentication token computed based on a set of t partial tokens, each partial token T_dj of the set received from a corresponding one of the t authentication severs A_dj, and wherein the user is granted access to the service if the authentication token is verified by the service provider.

15. The system of claim 14 wherein the authentication token is encrypted with a secret key associated with the service provider, and wherein the encrypted authentication token is computed from a set of partial authentication tokens, each partial authentication token T_dj in the set provided by the corresponding one of the t authentication severs A_dj.

16. The system of claim 14 wherein the correctness of each partial token T_dj received from a corresponding authentication server A_dj is verified with a non-interactive zero-knowledge proof.

17. The system of claim 14 wherein the service provider receives a user profile associated with the user wherein the user profile is encrypted with a secret key associated with the service provider, and wherein the encrypted user profile is computed from a set of partial profile tokens, each partial profile token T_dj′

in the set provided by the corresponding one of the t authentication severs A_dj.

18. The system of claim 17 wherein the correctness of each partial profile token T_dj′

received from a corresponding authentication server A_dj is verified with a non-interactive zero-knowledge proof.

19. A method for updating an original share of a secret, the method performed by each authentication server A_i of a plurality of n authentication servers, where 1≦

i≦

n, the method comprising;

generating a random polynomial f_i,update(x) of order t−

1 with a constant of 0 where 1≦

t≦

n;

computing an updating value S_i,j=f_i,update(x_j), where 1≦

j≦

n, corresponding to each authentication server A_j;

distributing each update value S_i,j to the corresponding authentication server A_j; and

updating the original share by adding the updating values received from the n authentication servers to the original share wherein the original share at each authentication server A_i is updated without changing the related secret.

20. A method of splitting a secret number P_f into a plurality of n shares P_f,Sⁱ, 1≦

i≦

n, the method comprising;

selecting a secret number S, 1<

S<

q−

1, where q is a large prime number that divides the Euler totient function of a large prime p;

calculating S ¹mod q and P_f,S=(P_f)^S1 mod p;

generating a random polynomial f(x) of order t−

1 with random coefficients and with a constant S, where 1≦

t≦

n, and

computing the plurality of n shares wherein each share P_f,Sⁱ, 1≦

i≦

n, is calculated by first computing v_i=f(x_i) for a set of n distinctive values {x_i ∈

Z_q\{0}}, where Z_q represents integers from 0 to q−

1, and then computing P_f,Sⁱ=(P_f,S)^vi, 1≦

i≦

n, wherein any t shares from the set of n shares P_f,Sⁱ, 1≦

i≦

n can be used to reconstruct the secret number P_f.