# A Simple Provably Secure AKE from the LWE Problem

Authors: Limin Zhou; Fengju Lv
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

We first propose an authenticated key exchange (AKE) from the LWE problem. The AKE is simple since it does not involve any other cryptographic primitives to achieve authentication and depends on solely the LWE problem in the worst-case (e.g., SVP and SIVP). We give its security under the BR model, which captures wPFS and might be appealing in specific applications.


---

## Body

## 1. Introduction

Authenticated key exchange (AKE) is one cryptographic tool in establishing secure communication channels which provide secrecy and authenticity for both communication parties. AKE not only allows parties to utilize their known information to compute a session key which is unknown to anybody except for parties, but also ensures authenticity of communication parties, so that an adversary cannot impersonate one party in the conversation.In an AKE, each party has astatic public key which is produced by itsstatic secret key and certified with a party’s identity through a public key. Communication parties utilizeephemeral secret keys to generateephemeral public keys and compute asession state from theirstatic public/secret keys, theephemeral public/secret keys, and the transcripts of the session. Communication parties then obtain asession key from these values using akey derivation function.Thesession key guarantees data integrity and confidentiality, which implies that security notion for AKE should be developed. To handle this case, Bellare and Rogaway [1] first provided BR security model for AKE which was based on indistinguishability. The BR95 [2] and BPR2000 [3] models were extensions to the BR93 model. Although the BR model captured key authentication, for example,confidentiality of session keys, and basic security requirement, for example, known key security and impersonation resilience, it cannot grasp more complex scenes if one party’sstatic secret key orsession state was revealed. Accordingly, Canetti and Krawczyk [4] defined the first Canetti-Krawczyk CK model which grasped the leakage of static secret keys and session state. But it was not resilient to advanced attacks, for example, key compromise impersonation (KCI) and perfect forward secrecy (PFS) which guaranteed an adversary not obtaining the session key after a completed session even if the static private keys of the parties were subsequently revealed. To resist advanced attacks, Krawczyk [5] proposed HMQV protocol in the CK+ model (which was stronger than CK model [6]) and showed that no 2-pass AKE achieved PFS. Alternatively, he presented weak perfect forward secrecy (wPFS) which guaranteed security only for previous sessions without an adversary’s intrusion. Namely, wPFS declared that the session key was still private if the static keys of a completed session were revealed [5]. To modify the CK+ model, LaMacchia et al. [7] and Sarr et al. [8] proposed the eCK model (which was not stronger than the CK model) and the seCK model, respectively. This paper will only show AKE security under the BR model [1].In the past three decades, there appeared a large number of AKEs based on number-theoretical problems [9, 10]. With the rapid development of computing technology, for example, quantum information technology, quantum computer brought great threat to these protocols based on classic number-theoretical problems. With a quantum computer, quantum polynomial time algorithm [11] for factorization and the discrete logarithm problem had brought challenges for these traditional cryptosystems. Recently, researchers plan to focus on quantum resistant cryptographic primitives. Lattice-based cryptosystem was one potential candidate for postquantum.To date, there existed a lot of lattice-based cryptosystems [12–16] because lattice-based cryptosystems can capture strong security proof based on worst-case hardness assumption that can resist quantum attack and be implemented efficiently. What is more, most of lattice-based cryptographic constructions [12, 15, 16] were based directly upon one of the two average-case problems that had been shown to enjoy worst-case hardness guarantees: the Small Integer Solution (SIS) problem [12, 15] and the (Ring-) Learning with Errors problem [13, 14, 16].As mentioned above, in view of the security guarantee against quantum adversaries, there had been a great number of lattice-based cryptosystems [12–19], which offered resilience against quantum computer attack. Cryptographers especially had put effort into constructing various key exchanges (KEs) and AKEs from the (Ring-) LWE problem, for example, lattice-based KE [20] which can only be secure in passive model but made a big step in constructing a post-quantum KE and a NTRU-KE based on Ring-LWE [21], as well as lattice-KEs [22–25]. However, we only know a few of results on lattice-based AKEs [17–19, 24, 26, 27]. What is more, Ding et al. presented an attack with the leakage of the signal function [28] on RLWE based KE [20]. Gong and Zhao presented a small field attack (SFA) [29] on the one-pass protocol [24]. Motivated by post-quantum security, our paper will focus on the construction of a lattice-based AKE based on the LWE problem [13, 14]. Our basic AKE is simple and comes with a rigorous proof of security based on the LWE problem under the BR model. The AKE is simple since it does not involve any other cryptographic primitive to achieve authentication and depends solely on some hard lattice problems in the worst-case (e.g., SVP and SIVP). We prove its AKE security with wPFS under the BR model.Ding et al. [28] showed that KE based on RLWE problem could be broken by analyzing the number of signal changes of each of the coefficients. Ding and Lin [20] utilized the signal function to construct a KE from (Ring-) LWE. Theoretically, the KE from LWE [20] could be broken by the attack with the leakage of the signal function [28], as the KE from (Ring-) LWE [20] only referred to matrix-vector multiplication in finite field. Hence, our proposed lattice-based AKE from the LWE problem could suffer from the same attack with leakage of signal function [28]; here we do not study it and omit it. Gong and Zhao exploited a SFA (with a property of the CRT basis of Rq, i.e., Proposition 5 in [29]) against one-pass AKE [24] although the SFA may not violate the security of one-pass AKE [24]. Notice that SFA [29] applied only to a special case of the original Ring-LWE problem [16] which sufficed for [24]. Likewise, maybe there exists a similar SFA (with the help of some properties) to break our proposed AKE since every cryptosystem will be broken in the future. And we do not know whether SFA can be applied to the LWE problem since Ring-LWE problem is one special case of the LWE problem [13, 14]. For example, cyclotomic polynomial [30] which was essential for SFA [29] applied only to polynomial ring. We leave them as open problems. Maybe our AKE could capture AKE security and resist some advanced attacks under the CK model, the CK+ model, or the eCK model, but we leave them as future works.This paper is organized as follows. Section2 contains definitions and properties related to lattice. In Section 3, we construct a lattice-based AKE based on the LWE problem. Section 4 gives its AKE security under the BR model. Section 5 gives comparison. Conclusion is in Section 6. The BR model is given in appendix.


## 2. Preliminaries

Notations. Assume that n is the main security parameter. Let notations be as defined in [13, 14]. Let Λ be a discrete subset of Zm. TheGaussian function on Rm centered at c∈Rm with any positive σ∈R is ρσ,c(x)=exp⁡(-π(x-c2/σ2)), ∀x∈Rm. Let ρσ,c(Λ)=∑x∈Λρσ,c(x) be the discrete integral of ρσ,c over Λ and DΛ,σ,c be thediscrete Gaussian distribution over Λ with center c and parameter σ. Concretely, ∀c∈Rm, ∀σ∈R, define DΛ,σ,c(x)=ρσ,c(x)/ρσ,c(Λ), ∀x∈Λ. If c=0, ρσ,0 and DΛ,σ,0 are shorted for ρσ and DΛ,σ, respectively.Regev proposed theLearning with Errors (LWE) problem [13].For integersn≥1 and q≥2, α∈(0,1). Let s∈Zqn, As,α be the distribution on Zqn×Z obtained by choosing a vector a∈Zqn uniformly at random and a noise term e←DZ,αq, and output (a,a,s+e)∈Zqn×Zq.The LWE problem is as follows: for uniformly random s←Zqn, given poly(n) number of samples that are either from As,α or uniformly random in Zqn×Zq, output 0 if the former holds and 1 if the latter holds.The decision LWE problem is at least hard as approximating several problems onn-dimensional lattice in the worst-case within O~(n/α) factors using a quantum computer [13] if αq≥2n, q=poly(n). Brakerski et al. [31, 32] showed that the LWE assumption still preserved if b=a,s+te for ∀t∈Z+ and gcd(q,t)=1 but security loses with a n factor. TheHNF-LWE assumption [32] declared that HNF-LWE problem was still hard if the secret came from the error distribution; for example, s←Dzn,αq.Formally, a random noise vector with a Gaussian distribution is used to prove that certain lattice problems are in coNP [33]. Lemma 1 [33] gives a norm bound of Gaussian distribution.Lemma 1 (see [33]).
For anyn-dimensional lattice Λ, a vector c∈Rn, and reals 0<ϵ<1, s≥ηϵ(Λ), we have(1)Prx~DΛ,s,cx-c>sn≤1+ϵ1+ϵ·2-n.
Signal Functions [20]. Define thesignal function discussed in [20]. For prime q>2, given Zq=-q-1/2,…,q-1/2, E={-⌊q/4⌋,⌊q/4⌋}, define σ as thesignal function in E: σ(υ)=0 if υ∈E and 1 otherwise as follows.For simplicity and requirements in some places, set(2)chaυ=συ=0,υ∈-q4+1,q41,otherwise. For any υ∈Zq,υ+cha(υ)·q-1/2modq belongs to [-⌊q/4⌋+1,⌊q/4⌋].We definemodular functionmod⁡2(υ,ω) from Zq×{0,1}:(3)mod⁡2υ,ω=υ+ωq-12modqmod2, where υ∈Zq,ω∈{0,1}.Modular function was discussed asrobust extractor [20] and can guarantee the correctness of our protocol.Lemma 2 (see [20]).
Letq>8 be an odd integer; the function mod⁡2 defined above is arobust extractor with respect to ω with error tolerance q/4-2.Lemma 3 (see [20]).
For any oddq>2, if υ is uniformly random in Zq, then mod⁡2(υ,ω) is uniformly random conditioned on ω∈{0,1}.Lemma 4 (see [24]).
Letn be the security parameter and odd prime q=2ω(log⁡n). For any b∈{0,1} and υ′∈Zq, the output distribution of mod⁡2(υ+υ′,b) conditioned on cha(υ)∈{0,1}, where the probability is taken over the uniform and independent choice of υ∈Zq.


## 3. One AKE from the LWE Problem

Letn≥1 and q≥2 be integers, α∈0,1, q is prime. For the same integer k, let h:{0,1}∗→{0,1}k be KDF which is modeled as random oracles.Sample a uniformly random matrixM←Zqn×n. Let pA=MsA+2eAmodq∈Zqn and sA be the static public key and static private key of Alice (A¯), where sA,eA←DZn,αq. Let pB=sBtM+2eAtmodq∈Zqn and sB be the static public key and static private key of Bob (B¯), where sB,eB←DZn,αq. Assume that the protocol works between Alice and Bob.Setup. Alice randomly chooses rA,e1←DZn,αq, computes RA=MrA+2e1modq, and sends RA to Bob.Response. Upon receiving RA from Alice, Bob randomly chooses rB,e2←DZn,αq, computes RB=rBtM+2e2tmodq, kB=rBt·pA+sBt·RAmodq, and ωB=cha(kB)∈{0,1}, and sends (RB,ωB) to Alice. Then, Bob computes σB=mod⁡2(kB,ωB)∈{0,1} and derives skj=h(A¯,B¯,RA,RB,ωB,σB)∈{0,1}k.Completion. Upon obtaining (RB,ωB), Alice computes kA=pB·rA+RB·sAmodq, ωA=cha(kA)∈{0,1}, σA=mod⁡2(kA,ωA)∈{0,1}, and skB=h(A¯,B¯,RA,RB,ωA,σA)∈{0,1}k.Correctness. If Alice and Bob run the protocol honestly, they will share the same session key. To show the correctness of our AKE, it is sufficient to show that σA=σB. σA and σB are output by mod⁡2 with the same second input cha(kB). According to Lemma 2, we only show that kA and kB are sufficiently close.If8(αq)2·n≤q/4-2, then kA=kB with overwhelming probability.Proof.
From the form ofkA,kB, (4)kA=pB·rA+RB·sA=sBtM+2eBt·rA+rBtM+2e2t·sA=sBtM·rA+2eBt·rA+rBtM·sA+2e2t·sA=sBtM·rA+rBtM·sA+2eBt·rA+2e2t·sAmodqkB=rBt·pA+sBt·RA=rBt·MsA+2eA+sBt·MrA+2e1=rBt·MsA+2rBt·eA+sBt·MrA+2sBt·e1=rBt·MsA+sBt·MrA+2rBt·eA+2sBt·e1modq,we obtain (5)kA=kB+2rBt·eA+2sBt·e1-2eBt·rA+2e2t·sAmodq=kB+2rBt·eA+sBt·e1-eBt·rA-e2t·sAmodq.
By Lemma1, we have(6)2rBt·eA+sBt·e1-eBt·rA-e2t·sA≤8·αqn·αqn=8αq2·n≤q4-2with overwhelming probability. That indicates kA and kB being sufficiently close.
By Lemma2, with mod⁡2 with respect to S with error tolerance q/4-2, we have (7)σA=mod⁡2kA,ωA=mod⁡2kB,ωB=σB. Further, we show that(8)σA=σB=rBt·MsA+sBt·MrA+q-12·ωB=rBt·MsA+sBt·MrA+q-12·chakBmodqmod2.
This is because(9)rBt·MsA+sBt·MrA+chakB·q-12modq=kB+chakB·q-12-2rBt·eA+2sBt·e1modqand kB+chakB·q-1/2<q/4+1.
Hence, we have(10)rBt·MsA+sBt·MrA+chakB·q-12=kB+chakB·q-12modq-2rBt·eA+2sBt·e1,σA=σB=rBt·MsA+sBt·MrA+chakB·q-12modqmod2.Parameter Selection. Here select the same parameters as those in [20]: n=λ,q=λ4,α=1/λ. It is easy to verify that αq≥n and the correctness holds.


## 4. Security

In our AKE, the public matrixM←Zqn×n is public and everystatic public key actually consists of a LWE tuple with Gaussian parameter α. Thus, thestatic public key is computationally indistinguishable from a random element in Zqn under the LWE assumption. Analogously, RA and RB are also computationally indistinguishable from random elements in Zqn under the LWE assumption with Gaussian parameter α.To show the randomness of the session key, it is enough to take Bob as an example. Obviously, ifkB is random over Zq, σB is statistically close to {0,1} even conditioned on ωB by Lemmas 2 and 3. Note that h is a random oracle; thus skB is uniform over {0,1}k. Now, we check the randomness of kB:(11)kB=rBt·pA+sBt·RA=rBt·MsA+2eA+sBt·MrA+2e1=rBt·MsA+2rBt·eA+sBt·MrA+2sBt·e1=rBt·MsA+sBt·MrA+2rBt·eA+2sBt·e1modq.It is necessary to establish the randomness ofkB on the hardness of the (decisional) LWE problem, since pA,RA are actually LWE instances, and rBt,sBt are random elements in Zqn under the LWE assumption with Gaussian parameter α. Generally, we will prove that kB is statistically close to a real LWE instance if the secret and the error are randomly from DZn,αq. Since pA=MsA+2eAmodq∈Zqn and RA=MrA+2e1modq are random over Zqn, thus (12)kB=rBt·pA+sBt·RA=rBt·MsA+sBt·MrA+2rBt·eA+2sBt·e1modq is random over Zq. That is, kB is statistically close to a real LWE instance.Formally, letN be the maximum number of parties and m be maximum number of sessions for each party. We separate the security proof for the initiator and responder, respectively.


### 4.1. Security for the Initiator

In this session, the AKE security for initiator is proved when the initiator is the owner of the test session. Letsid∗=(Π,I,A∗,B∗,RA∗,(RB∗,ωB∗)) be the test session chosen by the adversary A. Consider two types of adversaries.Type One: RB∗ is output by a session activated at B∗ by a Send1(Π,R,B∗,A∗,RA∗).Type Two: RB∗ is not output by any session activated at B∗ by a Send1(Π,R,B∗,A∗,RA∗).To capture wPFS,TypeOne adversary is allowed to obtain the static secret keys of parties A∗ and B∗ by corrupting A∗ and B∗ (butType Two adversary is not allowed to corrupt either A∗ or B∗).


#### 4.1.1. Security against Type One Adversary

First, AKE security is proved for any PPTType One adversary A.Theorem 5.
IfHNF-LWEq,n,α is hard, the proposed AKE is secure for any PPT Type One adversary A under the BR model.Proof.
The security analysis is performed with a sequence of gamesG1,l for 0≤l≤4. It starts with the real security game, between an adversary A and a simulator S, that models the indistinguishability of the fresh session key. Use underline to show the differences between the previous game and its next one. Let F1,l be the event that A outputs a guess b′: b′=b in GameG1,l, l=0,1,2,3,4.
Game
G
1,0. This is the original game where the messages are generated honestly. In Game G1,0, S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{1,…,m}, and hopes the adversary will choose sid∗=(Π,I,A∗,B∗,RA∗,(RB∗,ωB∗)) as the test session, where RA∗ is output by sA∗th session of party A∗, and RB∗ is output by sB∗th session of party B∗ activated by a Send1(Π,R,B∗,A∗,RA∗). S selects M←Zqn×n at random, honestly generates static public keys for all parties by randomly choosing sA,eA←DZn,αq, and simulates the attack environment for A. Specifically, S keeps one table L for random oracle h and responds to queries of A.(i)
h(in) queries: if there is no tuple (in,out) in L, it randomly selects an element out∈{0,1}k and adds (in,out) to L list. At last it returns out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates a new session of A¯ with intended partner B¯, S randomly selects rA,e1←DZn,αq and sends RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1(Π,R,B¯,A¯,RA): S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to the protocol. Finally, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA by using rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA if session key of sid has been produced.(vi)
Corrupt(A¯): return Alice’s static secret key sA to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1}, and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session key skA of sid.
Analysis of
G
1,0. In this game, S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{1,…,m} independently from the view of A. Hence, the probability that S will not stop in G1,0 is at least 1/m2·N2.
G
a
m
e
G
1,1. S first computes RB′=rB′tM+2e2′tmodq_, where rB′,e2′←DZn,αq randomly. Then, it acts almost the same as in G1,0 except for the case below.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of B∗, S responds to the query as in GameG1,0. Otherwise, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_. Then S computes kB=rB′t·pA+rB′t·RAmodq_: (13)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
Finally, it honestly computesωB,skB according to the protocol and sends (RB,ωB) to A.
Analysis of
G
1,1. Since (M,RB′=rB′t·M+2e2′t) is a LWE tuple with randomly rB′,e2′←DZn,αq, then RB′ is computationally indistinguishable from uniform distribution over Zqn; thus the probability that A guesses the correct RB=RB′-d·pB before is negligible. Since pB=sBtM+2eBtmodq, sB,eB←DZn,αq, we have (14)RB=RB′-d·pB=rB′t-dsBtM+2e2′t-deBtmodq.
By Lemma1, the norm of each entry in both rB′t-dsBt and e2′t-deBt is at most sn; thus both rB′t-dsBt and e2′t-deBt have distribution negligibly close to DZn,αq. This implies that the distribution of RB in GameG1,1 is statistically close to that in GameG1,0. Thus, under the HNF-LWEq,n,α assumption, we have Pr[F1,1]=Pr[F1,0]-negl(n).
G
a
m
e
G
1,2. S computes RA′=MrA′+2e1′modq_, where it randomly selects rA′,e1′←DZn,αq. Then it acts almost the same as in G1,1 apart from the following cases.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to the query as in GameG1,1. Otherwise, S randomly selects c←DZ,αq and computes RA=RA′-c·pAmodq_. Finally, it sends RA to A.
(ii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗) or it is not the sA∗th of A∗, S responds to the query as in GameG1,1. Otherwise, if (RB,ωB) is output by the sB∗th session of party B∗, let skB be the session key of session sid=(Π,R,B¯,A¯,RA,(RB,ωB)), S sets skA=skB_. Else, S computes kA=pB·rA′+RB·rA′modq_. At last, it honestly computes skA according to the protocol.(15)kA=pB·rA′+RB·rA′=sBtM+2eBt·rA′+rBtM+2e2t·rA′=sBtM·rA′+rBtM·rA′+2eBt·rA′+2e2t·rA′modq.
Analysis of
G
1,2. The proof of the distribution of RA being statistically close to that in GameG1,1 is the same as the proof ofAnalysis ofG1,1; as a result, the probability that S stops in G1,2 is negligibly close to that of G1,1. Under the LWEq,n,α assumption, we have (16)PrF1,2=PrF1,1-negln.
G
a
m
e
s
G
1,3. S randomly chooses RA′←Zqn_ and acts almost the same as in G1,2 apart from the following case.
(i)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of party A∗, or (RB,ωB) is output by the sB∗th session of party B∗, S acts the same as in GameG1,2. Else, it randomly selects skA←{0,1}k_ as the session key.
We discuss the differences betweenG1,2 and G1,3. The real session key skA in GameG1,2 is changed to a randomly chosen one in GameG1,3, where (RB,ωB′) (ωB≠ωB′) is output by the sB∗th session of party B∗. Fortunately, the adversary cannot notice the difference if he does not query h with exact σA, since h is a random oracle. To prove it conveniently, denote Q1,l by the event that in GameG1,l  A can query h with σA for the sA∗th session of A∗, when (RB,ωB′) (ωB≠ωB′) is output by the sB∗th session of B∗, where l=2,3,4.
Analysis of
G
1,3. Since h is a random oracle, the event Q1,2 is independent from the distribution of skA. Namely, no matter whether or not A obtains skA, P[Q1,2] is identical, which is suitable for Pr[Q1,3]. Especially, under the LWE assumption, the public information in G1,2 and G1,3 is computationally indistinguishable, so that Pr[Q1,3]=Pr[Q1,2]-negl(n). In addition, if PrQ1,i,l=2,3 does not happen, the distribution of skA is identical in G1,2 and G1,3. Namely, PrF1,3∣¬Q1,3=PrF1,2∣¬Q1,2-negl(n).
G
a
m
e
G
1,4. S randomly selects RB′←Zqn_ and acts almost the same as in G1,3 except for the following case.
(i)
S
e
n
d
1
(
Π
,
R
,
B
,
A
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗th session of B∗, S responds to the query as in GameG1,3. Otherwise, randomly select d←DZ,αq and compute RB=RB′-pB·dmodq. S randomly choose kB←Zq_ and compute ωB,σB according to the protocol. If A made a query h(A¯,B¯,RA,RB,ωB,σB), S stops the simulation. Else, it randomly selects skB←{0,1}k and sets h(A¯,B¯,RA,RB,ωB,σB)=skB. At last, it returns (RB,ωB) to A.
Analysis of
G
1,4. Let (f1,h1),(f2,h2) be two challenge LWE tuples with error distribution (scale by multiplying t=2). Suppose that there exists an adversary that distinguishes GameG1,3 and GameG1,4, there must exist a distinguisher D that can solve the LWE problem. In particular, D first sets M=f1,RA′=f2,RB′=h1; then it acts identically as S in GameG1,3 except for cases as follows.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗th session of B∗, D responds to queries as in GameG1,3. Otherwise, it randomly selects d←DZ,αq and computes RB=RB′-dpBmodq_. Then D sets kB=h2_, computes ωB,σB according to the protocol, and stops if A made a h query h(B¯,A¯,RA,RB,ωB,σB). Otherwise, it sets h(B¯,A¯,RA,RB,ωB,σB)=skB with a randomly chosen skB←{0,1}k. At last, it returns (RB,ωB) to A.
If(f1,h1),(f2,h2) are LWE tuples for some secret s′, A is in GameG1,3; else it is in GameG1,4. Thus, under the LWEq,n,α assumption, GameG1,3 and GameG1,4 are computationally indistinguishable. Especially, (17)PrQ1,4=PrQ1,3,PrF1,4∣¬Q1,4=PrF1,3∣¬Q1,3-negln.
Next, we analyze(18)PrQ1,4=negln,PrF1,4∣¬Q1,4=12+negln.
Let(RB,ωB) be output by the sB∗th session of B¯=B∗ and (RB,ωB′) be the information that finishes the test session (e.g., the sA∗th session of party A¯=A∗). In G1,4, kB is randomly selected from uniform distribution over Zq which is independent from both public keys and transcripts (except for ωB). This still holds even if the adversary uses a session key reveal query to obtain skB, since skB is randomly chosen and h is a random oracle. Let kA be the element computed by S; according to the protocol, kA and kB are sufficiently close; that is, kA=kB+gmodq; (19)kA=kB+2rBt·eA+sBt·e1-eBt·rA-e2t·sA≜kB+gmodqfor some g with short element. Since both public keys and transcripts (expect for ωB) are random and independent from kB, g is also independent from kB without the adversary’s view. Since mod⁡2(kA,ωB′)=mod⁡2(kB+g,ωB′), then σB′=mod⁡2(kA,ωB′) is also statistically close to {0,1} by Lemma 4. Namely, the probability that the adversary query h(B¯,A¯,RA,RB,ωB′,σB′) is at most 2-n+negl(n). Thus, Pr[Q1,4]=negl(n).
Let(RB,ωB) be output by the sB∗th session of party B¯=B∗ and (RB,ωB′) be the message that can finish the test session (e.g., the sA∗th session of party A¯=A∗). Consider two cases.
(ii)
ω
B
=
ω
B
′. In this case, skA=skB=h(A¯,B¯,RA,RB,ωB,σB), where σB=mod⁡2(kB,ωB). Since, in G1,4, kB is randomly chosen from the uniform distribution over Zq, then σB is statistically close to uniform distribution over {0,1} from the adversary’s point by Lemma 4. Thus the probability that A has made h query with σB is less than 2-n+negl(n).
(iii)
ω
B
≠
ω
B
′. By assumption that Q1,4 does not happen, thus A will never make a h query with σB.
In short, the probability thatA has made a h query with σA is negligible since h is a random oracle. If the adversary does not make a query with σA exactly, skA′s distribution is uniform over {0,1}k in the adversary’s point. Thus, PrF1,4∣¬Q1,4=1/2+negl(n).
In a word, we getPr[F1,0]=Pr[F1,2]+negl(n) by Analysis of G1,1 and G1,2. By Analysis of G1,3 and G1,4, we have (20)PrQ1,2=PrQ1,4+negln=neglnPrF1,2∣¬Q1,2=PrF1,4∣¬Q1,4+negln.By the law of the probability, (21)PrF1,2=PrF1,2∣¬Q1,21-PrQ1,2+PrF1,2∣Q1,2PrQ1,2.Thus (22)PrF1,2=PrF1,2∣¬Q1,2-negln.Combining this with PrF1,4∣¬Q1,4=1/2+negl(n), we obtain (23)PrF1,0=PrF1,2+negln=12+negln.
This finishes the proof.


#### 4.1.2. Type Two Adversary

We will prove that our AKE is secure against anyPPT Type Two adversaryA.Theorem 6.
If theHNF-LWEq,n,α is hard, the proposed AKE is secure against any PPT Type Two adversary A under the BR model.Proof.
It proceeds by a sequences ofGamesG2,l, 0≤l≤6.
G
a
m
e
G
2,0. This initial game corresponds to the real attack game in which all the honest players execute. S randomly selects A∗,B∗←{1,…,N}, sA∗←{1,…,m}, and hopes that the adversary will select sid∗=(Π,I,A∗,B∗,RA∗,(RB∗,ωB)) as the test session, where RA∗ is output by the sA∗th session of party A∗ with intended party B∗ (remark that sid∗ has no matching session forType Two adversary). Then, S randomly selects M←Zqn×n, produces static public keys for all parties (by randomly choosing sA,eA←DZn,αq), and simulates the security game for A. In particular, S preserves one table L for random oracle h and responds to queries from A.(i)
h(in) queries: if there is no tuple (in,out) in L list, randomly select out∈{0,1}k and add (in,out) to L list. Then, send out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates one session of A¯ with intended partner B¯, S randomly selects rA,e1←DZn,αq and returns RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1(Π,R,B¯,A¯,RA). S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to the protocol. Then, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA by using rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA once session key of sid has been produced.(vi)
Corrupt(A¯): return Alice’s static secret key sA to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1} and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session skA of sid.
Analysis of
G
2,0. In this game, S randomly selects A∗,B∗←{1,…,N} and sA∗←{1,…,m} independently from A’s view. Thus, the probability that S will not stop in G2,0 is at least 1/m·N2.
G
a
m
e
G
2,1. S acts identically as in G2,0 except for the following case.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If A¯≠A∗, S responds to queries as in GameG2,0. Otherwise, S computes RA′=MrA′+2e1′modq_, where rA′,e1′←DZn,αq. Then, it randomly selects c←DZ,αq, computes RA=RA′-c·pAmodq_, and sends RA to A.
(ii)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If B¯≠B∗, S responds to queries as in GameG2,0. Otherwise, S computes RB′=rB′tM+2e2′tmodq_, where rB′,e2′←DZn,αq. Then, it randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_. S also computes kB=rB′t·pA+rB′t·RAmodq_:(24)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
Finally, it honestly computesωB,skB following the protocol, and sends (yB,ωB) to A.
(iii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If A≠A∗, S responds to queries as in GameG2,0. Else, let RA=RA′-pAcmodq for RA′=MrA′+2e1′modq; S computes kA=(pB+RB)·rA′modq_. At last, S computes skA according to the protocol.
Analysis of
G
2,1. Let F2,l be the event that A outputs a guess b′=b in GameG2,l,l=1,2,3,4,5,6. Similar toAnalysis ofG1,1, under HNF-LWEq,n,α assumption, then (25)PrF2,1=PrF2,0-negln.
G
a
m
e
G
2,2. S acts almost identically as in G2,1, except it replaces B∗’s public key with a uniformly chosen pB∗←Zqn_.
Analysis of
G
2,2. Note that the only difference between G2,1 and G2,2 is that S replaces pB∗=sB∗tM+2eB∗t in G2,1 with a randomly chosen pB∗ over Zqn in G2,2; thus an adversary that can distinguish the difference between G2,1 and G2,2 could solve the LWEq,n,α problem. That implies that if LWEq,n,α is hard, then (26)PrF2,2=PrF2,1-negln.
G
a
m
e
G
2,3. S first computes RA′=MrA′+2e1′modq_, where it randomly chooses rA′,e1′←DZn,αq. Then it acts identically as in G2,2 except for such cases as follows.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to queries as in GameG2,2. Else, S randomly selects c←DZ,αq and computes RA=RA′-c·pAmodq_. Finally, S returns RA to A.
(ii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗) or it is not the sA∗th of A∗, S responds to the query as in GameG2,2. Otherwise, S computes kA=pB·rA′+RB·rA′modq_, where rA′←DZn,αq. Finally, it computes skA according to the protocol.(27)kA=pB·rA′+RB·rA′=sBtM+2eBt·rA′+rBtM+2e2t·sA′=sBtM·rA′+rBtM·rA′+2eBt·rA′+2e2t·rA′modq.
Analysis of
G
2,3. Similar toAnalysis ofG1,1, under HNF-LWEq,n,α assumption, we have (28)PrF2,3=PrF2,2-negln.
G
a
m
e
s
G
2,4. S first computes h1=MrA′+2e~1′,h2=pBrA′, where rA′,e~1′←DZn,αq. Then it computes RA′=h1+2e1′=MrA′+2(e~1′+e1′)_ (or set RA′=h1), where e1′←DZn,α,q. Finally, it acts identically as in G2,3 except for the following cases.
(i)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of party A∗, S responds to queries as in GameG2,3. Else, S computes (29)kA=dh2+RBrA′=dsBtMrA′+rBtMrA′+2deBtrA′+e2trA′modq_.
At last, it computesskA according to the protocol.
Analysis of
G
2,4. In GameG2,4, we have (30)RA′=MrA′+2e~1′+e1′modqRA′=MrA′+2e~1′modqkA=sBtMrA′+rBtMrA′+2eBtrA′+e2trA′modq,where e~1′,e1′,eB,e2,rA′←DZn,α,q. By Lemma 2, the distribution of e~1′+e1′ is statistically close to DZn,α,q; the distribution of eBtrA′+e2trA′ is statistically close to DZ,α,q. Thus, if LWEq,n,α is hard, we get (31)PrF2,4=PrF2,3-negln.
G
a
m
e
G
2,5. S acts identically as in G2,4 except for the following cases.
(i)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗) or it is not the sA∗th session of A∗, S responds to queries as in GameG2,4. Otherwise, it randomly selects kA←Zq_ and computes skA according to the protocol.
Analysis of
G
2,5. The only difference between G2,4 and G2,5 is that S replaces the real kA=h2+RBrA′ in GameG2,4 with a randomly chosen kA∈Zq in G2,5. Since h is a random oracle, the only difference will not affect the A’s view until it makes a h query with σA derived from kA. Formally, denote Q2,l for l=4,5,6 as the event that A makes a h query with σA derived from kA.
Now, we prove that ifLWEq,n,α is hard, then (32)PrQ2,5=PrQ2,4PrF2,4∣¬Q2,4=PrF2,5∣¬Q2,5=12+negln.
Becauseh is a random oracle, Q2,4 is independent from (skA)’s distribution. No matter whether or not A gets skA, Pr[Q2,4] is identical; Pr[Q2,5] is so. Besides, if Q2,l for l=4,5 does not happen, G2,5 is actually identical to G2,4 in adversary view. In particular, (skA)’s distribution is random and uniform over {0,1}k; namely, the advantage of A guessing b is negligible if Q2,5 does not happen. This finishes the proof.
IfPr[Q2,5]≤negl(n), this completes the proof. But it is not easy to do so. As a matter of fact, though h2 is random in the adversary’s view under the LWE assumption, we cannot have the fact that kA=dh2+RBrA′ is random since RBrA′ is related to h2. Now we show kA is random. If we randomly chose another d~←DZ,α,q and obtain kA′=d~h2+RBrA′ we have kA′=kA+(d~-d)h2. That is, kA′-kA=(d~-d)h2. Naturally, if the adversary can distinguish kA (and kA′) from a uniformly chosen one, it can distinguish h2 (which is computationally under the LWE assumption) from a random chosen from Zq.
Actually,Q2,5 will happen with negligible probability according to Lemma 1. Let sid∗=(Π,I,A∗,B∗,RA,(RB,ωB)) be the test session. By assumption that A is a TypeTwo adversary, namely, RB is not output by B∗ by a Send1(Π,R,B∗,A∗,RA), given h1=MrA′+2e~1′, h2=pBrA′ in G2,5, denote kA=dh2+RBrA′ (which is the same as in G2,4), where d~←DZ,α,q. By our assumption, A will make a h query with σA derived from kA with probability at least Pr[Q2,5].
Now, fixingh1,h2,rA′ which are all chosen by S and are independent from the adversary’s actions, S sets d~≠d by randomly choosing d~,d←DZ,α,q and sets kA′=kA+(d~-d)h2. By Lemma 1, A will utilize RB to finish the test session and makes a h query with σA′ derived from kA′ with probability at least P[Q2,5]·2-n. Denote d-Q2,l such that an event for l=5,6  A in GameG2,l will make σA,σA′ in A’s two runs, where σA is derived from kA in A’s first run and σA′ is derived from kA′=kA+(d~-d)h2 in A’s second run. In particular, Pr[d-Q2,5]≥P[Q2,5]·2-n.
G
a
m
e
G
2,6. S randomly chooses h1←Zqn,h2←Zq_ and acts identically as in GameG2,5.
Analysis of
G
2,6. Since the only difference between G2,6 and G2,5 is that S replaces h1=MrA′+2e~1′ and h2=pBrA′ with randomly chosen elements in Zqn,Zq, respectively, an adversary that distinguishes the difference between G2,5 and G2,6 could solve the LWEq,n,α problem. Hence, under the HNF-LWEq,n,α assumption, GameG2,6 is computationally indistinguishable from GameG2,5. In particular, we get (33)Prd-G2,6=Prd-G2,5-negln.
Besides, we can getPr[d-G2,6]=negl(n). Actually, in GameG2,6, S does not really compute kA and kA′ (it cannot compute the values since h1 is randomly chosen from Zqn and h2 is randomly chosen from Zq). Suppose that kA and kA′ (e.g., the values determined before) are as A’s target values. kA′=kA+(d~-d)h2 especially holds, since A cannot efficiently distinguish GameG2,6 from G2,5 as mentioned above. Since h2 is uniformly distributed over Zq and independent from A’s view (thus is independent from kA and kA′), then σA′=mod⁡2(kA′,ωA′) is statistically close to uniform over {0,1} even when conditioned on σA=mod⁡2(kA,ωA) by Lemma 4 ((d~-d) is in invertible with overwhelming probability). Thus, the probability that A will make a h query with σA′ is at most 2-n+negl(n). Namely, Pr(d-G2,6)≤2-n+negl(n), which is negligible in n. Namely, Pr[d-G2,6]=negl(n).
Generally speaking, byAnalysis ofG2,6, we have Pr[d-G2,5]=negl(n), which implies that Pr[Q2,5]=negl(n) by the condition that Pr[double-Q2,5]≥Pr[Q2,5]1/2n2). Combining this withAnalysis ofG2,5, we obtain Pr[F2,4]=1/2+negl(n). A simple computation shows that Pr[F2,0]=1/2+negl(n). The proof is completed.


### 4.2. Security for the Responder

Now we prove the security when the responder is the owner of the test session. Letsid∗=(Π,R,B∗,A∗,RA∗,(RB∗ωB∗)) be the test session; consider three types of adversaries.T
y
p
e
T
h
r
e
e: RA∗ is not output by any session of A∗ activated by a Send0(Π,I,A∗,B∗).T
y
p
e
F
o
u
r: RA∗ is output by a session of A∗ activated by a Send0(Π,I,A∗,B∗), but A∗ never completes the session, or it completes it with exact RB∗.T
y
p
e
F
i
v
e: RA∗ is output by a session of A∗ activated by a Send0(Π,I,A∗,B∗), but A∗ completes the session with another RB′≠RB.T
y
p
e
T
h
r
e
e
,
T
y
p
e
F
o
u
r, and TypeFive give a complete partition of all the adversaries that choose sid∗ as the test session. Note that if the adversary is a TypeThree or TypeFive one, the test session has no matching session. To address wPFS in our security proof, TypeFour adversary A is allowed to obtain the static secret keys of parties A∗ and B∗ by corrupting both parties (a TypeThree or TypeFive adversary is not allowed to corrupt party A∗ or B∗).


#### 4.2.1. Type Three

Here we prove AKE security against any PPTTypeThree adversary A.Theorem 7.
IfHNF-LWEq,n,α is hard, the proposed AKE is secure against any PPT TypeThree adversary A under the BR model.Proof.
We prove the theorem by a series of gamesG3,l for 0≤l≤7.
G
a
m
e
G
3,0. S randomly selects A∗,B∗←{1,…,N} and sB∗←{0,…,m} and hopes that the adversary will select sid∗=(Π,R,B∗,A∗,RA∗,(RB∗,ωB)) as the test session, where (RB∗,ωB) is output by the sB∗th session of party B∗ activated by Send0(Π,R,B∗,A∗,RA∗) for some party A∗. Then, S randomly selects M←Zqn×n, honestly generates static public keys for all parties (by randomly choosing sA,eA←DZn,αq), and simulates security game for A. Specially, S preserves one table L for random oracle h, and responds to queries from A as follows.(i)
h(in) queries: if there is no tuple (in,out) in L, randomly select an element out∈{0,1}k and add (in,out) to L list. Then send out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates a new session of A¯ with intended partner B¯, S randomly selects rA,e1←DZn,αq and sends RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1Π,R,B¯,A¯,RA: S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to the protocol. At last, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA by using rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA once session key of sid has been generated.(vi)
Corrupt(A¯): return the static secret key sA of Alice to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1}, and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session skA of sid.
Analysis of
G
3,0. In this game, S randomly chooses A∗,B∗←{1,…,N} and sB∗←{1,…,m} without A’s view. Thus, the probability that S will not abort in G3,0 is at least 1/m·N2.
G
a
m
e
G
3,1. S acts identically as in G3,0 except for the following cases.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If A¯≠A∗, S responds to queries as in GameG3,0. Else, S computes RA′=MrA′+2e1′modq_, where rA′,e1′←DZn,αq. Then, it randomly selects c←DZ,αq, computes RA=RA′-c·pAmodq_, and sends RA to A.
(ii)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If B¯≠B∗, S responds to the query as in GameG3,0. Otherwise, S computes RB′=rB′tM+2e2′tmodq_, where rB′,e2′←DZn,αq. Then, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_ and kB=rB′t·pA+rB′t·RAmodq_:(34)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
At last, it computesωB,skB according to the protocol and sends (yB,ωB) to A.
(iii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If A≠A∗, S responds to query as in GameG3,0. Else, it chooses randomly c←DZ,αq, let RA=RA′-pAcmodq for RA′=MrA′+2e1′modq; S computes kA=(pB+RB)·rA′modq_. Finally, S computes skA according to the protocol.
Analysis of
G
3,1. Let F3,l be the event that A outputs a guess b′=b in GameG3,l, l=2,3,4,5,6. Similar to theAnalysis ofG1,1, under HNF-LWEq,n,α assumption, we have (35)PrF3,1=PrF3,0-negln.
G
a
m
e
G
3,2. S acts identically as in G3,1, except it replaces the public key for the party A∗ with a uniformly chosen pA∗←Zqn_.
Analysis of
G
3,2. Similar toAnalysis ofG2,3 or G1,1, under HNF-LWEq,n,α assumption, then (36)PrF3,2=PrF3,1-negln.
G
a
m
e
G
3,3. S first computes RB′=rB′tM+2e2′tmodq_, where it randomly chooses rB′,e2′←DZn,αq. Then it acts identically as in G3,2 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
A
¯
,
B
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of B∗, S responds to the query as in GameG3,2. Else, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_ and kB=rB′t·pA+rB′t·RA_, where rB′←DZn,αq. At last, it computes skB,ωB according to the protocol and returns (RB,ωB) to A.(37)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+2rB′teA+2rB′t·e1modq.
Analysis of
G
3,3. Similar to Analysis of G1,1, under LWEq,n,α assumption, then (38)PrF3,3=PrF3,2-negln.
G
a
m
e
s
G
3,4. S first computes h1=rB′tM+2e~2′t,h2=rB′tpA, where rB′,e~2′←DZn,αq. Then it computes RB′=h1+2e2′t=rB′tM+2(e~2′t+e2′t) (or set RB′=h1), where e2′←DZn,α,q. Finally, it acts identically as in G3,3 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of party B∗, S responds to queries as in GameG3,3. Otherwise, S randomly selects c←DZ,α,q, and computes RB=RB′-d·pBmodq_, (39)kB=ch2+rB′tRA=crBtMsA+rB′tMrA+2drB′teA+rB′te1modq._
At last, it computesωB, skB according to the protocol and returns (RB,ωB) to A.
Analysis of
G
3,4. Similar to Analysis of G1,1, under LWEq,n,α assumption, then (40)PrF3,4=PrF3,3-negln.
G
a
m
e
G
3,5. S acts identically as in G3,4 apart from the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗ − th session of B∗, S responds to the query as in GameG3,4. Otherwise, S randomly selects d←DZ,α,q and computes RB=RB′-d·pBmodq. Then, it randomly selects kB←Zq_ and computes ωB,σB as described in protocol. If A has made a h query h(A¯,B¯,RA,RB,ωB,σB), S stops. Otherwise, it randomly selects skB←{0,1}k_ and sets h(A¯,B¯,RA,RB,ωB,σB)=skB. At last, it returns (RB,ωB) to A.
Analysis of
G
3,5. The only difference between G3,4 and G3,5 is that S replace the real key kB=ch2+rB′tRA=crBtMsA+rB′tMrA+2(crB′teA+rB′te1)modq in Game G3,4 with a randomly chosen kB∈Zq in Game G3,5. Since h is a random oracle, the only difference cannot affect A’s view until it makes a h query with σB derived from kB. Denote Q3,l for l=4,5,6 as the event where A makes a h query with σB derived from kB.
Now, we prove(41)PrQ3,4=PrQ3,5PrF3,4∣¬Q3,4=PrF3,5∣¬Q3,5=12+negln.
Becauseh is a random oracle, Q3,4 is independent from (skB)’s distribution. No matter whether or not A gets skA, Pr[Q3,4] is identical; Pr[Q3,5] is so. Besides, if Q3,l for l=4,5 does not happen, G3,5 is actually identical as G3,4 in adversary view. In particular, (skB)’s distribution is random and uniform over {0,1}k; namely, the advantage of A guessing b is negligible if Q3,5 does not happen. This completes the proof.
Likewise, letsid∗=(Π,R,B∗,A∗,RA,(RB,ωB)) be the test session. By assumption that A is a TypeThree adversary, namely, RA is not output by party A∗, given h1=rB′tM+2e~2′t,h2=rB′tpA in G3,5, denote kB=ch2+rB′tRA (which is the same as in G3,4), where c←DZ,α,q. By our assumption, A will make a h query with σB derived from kB with probability at least Pr[Q3,5].
Now, fixingh1,h2,rB′ which are all chosen by S and are independent from the adversary’s actions, S sets c~≠c by randomly choosing c~←DZ,α,q, and sets kB′=c~h+rB′tRA=kB+(c~-c)h2. By Lemma 1, A will utilize RA in the test session and makes a h query with σB′ derived from kB′ with probability at least P[Q3,5]·2-n. Denote d-Q3,l as an event for l=5,6; A in GameG3,l will make σB,σB′ in A’s two runs, where σB is derived from kB in A’s first run and σB′ is derived from kB′=kB+(c~-c)h2 in A’s second run. In particular, Pr[d-Q3,5]≥P[Q3,5]·2-n.
G
a
m
e
G
3,6. S randomly chooses h1←Zqn,h2←Zq_ and acts identically as in GameG3,5.
Analysis of
G
3,6. On the one hand, the difference between G3,5 and G3,6 is that S replaces h1=rB′tM+2e~2′t,h2=rB′tpA with randomly chosen elements in Zqn,Zq, respectively; an adversary that distinguishes the difference between G3,5 and G3,6 could solve the HNF-LWEq,n,α problem. Under the HNF-LWEq,n,α assumption, GameG3,6 is computationally indistinguishable from GameG3,5. In particular, (42)Prd-G3,6=Prd-G3,5-negln.
On the other hand, inGameG3,6, S does not really compute kB and kB′ ( it cannot compute them since h1 is randomly chosen from Zqn and h2 is randomly chosen from Zq). Suppose that kB and kB′ (e.g., the values determined before) are as A’s target values. kB′=kB+(c~-c)h2 especially holds, since A cannot distinguish GameG3,6 from G3,5 as mentioned above. Since h2 is uniformly distributed over Zq and independent from A’s view (thus is independent from kB and kB′), then σB′=mod⁡2(kB′,ωB′) is statistically close to uniform over {0,1} even when conditioned on σB=mod⁡2(kB,ωB) by Lemma 4 ((c~-c) is in invertible with overwhelming probability). Thus, the probability that A will make a h query with σB′ is at most 2-n+negl(n). Namely, Pr(d-G3,6)≤2-n+negl(n) which is negligible in n. As a result, Pr[d-G3,6]=negl(n).
Generally speaking, byAnalysis ofG3,6, Pr[d-Q3,5]=negl(n), which implies that Pr[Q3,5]=negl(n) by the condition that Pr[d-Q3,5]≥Pr[Q3,5]·2-n. Combining this withAnalysis ofG3,5, we get Pr[F3,4]=1/2+negl(n). A simple computation shows that Pr[F3,0]=1/2+negl(n). The proof is completed.


#### 4.2.2. Type Four Adversary

Theorem 8.
IfHNF-LWEq,n,α is hard, the proposed AKE is secure against any PPT Type Four adversary A under the BR model.Proof.
We prove it by a series of GameG4,l for 0≤l≤4.
G
a
m
e
G
4,0. S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{0,…,m} and hopes that the adversary will select sid∗=(Π,R,B∗,A∗,RA∗,(RB∗,ωB∗)) as the test session, where RA∗ is output by the sA∗th session of party A∗, (RB∗,ωB∗) is output by the sB∗th session of party B∗ activated by Send1(Π,R,B∗,A∗,RA∗). Then, S randomly selects M←Zqn×n, generates static public keys for all parties (by randomly choosing sA,eA←DZn,αq), and simulates security game for A. In particular, S preserves one table L for random oracle h, and responds the queries from A in the following.(i)
h(in) queries: if there is no tuple (in,out) in L, randomly select an element out∈{0,1}k and add (in,out) to L list. Then send out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates a session of A¯ with intended partner B¯; S randomly selects rA,e1←DZn,αq and sends RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1(Π,R,B¯,A¯,RA): S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to protocol. At last, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA with rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA if session key of sid has been generated.(vi)
Corrupt(A¯): send the static secret key sA of Alice to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1}, and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session key skA of sid.
Analysis of
G
4,0. In this game, S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{1,…,m} independent from A’s view. Thus, the probability that S will not stop in G4,0 is at least 1/m2·N2.
LetF4,l be the event that A outputs a guess b′=b in GameG4,l,l=1,2,3,4.
G
a
m
e
G
4,1. S first computes RB′=rB′tM+2e2′modq_, where rB′,e2′←DZn,αq. Then, it acts identically as in G4,0 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of B∗, S responds to the query as in GameG4,0. Otherwise, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_. Then, S also computes kB=rB′t·pA+rB′t·RAmodq_:(43)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
Finally, it honestly computesωB,skB following the protocol and returns (yB,ωB) to A.
Analysis of
G
4,1. Similar toAnalysis ofG1,1, under HNF-LWEq,n,α assumption, we have (44)PrF4,1=PrF4,0-negln.
G
a
m
e
G
4,2. S first computes RA′=MrA′+2e1′modq_, where rA′,e1′←DZn,αq. Then, S acts identically as in G4,1, apart from the following cases.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to the query as in GameG4,1. Else, it randomly selects c←DZ,αq, computes RA=RA′-c·pAmodq_, and sends RA to A.
(ii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to queries as in GameG4,1. Otherwise, (RB,ωB) is output by the sB∗th session of party B∗. Let skB be the session key of session sid=(Π,R,B¯,A¯,RA,(RB,ωB)); S sets skA=skB_. Otherwise, it computes kA=pB+RB·rA′modq_. At last, S computes skA according to the protocol.
Analysis of
G
4,2. Similar toAnalysis ofG1,2, under HNF-LWEq,n,α assumption, we have (45)PrF4,2=PrF4,1-negln.
G
a
m
e
G
4,3. S first randomly selects RA′←Zqn_. Then it acts identically as in G4,2 except in the following cases.
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, or (RB,ωB) is output by the sB∗th session of party B∗, S answers the query as in GameG4,2. Else, it randomly selects skA←{0,1}k_ as the session key.
Analysis of
G
4,3. Denote Q4,l as the event where in GameG4,l for l=2,3,4, A makes a h query with σA for the sA∗th session of party A∗, when (RB,ωB′) is output by the sB∗th session of party B∗ but ωB≠ωB′.
Similar toAnalysis ofG1,3, under HNF-LWEq,n,α assumption, we have (46)PrQ4,3=PrQ4,2-neglnPrF4,3∣¬Q4,3=Pr⁡F4,2∣¬Q4,2-negln.
G
a
m
e
G
4,4. S randomly selects RB′←Zqn_ and acts almost identically in G4,3 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗th session of B∗, S responds to the query as in GameG4,3. Otherwise, S randomly chooses d←DZ,α,q and computes RB=RB′-d·pBmodq_. Then S randomly selects kB←Zq_ and computes ωB,σB as described in protocol. If A has made a h query h(A¯,B¯,RA,RB,ωB,σB), S stops. Else, it randomly selects skB←{0,1}k_ and sets h(A¯,B¯,RA,RB,ωB,σB)=skB. Finally, it sends (RB,ωB) to A.
Analysis of
G
4,4. Similar toAnalysis ofG1,4, under HNF-LWEq,n,α assumption, G4,3 and G4,4 are computationally indistinguishable. In particular, Pr[Q4,4]=Pr[Q4,3] and PrF4,4∣¬Q4,4=Pr⁡[F4,3∣¬Q4,3]-negl(n).
Similar toAnalysis ofG1,4 about Pr[Q1,4]=negl(n), under HNF-LWEq,n,α assumption, we have Pr[Q4,4]=negl(n).
Similar toAnalysis ofG1,4 about PrF1,4∣¬Q1,4=1/2+negl(n), we get PrF4,4∣¬Q4,4=1/2+negl(n).
In summary,Pr[F4,0]=Pr[F4,2]+negl(n) byAnalysis ofG4,1 and G4,2. ByAnalysis ofG4,4, (47)Pr⁡Q4,3=Pr⁡Q4,4=neglnPr⁡F4,3=Pr⁡F4,4+negln. Since (48)PrF4,3=Pr⁡F4,3∣Q4,3PrQ4,3+PrF4,3∣¬Q4,31-PrQ4,3,thus (49)PrF4,3=PrF4,3∣¬Q4,3-negln.Combining this withAnalysis ofG4,3 and G4,4, then (50)PrF4,0=PrF4,2+negln=12+negln.
This finishes the proof.


#### 4.2.3. Type Five Adversary

Theorem 9.
IfHNF-LWEq,n,α is hard, the proposed AKE is secure against any PPT Type Five adversary A under the BR model.Proof.
We prove the theorem by a series of GamesG5,l for 0≤l≤4.
Game
G
5,0. S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{0,…,m}, and hopes that the adversary will select sid∗=(Π,R,B∗,A∗,RA∗,(RB∗,ωB∗)) as the test session, where RA∗ is output by the sA∗th session of party B∗ and (RB∗,ωB∗) is output by the sB∗th session of party B∗ activated by Send1(Π,R,B∗,A∗,RA∗). Then, S randomly selects M←Zqn×n, honestly generates static public keys for all parties (by randomly choosing sA,eA←DZn,αq), and simulates security game for A. In particular, S preserves one table L for random oracle h and responds to queries from A in the following.(i)
h(in) queries: if there is no tuple (in,out) in L, randomly select an element out∈{0,1}k and add (in,out) to L list. Then send out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates a session of A¯ with intended partner B¯; S randomly selects rA,e1←DZn,αq and returns RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1Π,R,B¯,A¯,RA: S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to the protocol. At last, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA by using rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA if session key of sid has been generated.(vi)
Corrupt(A¯): send Alice’s static secret key sA to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1}, and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session key skA of sid.
Analysis of
G
5,0. In this game, S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{1,…,m} independent from A’s view. Thus, the probability that S will not stop in G5,0 is at least 1/m2·N2.
Game
G
5,1. S first computes RB′=rB′tM+2e2′modq_, where rB′,e2′←DZn,αq. Then, it acts identically as in G5,0 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of B∗, S responds to queries as in GameG5,0. Else, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_, kB=rB′t·pA+rB′t·RAmodq_:(51)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
Finally, it honestly computesωB,skB according to the protocol and sends (yB,ωB) to A.
LetF5,l be the event that A outputs a guess b′=b in GameG5,l for l=1,2,3,4.
Analysis of
G
5,1. Similar toAnalysis of  G1,1, under HNF-LWEq,n,α assumption, then (52)PrF5,1=PrF5,0-negln.
G
a
m
e
G
5,2. S first computes RA′=MrA′+2e1′modq_, where rA′,e1′←DZn,αq. Then, S acts identically as in G5,1 apart from the following cases.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds as in GameG5,1. Else, it randomly selects c←DZ,αq, computes RA=RA′-c·pAmodq_, and sends RA to A.
(ii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to queries as in GameG5,1. Otherwise, (RB,ωB) is output by the sB∗th session of party B∗; let skB be the session key of session sid=(Π,R,B¯,A¯,RA,(RB,ωB)); S sets skA=skB_. Otherwise, it computes kA=(pB+RB)·rA′modq_. At last, S computes skA according to the protocol.
Analysis of
G
5,2. Similar toAnalysis ofG1,2, under HNF-LWEq,n,α assumption, we have (53)PrF5,2=PrF5,1-negln.
G
a
m
e
G
5,3. S first randomly chooses RA′←Zqn_. Then it acts identically as in G5,2 with the following exceptions.
(i)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, or (RB,ωB) is output by the sB∗th session of party B∗, S responds to query as in GameG5,2. Else, it randomly selects skA←{0,1}k_ as the session key.
Analysis of
G
5,3. Similar to Analysis of G2,4, G2,5, and G2,6, under LWEq,n,α assumption, we have (54)PrF5,3=PrF5,2-negln.
G
a
m
e
G
5,4. S randomly selects RB′←Zqn_ and acts identically in G5,3 with the following exceptions.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗th session of B∗, S responds to the query as in GameG5,3. Otherwise, S randomly chooses d←DZ,α,q and computes RB=RB′-d·pBmodq_. Then S randomly selects kB←Zq_ and computes ωB,σB as described in protocol. If A has made a h query h(A¯,B¯,RA,RB,ωB,σB), S stops. Otherwise, it randomly selects skB←{0,1}k_ and sets h(A¯,B¯,RA,RB,ωB,σB)=skB. At last, it returns (RB,ωB) to A.
Analysis of
G
5,4. Similar toAnalysis ofG1,4, under HNF-LWEq,n,α assumption, we have Pr[F5,4]=Pr[F5,3]-negl(n).
Similar toAnalysis ofG1,4 about Pr[F1,4]=1/2+negl(n), under HNF-LWEq,n,α assumption, we have (55)PrF5,4∣¬Q5,4=12+negln.
In summary,Pr[F5,0]=Pr[F5,2]+negl(n) byAnalysis ofG5,1 and G5,2. ByAnalysis ofG5,4, Pr[F5,3]=Pr[F5,4]+negl(n). Combining this withAnalysis ofG5,3 and G5,4, we have (56)PrF5,0=PrF5,2+negln=12+negln.
This completes the proof.


## 4.1. Security for the Initiator

In this session, the AKE security for initiator is proved when the initiator is the owner of the test session. Letsid∗=(Π,I,A∗,B∗,RA∗,(RB∗,ωB∗)) be the test session chosen by the adversary A. Consider two types of adversaries.Type One: RB∗ is output by a session activated at B∗ by a Send1(Π,R,B∗,A∗,RA∗).Type Two: RB∗ is not output by any session activated at B∗ by a Send1(Π,R,B∗,A∗,RA∗).To capture wPFS,TypeOne adversary is allowed to obtain the static secret keys of parties A∗ and B∗ by corrupting A∗ and B∗ (butType Two adversary is not allowed to corrupt either A∗ or B∗).


### 4.1.1. Security against Type One Adversary

First, AKE security is proved for any PPTType One adversary A.Theorem 5.
IfHNF-LWEq,n,α is hard, the proposed AKE is secure for any PPT Type One adversary A under the BR model.Proof.
The security analysis is performed with a sequence of gamesG1,l for 0≤l≤4. It starts with the real security game, between an adversary A and a simulator S, that models the indistinguishability of the fresh session key. Use underline to show the differences between the previous game and its next one. Let F1,l be the event that A outputs a guess b′: b′=b in GameG1,l, l=0,1,2,3,4.
Game
G
1,0. This is the original game where the messages are generated honestly. In Game G1,0, S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{1,…,m}, and hopes the adversary will choose sid∗=(Π,I,A∗,B∗,RA∗,(RB∗,ωB∗)) as the test session, where RA∗ is output by sA∗th session of party A∗, and RB∗ is output by sB∗th session of party B∗ activated by a Send1(Π,R,B∗,A∗,RA∗). S selects M←Zqn×n at random, honestly generates static public keys for all parties by randomly choosing sA,eA←DZn,αq, and simulates the attack environment for A. Specifically, S keeps one table L for random oracle h and responds to queries of A.(i)
h(in) queries: if there is no tuple (in,out) in L, it randomly selects an element out∈{0,1}k and adds (in,out) to L list. At last it returns out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates a new session of A¯ with intended partner B¯, S randomly selects rA,e1←DZn,αq and sends RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1(Π,R,B¯,A¯,RA): S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to the protocol. Finally, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA by using rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA if session key of sid has been produced.(vi)
Corrupt(A¯): return Alice’s static secret key sA to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1}, and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session key skA of sid.
Analysis of
G
1,0. In this game, S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{1,…,m} independently from the view of A. Hence, the probability that S will not stop in G1,0 is at least 1/m2·N2.
G
a
m
e
G
1,1. S first computes RB′=rB′tM+2e2′tmodq_, where rB′,e2′←DZn,αq randomly. Then, it acts almost the same as in G1,0 except for the case below.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of B∗, S responds to the query as in GameG1,0. Otherwise, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_. Then S computes kB=rB′t·pA+rB′t·RAmodq_: (13)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
Finally, it honestly computesωB,skB according to the protocol and sends (RB,ωB) to A.
Analysis of
G
1,1. Since (M,RB′=rB′t·M+2e2′t) is a LWE tuple with randomly rB′,e2′←DZn,αq, then RB′ is computationally indistinguishable from uniform distribution over Zqn; thus the probability that A guesses the correct RB=RB′-d·pB before is negligible. Since pB=sBtM+2eBtmodq, sB,eB←DZn,αq, we have (14)RB=RB′-d·pB=rB′t-dsBtM+2e2′t-deBtmodq.
By Lemma1, the norm of each entry in both rB′t-dsBt and e2′t-deBt is at most sn; thus both rB′t-dsBt and e2′t-deBt have distribution negligibly close to DZn,αq. This implies that the distribution of RB in GameG1,1 is statistically close to that in GameG1,0. Thus, under the HNF-LWEq,n,α assumption, we have Pr[F1,1]=Pr[F1,0]-negl(n).
G
a
m
e
G
1,2. S computes RA′=MrA′+2e1′modq_, where it randomly selects rA′,e1′←DZn,αq. Then it acts almost the same as in G1,1 apart from the following cases.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to the query as in GameG1,1. Otherwise, S randomly selects c←DZ,αq and computes RA=RA′-c·pAmodq_. Finally, it sends RA to A.
(ii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗) or it is not the sA∗th of A∗, S responds to the query as in GameG1,1. Otherwise, if (RB,ωB) is output by the sB∗th session of party B∗, let skB be the session key of session sid=(Π,R,B¯,A¯,RA,(RB,ωB)), S sets skA=skB_. Else, S computes kA=pB·rA′+RB·rA′modq_. At last, it honestly computes skA according to the protocol.(15)kA=pB·rA′+RB·rA′=sBtM+2eBt·rA′+rBtM+2e2t·rA′=sBtM·rA′+rBtM·rA′+2eBt·rA′+2e2t·rA′modq.
Analysis of
G
1,2. The proof of the distribution of RA being statistically close to that in GameG1,1 is the same as the proof ofAnalysis ofG1,1; as a result, the probability that S stops in G1,2 is negligibly close to that of G1,1. Under the LWEq,n,α assumption, we have (16)PrF1,2=PrF1,1-negln.
G
a
m
e
s
G
1,3. S randomly chooses RA′←Zqn_ and acts almost the same as in G1,2 apart from the following case.
(i)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of party A∗, or (RB,ωB) is output by the sB∗th session of party B∗, S acts the same as in GameG1,2. Else, it randomly selects skA←{0,1}k_ as the session key.
We discuss the differences betweenG1,2 and G1,3. The real session key skA in GameG1,2 is changed to a randomly chosen one in GameG1,3, where (RB,ωB′) (ωB≠ωB′) is output by the sB∗th session of party B∗. Fortunately, the adversary cannot notice the difference if he does not query h with exact σA, since h is a random oracle. To prove it conveniently, denote Q1,l by the event that in GameG1,l  A can query h with σA for the sA∗th session of A∗, when (RB,ωB′) (ωB≠ωB′) is output by the sB∗th session of B∗, where l=2,3,4.
Analysis of
G
1,3. Since h is a random oracle, the event Q1,2 is independent from the distribution of skA. Namely, no matter whether or not A obtains skA, P[Q1,2] is identical, which is suitable for Pr[Q1,3]. Especially, under the LWE assumption, the public information in G1,2 and G1,3 is computationally indistinguishable, so that Pr[Q1,3]=Pr[Q1,2]-negl(n). In addition, if PrQ1,i,l=2,3 does not happen, the distribution of skA is identical in G1,2 and G1,3. Namely, PrF1,3∣¬Q1,3=PrF1,2∣¬Q1,2-negl(n).
G
a
m
e
G
1,4. S randomly selects RB′←Zqn_ and acts almost the same as in G1,3 except for the following case.
(i)
S
e
n
d
1
(
Π
,
R
,
B
,
A
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗th session of B∗, S responds to the query as in GameG1,3. Otherwise, randomly select d←DZ,αq and compute RB=RB′-pB·dmodq. S randomly choose kB←Zq_ and compute ωB,σB according to the protocol. If A made a query h(A¯,B¯,RA,RB,ωB,σB), S stops the simulation. Else, it randomly selects skB←{0,1}k and sets h(A¯,B¯,RA,RB,ωB,σB)=skB. At last, it returns (RB,ωB) to A.
Analysis of
G
1,4. Let (f1,h1),(f2,h2) be two challenge LWE tuples with error distribution (scale by multiplying t=2). Suppose that there exists an adversary that distinguishes GameG1,3 and GameG1,4, there must exist a distinguisher D that can solve the LWE problem. In particular, D first sets M=f1,RA′=f2,RB′=h1; then it acts identically as S in GameG1,3 except for cases as follows.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗th session of B∗, D responds to queries as in GameG1,3. Otherwise, it randomly selects d←DZ,αq and computes RB=RB′-dpBmodq_. Then D sets kB=h2_, computes ωB,σB according to the protocol, and stops if A made a h query h(B¯,A¯,RA,RB,ωB,σB). Otherwise, it sets h(B¯,A¯,RA,RB,ωB,σB)=skB with a randomly chosen skB←{0,1}k. At last, it returns (RB,ωB) to A.
If(f1,h1),(f2,h2) are LWE tuples for some secret s′, A is in GameG1,3; else it is in GameG1,4. Thus, under the LWEq,n,α assumption, GameG1,3 and GameG1,4 are computationally indistinguishable. Especially, (17)PrQ1,4=PrQ1,3,PrF1,4∣¬Q1,4=PrF1,3∣¬Q1,3-negln.
Next, we analyze(18)PrQ1,4=negln,PrF1,4∣¬Q1,4=12+negln.
Let(RB,ωB) be output by the sB∗th session of B¯=B∗ and (RB,ωB′) be the information that finishes the test session (e.g., the sA∗th session of party A¯=A∗). In G1,4, kB is randomly selected from uniform distribution over Zq which is independent from both public keys and transcripts (except for ωB). This still holds even if the adversary uses a session key reveal query to obtain skB, since skB is randomly chosen and h is a random oracle. Let kA be the element computed by S; according to the protocol, kA and kB are sufficiently close; that is, kA=kB+gmodq; (19)kA=kB+2rBt·eA+sBt·e1-eBt·rA-e2t·sA≜kB+gmodqfor some g with short element. Since both public keys and transcripts (expect for ωB) are random and independent from kB, g is also independent from kB without the adversary’s view. Since mod⁡2(kA,ωB′)=mod⁡2(kB+g,ωB′), then σB′=mod⁡2(kA,ωB′) is also statistically close to {0,1} by Lemma 4. Namely, the probability that the adversary query h(B¯,A¯,RA,RB,ωB′,σB′) is at most 2-n+negl(n). Thus, Pr[Q1,4]=negl(n).
Let(RB,ωB) be output by the sB∗th session of party B¯=B∗ and (RB,ωB′) be the message that can finish the test session (e.g., the sA∗th session of party A¯=A∗). Consider two cases.
(ii)
ω
B
=
ω
B
′. In this case, skA=skB=h(A¯,B¯,RA,RB,ωB,σB), where σB=mod⁡2(kB,ωB). Since, in G1,4, kB is randomly chosen from the uniform distribution over Zq, then σB is statistically close to uniform distribution over {0,1} from the adversary’s point by Lemma 4. Thus the probability that A has made h query with σB is less than 2-n+negl(n).
(iii)
ω
B
≠
ω
B
′. By assumption that Q1,4 does not happen, thus A will never make a h query with σB.
In short, the probability thatA has made a h query with σA is negligible since h is a random oracle. If the adversary does not make a query with σA exactly, skA′s distribution is uniform over {0,1}k in the adversary’s point. Thus, PrF1,4∣¬Q1,4=1/2+negl(n).
In a word, we getPr[F1,0]=Pr[F1,2]+negl(n) by Analysis of G1,1 and G1,2. By Analysis of G1,3 and G1,4, we have (20)PrQ1,2=PrQ1,4+negln=neglnPrF1,2∣¬Q1,2=PrF1,4∣¬Q1,4+negln.By the law of the probability, (21)PrF1,2=PrF1,2∣¬Q1,21-PrQ1,2+PrF1,2∣Q1,2PrQ1,2.Thus (22)PrF1,2=PrF1,2∣¬Q1,2-negln.Combining this with PrF1,4∣¬Q1,4=1/2+negl(n), we obtain (23)PrF1,0=PrF1,2+negln=12+negln.
This finishes the proof.


### 4.1.2. Type Two Adversary

We will prove that our AKE is secure against anyPPT Type Two adversaryA.Theorem 6.
If theHNF-LWEq,n,α is hard, the proposed AKE is secure against any PPT Type Two adversary A under the BR model.Proof.
It proceeds by a sequences ofGamesG2,l, 0≤l≤6.
G
a
m
e
G
2,0. This initial game corresponds to the real attack game in which all the honest players execute. S randomly selects A∗,B∗←{1,…,N}, sA∗←{1,…,m}, and hopes that the adversary will select sid∗=(Π,I,A∗,B∗,RA∗,(RB∗,ωB)) as the test session, where RA∗ is output by the sA∗th session of party A∗ with intended party B∗ (remark that sid∗ has no matching session forType Two adversary). Then, S randomly selects M←Zqn×n, produces static public keys for all parties (by randomly choosing sA,eA←DZn,αq), and simulates the security game for A. In particular, S preserves one table L for random oracle h and responds to queries from A.(i)
h(in) queries: if there is no tuple (in,out) in L list, randomly select out∈{0,1}k and add (in,out) to L list. Then, send out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates one session of A¯ with intended partner B¯, S randomly selects rA,e1←DZn,αq and returns RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1(Π,R,B¯,A¯,RA). S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to the protocol. Then, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA by using rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA once session key of sid has been produced.(vi)
Corrupt(A¯): return Alice’s static secret key sA to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1} and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session skA of sid.
Analysis of
G
2,0. In this game, S randomly selects A∗,B∗←{1,…,N} and sA∗←{1,…,m} independently from A’s view. Thus, the probability that S will not stop in G2,0 is at least 1/m·N2.
G
a
m
e
G
2,1. S acts identically as in G2,0 except for the following case.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If A¯≠A∗, S responds to queries as in GameG2,0. Otherwise, S computes RA′=MrA′+2e1′modq_, where rA′,e1′←DZn,αq. Then, it randomly selects c←DZ,αq, computes RA=RA′-c·pAmodq_, and sends RA to A.
(ii)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If B¯≠B∗, S responds to queries as in GameG2,0. Otherwise, S computes RB′=rB′tM+2e2′tmodq_, where rB′,e2′←DZn,αq. Then, it randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_. S also computes kB=rB′t·pA+rB′t·RAmodq_:(24)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
Finally, it honestly computesωB,skB following the protocol, and sends (yB,ωB) to A.
(iii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If A≠A∗, S responds to queries as in GameG2,0. Else, let RA=RA′-pAcmodq for RA′=MrA′+2e1′modq; S computes kA=(pB+RB)·rA′modq_. At last, S computes skA according to the protocol.
Analysis of
G
2,1. Let F2,l be the event that A outputs a guess b′=b in GameG2,l,l=1,2,3,4,5,6. Similar toAnalysis ofG1,1, under HNF-LWEq,n,α assumption, then (25)PrF2,1=PrF2,0-negln.
G
a
m
e
G
2,2. S acts almost identically as in G2,1, except it replaces B∗’s public key with a uniformly chosen pB∗←Zqn_.
Analysis of
G
2,2. Note that the only difference between G2,1 and G2,2 is that S replaces pB∗=sB∗tM+2eB∗t in G2,1 with a randomly chosen pB∗ over Zqn in G2,2; thus an adversary that can distinguish the difference between G2,1 and G2,2 could solve the LWEq,n,α problem. That implies that if LWEq,n,α is hard, then (26)PrF2,2=PrF2,1-negln.
G
a
m
e
G
2,3. S first computes RA′=MrA′+2e1′modq_, where it randomly chooses rA′,e1′←DZn,αq. Then it acts identically as in G2,2 except for such cases as follows.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to queries as in GameG2,2. Else, S randomly selects c←DZ,αq and computes RA=RA′-c·pAmodq_. Finally, S returns RA to A.
(ii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗) or it is not the sA∗th of A∗, S responds to the query as in GameG2,2. Otherwise, S computes kA=pB·rA′+RB·rA′modq_, where rA′←DZn,αq. Finally, it computes skA according to the protocol.(27)kA=pB·rA′+RB·rA′=sBtM+2eBt·rA′+rBtM+2e2t·sA′=sBtM·rA′+rBtM·rA′+2eBt·rA′+2e2t·rA′modq.
Analysis of
G
2,3. Similar toAnalysis ofG1,1, under HNF-LWEq,n,α assumption, we have (28)PrF2,3=PrF2,2-negln.
G
a
m
e
s
G
2,4. S first computes h1=MrA′+2e~1′,h2=pBrA′, where rA′,e~1′←DZn,αq. Then it computes RA′=h1+2e1′=MrA′+2(e~1′+e1′)_ (or set RA′=h1), where e1′←DZn,α,q. Finally, it acts identically as in G2,3 except for the following cases.
(i)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of party A∗, S responds to queries as in GameG2,3. Else, S computes (29)kA=dh2+RBrA′=dsBtMrA′+rBtMrA′+2deBtrA′+e2trA′modq_.
At last, it computesskA according to the protocol.
Analysis of
G
2,4. In GameG2,4, we have (30)RA′=MrA′+2e~1′+e1′modqRA′=MrA′+2e~1′modqkA=sBtMrA′+rBtMrA′+2eBtrA′+e2trA′modq,where e~1′,e1′,eB,e2,rA′←DZn,α,q. By Lemma 2, the distribution of e~1′+e1′ is statistically close to DZn,α,q; the distribution of eBtrA′+e2trA′ is statistically close to DZ,α,q. Thus, if LWEq,n,α is hard, we get (31)PrF2,4=PrF2,3-negln.
G
a
m
e
G
2,5. S acts identically as in G2,4 except for the following cases.
(i)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗) or it is not the sA∗th session of A∗, S responds to queries as in GameG2,4. Otherwise, it randomly selects kA←Zq_ and computes skA according to the protocol.
Analysis of
G
2,5. The only difference between G2,4 and G2,5 is that S replaces the real kA=h2+RBrA′ in GameG2,4 with a randomly chosen kA∈Zq in G2,5. Since h is a random oracle, the only difference will not affect the A’s view until it makes a h query with σA derived from kA. Formally, denote Q2,l for l=4,5,6 as the event that A makes a h query with σA derived from kA.
Now, we prove that ifLWEq,n,α is hard, then (32)PrQ2,5=PrQ2,4PrF2,4∣¬Q2,4=PrF2,5∣¬Q2,5=12+negln.
Becauseh is a random oracle, Q2,4 is independent from (skA)’s distribution. No matter whether or not A gets skA, Pr[Q2,4] is identical; Pr[Q2,5] is so. Besides, if Q2,l for l=4,5 does not happen, G2,5 is actually identical to G2,4 in adversary view. In particular, (skA)’s distribution is random and uniform over {0,1}k; namely, the advantage of A guessing b is negligible if Q2,5 does not happen. This finishes the proof.
IfPr[Q2,5]≤negl(n), this completes the proof. But it is not easy to do so. As a matter of fact, though h2 is random in the adversary’s view under the LWE assumption, we cannot have the fact that kA=dh2+RBrA′ is random since RBrA′ is related to h2. Now we show kA is random. If we randomly chose another d~←DZ,α,q and obtain kA′=d~h2+RBrA′ we have kA′=kA+(d~-d)h2. That is, kA′-kA=(d~-d)h2. Naturally, if the adversary can distinguish kA (and kA′) from a uniformly chosen one, it can distinguish h2 (which is computationally under the LWE assumption) from a random chosen from Zq.
Actually,Q2,5 will happen with negligible probability according to Lemma 1. Let sid∗=(Π,I,A∗,B∗,RA,(RB,ωB)) be the test session. By assumption that A is a TypeTwo adversary, namely, RB is not output by B∗ by a Send1(Π,R,B∗,A∗,RA), given h1=MrA′+2e~1′, h2=pBrA′ in G2,5, denote kA=dh2+RBrA′ (which is the same as in G2,4), where d~←DZ,α,q. By our assumption, A will make a h query with σA derived from kA with probability at least Pr[Q2,5].
Now, fixingh1,h2,rA′ which are all chosen by S and are independent from the adversary’s actions, S sets d~≠d by randomly choosing d~,d←DZ,α,q and sets kA′=kA+(d~-d)h2. By Lemma 1, A will utilize RB to finish the test session and makes a h query with σA′ derived from kA′ with probability at least P[Q2,5]·2-n. Denote d-Q2,l such that an event for l=5,6  A in GameG2,l will make σA,σA′ in A’s two runs, where σA is derived from kA in A’s first run and σA′ is derived from kA′=kA+(d~-d)h2 in A’s second run. In particular, Pr[d-Q2,5]≥P[Q2,5]·2-n.
G
a
m
e
G
2,6. S randomly chooses h1←Zqn,h2←Zq_ and acts identically as in GameG2,5.
Analysis of
G
2,6. Since the only difference between G2,6 and G2,5 is that S replaces h1=MrA′+2e~1′ and h2=pBrA′ with randomly chosen elements in Zqn,Zq, respectively, an adversary that distinguishes the difference between G2,5 and G2,6 could solve the LWEq,n,α problem. Hence, under the HNF-LWEq,n,α assumption, GameG2,6 is computationally indistinguishable from GameG2,5. In particular, we get (33)Prd-G2,6=Prd-G2,5-negln.
Besides, we can getPr[d-G2,6]=negl(n). Actually, in GameG2,6, S does not really compute kA and kA′ (it cannot compute the values since h1 is randomly chosen from Zqn and h2 is randomly chosen from Zq). Suppose that kA and kA′ (e.g., the values determined before) are as A’s target values. kA′=kA+(d~-d)h2 especially holds, since A cannot efficiently distinguish GameG2,6 from G2,5 as mentioned above. Since h2 is uniformly distributed over Zq and independent from A’s view (thus is independent from kA and kA′), then σA′=mod⁡2(kA′,ωA′) is statistically close to uniform over {0,1} even when conditioned on σA=mod⁡2(kA,ωA) by Lemma 4 ((d~-d) is in invertible with overwhelming probability). Thus, the probability that A will make a h query with σA′ is at most 2-n+negl(n). Namely, Pr(d-G2,6)≤2-n+negl(n), which is negligible in n. Namely, Pr[d-G2,6]=negl(n).
Generally speaking, byAnalysis ofG2,6, we have Pr[d-G2,5]=negl(n), which implies that Pr[Q2,5]=negl(n) by the condition that Pr[double-Q2,5]≥Pr[Q2,5]1/2n2). Combining this withAnalysis ofG2,5, we obtain Pr[F2,4]=1/2+negl(n). A simple computation shows that Pr[F2,0]=1/2+negl(n). The proof is completed.


## 4.1.1. Security against Type One Adversary

First, AKE security is proved for any PPTType One adversary A.Theorem 5.
IfHNF-LWEq,n,α is hard, the proposed AKE is secure for any PPT Type One adversary A under the BR model.Proof.
The security analysis is performed with a sequence of gamesG1,l for 0≤l≤4. It starts with the real security game, between an adversary A and a simulator S, that models the indistinguishability of the fresh session key. Use underline to show the differences between the previous game and its next one. Let F1,l be the event that A outputs a guess b′: b′=b in GameG1,l, l=0,1,2,3,4.
Game
G
1,0. This is the original game where the messages are generated honestly. In Game G1,0, S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{1,…,m}, and hopes the adversary will choose sid∗=(Π,I,A∗,B∗,RA∗,(RB∗,ωB∗)) as the test session, where RA∗ is output by sA∗th session of party A∗, and RB∗ is output by sB∗th session of party B∗ activated by a Send1(Π,R,B∗,A∗,RA∗). S selects M←Zqn×n at random, honestly generates static public keys for all parties by randomly choosing sA,eA←DZn,αq, and simulates the attack environment for A. Specifically, S keeps one table L for random oracle h and responds to queries of A.(i)
h(in) queries: if there is no tuple (in,out) in L, it randomly selects an element out∈{0,1}k and adds (in,out) to L list. At last it returns out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates a new session of A¯ with intended partner B¯, S randomly selects rA,e1←DZn,αq and sends RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1(Π,R,B¯,A¯,RA): S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to the protocol. Finally, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA by using rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA if session key of sid has been produced.(vi)
Corrupt(A¯): return Alice’s static secret key sA to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1}, and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session key skA of sid.
Analysis of
G
1,0. In this game, S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{1,…,m} independently from the view of A. Hence, the probability that S will not stop in G1,0 is at least 1/m2·N2.
G
a
m
e
G
1,1. S first computes RB′=rB′tM+2e2′tmodq_, where rB′,e2′←DZn,αq randomly. Then, it acts almost the same as in G1,0 except for the case below.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of B∗, S responds to the query as in GameG1,0. Otherwise, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_. Then S computes kB=rB′t·pA+rB′t·RAmodq_: (13)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
Finally, it honestly computesωB,skB according to the protocol and sends (RB,ωB) to A.
Analysis of
G
1,1. Since (M,RB′=rB′t·M+2e2′t) is a LWE tuple with randomly rB′,e2′←DZn,αq, then RB′ is computationally indistinguishable from uniform distribution over Zqn; thus the probability that A guesses the correct RB=RB′-d·pB before is negligible. Since pB=sBtM+2eBtmodq, sB,eB←DZn,αq, we have (14)RB=RB′-d·pB=rB′t-dsBtM+2e2′t-deBtmodq.
By Lemma1, the norm of each entry in both rB′t-dsBt and e2′t-deBt is at most sn; thus both rB′t-dsBt and e2′t-deBt have distribution negligibly close to DZn,αq. This implies that the distribution of RB in GameG1,1 is statistically close to that in GameG1,0. Thus, under the HNF-LWEq,n,α assumption, we have Pr[F1,1]=Pr[F1,0]-negl(n).
G
a
m
e
G
1,2. S computes RA′=MrA′+2e1′modq_, where it randomly selects rA′,e1′←DZn,αq. Then it acts almost the same as in G1,1 apart from the following cases.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to the query as in GameG1,1. Otherwise, S randomly selects c←DZ,αq and computes RA=RA′-c·pAmodq_. Finally, it sends RA to A.
(ii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗) or it is not the sA∗th of A∗, S responds to the query as in GameG1,1. Otherwise, if (RB,ωB) is output by the sB∗th session of party B∗, let skB be the session key of session sid=(Π,R,B¯,A¯,RA,(RB,ωB)), S sets skA=skB_. Else, S computes kA=pB·rA′+RB·rA′modq_. At last, it honestly computes skA according to the protocol.(15)kA=pB·rA′+RB·rA′=sBtM+2eBt·rA′+rBtM+2e2t·rA′=sBtM·rA′+rBtM·rA′+2eBt·rA′+2e2t·rA′modq.
Analysis of
G
1,2. The proof of the distribution of RA being statistically close to that in GameG1,1 is the same as the proof ofAnalysis ofG1,1; as a result, the probability that S stops in G1,2 is negligibly close to that of G1,1. Under the LWEq,n,α assumption, we have (16)PrF1,2=PrF1,1-negln.
G
a
m
e
s
G
1,3. S randomly chooses RA′←Zqn_ and acts almost the same as in G1,2 apart from the following case.
(i)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of party A∗, or (RB,ωB) is output by the sB∗th session of party B∗, S acts the same as in GameG1,2. Else, it randomly selects skA←{0,1}k_ as the session key.
We discuss the differences betweenG1,2 and G1,3. The real session key skA in GameG1,2 is changed to a randomly chosen one in GameG1,3, where (RB,ωB′) (ωB≠ωB′) is output by the sB∗th session of party B∗. Fortunately, the adversary cannot notice the difference if he does not query h with exact σA, since h is a random oracle. To prove it conveniently, denote Q1,l by the event that in GameG1,l  A can query h with σA for the sA∗th session of A∗, when (RB,ωB′) (ωB≠ωB′) is output by the sB∗th session of B∗, where l=2,3,4.
Analysis of
G
1,3. Since h is a random oracle, the event Q1,2 is independent from the distribution of skA. Namely, no matter whether or not A obtains skA, P[Q1,2] is identical, which is suitable for Pr[Q1,3]. Especially, under the LWE assumption, the public information in G1,2 and G1,3 is computationally indistinguishable, so that Pr[Q1,3]=Pr[Q1,2]-negl(n). In addition, if PrQ1,i,l=2,3 does not happen, the distribution of skA is identical in G1,2 and G1,3. Namely, PrF1,3∣¬Q1,3=PrF1,2∣¬Q1,2-negl(n).
G
a
m
e
G
1,4. S randomly selects RB′←Zqn_ and acts almost the same as in G1,3 except for the following case.
(i)
S
e
n
d
1
(
Π
,
R
,
B
,
A
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗th session of B∗, S responds to the query as in GameG1,3. Otherwise, randomly select d←DZ,αq and compute RB=RB′-pB·dmodq. S randomly choose kB←Zq_ and compute ωB,σB according to the protocol. If A made a query h(A¯,B¯,RA,RB,ωB,σB), S stops the simulation. Else, it randomly selects skB←{0,1}k and sets h(A¯,B¯,RA,RB,ωB,σB)=skB. At last, it returns (RB,ωB) to A.
Analysis of
G
1,4. Let (f1,h1),(f2,h2) be two challenge LWE tuples with error distribution (scale by multiplying t=2). Suppose that there exists an adversary that distinguishes GameG1,3 and GameG1,4, there must exist a distinguisher D that can solve the LWE problem. In particular, D first sets M=f1,RA′=f2,RB′=h1; then it acts identically as S in GameG1,3 except for cases as follows.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗th session of B∗, D responds to queries as in GameG1,3. Otherwise, it randomly selects d←DZ,αq and computes RB=RB′-dpBmodq_. Then D sets kB=h2_, computes ωB,σB according to the protocol, and stops if A made a h query h(B¯,A¯,RA,RB,ωB,σB). Otherwise, it sets h(B¯,A¯,RA,RB,ωB,σB)=skB with a randomly chosen skB←{0,1}k. At last, it returns (RB,ωB) to A.
If(f1,h1),(f2,h2) are LWE tuples for some secret s′, A is in GameG1,3; else it is in GameG1,4. Thus, under the LWEq,n,α assumption, GameG1,3 and GameG1,4 are computationally indistinguishable. Especially, (17)PrQ1,4=PrQ1,3,PrF1,4∣¬Q1,4=PrF1,3∣¬Q1,3-negln.
Next, we analyze(18)PrQ1,4=negln,PrF1,4∣¬Q1,4=12+negln.
Let(RB,ωB) be output by the sB∗th session of B¯=B∗ and (RB,ωB′) be the information that finishes the test session (e.g., the sA∗th session of party A¯=A∗). In G1,4, kB is randomly selected from uniform distribution over Zq which is independent from both public keys and transcripts (except for ωB). This still holds even if the adversary uses a session key reveal query to obtain skB, since skB is randomly chosen and h is a random oracle. Let kA be the element computed by S; according to the protocol, kA and kB are sufficiently close; that is, kA=kB+gmodq; (19)kA=kB+2rBt·eA+sBt·e1-eBt·rA-e2t·sA≜kB+gmodqfor some g with short element. Since both public keys and transcripts (expect for ωB) are random and independent from kB, g is also independent from kB without the adversary’s view. Since mod⁡2(kA,ωB′)=mod⁡2(kB+g,ωB′), then σB′=mod⁡2(kA,ωB′) is also statistically close to {0,1} by Lemma 4. Namely, the probability that the adversary query h(B¯,A¯,RA,RB,ωB′,σB′) is at most 2-n+negl(n). Thus, Pr[Q1,4]=negl(n).
Let(RB,ωB) be output by the sB∗th session of party B¯=B∗ and (RB,ωB′) be the message that can finish the test session (e.g., the sA∗th session of party A¯=A∗). Consider two cases.
(ii)
ω
B
=
ω
B
′. In this case, skA=skB=h(A¯,B¯,RA,RB,ωB,σB), where σB=mod⁡2(kB,ωB). Since, in G1,4, kB is randomly chosen from the uniform distribution over Zq, then σB is statistically close to uniform distribution over {0,1} from the adversary’s point by Lemma 4. Thus the probability that A has made h query with σB is less than 2-n+negl(n).
(iii)
ω
B
≠
ω
B
′. By assumption that Q1,4 does not happen, thus A will never make a h query with σB.
In short, the probability thatA has made a h query with σA is negligible since h is a random oracle. If the adversary does not make a query with σA exactly, skA′s distribution is uniform over {0,1}k in the adversary’s point. Thus, PrF1,4∣¬Q1,4=1/2+negl(n).
In a word, we getPr[F1,0]=Pr[F1,2]+negl(n) by Analysis of G1,1 and G1,2. By Analysis of G1,3 and G1,4, we have (20)PrQ1,2=PrQ1,4+negln=neglnPrF1,2∣¬Q1,2=PrF1,4∣¬Q1,4+negln.By the law of the probability, (21)PrF1,2=PrF1,2∣¬Q1,21-PrQ1,2+PrF1,2∣Q1,2PrQ1,2.Thus (22)PrF1,2=PrF1,2∣¬Q1,2-negln.Combining this with PrF1,4∣¬Q1,4=1/2+negl(n), we obtain (23)PrF1,0=PrF1,2+negln=12+negln.
This finishes the proof.


## 4.1.2. Type Two Adversary

We will prove that our AKE is secure against anyPPT Type Two adversaryA.Theorem 6.
If theHNF-LWEq,n,α is hard, the proposed AKE is secure against any PPT Type Two adversary A under the BR model.Proof.
It proceeds by a sequences ofGamesG2,l, 0≤l≤6.
G
a
m
e
G
2,0. This initial game corresponds to the real attack game in which all the honest players execute. S randomly selects A∗,B∗←{1,…,N}, sA∗←{1,…,m}, and hopes that the adversary will select sid∗=(Π,I,A∗,B∗,RA∗,(RB∗,ωB)) as the test session, where RA∗ is output by the sA∗th session of party A∗ with intended party B∗ (remark that sid∗ has no matching session forType Two adversary). Then, S randomly selects M←Zqn×n, produces static public keys for all parties (by randomly choosing sA,eA←DZn,αq), and simulates the security game for A. In particular, S preserves one table L for random oracle h and responds to queries from A.(i)
h(in) queries: if there is no tuple (in,out) in L list, randomly select out∈{0,1}k and add (in,out) to L list. Then, send out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates one session of A¯ with intended partner B¯, S randomly selects rA,e1←DZn,αq and returns RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1(Π,R,B¯,A¯,RA). S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to the protocol. Then, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA by using rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA once session key of sid has been produced.(vi)
Corrupt(A¯): return Alice’s static secret key sA to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1} and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session skA of sid.
Analysis of
G
2,0. In this game, S randomly selects A∗,B∗←{1,…,N} and sA∗←{1,…,m} independently from A’s view. Thus, the probability that S will not stop in G2,0 is at least 1/m·N2.
G
a
m
e
G
2,1. S acts identically as in G2,0 except for the following case.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If A¯≠A∗, S responds to queries as in GameG2,0. Otherwise, S computes RA′=MrA′+2e1′modq_, where rA′,e1′←DZn,αq. Then, it randomly selects c←DZ,αq, computes RA=RA′-c·pAmodq_, and sends RA to A.
(ii)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If B¯≠B∗, S responds to queries as in GameG2,0. Otherwise, S computes RB′=rB′tM+2e2′tmodq_, where rB′,e2′←DZn,αq. Then, it randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_. S also computes kB=rB′t·pA+rB′t·RAmodq_:(24)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
Finally, it honestly computesωB,skB following the protocol, and sends (yB,ωB) to A.
(iii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If A≠A∗, S responds to queries as in GameG2,0. Else, let RA=RA′-pAcmodq for RA′=MrA′+2e1′modq; S computes kA=(pB+RB)·rA′modq_. At last, S computes skA according to the protocol.
Analysis of
G
2,1. Let F2,l be the event that A outputs a guess b′=b in GameG2,l,l=1,2,3,4,5,6. Similar toAnalysis ofG1,1, under HNF-LWEq,n,α assumption, then (25)PrF2,1=PrF2,0-negln.
G
a
m
e
G
2,2. S acts almost identically as in G2,1, except it replaces B∗’s public key with a uniformly chosen pB∗←Zqn_.
Analysis of
G
2,2. Note that the only difference between G2,1 and G2,2 is that S replaces pB∗=sB∗tM+2eB∗t in G2,1 with a randomly chosen pB∗ over Zqn in G2,2; thus an adversary that can distinguish the difference between G2,1 and G2,2 could solve the LWEq,n,α problem. That implies that if LWEq,n,α is hard, then (26)PrF2,2=PrF2,1-negln.
G
a
m
e
G
2,3. S first computes RA′=MrA′+2e1′modq_, where it randomly chooses rA′,e1′←DZn,αq. Then it acts identically as in G2,2 except for such cases as follows.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to queries as in GameG2,2. Else, S randomly selects c←DZ,αq and computes RA=RA′-c·pAmodq_. Finally, S returns RA to A.
(ii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗) or it is not the sA∗th of A∗, S responds to the query as in GameG2,2. Otherwise, S computes kA=pB·rA′+RB·rA′modq_, where rA′←DZn,αq. Finally, it computes skA according to the protocol.(27)kA=pB·rA′+RB·rA′=sBtM+2eBt·rA′+rBtM+2e2t·sA′=sBtM·rA′+rBtM·rA′+2eBt·rA′+2e2t·rA′modq.
Analysis of
G
2,3. Similar toAnalysis ofG1,1, under HNF-LWEq,n,α assumption, we have (28)PrF2,3=PrF2,2-negln.
G
a
m
e
s
G
2,4. S first computes h1=MrA′+2e~1′,h2=pBrA′, where rA′,e~1′←DZn,αq. Then it computes RA′=h1+2e1′=MrA′+2(e~1′+e1′)_ (or set RA′=h1), where e1′←DZn,α,q. Finally, it acts identically as in G2,3 except for the following cases.
(i)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of party A∗, S responds to queries as in GameG2,3. Else, S computes (29)kA=dh2+RBrA′=dsBtMrA′+rBtMrA′+2deBtrA′+e2trA′modq_.
At last, it computesskA according to the protocol.
Analysis of
G
2,4. In GameG2,4, we have (30)RA′=MrA′+2e~1′+e1′modqRA′=MrA′+2e~1′modqkA=sBtMrA′+rBtMrA′+2eBtrA′+e2trA′modq,where e~1′,e1′,eB,e2,rA′←DZn,α,q. By Lemma 2, the distribution of e~1′+e1′ is statistically close to DZn,α,q; the distribution of eBtrA′+e2trA′ is statistically close to DZ,α,q. Thus, if LWEq,n,α is hard, we get (31)PrF2,4=PrF2,3-negln.
G
a
m
e
G
2,5. S acts identically as in G2,4 except for the following cases.
(i)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗) or it is not the sA∗th session of A∗, S responds to queries as in GameG2,4. Otherwise, it randomly selects kA←Zq_ and computes skA according to the protocol.
Analysis of
G
2,5. The only difference between G2,4 and G2,5 is that S replaces the real kA=h2+RBrA′ in GameG2,4 with a randomly chosen kA∈Zq in G2,5. Since h is a random oracle, the only difference will not affect the A’s view until it makes a h query with σA derived from kA. Formally, denote Q2,l for l=4,5,6 as the event that A makes a h query with σA derived from kA.
Now, we prove that ifLWEq,n,α is hard, then (32)PrQ2,5=PrQ2,4PrF2,4∣¬Q2,4=PrF2,5∣¬Q2,5=12+negln.
Becauseh is a random oracle, Q2,4 is independent from (skA)’s distribution. No matter whether or not A gets skA, Pr[Q2,4] is identical; Pr[Q2,5] is so. Besides, if Q2,l for l=4,5 does not happen, G2,5 is actually identical to G2,4 in adversary view. In particular, (skA)’s distribution is random and uniform over {0,1}k; namely, the advantage of A guessing b is negligible if Q2,5 does not happen. This finishes the proof.
IfPr[Q2,5]≤negl(n), this completes the proof. But it is not easy to do so. As a matter of fact, though h2 is random in the adversary’s view under the LWE assumption, we cannot have the fact that kA=dh2+RBrA′ is random since RBrA′ is related to h2. Now we show kA is random. If we randomly chose another d~←DZ,α,q and obtain kA′=d~h2+RBrA′ we have kA′=kA+(d~-d)h2. That is, kA′-kA=(d~-d)h2. Naturally, if the adversary can distinguish kA (and kA′) from a uniformly chosen one, it can distinguish h2 (which is computationally under the LWE assumption) from a random chosen from Zq.
Actually,Q2,5 will happen with negligible probability according to Lemma 1. Let sid∗=(Π,I,A∗,B∗,RA,(RB,ωB)) be the test session. By assumption that A is a TypeTwo adversary, namely, RB is not output by B∗ by a Send1(Π,R,B∗,A∗,RA), given h1=MrA′+2e~1′, h2=pBrA′ in G2,5, denote kA=dh2+RBrA′ (which is the same as in G2,4), where d~←DZ,α,q. By our assumption, A will make a h query with σA derived from kA with probability at least Pr[Q2,5].
Now, fixingh1,h2,rA′ which are all chosen by S and are independent from the adversary’s actions, S sets d~≠d by randomly choosing d~,d←DZ,α,q and sets kA′=kA+(d~-d)h2. By Lemma 1, A will utilize RB to finish the test session and makes a h query with σA′ derived from kA′ with probability at least P[Q2,5]·2-n. Denote d-Q2,l such that an event for l=5,6  A in GameG2,l will make σA,σA′ in A’s two runs, where σA is derived from kA in A’s first run and σA′ is derived from kA′=kA+(d~-d)h2 in A’s second run. In particular, Pr[d-Q2,5]≥P[Q2,5]·2-n.
G
a
m
e
G
2,6. S randomly chooses h1←Zqn,h2←Zq_ and acts identically as in GameG2,5.
Analysis of
G
2,6. Since the only difference between G2,6 and G2,5 is that S replaces h1=MrA′+2e~1′ and h2=pBrA′ with randomly chosen elements in Zqn,Zq, respectively, an adversary that distinguishes the difference between G2,5 and G2,6 could solve the LWEq,n,α problem. Hence, under the HNF-LWEq,n,α assumption, GameG2,6 is computationally indistinguishable from GameG2,5. In particular, we get (33)Prd-G2,6=Prd-G2,5-negln.
Besides, we can getPr[d-G2,6]=negl(n). Actually, in GameG2,6, S does not really compute kA and kA′ (it cannot compute the values since h1 is randomly chosen from Zqn and h2 is randomly chosen from Zq). Suppose that kA and kA′ (e.g., the values determined before) are as A’s target values. kA′=kA+(d~-d)h2 especially holds, since A cannot efficiently distinguish GameG2,6 from G2,5 as mentioned above. Since h2 is uniformly distributed over Zq and independent from A’s view (thus is independent from kA and kA′), then σA′=mod⁡2(kA′,ωA′) is statistically close to uniform over {0,1} even when conditioned on σA=mod⁡2(kA,ωA) by Lemma 4 ((d~-d) is in invertible with overwhelming probability). Thus, the probability that A will make a h query with σA′ is at most 2-n+negl(n). Namely, Pr(d-G2,6)≤2-n+negl(n), which is negligible in n. Namely, Pr[d-G2,6]=negl(n).
Generally speaking, byAnalysis ofG2,6, we have Pr[d-G2,5]=negl(n), which implies that Pr[Q2,5]=negl(n) by the condition that Pr[double-Q2,5]≥Pr[Q2,5]1/2n2). Combining this withAnalysis ofG2,5, we obtain Pr[F2,4]=1/2+negl(n). A simple computation shows that Pr[F2,0]=1/2+negl(n). The proof is completed.


## 4.2. Security for the Responder

Now we prove the security when the responder is the owner of the test session. Letsid∗=(Π,R,B∗,A∗,RA∗,(RB∗ωB∗)) be the test session; consider three types of adversaries.T
y
p
e
T
h
r
e
e: RA∗ is not output by any session of A∗ activated by a Send0(Π,I,A∗,B∗).T
y
p
e
F
o
u
r: RA∗ is output by a session of A∗ activated by a Send0(Π,I,A∗,B∗), but A∗ never completes the session, or it completes it with exact RB∗.T
y
p
e
F
i
v
e: RA∗ is output by a session of A∗ activated by a Send0(Π,I,A∗,B∗), but A∗ completes the session with another RB′≠RB.T
y
p
e
T
h
r
e
e
,
T
y
p
e
F
o
u
r, and TypeFive give a complete partition of all the adversaries that choose sid∗ as the test session. Note that if the adversary is a TypeThree or TypeFive one, the test session has no matching session. To address wPFS in our security proof, TypeFour adversary A is allowed to obtain the static secret keys of parties A∗ and B∗ by corrupting both parties (a TypeThree or TypeFive adversary is not allowed to corrupt party A∗ or B∗).


### 4.2.1. Type Three

Here we prove AKE security against any PPTTypeThree adversary A.Theorem 7.
IfHNF-LWEq,n,α is hard, the proposed AKE is secure against any PPT TypeThree adversary A under the BR model.Proof.
We prove the theorem by a series of gamesG3,l for 0≤l≤7.
G
a
m
e
G
3,0. S randomly selects A∗,B∗←{1,…,N} and sB∗←{0,…,m} and hopes that the adversary will select sid∗=(Π,R,B∗,A∗,RA∗,(RB∗,ωB)) as the test session, where (RB∗,ωB) is output by the sB∗th session of party B∗ activated by Send0(Π,R,B∗,A∗,RA∗) for some party A∗. Then, S randomly selects M←Zqn×n, honestly generates static public keys for all parties (by randomly choosing sA,eA←DZn,αq), and simulates security game for A. Specially, S preserves one table L for random oracle h, and responds to queries from A as follows.(i)
h(in) queries: if there is no tuple (in,out) in L, randomly select an element out∈{0,1}k and add (in,out) to L list. Then send out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates a new session of A¯ with intended partner B¯, S randomly selects rA,e1←DZn,αq and sends RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1Π,R,B¯,A¯,RA: S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to the protocol. At last, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA by using rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA once session key of sid has been generated.(vi)
Corrupt(A¯): return the static secret key sA of Alice to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1}, and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session skA of sid.
Analysis of
G
3,0. In this game, S randomly chooses A∗,B∗←{1,…,N} and sB∗←{1,…,m} without A’s view. Thus, the probability that S will not abort in G3,0 is at least 1/m·N2.
G
a
m
e
G
3,1. S acts identically as in G3,0 except for the following cases.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If A¯≠A∗, S responds to queries as in GameG3,0. Else, S computes RA′=MrA′+2e1′modq_, where rA′,e1′←DZn,αq. Then, it randomly selects c←DZ,αq, computes RA=RA′-c·pAmodq_, and sends RA to A.
(ii)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If B¯≠B∗, S responds to the query as in GameG3,0. Otherwise, S computes RB′=rB′tM+2e2′tmodq_, where rB′,e2′←DZn,αq. Then, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_ and kB=rB′t·pA+rB′t·RAmodq_:(34)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
At last, it computesωB,skB according to the protocol and sends (yB,ωB) to A.
(iii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If A≠A∗, S responds to query as in GameG3,0. Else, it chooses randomly c←DZ,αq, let RA=RA′-pAcmodq for RA′=MrA′+2e1′modq; S computes kA=(pB+RB)·rA′modq_. Finally, S computes skA according to the protocol.
Analysis of
G
3,1. Let F3,l be the event that A outputs a guess b′=b in GameG3,l, l=2,3,4,5,6. Similar to theAnalysis ofG1,1, under HNF-LWEq,n,α assumption, we have (35)PrF3,1=PrF3,0-negln.
G
a
m
e
G
3,2. S acts identically as in G3,1, except it replaces the public key for the party A∗ with a uniformly chosen pA∗←Zqn_.
Analysis of
G
3,2. Similar toAnalysis ofG2,3 or G1,1, under HNF-LWEq,n,α assumption, then (36)PrF3,2=PrF3,1-negln.
G
a
m
e
G
3,3. S first computes RB′=rB′tM+2e2′tmodq_, where it randomly chooses rB′,e2′←DZn,αq. Then it acts identically as in G3,2 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
A
¯
,
B
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of B∗, S responds to the query as in GameG3,2. Else, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_ and kB=rB′t·pA+rB′t·RA_, where rB′←DZn,αq. At last, it computes skB,ωB according to the protocol and returns (RB,ωB) to A.(37)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+2rB′teA+2rB′t·e1modq.
Analysis of
G
3,3. Similar to Analysis of G1,1, under LWEq,n,α assumption, then (38)PrF3,3=PrF3,2-negln.
G
a
m
e
s
G
3,4. S first computes h1=rB′tM+2e~2′t,h2=rB′tpA, where rB′,e~2′←DZn,αq. Then it computes RB′=h1+2e2′t=rB′tM+2(e~2′t+e2′t) (or set RB′=h1), where e2′←DZn,α,q. Finally, it acts identically as in G3,3 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of party B∗, S responds to queries as in GameG3,3. Otherwise, S randomly selects c←DZ,α,q, and computes RB=RB′-d·pBmodq_, (39)kB=ch2+rB′tRA=crBtMsA+rB′tMrA+2drB′teA+rB′te1modq._
At last, it computesωB, skB according to the protocol and returns (RB,ωB) to A.
Analysis of
G
3,4. Similar to Analysis of G1,1, under LWEq,n,α assumption, then (40)PrF3,4=PrF3,3-negln.
G
a
m
e
G
3,5. S acts identically as in G3,4 apart from the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗ − th session of B∗, S responds to the query as in GameG3,4. Otherwise, S randomly selects d←DZ,α,q and computes RB=RB′-d·pBmodq. Then, it randomly selects kB←Zq_ and computes ωB,σB as described in protocol. If A has made a h query h(A¯,B¯,RA,RB,ωB,σB), S stops. Otherwise, it randomly selects skB←{0,1}k_ and sets h(A¯,B¯,RA,RB,ωB,σB)=skB. At last, it returns (RB,ωB) to A.
Analysis of
G
3,5. The only difference between G3,4 and G3,5 is that S replace the real key kB=ch2+rB′tRA=crBtMsA+rB′tMrA+2(crB′teA+rB′te1)modq in Game G3,4 with a randomly chosen kB∈Zq in Game G3,5. Since h is a random oracle, the only difference cannot affect A’s view until it makes a h query with σB derived from kB. Denote Q3,l for l=4,5,6 as the event where A makes a h query with σB derived from kB.
Now, we prove(41)PrQ3,4=PrQ3,5PrF3,4∣¬Q3,4=PrF3,5∣¬Q3,5=12+negln.
Becauseh is a random oracle, Q3,4 is independent from (skB)’s distribution. No matter whether or not A gets skA, Pr[Q3,4] is identical; Pr[Q3,5] is so. Besides, if Q3,l for l=4,5 does not happen, G3,5 is actually identical as G3,4 in adversary view. In particular, (skB)’s distribution is random and uniform over {0,1}k; namely, the advantage of A guessing b is negligible if Q3,5 does not happen. This completes the proof.
Likewise, letsid∗=(Π,R,B∗,A∗,RA,(RB,ωB)) be the test session. By assumption that A is a TypeThree adversary, namely, RA is not output by party A∗, given h1=rB′tM+2e~2′t,h2=rB′tpA in G3,5, denote kB=ch2+rB′tRA (which is the same as in G3,4), where c←DZ,α,q. By our assumption, A will make a h query with σB derived from kB with probability at least Pr[Q3,5].
Now, fixingh1,h2,rB′ which are all chosen by S and are independent from the adversary’s actions, S sets c~≠c by randomly choosing c~←DZ,α,q, and sets kB′=c~h+rB′tRA=kB+(c~-c)h2. By Lemma 1, A will utilize RA in the test session and makes a h query with σB′ derived from kB′ with probability at least P[Q3,5]·2-n. Denote d-Q3,l as an event for l=5,6; A in GameG3,l will make σB,σB′ in A’s two runs, where σB is derived from kB in A’s first run and σB′ is derived from kB′=kB+(c~-c)h2 in A’s second run. In particular, Pr[d-Q3,5]≥P[Q3,5]·2-n.
G
a
m
e
G
3,6. S randomly chooses h1←Zqn,h2←Zq_ and acts identically as in GameG3,5.
Analysis of
G
3,6. On the one hand, the difference between G3,5 and G3,6 is that S replaces h1=rB′tM+2e~2′t,h2=rB′tpA with randomly chosen elements in Zqn,Zq, respectively; an adversary that distinguishes the difference between G3,5 and G3,6 could solve the HNF-LWEq,n,α problem. Under the HNF-LWEq,n,α assumption, GameG3,6 is computationally indistinguishable from GameG3,5. In particular, (42)Prd-G3,6=Prd-G3,5-negln.
On the other hand, inGameG3,6, S does not really compute kB and kB′ ( it cannot compute them since h1 is randomly chosen from Zqn and h2 is randomly chosen from Zq). Suppose that kB and kB′ (e.g., the values determined before) are as A’s target values. kB′=kB+(c~-c)h2 especially holds, since A cannot distinguish GameG3,6 from G3,5 as mentioned above. Since h2 is uniformly distributed over Zq and independent from A’s view (thus is independent from kB and kB′), then σB′=mod⁡2(kB′,ωB′) is statistically close to uniform over {0,1} even when conditioned on σB=mod⁡2(kB,ωB) by Lemma 4 ((c~-c) is in invertible with overwhelming probability). Thus, the probability that A will make a h query with σB′ is at most 2-n+negl(n). Namely, Pr(d-G3,6)≤2-n+negl(n) which is negligible in n. As a result, Pr[d-G3,6]=negl(n).
Generally speaking, byAnalysis ofG3,6, Pr[d-Q3,5]=negl(n), which implies that Pr[Q3,5]=negl(n) by the condition that Pr[d-Q3,5]≥Pr[Q3,5]·2-n. Combining this withAnalysis ofG3,5, we get Pr[F3,4]=1/2+negl(n). A simple computation shows that Pr[F3,0]=1/2+negl(n). The proof is completed.


### 4.2.2. Type Four Adversary

Theorem 8.
IfHNF-LWEq,n,α is hard, the proposed AKE is secure against any PPT Type Four adversary A under the BR model.Proof.
We prove it by a series of GameG4,l for 0≤l≤4.
G
a
m
e
G
4,0. S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{0,…,m} and hopes that the adversary will select sid∗=(Π,R,B∗,A∗,RA∗,(RB∗,ωB∗)) as the test session, where RA∗ is output by the sA∗th session of party A∗, (RB∗,ωB∗) is output by the sB∗th session of party B∗ activated by Send1(Π,R,B∗,A∗,RA∗). Then, S randomly selects M←Zqn×n, generates static public keys for all parties (by randomly choosing sA,eA←DZn,αq), and simulates security game for A. In particular, S preserves one table L for random oracle h, and responds the queries from A in the following.(i)
h(in) queries: if there is no tuple (in,out) in L, randomly select an element out∈{0,1}k and add (in,out) to L list. Then send out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates a session of A¯ with intended partner B¯; S randomly selects rA,e1←DZn,αq and sends RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1(Π,R,B¯,A¯,RA): S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to protocol. At last, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA with rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA if session key of sid has been generated.(vi)
Corrupt(A¯): send the static secret key sA of Alice to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1}, and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session key skA of sid.
Analysis of
G
4,0. In this game, S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{1,…,m} independent from A’s view. Thus, the probability that S will not stop in G4,0 is at least 1/m2·N2.
LetF4,l be the event that A outputs a guess b′=b in GameG4,l,l=1,2,3,4.
G
a
m
e
G
4,1. S first computes RB′=rB′tM+2e2′modq_, where rB′,e2′←DZn,αq. Then, it acts identically as in G4,0 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of B∗, S responds to the query as in GameG4,0. Otherwise, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_. Then, S also computes kB=rB′t·pA+rB′t·RAmodq_:(43)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
Finally, it honestly computesωB,skB following the protocol and returns (yB,ωB) to A.
Analysis of
G
4,1. Similar toAnalysis ofG1,1, under HNF-LWEq,n,α assumption, we have (44)PrF4,1=PrF4,0-negln.
G
a
m
e
G
4,2. S first computes RA′=MrA′+2e1′modq_, where rA′,e1′←DZn,αq. Then, S acts identically as in G4,1, apart from the following cases.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to the query as in GameG4,1. Else, it randomly selects c←DZ,αq, computes RA=RA′-c·pAmodq_, and sends RA to A.
(ii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to queries as in GameG4,1. Otherwise, (RB,ωB) is output by the sB∗th session of party B∗. Let skB be the session key of session sid=(Π,R,B¯,A¯,RA,(RB,ωB)); S sets skA=skB_. Otherwise, it computes kA=pB+RB·rA′modq_. At last, S computes skA according to the protocol.
Analysis of
G
4,2. Similar toAnalysis ofG1,2, under HNF-LWEq,n,α assumption, we have (45)PrF4,2=PrF4,1-negln.
G
a
m
e
G
4,3. S first randomly selects RA′←Zqn_. Then it acts identically as in G4,2 except in the following cases.
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, or (RB,ωB) is output by the sB∗th session of party B∗, S answers the query as in GameG4,2. Else, it randomly selects skA←{0,1}k_ as the session key.
Analysis of
G
4,3. Denote Q4,l as the event where in GameG4,l for l=2,3,4, A makes a h query with σA for the sA∗th session of party A∗, when (RB,ωB′) is output by the sB∗th session of party B∗ but ωB≠ωB′.
Similar toAnalysis ofG1,3, under HNF-LWEq,n,α assumption, we have (46)PrQ4,3=PrQ4,2-neglnPrF4,3∣¬Q4,3=Pr⁡F4,2∣¬Q4,2-negln.
G
a
m
e
G
4,4. S randomly selects RB′←Zqn_ and acts almost identically in G4,3 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗th session of B∗, S responds to the query as in GameG4,3. Otherwise, S randomly chooses d←DZ,α,q and computes RB=RB′-d·pBmodq_. Then S randomly selects kB←Zq_ and computes ωB,σB as described in protocol. If A has made a h query h(A¯,B¯,RA,RB,ωB,σB), S stops. Else, it randomly selects skB←{0,1}k_ and sets h(A¯,B¯,RA,RB,ωB,σB)=skB. Finally, it sends (RB,ωB) to A.
Analysis of
G
4,4. Similar toAnalysis ofG1,4, under HNF-LWEq,n,α assumption, G4,3 and G4,4 are computationally indistinguishable. In particular, Pr[Q4,4]=Pr[Q4,3] and PrF4,4∣¬Q4,4=Pr⁡[F4,3∣¬Q4,3]-negl(n).
Similar toAnalysis ofG1,4 about Pr[Q1,4]=negl(n), under HNF-LWEq,n,α assumption, we have Pr[Q4,4]=negl(n).
Similar toAnalysis ofG1,4 about PrF1,4∣¬Q1,4=1/2+negl(n), we get PrF4,4∣¬Q4,4=1/2+negl(n).
In summary,Pr[F4,0]=Pr[F4,2]+negl(n) byAnalysis ofG4,1 and G4,2. ByAnalysis ofG4,4, (47)Pr⁡Q4,3=Pr⁡Q4,4=neglnPr⁡F4,3=Pr⁡F4,4+negln. Since (48)PrF4,3=Pr⁡F4,3∣Q4,3PrQ4,3+PrF4,3∣¬Q4,31-PrQ4,3,thus (49)PrF4,3=PrF4,3∣¬Q4,3-negln.Combining this withAnalysis ofG4,3 and G4,4, then (50)PrF4,0=PrF4,2+negln=12+negln.
This finishes the proof.


### 4.2.3. Type Five Adversary

Theorem 9.
IfHNF-LWEq,n,α is hard, the proposed AKE is secure against any PPT Type Five adversary A under the BR model.Proof.
We prove the theorem by a series of GamesG5,l for 0≤l≤4.
Game
G
5,0. S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{0,…,m}, and hopes that the adversary will select sid∗=(Π,R,B∗,A∗,RA∗,(RB∗,ωB∗)) as the test session, where RA∗ is output by the sA∗th session of party B∗ and (RB∗,ωB∗) is output by the sB∗th session of party B∗ activated by Send1(Π,R,B∗,A∗,RA∗). Then, S randomly selects M←Zqn×n, honestly generates static public keys for all parties (by randomly choosing sA,eA←DZn,αq), and simulates security game for A. In particular, S preserves one table L for random oracle h and responds to queries from A in the following.(i)
h(in) queries: if there is no tuple (in,out) in L, randomly select an element out∈{0,1}k and add (in,out) to L list. Then send out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates a session of A¯ with intended partner B¯; S randomly selects rA,e1←DZn,αq and returns RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1Π,R,B¯,A¯,RA: S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to the protocol. At last, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA by using rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA if session key of sid has been generated.(vi)
Corrupt(A¯): send Alice’s static secret key sA to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1}, and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session key skA of sid.
Analysis of
G
5,0. In this game, S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{1,…,m} independent from A’s view. Thus, the probability that S will not stop in G5,0 is at least 1/m2·N2.
Game
G
5,1. S first computes RB′=rB′tM+2e2′modq_, where rB′,e2′←DZn,αq. Then, it acts identically as in G5,0 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of B∗, S responds to queries as in GameG5,0. Else, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_, kB=rB′t·pA+rB′t·RAmodq_:(51)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
Finally, it honestly computesωB,skB according to the protocol and sends (yB,ωB) to A.
LetF5,l be the event that A outputs a guess b′=b in GameG5,l for l=1,2,3,4.
Analysis of
G
5,1. Similar toAnalysis of  G1,1, under HNF-LWEq,n,α assumption, then (52)PrF5,1=PrF5,0-negln.
G
a
m
e
G
5,2. S first computes RA′=MrA′+2e1′modq_, where rA′,e1′←DZn,αq. Then, S acts identically as in G5,1 apart from the following cases.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds as in GameG5,1. Else, it randomly selects c←DZ,αq, computes RA=RA′-c·pAmodq_, and sends RA to A.
(ii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to queries as in GameG5,1. Otherwise, (RB,ωB) is output by the sB∗th session of party B∗; let skB be the session key of session sid=(Π,R,B¯,A¯,RA,(RB,ωB)); S sets skA=skB_. Otherwise, it computes kA=(pB+RB)·rA′modq_. At last, S computes skA according to the protocol.
Analysis of
G
5,2. Similar toAnalysis ofG1,2, under HNF-LWEq,n,α assumption, we have (53)PrF5,2=PrF5,1-negln.
G
a
m
e
G
5,3. S first randomly chooses RA′←Zqn_. Then it acts identically as in G5,2 with the following exceptions.
(i)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, or (RB,ωB) is output by the sB∗th session of party B∗, S responds to query as in GameG5,2. Else, it randomly selects skA←{0,1}k_ as the session key.
Analysis of
G
5,3. Similar to Analysis of G2,4, G2,5, and G2,6, under LWEq,n,α assumption, we have (54)PrF5,3=PrF5,2-negln.
G
a
m
e
G
5,4. S randomly selects RB′←Zqn_ and acts identically in G5,3 with the following exceptions.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗th session of B∗, S responds to the query as in GameG5,3. Otherwise, S randomly chooses d←DZ,α,q and computes RB=RB′-d·pBmodq_. Then S randomly selects kB←Zq_ and computes ωB,σB as described in protocol. If A has made a h query h(A¯,B¯,RA,RB,ωB,σB), S stops. Otherwise, it randomly selects skB←{0,1}k_ and sets h(A¯,B¯,RA,RB,ωB,σB)=skB. At last, it returns (RB,ωB) to A.
Analysis of
G
5,4. Similar toAnalysis ofG1,4, under HNF-LWEq,n,α assumption, we have Pr[F5,4]=Pr[F5,3]-negl(n).
Similar toAnalysis ofG1,4 about Pr[F1,4]=1/2+negl(n), under HNF-LWEq,n,α assumption, we have (55)PrF5,4∣¬Q5,4=12+negln.
In summary,Pr[F5,0]=Pr[F5,2]+negl(n) byAnalysis ofG5,1 and G5,2. ByAnalysis ofG5,4, Pr[F5,3]=Pr[F5,4]+negl(n). Combining this withAnalysis ofG5,3 and G5,4, we have (56)PrF5,0=PrF5,2+negln=12+negln.
This completes the proof.


## 4.2.1. Type Three

Here we prove AKE security against any PPTTypeThree adversary A.Theorem 7.
IfHNF-LWEq,n,α is hard, the proposed AKE is secure against any PPT TypeThree adversary A under the BR model.Proof.
We prove the theorem by a series of gamesG3,l for 0≤l≤7.
G
a
m
e
G
3,0. S randomly selects A∗,B∗←{1,…,N} and sB∗←{0,…,m} and hopes that the adversary will select sid∗=(Π,R,B∗,A∗,RA∗,(RB∗,ωB)) as the test session, where (RB∗,ωB) is output by the sB∗th session of party B∗ activated by Send0(Π,R,B∗,A∗,RA∗) for some party A∗. Then, S randomly selects M←Zqn×n, honestly generates static public keys for all parties (by randomly choosing sA,eA←DZn,αq), and simulates security game for A. Specially, S preserves one table L for random oracle h, and responds to queries from A as follows.(i)
h(in) queries: if there is no tuple (in,out) in L, randomly select an element out∈{0,1}k and add (in,out) to L list. Then send out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates a new session of A¯ with intended partner B¯, S randomly selects rA,e1←DZn,αq and sends RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1Π,R,B¯,A¯,RA: S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to the protocol. At last, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA by using rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA once session key of sid has been generated.(vi)
Corrupt(A¯): return the static secret key sA of Alice to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1}, and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session skA of sid.
Analysis of
G
3,0. In this game, S randomly chooses A∗,B∗←{1,…,N} and sB∗←{1,…,m} without A’s view. Thus, the probability that S will not abort in G3,0 is at least 1/m·N2.
G
a
m
e
G
3,1. S acts identically as in G3,0 except for the following cases.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If A¯≠A∗, S responds to queries as in GameG3,0. Else, S computes RA′=MrA′+2e1′modq_, where rA′,e1′←DZn,αq. Then, it randomly selects c←DZ,αq, computes RA=RA′-c·pAmodq_, and sends RA to A.
(ii)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If B¯≠B∗, S responds to the query as in GameG3,0. Otherwise, S computes RB′=rB′tM+2e2′tmodq_, where rB′,e2′←DZn,αq. Then, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_ and kB=rB′t·pA+rB′t·RAmodq_:(34)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
At last, it computesωB,skB according to the protocol and sends (yB,ωB) to A.
(iii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If A≠A∗, S responds to query as in GameG3,0. Else, it chooses randomly c←DZ,αq, let RA=RA′-pAcmodq for RA′=MrA′+2e1′modq; S computes kA=(pB+RB)·rA′modq_. Finally, S computes skA according to the protocol.
Analysis of
G
3,1. Let F3,l be the event that A outputs a guess b′=b in GameG3,l, l=2,3,4,5,6. Similar to theAnalysis ofG1,1, under HNF-LWEq,n,α assumption, we have (35)PrF3,1=PrF3,0-negln.
G
a
m
e
G
3,2. S acts identically as in G3,1, except it replaces the public key for the party A∗ with a uniformly chosen pA∗←Zqn_.
Analysis of
G
3,2. Similar toAnalysis ofG2,3 or G1,1, under HNF-LWEq,n,α assumption, then (36)PrF3,2=PrF3,1-negln.
G
a
m
e
G
3,3. S first computes RB′=rB′tM+2e2′tmodq_, where it randomly chooses rB′,e2′←DZn,αq. Then it acts identically as in G3,2 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
A
¯
,
B
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of B∗, S responds to the query as in GameG3,2. Else, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_ and kB=rB′t·pA+rB′t·RA_, where rB′←DZn,αq. At last, it computes skB,ωB according to the protocol and returns (RB,ωB) to A.(37)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+2rB′teA+2rB′t·e1modq.
Analysis of
G
3,3. Similar to Analysis of G1,1, under LWEq,n,α assumption, then (38)PrF3,3=PrF3,2-negln.
G
a
m
e
s
G
3,4. S first computes h1=rB′tM+2e~2′t,h2=rB′tpA, where rB′,e~2′←DZn,αq. Then it computes RB′=h1+2e2′t=rB′tM+2(e~2′t+e2′t) (or set RB′=h1), where e2′←DZn,α,q. Finally, it acts identically as in G3,3 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of party B∗, S responds to queries as in GameG3,3. Otherwise, S randomly selects c←DZ,α,q, and computes RB=RB′-d·pBmodq_, (39)kB=ch2+rB′tRA=crBtMsA+rB′tMrA+2drB′teA+rB′te1modq._
At last, it computesωB, skB according to the protocol and returns (RB,ωB) to A.
Analysis of
G
3,4. Similar to Analysis of G1,1, under LWEq,n,α assumption, then (40)PrF3,4=PrF3,3-negln.
G
a
m
e
G
3,5. S acts identically as in G3,4 apart from the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗ − th session of B∗, S responds to the query as in GameG3,4. Otherwise, S randomly selects d←DZ,α,q and computes RB=RB′-d·pBmodq. Then, it randomly selects kB←Zq_ and computes ωB,σB as described in protocol. If A has made a h query h(A¯,B¯,RA,RB,ωB,σB), S stops. Otherwise, it randomly selects skB←{0,1}k_ and sets h(A¯,B¯,RA,RB,ωB,σB)=skB. At last, it returns (RB,ωB) to A.
Analysis of
G
3,5. The only difference between G3,4 and G3,5 is that S replace the real key kB=ch2+rB′tRA=crBtMsA+rB′tMrA+2(crB′teA+rB′te1)modq in Game G3,4 with a randomly chosen kB∈Zq in Game G3,5. Since h is a random oracle, the only difference cannot affect A’s view until it makes a h query with σB derived from kB. Denote Q3,l for l=4,5,6 as the event where A makes a h query with σB derived from kB.
Now, we prove(41)PrQ3,4=PrQ3,5PrF3,4∣¬Q3,4=PrF3,5∣¬Q3,5=12+negln.
Becauseh is a random oracle, Q3,4 is independent from (skB)’s distribution. No matter whether or not A gets skA, Pr[Q3,4] is identical; Pr[Q3,5] is so. Besides, if Q3,l for l=4,5 does not happen, G3,5 is actually identical as G3,4 in adversary view. In particular, (skB)’s distribution is random and uniform over {0,1}k; namely, the advantage of A guessing b is negligible if Q3,5 does not happen. This completes the proof.
Likewise, letsid∗=(Π,R,B∗,A∗,RA,(RB,ωB)) be the test session. By assumption that A is a TypeThree adversary, namely, RA is not output by party A∗, given h1=rB′tM+2e~2′t,h2=rB′tpA in G3,5, denote kB=ch2+rB′tRA (which is the same as in G3,4), where c←DZ,α,q. By our assumption, A will make a h query with σB derived from kB with probability at least Pr[Q3,5].
Now, fixingh1,h2,rB′ which are all chosen by S and are independent from the adversary’s actions, S sets c~≠c by randomly choosing c~←DZ,α,q, and sets kB′=c~h+rB′tRA=kB+(c~-c)h2. By Lemma 1, A will utilize RA in the test session and makes a h query with σB′ derived from kB′ with probability at least P[Q3,5]·2-n. Denote d-Q3,l as an event for l=5,6; A in GameG3,l will make σB,σB′ in A’s two runs, where σB is derived from kB in A’s first run and σB′ is derived from kB′=kB+(c~-c)h2 in A’s second run. In particular, Pr[d-Q3,5]≥P[Q3,5]·2-n.
G
a
m
e
G
3,6. S randomly chooses h1←Zqn,h2←Zq_ and acts identically as in GameG3,5.
Analysis of
G
3,6. On the one hand, the difference between G3,5 and G3,6 is that S replaces h1=rB′tM+2e~2′t,h2=rB′tpA with randomly chosen elements in Zqn,Zq, respectively; an adversary that distinguishes the difference between G3,5 and G3,6 could solve the HNF-LWEq,n,α problem. Under the HNF-LWEq,n,α assumption, GameG3,6 is computationally indistinguishable from GameG3,5. In particular, (42)Prd-G3,6=Prd-G3,5-negln.
On the other hand, inGameG3,6, S does not really compute kB and kB′ ( it cannot compute them since h1 is randomly chosen from Zqn and h2 is randomly chosen from Zq). Suppose that kB and kB′ (e.g., the values determined before) are as A’s target values. kB′=kB+(c~-c)h2 especially holds, since A cannot distinguish GameG3,6 from G3,5 as mentioned above. Since h2 is uniformly distributed over Zq and independent from A’s view (thus is independent from kB and kB′), then σB′=mod⁡2(kB′,ωB′) is statistically close to uniform over {0,1} even when conditioned on σB=mod⁡2(kB,ωB) by Lemma 4 ((c~-c) is in invertible with overwhelming probability). Thus, the probability that A will make a h query with σB′ is at most 2-n+negl(n). Namely, Pr(d-G3,6)≤2-n+negl(n) which is negligible in n. As a result, Pr[d-G3,6]=negl(n).
Generally speaking, byAnalysis ofG3,6, Pr[d-Q3,5]=negl(n), which implies that Pr[Q3,5]=negl(n) by the condition that Pr[d-Q3,5]≥Pr[Q3,5]·2-n. Combining this withAnalysis ofG3,5, we get Pr[F3,4]=1/2+negl(n). A simple computation shows that Pr[F3,0]=1/2+negl(n). The proof is completed.


## 4.2.2. Type Four Adversary

Theorem 8.
IfHNF-LWEq,n,α is hard, the proposed AKE is secure against any PPT Type Four adversary A under the BR model.Proof.
We prove it by a series of GameG4,l for 0≤l≤4.
G
a
m
e
G
4,0. S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{0,…,m} and hopes that the adversary will select sid∗=(Π,R,B∗,A∗,RA∗,(RB∗,ωB∗)) as the test session, where RA∗ is output by the sA∗th session of party A∗, (RB∗,ωB∗) is output by the sB∗th session of party B∗ activated by Send1(Π,R,B∗,A∗,RA∗). Then, S randomly selects M←Zqn×n, generates static public keys for all parties (by randomly choosing sA,eA←DZn,αq), and simulates security game for A. In particular, S preserves one table L for random oracle h, and responds the queries from A in the following.(i)
h(in) queries: if there is no tuple (in,out) in L, randomly select an element out∈{0,1}k and add (in,out) to L list. Then send out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates a session of A¯ with intended partner B¯; S randomly selects rA,e1←DZn,αq and sends RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1(Π,R,B¯,A¯,RA): S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to protocol. At last, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA with rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA if session key of sid has been generated.(vi)
Corrupt(A¯): send the static secret key sA of Alice to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1}, and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session key skA of sid.
Analysis of
G
4,0. In this game, S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{1,…,m} independent from A’s view. Thus, the probability that S will not stop in G4,0 is at least 1/m2·N2.
LetF4,l be the event that A outputs a guess b′=b in GameG4,l,l=1,2,3,4.
G
a
m
e
G
4,1. S first computes RB′=rB′tM+2e2′modq_, where rB′,e2′←DZn,αq. Then, it acts identically as in G4,0 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of B∗, S responds to the query as in GameG4,0. Otherwise, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_. Then, S also computes kB=rB′t·pA+rB′t·RAmodq_:(43)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
Finally, it honestly computesωB,skB following the protocol and returns (yB,ωB) to A.
Analysis of
G
4,1. Similar toAnalysis ofG1,1, under HNF-LWEq,n,α assumption, we have (44)PrF4,1=PrF4,0-negln.
G
a
m
e
G
4,2. S first computes RA′=MrA′+2e1′modq_, where rA′,e1′←DZn,αq. Then, S acts identically as in G4,1, apart from the following cases.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to the query as in GameG4,1. Else, it randomly selects c←DZ,αq, computes RA=RA′-c·pAmodq_, and sends RA to A.
(ii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to queries as in GameG4,1. Otherwise, (RB,ωB) is output by the sB∗th session of party B∗. Let skB be the session key of session sid=(Π,R,B¯,A¯,RA,(RB,ωB)); S sets skA=skB_. Otherwise, it computes kA=pB+RB·rA′modq_. At last, S computes skA according to the protocol.
Analysis of
G
4,2. Similar toAnalysis ofG1,2, under HNF-LWEq,n,α assumption, we have (45)PrF4,2=PrF4,1-negln.
G
a
m
e
G
4,3. S first randomly selects RA′←Zqn_. Then it acts identically as in G4,2 except in the following cases.
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, or (RB,ωB) is output by the sB∗th session of party B∗, S answers the query as in GameG4,2. Else, it randomly selects skA←{0,1}k_ as the session key.
Analysis of
G
4,3. Denote Q4,l as the event where in GameG4,l for l=2,3,4, A makes a h query with σA for the sA∗th session of party A∗, when (RB,ωB′) is output by the sB∗th session of party B∗ but ωB≠ωB′.
Similar toAnalysis ofG1,3, under HNF-LWEq,n,α assumption, we have (46)PrQ4,3=PrQ4,2-neglnPrF4,3∣¬Q4,3=Pr⁡F4,2∣¬Q4,2-negln.
G
a
m
e
G
4,4. S randomly selects RB′←Zqn_ and acts almost identically in G4,3 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗th session of B∗, S responds to the query as in GameG4,3. Otherwise, S randomly chooses d←DZ,α,q and computes RB=RB′-d·pBmodq_. Then S randomly selects kB←Zq_ and computes ωB,σB as described in protocol. If A has made a h query h(A¯,B¯,RA,RB,ωB,σB), S stops. Else, it randomly selects skB←{0,1}k_ and sets h(A¯,B¯,RA,RB,ωB,σB)=skB. Finally, it sends (RB,ωB) to A.
Analysis of
G
4,4. Similar toAnalysis ofG1,4, under HNF-LWEq,n,α assumption, G4,3 and G4,4 are computationally indistinguishable. In particular, Pr[Q4,4]=Pr[Q4,3] and PrF4,4∣¬Q4,4=Pr⁡[F4,3∣¬Q4,3]-negl(n).
Similar toAnalysis ofG1,4 about Pr[Q1,4]=negl(n), under HNF-LWEq,n,α assumption, we have Pr[Q4,4]=negl(n).
Similar toAnalysis ofG1,4 about PrF1,4∣¬Q1,4=1/2+negl(n), we get PrF4,4∣¬Q4,4=1/2+negl(n).
In summary,Pr[F4,0]=Pr[F4,2]+negl(n) byAnalysis ofG4,1 and G4,2. ByAnalysis ofG4,4, (47)Pr⁡Q4,3=Pr⁡Q4,4=neglnPr⁡F4,3=Pr⁡F4,4+negln. Since (48)PrF4,3=Pr⁡F4,3∣Q4,3PrQ4,3+PrF4,3∣¬Q4,31-PrQ4,3,thus (49)PrF4,3=PrF4,3∣¬Q4,3-negln.Combining this withAnalysis ofG4,3 and G4,4, then (50)PrF4,0=PrF4,2+negln=12+negln.
This finishes the proof.


## 4.2.3. Type Five Adversary

Theorem 9.
IfHNF-LWEq,n,α is hard, the proposed AKE is secure against any PPT Type Five adversary A under the BR model.Proof.
We prove the theorem by a series of GamesG5,l for 0≤l≤4.
Game
G
5,0. S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{0,…,m}, and hopes that the adversary will select sid∗=(Π,R,B∗,A∗,RA∗,(RB∗,ωB∗)) as the test session, where RA∗ is output by the sA∗th session of party B∗ and (RB∗,ωB∗) is output by the sB∗th session of party B∗ activated by Send1(Π,R,B∗,A∗,RA∗). Then, S randomly selects M←Zqn×n, honestly generates static public keys for all parties (by randomly choosing sA,eA←DZn,αq), and simulates security game for A. In particular, S preserves one table L for random oracle h and responds to queries from A in the following.(i)
h(in) queries: if there is no tuple (in,out) in L, randomly select an element out∈{0,1}k and add (in,out) to L list. Then send out to A.(ii)
Send0(Π,I,A¯,B¯): A initiates a session of A¯ with intended partner B¯; S randomly selects rA,e1←DZn,αq and returns RA=MrA+2e1modq∈Zqn to A on behalf of Alice (A¯).(iii)
Send1Π,R,B¯,A¯,RA: S randomly selects rB,e2←DZn,αq and computes RB=rBtM+2e2tmodq∈Zqn, kB,ωB, and skB according to the protocol. At last, send (RB,ωB) to A on behalf of Bob.(iv)
Send2(Π,I,A¯,B¯,RA,(RB,ωB)): S computes kA,skA by using rA,sA according to the protocol.(v)
SessionKeyReveal(sid): let sid=(Π,∗,A¯,∗,∗,∗,∗); S returns skA if session key of sid has been generated.(vi)
Corrupt(A¯): send Alice’s static secret key sA to A.(vii)
Test(sid): let sid=(Π,I,A¯,B¯,RA,(RB,ωB)); if (A¯,B¯)≠(A∗,B∗), or RA and RB are not output by the sA∗th session of A∗ and the sB∗th session of B∗, respectively, S stops. Otherwise, S randomly selects b←{0,1}, and skA′←{0,1}k. If b=0, S returns skA′; else it returns the real session key skA of sid.
Analysis of
G
5,0. In this game, S randomly selects A∗,B∗←{1,…,N} and sA∗,sB∗←{1,…,m} independent from A’s view. Thus, the probability that S will not stop in G5,0 is at least 1/m2·N2.
Game
G
5,1. S first computes RB′=rB′tM+2e2′modq_, where rB′,e2′←DZn,αq. Then, it acts identically as in G5,0 except for the following cases.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗), or it is not the sB∗th session of B∗, S responds to queries as in GameG5,0. Else, S randomly selects d←DZ,αq and computes RB=RB′-d·pBmodq_, kB=rB′t·pA+rB′t·RAmodq_:(51)kB=rB′t·pA+rB′t·RA=rB′t·MsA+2eA+rB′t·MrA+2e1=rB′t·MsA+rB′t·MrA+rB′t·2eA+2rB′t·e1modq.
Finally, it honestly computesωB,skB according to the protocol and sends (yB,ωB) to A.
LetF5,l be the event that A outputs a guess b′=b in GameG5,l for l=1,2,3,4.
Analysis of
G
5,1. Similar toAnalysis of  G1,1, under HNF-LWEq,n,α assumption, then (52)PrF5,1=PrF5,0-negln.
G
a
m
e
G
5,2. S first computes RA′=MrA′+2e1′modq_, where rA′,e1′←DZn,αq. Then, S acts identically as in G5,1 apart from the following cases.
(i)
S
e
n
d
0
(
Π
,
I
,
A
¯
,
B
¯
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds as in GameG5,1. Else, it randomly selects c←DZ,αq, computes RA=RA′-c·pAmodq_, and sends RA to A.
(ii)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, S responds to queries as in GameG5,1. Otherwise, (RB,ωB) is output by the sB∗th session of party B∗; let skB be the session key of session sid=(Π,R,B¯,A¯,RA,(RB,ωB)); S sets skA=skB_. Otherwise, it computes kA=(pB+RB)·rA′modq_. At last, S computes skA according to the protocol.
Analysis of
G
5,2. Similar toAnalysis ofG1,2, under HNF-LWEq,n,α assumption, we have (53)PrF5,2=PrF5,1-negln.
G
a
m
e
G
5,3. S first randomly chooses RA′←Zqn_. Then it acts identically as in G5,2 with the following exceptions.
(i)
S
e
n
d
2
(
Π
,
I
,
A
¯
,
B
¯
,
R
A
,
(
R
B
,
ω
B
)
). If (A¯,B¯)≠(A∗,B∗), or it is not the sA∗th session of A∗, or (RB,ωB) is output by the sB∗th session of party B∗, S responds to query as in GameG5,2. Else, it randomly selects skA←{0,1}k_ as the session key.
Analysis of
G
5,3. Similar to Analysis of G2,4, G2,5, and G2,6, under LWEq,n,α assumption, we have (54)PrF5,3=PrF5,2-negln.
G
a
m
e
G
5,4. S randomly selects RB′←Zqn_ and acts identically in G5,3 with the following exceptions.
(i)
S
e
n
d
1
(
Π
,
R
,
B
¯
,
A
¯
,
R
A
). If (A¯,B¯)≠(A∗,B∗) or it is not the sB∗th session of B∗, S responds to the query as in GameG5,3. Otherwise, S randomly chooses d←DZ,α,q and computes RB=RB′-d·pBmodq_. Then S randomly selects kB←Zq_ and computes ωB,σB as described in protocol. If A has made a h query h(A¯,B¯,RA,RB,ωB,σB), S stops. Otherwise, it randomly selects skB←{0,1}k_ and sets h(A¯,B¯,RA,RB,ωB,σB)=skB. At last, it returns (RB,ωB) to A.
Analysis of
G
5,4. Similar toAnalysis ofG1,4, under HNF-LWEq,n,α assumption, we have Pr[F5,4]=Pr[F5,3]-negl(n).
Similar toAnalysis ofG1,4 about Pr[F1,4]=1/2+negl(n), under HNF-LWEq,n,α assumption, we have (55)PrF5,4∣¬Q5,4=12+negln.
In summary,Pr[F5,0]=Pr[F5,2]+negl(n) byAnalysis ofG5,1 and G5,2. ByAnalysis ofG5,4, Pr[F5,3]=Pr[F5,4]+negl(n). Combining this withAnalysis ofG5,3 and G5,4, we have (56)PrF5,0=PrF5,2+negln=12+negln.
This completes the proof.


## 5. Comparison of Performance and Security

At present, there is a handful of results on lattice-based AKE under the BR model. Table1 compares our protocol with other AKEs in terms of computational complexity and security. For simplicity, Comp. means computation methods. “E” denotes the exponentiation. “0” means matrix-vector multiplication, not exponentiation operation. Sec. stands for security level. For example, CCA+ means CCA security with high min-entropy keys [27]. Denote by ∘ no security level. Model means security model. For example, CK+ [5] denotes modified CK security model [4]. ACCE means authenticated and confidential channel establishment [18]. Rom means random oracle model. × denotes no Rom. Assum. denotes underlying hardness assumptions. GDH stands for gap Diffie-Hellman assumptions. Qua. denotes quantum attack. Yes means resisting quantum attack; No means suffering quantum attack.Table 1
Comparison between previous AKEs and our proposed AKE.
AKE
Comp.
Sec.
Model
Rom
Assum.
Qua.
NAXOS [7]
4
E
∘
eCK, wPFS
Rom
GDH
No
CMQV [34]
3
E
∘
eCK, wPFS
Rom
GDH
No
HMQV [5]
3
E
∘
CK+, wPFS
Rom
GDH
No
FSX [26]
0
OW-CCA
CK+
Rom
RLWE
Yes
FSXY [27]
0
CCA+
CK+
×
(R-)LWE
Yes
BCN [18]
0
CPA
ACCE
Rom
RLWE
Yes
Ours
0
∘
BR, wPFS
Rom
LWE
YesNote that NAXOS [7], CMQV [34], and HMQV [5] referred to exponentiation computation and achieve AKE security with wPFS in GDH assumption which indicated that they were vulnerable to quantum attack although they are secure in stronger model. Compared with NAXOS [7], CMQV [34], and HMQV [5] based on GDH assumption, our protocol has much more advantages in terms of computation because our protocol grasps matrix-vector multiplication besides resistance to quantum attack. In terms of Sec., [18, 26, 27] captured OW-CCA, CCA+, and CPA security without wPFS. But ours achieves security and wPFS without authentication tools under the BR model.The new protocol has a good balance between computation and security.


## 6. Conclusion

This paper first proposes an AKE from the LWE problem. The AKE is simple since it does not involve any other cryptographic primitives (e.g., MAC, signature) to achieve authentication and depends on solely the LWE problem in the worst-case (e.g., SVP and SIVP [12–14]). Security analysis with wPFS is proved to resist five kinds of adversaries under the BR model and it might be appealing in specific applications.This paper also motivates interesting open problems, such as an attack on it, converting it to one AKE under the CK model. If our lattice-based AKE is improved, it may achieve CPA and CCA security with wPFS, PFS, KCI, and so on under the CK, eCK, andCK+ model. Maybe there exists a SFA on our protocol. We do not study them here and leave them as the future works.



---

*Source: 1740572-2017-04-19.xml*