Password based key exchange from ring learning with errors
View Patent ↗Use the same basic idea of KE based on Ring LWE, this invention gives constructions of a new authenticated key exchanges system, where the authentication is achieved through a shared password between two parties. These new systems are efficient and have very strong security property including provable security and resistance to quantum computer attacks. This invention can also be modified using the LWE problem.
1. A computer-implemented method for establishing a key exchange over an open channel between a first Party i and a second Party j with a shared password and explicit authentication, comprising:
(Set Up) defining, by Party i and Party j, a function f(x)=x n +1, wherein n is a power of 2, q≈ ω(log n) is an odd prime such that q mod 2n=1, and R= [x]/ f(x) and R q = q [x]/ f(x) ,
selecting γ∈ + , wherein H 1 : {0,1}*→x γ = ,γ is a hash function with output distribution x γ , H 2 : {0,1}*→{0,1} k is a Key Derivation Function (KDF) such that k is the bit-length of a final shared key,
defining x α , x β as two discrete Gaussian distributions with parameters α, β∈ + , wherein π i,j is the shared password of Party i and Party j,
selecting h: {0,1}*→R q as a uniform hash function to hide the shared password, and
determining Sig and Mod 2 functions, such that
ℤ
q
=
{
-
q
-
1
2
,
…
,
q
-
1
2
}
,
set
E
:=
{
-
⌊
q
4
⌋
,
…
,
⌊
q
4
⌋
}
is considered to be a middle portion of q , Sig is a characteristic function of a complement of E[DiLi], and Mod 2 : q ×{0,1}→{0,1} is defined as
Mod
2
(
v
,
b
)
=
(
v
+
b
·
q
-
1
2
)
mod
q
mod
2
,
wherein, when Sig and Mod 2 are applied to a ring element, Sig and Mod 2 apply to each coefficient of the ring element;
(Initiation) randomly sampling r i , by Party i, wherein f i ←x β , computes x i =ar i +2f i , and
sending m=x i +h(π) to Party j;
(Response) receiving, at Party j, x i +h(π) from party i, and recovering x i =m−h(π),
randomly sampling r j , at Party j, f j ←x β computing y j =ar j +2f j and k j =x i ·r j ,
computing, at Party j, w j =Sig(k j ) ∈{0,1} 2 and σ=Mod 2 (k j , w j ), and
sending y j , w j , and κ=η(i, j, x i , y j , σ, π) to Party i to derive a session key sk j =H 2 (i, j, x i , y j , w j , σ);
(Finish) computing, at Party i, k i =r i ·y j and κ′=η′(j, i, x i , y j , σ, π),
computing, at Party i, σ=Mod 2 (k j , w j ),
deriving the session key sk i =H 2 (i, j, x i , y j , w j , σ),
verifying whether κ=η(i, j, x i , y j , σ, π) matches the value of κ received from party j, wherein κ does not match the value of κ received from Party j, Party i ends the communication, and when κ does match the value of κ received from Party j, Party i sends κ′ to Party j to verify the value of κ.
2. The computer-implemented method, according to claim 1 , further comprising:
in the Response step, sending μ=y j +h(π) and w j to Party i by Party j, and
computing, by Party j, σ j =Mod 2 (k j , w j ); and
in the Finish step, recovering the pair (y j , w j ) from Party i, and using the pair to compute k i =r i ·y j .
3. The computer-implemented method, for establishing a key exchange over an open channel between a first Party i and a second Party j with a shared password and explicit authentication by multiplication of hashed password, comprising:
(Set Up) defining, by Party i and Party j, a function f(x)=x n +1, wherein n is a power of 2, q≈ ω(log n) is an odd prime such that q mod 2n=1, and R= [x]/ f(x) and R q = q [x]/ , f(x) ,
selecting γ∈ + , wherein H 1 : {0,1}*→x γ = , γ is a hash function with output distribution x γ , H 2 : {0,1}*→{0,1} k is a Key Derivation Function (KDF) such that k is the bit-length of a final shared key,
defining x α , x β as two discrete Gaussian distributions with parameters α, β∈ + , wherein π i,j is the shared password of Party i and Party j,
selecting h: {0,1}*→R q as a uniform hash function to hide the shared password, and
determining Sig and Mod 2 functions, such that
ℤ
q
=
{
-
q
-
1
2
,
…
,
q
-
1
2
}
,
set
E
:=
{
-
⌊
q
4
⌋
,
…
,
⌊
q
4
⌋
}
is considered to be a middle portion of q , Sig is a characteristic function of a complement of E[DiLi], and Mod 2 : q ×{0,1}→{0,1} is defined as
Mod
2
(
v
,
b
)
=
(
v
+
b
·
q
-
1
2
)
mod
q
mod
2
,
wherein, when Sig and Mod 2 are applied to a ring element, Sig and Mod 2 apply to each coefficient of the ring element;
(Initiation) randomly sampling r i , by Party i, wherein f i ←x β , computes x i =ar i +2f i , and
sending m=x i +h(π) to Party j;
(Response) receiving, at Party j, x i ·h(π) from party i, and recovering x i =m−h(π) −1 ,
randomly sampling r j at Party j, f j ←x β computing y j =ar j +2f j and k j =x i ·r j ,
computing, at Party j, w j =Sig(k j ) ∈{0,1} 2 and σ=Mod 2 (k j , w j ), and
sending y j , w j , and κ=η(i, j, x i , y j , σ, π) to Party i to derive a session key sk j =H 2 (i, j, x i ,y j , w j , σ);
(Finish) computing, at Party i, k i =r i ·y j and κ′=η′(j, i, x i , y j , σ, π),
computing, at Party i, σ=Mod 2 (k i , w j ),
deriving the session key sk i =H 2 (i, j, x i , y j , w j , σ),
verifying whether κ=η(i, j, x i , y j , σ, π) matches the value of κ received from party j, wherein κ does not match the value of κ received from Party j, Party i ends the communication, and when κ does match the value of κ received from Party j, Party i sends κ′ to Party j to verify the value of κ.
4. The computer-implemented method according to claim 3 , further comprising:
in the Response step, sending μ=y j +h(π) −1 and w j to Party i by Party j, and
computing, by Party j, σ j =Mod 2 (k j , w j ); and
in the Finish step, recovering the pair (y j , w j ) from Party i, and using the pair to compute k i =r i ·y j .
5. The computer-implemented method according to claim 1 , wherein the “Set Up” step defines a q, n distribution.
6. The computer-implemented method according to claim 1 , wherein the “Set Up” step selects parameters from a LWE problem.
7. The computer-implemented method according to claim 1 , wherein one of Party i and Party j is a server and the other a client.
8. The computer-implemented method according to claim 1 , wherein the shared key is derived from a similar rounding technique.
9. The computer-implemented method according to claim 2 , wherein the “Set Up” step defines a q, n distribution.
10. The computer-implemented method according to claim 2 , wherein the “Set Up” step selects parameters from a LWE problem.
11. The computer-implemented method according to claim 2 , wherein one of Party i and Party j is a server and the other a client.
12. The computer-implemented method according to claim 2 , wherein the shared key is derived from a similar rounding technique.
13. The computer-implemented method according to claim 3 , wherein the “Set Up” step defines a q, n distribution.
14. The computer-implemented method according to claim 3 , wherein the “Set Up” step selects parameters from a LWE problem.
15. The computer-implemented method according to claim 3 , wherein one of Party i and Party j is a server and the other a client.
16. The computer-implemented method according to claim 3 , wherein the shared key is derived from a similar rounding technique.
17. The computer-implemented method according to claim 4 , wherein the “Set Up” step selects a q, n distribution.
18. The computer-implemented method according to claim 4 , wherein the “Set Up” step selects parameters from a LWE problem.
19. The computer-implemented method according to claim 6 , wherein the parameters utilize matrix operations.
20. The computer-implemented method according to claim 14 , wherein the parameters utilize matrix operations.