Password based key exchange from ring learning with errors

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)=xn+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 Rq=q[x]/, f(x),
• selecting γ∈+, wherein H1:
• {0,1}*→xγ=, γ is a hash function with output distribution xγ, H2:
• {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}*→Rq as a uniform hash function to hide the shared password, and
• determining Sig and Mod2 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 Mod2:
• 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 Mod2 are applied to a ring element, Sig and Mod2 apply to each coefficient of the ring element;
• (Initiation) randomly sampling ri, by Party i, wherein fi←xβ, computes xi=ari+2fi, and
• sending m=xi+h(π) to Party j;
• (Response) receiving, at Party j, xi·h(π) from party i, and recovering xi=m−h(π)−1,
• randomly sampling rj at Party j, fj←xβ computing yj=arj+2fj and kj=xi·rj,
• computing, at Party j, wj=Sig(kj) ∈{0,1}2 and σ=Mod2 (kj, wj), and
• sending yj, wj, and κ=η(i, j, xi, yj, σ, π) to Party i to derive a session key skj=H2 (i, j, xi,yj, wj, σ);
• (Finish) computing, at Party i, ki=ri·yj and κ′=η′(j, i, xi, yj, σ, π),
• computing, at Party i, σ=Mod2 (ki, wj),
• deriving the session key ski=H2 (i, j, xi, yj, wj, σ),
• verifying whether κ=η(i, j, xi, yj, σ, π) 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 κ.