Provably Secure Two-Round PAKE Based on Ciphertext Standard Language over Lattices

YIN An-qi; QU Tong-zhou; GUO Yuan-bo; WANG Ding; CHEN Lin; LI Yong-fei

doi:10.12263/DZXB.20210517

PDF(911 KB)

ACTA ELECTRONICA SINICA ›› 2022, Vol. 50 ›› Issue (5) : 1140-1149. DOI: 10.12263/DZXB.20210517

PAPERS

Provably Secure Two-Round PAKE Based on Ciphertext Standard Language over Lattices

Author information +

History +

HeighLight

Reducing the communication round complexity and security assumptions are important directions of password-based authenticated key exchange(PAKE) protocol over lattices. Smooth projective Hash function(SPHF) is an important mathematical tool for constructing PAKE. But most of the existing lattice-based SPHFs cannot be applied under hyperpolynomial modulus. This paper proposes two SPHFs based on the standard language of ciphertext over lattices, which solves the above problem without increasing communication and storage overhead. Based on the proposed SPHFs, this paper proposes a provably secure two-round PAKE protocol over lattices, which can resist quantum attacks and reduce the communication round complexity and the security assumptions without random oracle and zero-knowledge proof. And this paper also provides a strict security proof for the proposed protocol based on a more accurate security model. Experiment results show that the protocol proposed has better communication round complexity, computational overhead, security assumptions and actual security.

Key words

password / key exchange / SPHF(Smooth Projective Hash Function) / provably secure / lattice / post-quantum

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

YIN An-qi , QU Tong-zhou , GUO Yuan-bo , WANG Ding , CHEN Lin , LI Yong-fei. Provably Secure Two-Round PAKE Based on Ciphertext Standard Language over Lattices[J]. ACTA ELECTONICA SINICA, 2022, 50(5): 1140-1149. https://doi.org/10.12263/DZXB.20210517

1 引言

口令认证密钥交换协议可使只拥有低熵口令的协议参与方，在不安全的公开网络上，协商密码学安全的会话密钥^［1］.现有PAKE的研究多是基于传统困难问题的^［2~5］；Shor算法^［6］证明，存在量子算法可以解密所有基于大整数分解或离散对数的公钥密码体制；因此上述PAKE无法抵抗量子攻击.而基于格的密码体制可有效抵抗量子攻击；与其他抗量子密码体制（多变量公钥密码体制、基于Hash函数的数字签名方案、基于编码的密码体制）相比，其在计算效率^［7］、困难实例随机选取^［8］等方面具有显著优势，但关于其的研究却相对有限.

平滑投射哈希函数是构造PAKE的重要数学工具.现有SPHF一般是基于非标准密文语言的，不能在超多项式模数下应用^［9］.文献［10］提出了一种支持一轮PAKE协议构造的适应性SPHF；但并不能解决上述问题.文献［11］提出了一种基于密文标准语言的SPHF，但其所基于的公钥加密（Public Key Encryption，PKE）方案计算效率较低，且该文未对相关协议进行安全性证明.

KOY/GL^［3，12］和JG/GK^［4，5］架构是目前应用最广泛的PAKE协议架构，但都需要三轮通信.文献［1］率先提出了格上的两轮PAKE；文献［13］则利用可拆分函数，提出了一种可实现互认证的两轮PAKE；但二者均是基于随机预言机的，且前者还需要基于可靠性模拟的非交互式零知识（Simulation-Sound Non-Interactive Zero- Knowledge，SS-NIZK）证明，计算效率较低.文献［14］提出了第一个格上不需要SS-NIZK的两轮PAKE，但也是基于非标准密文语言的.

KOY/GL架构下的协议需要适应性选择密文攻击下不可区分（INDistinguishability under Adaptive Chosen-Ciphertext Attack，IND-CCA2）的安全性假设，这导致协议计算效率较低，存储开销较大.文献［15］优化了PAKE的密文长度，但仍需要IND-CCA2的安全性假设.JG/GK架构下的协议在客户端仅需要选择明文攻击下不可区分（INDistinguishability under Chosen-Plaintext Attack，IND-CPA）的安全性假设，但此类协议仍需要三轮通信.目前格上的二轮^［1，16］、一轮^［2，10］PAKE在服务器和客户端一般都需要IND-CCA2安全的加密方案.虽然文献［14］提出的两轮协议降低了服务器端的安全性假设，但本文指出了其协议设计中的一个错误.

因此，研究格上基于密文标准语言的平滑投射哈希函数，是解决格上SPHF不能在超多项式模数下应用的有效方法；而降低格上PAKE协议的通信轮次和安全性假设则对降低PAKE协议的通信开销、计算开销以及提高协议的实际安全性具有重要意义．为此，本文提出了两种格上基于密文标准语言的平滑投射哈希函数；并基于此提出了一种格上可证明安全的两轮口令认证密钥交换协议，协议降低了客户端所需的安全性假设；实验结果表明本文具有更优的计算开销、通信开销和安全性假设．

2 预备知识

2.1 符号说明

本文的符号定义见表1.

表1 符号定义

符号	含义
n	安全参数
［ A \| B ］/［ A \|\| B ］	矩阵 A 和 B 的横/纵向级联
negl（.）	可忽略函数
q	LWE困难问题模数
Ham（.， .）	汉明距离函数
A ^T	矩阵 A 的转置矩阵
←/ $\overset{r}{\leftarrow}$	取样/随机取样
\| D \|	集合D的大小
d（.， .）	距离函数（欧式距离）
\|\| x \|\|	向量 x 的欧几里得范数
$⊥$	非法标识
「a⌉/⌊a」	大于/小于a的最小/最大整数
「a」	与a最接近的整数
〈.， .〉	内积运算

2.2 格及格上的加密方案

格^［1］　设

m \geq n

，基矩阵

B \in R^{m \times n}

（ B 的列向量线性无关），m维的格Λ格定义为

Λ_{B} = {B s | s \in Z^{n}}

（1）

高斯离散分布^［9］　设

s > 0

，

y \in R^{m}

，定义

R^{m}

上的高斯权重函数为

ρ_{s, y} (x) : = e x p (- π {|x - y|}^{2} / s^{2})

（2）

设参数为s，中心为 y，格Λ上的离散高斯分布为

D_{Λ, s, y} (x) = {ρ_{s}}_{, y} (x) / {ρ_{s}}_{, y} (Λ)

（3）

其中

x \in Λ

，

{ρ_{s}}_{, y} (Λ) = \sum_{x \in Λ} {ρ_{s}}_{, y} (x)

，此外若 y 为零向量，可将其省略.

带差错学习（Learning With Errors，LWE）问题^［1］令

q \geq 2

，另设

χ

是

Z

上的离散高斯分布.LWE问题的定义为，给定多项式数目的取样，区分以下两个分布：（1）

(a, < a, s > + x)

，

a \overset{r}{\leftarrow} Z_{q}^{n}

，

x \leftarrow χ

，

s \in Z_{q}^{n}

是固定的随机均匀选择的秘密；（2）

(a, b)

，

a \overset{r}{\leftarrow} Z_{q}^{n}

，

b \overset{r}{\leftarrow} Z_{q}

. LWE问题的困难性说明见文献［6］.

格上的公钥加密方案　文献［17］中的GPV方案是格上经典的基于LWE问题的IND-CPA安全的PKE之一，设明文为

p_{0} \in {0, 1}

，其定义如下.

G P V . K e y G e n (p a r a m s)

：私钥

s k_{G P V} = s_{} \overset{r}{\leftarrow} Z_{q}^{n}

，公钥

p k_{G P V} = B_{G P V} = A s + x \in Z_{q}^{n}

，其中

x_{i} \overset{r}{\leftarrow} χ

(i \in [m], χ = {\bar{ψ}}_{α})

G P V . E n c (B_{G P V}, p_{0}; s)

：

y_{} \overset{r}{\leftarrow} D_{Z^{m}, y}

，密文

(u, c_{0})

= ({B_{G P V}}^{T} y, {B_{G P V}}^{T} y + p_{0} \cdot ⌊q / 2⌋) \in Z_{q}^{n + 1}

G P V . D e c (s, (u, c_{0}))

：计算

p_{0}' = c_{0} - s^{T} u

，若

D i s (p_{0}',

0) < D i s (p_{0}', ⌊q / 2⌋) m o d q

，输出0；否则，输出1.

文献［9］中的KV方案是格上最广泛应用的IND-CCA2安全的PKE之一.设

B \in Z_{q}^{m \times n}

，

U = (u_{0}, u_{1}, \dots, u_{l}) \in (Z_{q}^{m \times n} {)^{l}}^{+ 1}

，

x \leftarrow {\bar{ψ}}_{b}^{m} \in Z_{q}^{l}

，

s_{} \overset{r}{\leftarrow} Z_{q}^{n}

，公钥

p k_{K V} = B_{K V} = [B | U] \in Z_{q}^{m \times n}

，标签

l a b e l = U

，明文

p = (p_{1}, p_{2}, \dots, p_{l}) \in Z_{q}^{l}

. KV方案定义如下.

K V . K e y G e n (p a r a m s)

：

(B, T) \leftarrow T r a p S a m p (1^{n}, q, m)

^［18］，输出

B \in Z_{q}^{m \times n}

，

T \in Z_{q}^{m \times m}

K V . E n c^{l a b e l} (B_{K V}, p; s)

：为加密明文

p = (p_{1}, p_{2}, \dots, p_{l}) \in Z_{q}^{l}

，随机选择一个错误向量

x \leftarrow {\bar{ψ}}_{b}^{m} \in Z_{q}^{l}

，计算并输出密文

y = B_{K V}^{T} (\begin{array}{l} s^{T} \\ 1 \\ p^{T} \end{array}) + x \in Z_{q}^{m}

（4）

K V . D e c^{l a b e l} (T, c)

：

(s, 1, p) \leftarrow B B D s o l v e (T, c, U)

^［17］，输出 p .

为简化说明，下文以IND-CPA安全的方案为例构造格上的SPHF，基于IND-CCA2安全的方案构造SPHF的方法与其相同.

2.3 平滑投射哈希函数

近似平滑投射哈希函数（Approximate Smooth Projective Hash Function，ASPHF）可通过抽样算法定义，抽样算法输出（K， l， H = ｛Hash（params， hk， W ）｝ ^l， S， HashKG： hk

\overset{r}{\leftarrow}

K， ProjKG： K → S）；其中K、S为哈希、投射密钥空间，HashKG为K上的哈希密钥生成函数；ProjKG为K到S上的投射密钥生成函数^［2］.ASPHF满足：

（1）存在高效算法可以计算HashKG、ProjKG和

H a s h (p a r a m s, h k, W)

；

（2）近似正确性：对于

\forall h k \in K

，

\forall W \in L

，

p h \leftarrow P r o j K G (p a r a m s, h k, W)

以及可忽略函数

n e g l (\cdot)

，若存在投射哈希函数ProjHash使式（5）成立，称该ASPHF为

ε - A S P H F

P r (H a m (\begin{array}{l} H a s h (p a r a m s, h k, W), \\ P r o j H a s h (p h, W, w) \end{array}) \geq ε) = n e g l (n)

（5）

（3）平滑性：对于

\forall h k \overset{r}{\leftarrow} K

，

\forall W' \in X - L

，

p h \leftarrow P r o j K G (p a r a m s, h k, W')

和

v \overset{r}{\leftarrow} Y

（Y为Hash函数的值域），式（6）中的两个分布在统计上不可区分.

\{\begin{array}{l} (\begin{array}{l} p h \leftarrow P r o j K G (p a r a m s, h k, W'), \\ h \leftarrow H a s h (p a r a m s, h k, W') \end{array}) (1) \\ (p h \leftarrow P r o j K G (p a r a m s, h k, W'), v) (2) \end{array}

（6）

现介绍证明本文SPHF性质所需的定理.

定理1^［11］对于

A \in Z_{q}^{m \times n}

，

c \in Z_{q}^{m}

，

p \in Z_{q}^{n}

，其中m可以表示成n的多项式函数.对于概率舍入函数

R : Z_{q} \to {0, 1}

，满足对于

\forall x \in Z_{q}

，

p_{r} (x) = P r (R (x) = 1) = \sum_{j} {\hat{p}}_{r} \cdot e_{j / q} (x)

（7）

其中

j \in J

，

J \subset Z_{q}

，

{\hat{p}}_{r} \in C

.对于

ε = n e g l (n)

，令

s \geq η_{ε} (Λ_{A})

.假设

\forall j \in J - {0}, s \cdot d (j c, Λ_{A}) > q \sqrt[]{m}

（8）

令

p (c) = P r (R (h_{i}^{T} \cdot c) = 1 | u_{i} = B^{T} \cdot h_{i})

，在

u_{i} = B^{T} \cdot h

的条件下，

p (c)

由舍入函数R的随机性，以及 h_i 的分布决定.那么

|p (c) - {\hat{r}}_{0}| \leq (2 + O (ε)) |J| C^{m} + O (ε)

（9）

其中

C = {(2 π e)}^{1 / 2} \cdot {e^{-}}^{π} < 1

.此外，现有文献通常直接称ASPHF为SPHF^{［10，13，14］}，下文也如此.

3 PAKE协议的安全模型

通信模型^［19］假设通信在不安全的公开网络上进行，参与方包括客户

u_{1}, u_{2}, \dots \in U

，攻击者（或敌手）

a d_{1}, a d_{2}, \dots \in B

和可信服务器

s_{1}, s_{2}, \dots \in E

设各参与方可与其他参与方（并发地）执行多次协议；称一次协议的执行为一个实例（如

Π_{u_{1}}^{i}

表示客户u₁的第i个实例）.以实例

Π_{u_{1}}^{i}

为例，其维持本地状态变量

(s i d_{u_{1}}^{i}, p i d_{u_{1}}^{i}, s k_{u_{1}}^{i}, a c c_{u_{1}}^{i}, t e r m_{u_{1}}^{i})

，

s i d_{u_{1}}^{i}

为会话标识，

p i d_{u_{1}}^{i}

表示客体u₁所认为的与其共同参与协议执行的另一参与方的标识；

s k_{u_{1}}^{i}

表示客户u₁所得到的会话密钥；

a c c_{u_{1}}^{i}

是标识实例

Π_{u_{1}}^{i}

是否被客户u₁接受的布尔变量，

a c c_{u_{1}}^{i} = 1

表示接受；

t e r m_{u_{1}}^{i}

是标识实例

Π_{u_{1}}^{i}

是否被客户u₁拒绝的布尔变量，拒绝用

t e r m_{u_{1}}^{i} = 1

标识.下文中伙伴关系、正确性、新鲜性的定义与BRP模型^［19］保持一致.

攻击者模型攻击者ad₁可在协议执行过程中进行消息的窃听、拦截、注入、篡改等.根据BPR模型^［19］，本文用Execute（u₁， i， s₁， j）预言机、Send（u₁， i， msg）预言机、Reveal（u₁， i）预言机以及Test（u₁， i）预言机建模实例，并用预言机询问建模攻击者的攻击能力.各预言机的具体定义也与BRP模型^［19］保持一致.

攻击者优势^［11］协议的安全性是通过一系列Game定义的：攻击者可以执行一系列上述预言机询问（但只允许执行一次Test询问）；所有Game执行完毕后，攻击者输出猜测比特b'；若

b' = b

，称攻击者攻击成功.本文用Success表示攻击成功事件，ad₁在攻击协议Π时的攻击优势

A d v_{Π, a d_{1}}

为

A d v_{Π, a d_{1}} (n) = 2 P r (S u c c e s s) - 1

（10）

定义1（安全协议）设安全参数为n，口令空间为D，服从CDF-Zipf分布^［20］，另设概率多项式时间（Probabilistic Polynomial Time，PPT）攻击者最多可执行Q（n）次在线攻击，称PAKE协议Π是安全的，如果式（11）成立.

A d v_{Π, a d_{1}} (n) \leq C^{'} \cdot Q {(n)}^{s'} + n e g l (n)

（11）

其中C' = 0.062239，s' = 0.155478.

本文假设口令服从CDF-Zipf分布.根据文献［21］，CDF-Zipf分布下敌手优势的准确性，至少是均匀分布下敌手优势准确性的3~4倍.因此，本文安全协议模型至少比均匀随机模型精确3~4倍.

4 基于密文标准语言的SPHF

4.1 基于KV密文标准语言的SPHF

为解决现有SPHF不能在超多项式模数下应用的问题，本文提出了一种基于KV密文标准语言（standard languages）的SPHF，记作KV-S-SPHF.下面首先定义本文中基于KV密文的标准语言

\begin{array}{l} L_{0} = \{(p, c, u) | \exists s, e_{K V}, c \leftarrow E n c (p k_{K V}, p, u; s, e_{K V})\}, \\ L = \{(p, c, u) | D e c (s k_{K V}, c, u) = p\} \end{array}

（12）

为构造基于KV密文标准语言的SPHF （记作KV-S-SPHF），舍入函数应该满足：除1次谐波外的j（j为奇数）次谐波的权重尽量为0.本文选择的舍入函数及其波形分别如式（13）和图1所示.

图1 舍入函数波形图

Full size|PPT slide

R (x) = 1 / 2 + 1 / 2 c o s (2 π x / q)

（13）

本文构建的基于KV密文标准语言的SPHF（记作KV-S-SPHF）如下：

（1）

h k \leftarrow K V . H a s h K G (p a r a m s)

：随机输入

(h_{1}, \dots, h_{k})

\leftarrow (Z_{q}^{m})^{k}

；输出哈希密钥

h k : = (h_{1}, \dots, h_{k}) \in (Z_{q}^{m})^{k}

（2）

p h \leftarrow K V . P r o j K G (p a r a m s, h k = (h_{1}, \dots, h_{k}),

p k_{K V}

= B_{K V})

：输入

h k = (h_{1}, \dots, h_{k}) \in (Z_{q}^{m})^{k}

，公钥 B_KV；输出

p h : = (u_{1}, \dots, u_{k}) = α (h_{1}, \dots, h_{k})

，其中投射密钥

u_{i} = B_{K V}^{T} \cdot h_{i} (1 \leq i \leq k)

（3）

H \leftarrow K V . H a s h (h k = (h_{1}, \dots, h_{k}), W_{K V} : =

(l a b e l, c, p))

：输入

h k = (h_{1}, \dots, h_{k}) \in (Z_{q}^{m})^{k}

，单词

W_{K V} : = (l a b e l, c, p)

，其中

p \in Z_{q}^{l}

，

c \in Z_{q}^{m}

；哈希函数的计算方式如式（14）所示，其中

R (x) = 1 / 2 + 1 / 2 c o s (2 π x / q)

；输出

H = (b_{1}, \dots, b_{k})

\{\begin{array}{l} z_{i} = H a s h (h k = h_{i}, W_{K V} : = (l a b e l, c, p) \\ = h_{_{i}}^{T} \cdot [c - U \cdot (\begin{array}{l} 1 \\ p \end{array})] (m o d q) \in Z_{q} \\ b_{i} = R (z_{i}) \in {0,1} \end{array}

（14）

（4）

P \leftarrow K V . P r o j H a s h (p h = (u_{1}, \dots, u_{k}), W_{K V} =

(l a b e l, c, p); w = e_{K V})

：输入

p h = (u_{1}, \dots, u_{k})

，

W_{K V} =

(l a b e l, c, p)

和

e_{K V}

；投射函数如式（15）所示；输出

P = (b_{1}',

\dots, b_{k}')

\{\begin{array}{l} z'_{i} = P r o j H a s h (p h = (u_{1}, \dots, u_{k}), \\ W_{K V} : = (l a b e l, c, p); w = e_{K V}) \\ = u_{i}^{T} \cdot e_{K V} (m o d q) \in Z_{q} \\ b'_{i} = R (z'_{i}) \in {0,1} \end{array}

（15）

下面证明KV-S-SPHF满足正确性与平滑性.

证明（1）正确性证明

对于

\forall W_{K V} \in L

，满足

\begin{array}{l} p_{1} = P r (H = P) \\ = P r (\begin{array}{l} K V . H a s h ((h_{1}, \dots, h_{k}), (l a b e l, c, p)) = \\ K V . P r o j H a s h ((u_{1}, \dots, u_{k}), (l a b e l, c, p); e_{K V}) \end{array}) \\ > \frac{1}{2} + Δ \end{array}

（16）

其中，Δ是不可忽略的小数.因为在构建KV-S-SPHF中使用了舍入函数，只要保证式（17）成立即可.

\begin{array}{l} p_{1} = P r (R (h_{_{i}}^{T} [c - U (\begin{array}{l} 1 \\ p \end{array})]) = R (u_{_{i}}^{T} \cdot e_{K V})) \\ > \frac{1}{2} + Δ \end{array}

（17）

进一步，根据式（13）和式（17），可得式（18）.

\begin{array}{l} p_{1} = \frac{1}{q} \sum_{x \in ℤ_{q}} (R (x) R (x + h_{_{i}}^{T} \cdot c) + (1 - R (x)) (1 - R (x + h_{_{i}}^{T} \cdot c))) + n e g l (n) \\ = \frac{1}{2} + \frac{1}{q} \sum_{x \in Z_{q}} \frac{1}{2} c o s (2 π \frac{x}{q}) c o s (2 π \frac{x + h_{_{i}}^{T} \cdot c}{q}) + n e g l (n) \end{array}

（18）

因为

t \cdot s \cdot m = o (q)

，所以有

h_{i}^{T} c = o (q)

（ c 是高斯取样的误差）在统计上成立.余弦函数是Lipschitz连续函数，因此可通过积分来近似求和：

\begin{array}{l} p_{1} = \frac{1}{2} + \frac{1}{2} \int_{0}^{1} c o s^{2} (2 π x) d x + ο (1) \\ = \frac{3}{4} + ο (1) \end{array}

（19）

根据式（16）和式（19）可知，KV-S-SPHF满足近似正确性，根据文献［11］中的正确性放大技术，我们可以得到一个具有统计正确性的KV-S-SPHF.

（2）平滑性证明

本文引入新舍入函数后，只要保证对于

\forall W_{K V} \in X - L

，式（20）中的p₂满足

|p_{2} - 1 / 2| \leq n e g l (n)

，那么就可以保证KV-S-SPHF的平滑性.

\begin{array}{l} p_{2} = P r (R (z_{i} (m o d q)) = 1| u_{i} = B^{T} \cdot h_{i}) \\ = P r (R (h_{_{i}}^{T} \cdot [c - U \cdot (\begin{array}{l} 1 \\ p \end{array})] (m o d q)) = 1 |u_{i} = B^{T} \cdot h_{i}) \end{array}

（20）

令

p_{R} (x) = P r (R (x (m o d q)) = 1)

，那么

p_{R} (x)

是一个以q为周期的周期信号.现对

p_{R} (z_{i})

进行插值处理，得到式（21）.

p_{R} (z_{i}) = \sum_{j \in Z_{q}} {\hat{p}}_{r', j} \cdot e_{j / q} (z_{i})

（21）

其中

{\hat{p}}_{r'} \in C

是

p_{r'} : Z \to [0,1]

的傅里叶系数.令

s \geq η_{ε} (Λ_{A}^{⊥})

，并假设

\forall j \in J - {0}

s \times d (j [c - U (\begin{array}{l} 1 \\ p \end{array})], Λ_{A}) > q \sqrt[]{m}

（22）

根据式（13），有式（23）.

\{\begin{array}{l} {\hat{p}}_{r, 0} = 1 / 2 \\ {\hat{p}}_{r, \pm 1} = 1 / 2 \\ {\hat{p}}_{r, j} = 0 (j \neq 0, \pm 1) \end{array}

（23）

根据定理1及式（19）~（23），对于

\forall W_{K V} \in X - L

，

C = {(2 π e)}^{1 / 2} \cdot {e^{-}}^{π} < 1

，有

|2 p_{2} - 1| \leq 2 (6 + O (ε)) C^{m} + O (ε) \leq n e g l (n)

（24）

综上，KV-S-SPHF是平滑投射哈希函数.

证毕.

4.2 基于GPV密文标准语言的SPHF

本小节研究基于GPV密文标准语言的SPHF，记作GVP-S-SPHF.GPV方案的公共矩阵为 A，公钥为

p k_{G P V} = B_{G P V} = A s + x \in Z_{q}^{m}

，具体方案如下：

（1）

h k \leftarrow G P V . H a s h K G (p a r a m s)

：随机输入

(h_{1},

\dots, h_{k}) \leftarrow (Z_{q}^{m})^{k}

；输出哈希密钥

h k : = (h_{1}, \dots, h_{k}) \in (Z_{q}^{m})^{k}

（2）

p h \leftarrow G P V . P r o j K G (p a r a m s, h k = (h_{1}, \dots, h_{k}),

p k_{K V} =

B_{G P V})

：输入

h k = (h_{1}, \dots, h_{k}) \in (Z_{q}^{m})^{k}

，

p k_{K V} = B_{G P V}

；输出

p h : = (u_{1}, \dots, u_{k}) = α (h_{1}, \dots, h_{k})

，其中投射密钥

u_{i} = B_{G P V}^{T} \cdot h_{i} (1 \leq i \leq k)

（3）

H \leftarrow G P V . H a s h (h k = (h_{1}, \dots, h_{k}), W_{G P V} : =

(c, p))

：输入

h k = (h_{1}, \dots, h_{k}) \in (Z_{q}^{m})^{k}

，单词

W_{G P V} =

(c, p)

，其中

c = (c_{1}, \dots, c_{k}) \in Z_{q}^{k}

；哈希函数的计算方式如式（25）所示，其中

R (x) = 1 / 2 +

1 / 2 c o s (2 π x / q)

；输出

H = (b_{1}, \dots, b_{k})

\{\begin{array}{l} z_{i} = H a s h (h k = h_{i}, W_{G P V} : = (c_{i}, p_{i})) \\ = ‖h_{_{i}}^{T} \cdot [c_{i} - (⌊q / 2⌋ \cdot p_{i})]‖ \\ (m o d q) \in Z_{q} \\ b_{i} = R (z_{i}) \in {0,1} \end{array}

（25）

（4）

P \leftarrow G P V . P r o j H a s h (p h = (u_{1}, \dots, u_{k}), W_{G P V} =

(c, p);

w = e_{G P V})

：输入投射密钥

p h = (u_{1}, \dots, u_{k})

，

W_{G P V} = (c, p)

和

w = e_{G P V}

；其中

p = (p_{1}, \dots, p_{k})

，

c = (c_{1}, \dots, c_{k}) \in Z_{q}^{k}

；投射函数的计算方式如式（26）所示；输出

P = (b_{1}', \dots, b_{k}')

\{\begin{array}{l} z'_{i} = P r o j H a s h (p h = (u_{1}, \dots, u_{k}), \\ W_{G P V} : = (c, p); w = e_{G P V}) \\ = ‖u_{i} \cdot e_{G P V}‖ (m o d q) \in Z_{q} \\ b'_{i} = R (z'_{i}) \in {0,1} \end{array}

（26）

GPV-S-SPHF的正确性与平滑性证明过程与KV-S-SPHF类似，不再赘述.

5 格上可证明安全的两轮PAKE

5.1 两轮协议及正确性分析

基于本文提出的两种平滑投射哈希函数，本节提出了一种格上基于标准安全模型的不需要SS-NIZK的二轮PAKE，如算法1所示.

密码原语　（1） KV方案及KV-S-SPHF；（2） GPV方案及GPV-S-SPHF.

初始化阶段　建立KV和GPV方案的公钥，即公共参考序列（Common Reference String，CRS）.

算法1　格上基于标准安全模型的不需要SS⁃NIZK的二轮PAKE协议
客户u₁（ $p w_{u_{1}}$ ）	$C R S : p k_{K V}, p k_{G P V}$	服务器s₁（ $p w_{s_{1}, u_{1}}$ ）
（1） $h k_{u_{1}} \overset{r}{\leftarrow} G P V . H a s h K G (p a r a m s)$ ， $e_{G P V} \leftarrow D_{Z^{m}, y}$ （2） $p h_{u_{1}} \leftarrow G P V . P r o j K G (p a r a m s, h k_{u_{1}}, p k_{G P V})$ （3） $l a b e l = u_{1} \| \| s_{1} \| \| p h_{u_{1}}$ （4） $(u, c_{u_{1}}) \leftarrow G P V . E n c (p k_{G P V}, p w_{u_{1}}, l a b e l; e_{G P V})$	$\underset{⃗}{u_{1} \| \| c_{u_{1}} \| \| p h_{u_{1}}}$ $\underset{⃖}{s_{1} \| \| c_{s 1} \| \| p h_{s 1}}$
		（1） $h k_{s_{1}} \overset{r}{\leftarrow} K V . H a s h K G (p a r a m s)$ ， $e_{K V} \overset{r}{\leftarrow} (Z_{q})^{n}$ （2） $p h_{s_{1}} \leftarrow K V . P r o j K G (p a r a m s, h k_{s_{1}}, p k_{K V})$ （3） $l a b e l = u_{1} \| \| s_{1} \| \| p h_{u_{1}}$ ， $l a b e l' = u_{1} \| \| s_{1} \| \| p h_{u_{1}} \| \| c_{u_{1}} \| \| p h_{s_{1}}$ （4） $c_{s_{1}} \leftarrow K V . E n c^{l a b e l'} (p k_{K V}, p w_{s_{1}, u_{1}}; e_{K V})$
（5） $l a b e l' = u_{1} \| \| s_{1} \| \| p h_{u_{1}} \| \| c_{u_{1}} \| \| p h_{s_{1}}$ （6） $H_{u_{1}} \leftarrow K V . H a s h (h k_{u_{1}}, W_{K V} : = (l a b e l', c_{s_{1}}, p w_{u_{1}}))$ （7） $P_{u_{1}} \leftarrow G V P . P r o j H a s h (p h_{s_{1}}, W_{G P V} : = (c_{u_{1}}, p w_{u_{1}}); e_{G P V})$ （8） $K_{u_{1}} \leftarrow H_{u_{1}} \cdot P_{u_{1}}$		（5） $H_{s_{1}} \leftarrow G P V . H a s h (h k_{s_{1}}, W_{G P V} : = (c_{u_{1}}, p w_{s_{1}, u_{1}}))$ （6） $P_{s_{1}} \leftarrow K V . P r o j H a s h (p h_{u_{1}}, W_{K V} : = (l a b e l', c_{s_{1}}, p w_{s_{1}, u_{1}}); e_{K V})$ （7） $K_{s_{1}} \leftarrow H_{s_{1}} \cdot P_{s_{1}}$
（9）删除除 $p w_{u_{1}}$ 和 $K_{u_{1}}$ 外所有存储信息		（8）删除除 $p w_{s_{1}}$ 和 $K_{s_{1}}$ 外所有存储信息

协议执行过程　假设协议在客户u₁和服务器s₁之间执行，u₁和s₁共享口令

p w_{u_{1}}

u ₁选择

e_{G P V} \leftarrow D_{Z^{m}, y}

，哈希密钥

h k_{u_{1}} \overset{r}{\leftarrow} G P V .

H a s h K G (p a r a m s)

；计算投射密钥

p h_{u_{1}} \leftarrow G P V . P r o j K G

(p a r a m s,

h k_{u_{1}}, p k_{G P V})

；将己方标签设置为

l a b e l = u_{1} | | s_{1} | | p h_{u_{1}}

；并计算己方密文

(u, c_{u_{1}}) \leftarrow G P V . E n c

(p k_{G P V}, p w_{u_{1}}, l a b e l; e_{G P V})

；最后向s₁发送

u_{1} | | c_{u_{1}} | | p h_{u_{1}}

s ₁收到消息

u_{1} | | c_{u_{1}} | | p h_{u_{1}}

后，选择

e_{K V} \overset{r}{\leftarrow} (Z_{q})^{n}

，哈希密钥

h k_{s_{1}} \overset{r}{\leftarrow} K V . H a s h K G (p a r a m s)

；计算投射密钥

p h_{s_{1}} \leftarrow K V . P r o j K G (p a r a m s, h k_{s_{1}}, p k_{K V})

；设置客户方标签为

l a b e l = u_{1} | | s_{1} | | p h_{u_{1}}

，己方标签为

l a b e l' = u_{1} | | s_{1} | | p h_{u_{1}} | | c_{u_{1}} | | p h_{s_{1}}

；并计算己方密文

c_{s_{1}} \leftarrow K V . E n c^{l a b e l'}

(p k_{K V}, p w_{s_{1}, u_{1}}; e_{K V})

；最后向u₁发送

s_{1} | | c_{s_{1}} | | p h_{s_{1}}

u ₁收到

s_{1} | | c_{s_{1}} | | p h_{s_{1}}

后，计算

H_{u_{1}} \leftarrow K V . H a s h (h k_{u_{1}},

W_{K V} = (l a b e l', c_{s_{1}}, p w_{u_{1}}))

和

P_{u_{1}} \leftarrow G V P . P r o j H a s h (p h_{s_{1}},

(c_{u_{1}}, p w_{u_{1}}); e_{G P V})

；最后计算会话密钥

K_{u_{1}} \leftarrow H_{u_{1}} \cdot P_{u_{1}}

. s₁计算会话密钥的方式与u₁类似，但无需等待u₁收到

s_{1} | | c_{s_{1}} | | p h_{s_{1}}

正确性分析　根据式（27）以及SPHF的平滑性（见式（6）），本文协议满足正确性.

\begin{array}{l} K_{u_{1}} = H_{u_{1}} \cdot P_{u_{1}} \\ = K V . H a s h (h k_{u_{1}}, W_{K V} : = (l a b e l', c_{s_{1}}, p w_{u_{1}})) \cdot \\ G V P . P r o j H a s h (p h_{s_{1}}, W_{G P V} : = (c_{u_{1}}, p w_{u_{1}}); e_{G P V}) \\ = K V . P r o j H a s h (p h_{u_{1}}, W_{K V} : = (l a b e l', c_{s_{1}}, p w_{s_{1}, u_{1}}); \\ e_{K V}) \cdot G P V . H a s h (h k_{s_{1}}, W_{G P V} : = (c_{u_{1}}, p w_{s_{1}, u_{1}})) \\ = P_{s_{1}} \cdot H_{s_{1}} = H_{s_{1}} \cdot P_{s_{1}} = K_{s_{1}} \end{array}

（27）

5.2 安全性证明

本文通过证明定理2，来证明本文PAKE协议是一个安全的PAKE协议.

定理2 如果（1） KV方案是IND-CCA2安全的PKE，且KV-S-SPHF是SPHF；（2） GPV方案是IND-CPA安全的PKE，且GPV-S-SPHF是SPHF；那么算法1中的PAKE是一个安全的PAKE.

假设PPT攻击者（ad₁）对算法1所示的协议进行攻击，本文通过Game0，Game1，Game2，…，来评估攻击者的优势，其中Game0与真实攻击一致.在Gamei中，用Success _i 表示攻击成功事件，ad₁的优势为

A d {v_{a d}}_{_{1}, i} = 2 P r [S u c c e s s_{G a m e i}] - 1

.为方便表述，令

m s g 1 = u_{1} | | c_{u_{1}} | | p h_{u_{1}}

，

m s g 2 = s_{1} | | c_{s_{1}} | | p h_{s_{1}}

.注意模拟器已知参与双方的私有输入，每次Game只对其前一个Game进行修改.

Game1　修改Execute预言机，若

p {w_{u}}_{_{1}} = p {w_{s_{1}, u}}_{_{1}}

，将服务器与用户会话密钥的计算方式替换为

K V . H a s h (h {k_{u}}_{_{1}}, W = (l a b e l', c_{s_{1}}, p {w_{u}}_{_{1}})) \cdot

G P V . H a s h (h k_{s_{1}}, W = ({c_{u}}_{_{1}}, p {w_{s_{1},}}_{u}_{_{1}}))

.下证

|A d v_{a d_{1}, 1} (n) - A d v_{a d_{1}, 0} (n)| \leq n e g l (n)

（28）

证明根据SPHF的正确性，式（28）成立.

证毕.

Game2　修改Execute预言机，用服从Zipf分布的非法口令

p w {'_{u}}_{_{1}}

来生成

{c_{u}}_{_{1}}

.下证

|A d v_{a d_{1}, 2} (n) - A d v_{a d_{1}, 1} (n)| \leq n e g l (n)

（29）

证明构建一个PPT攻击者ad₂攻击GPV方案：给定公钥pk_GPV，ad₂将

(p {w_{u}}_{_{1}}, p w {'_{u}}_{_{1}})

发送给其自己的“挑战”预言机；当收到挑战密文

c {'_{u}}_{_{1}}

后，ad₂用

c {'_{u}}_{_{1}}

构建msg1，并发送给ad₁.

令

E v e n t_{G P V}^{p w_{u_{_{1}}}} (a d_{2})

表示事件：ad₂获得的挑战密文是由真实口令生成的，且ad₂输出1.令

E v e n t_{G P V}^{p w'_{u_{_{1}}}} (a d_{2})

表示事件：ad₂获得的挑战密文是由非法口令生成的，且ad₂输出1.如果ad₁攻击成功（即

b' = b

），那么ad₂输出1；否则ad₂输出0.因此“ad₂获得的挑战密文是由真实口令产生的且输出1”的概率，与ad₁攻击成功的概率是相同的（

P r (E v e n t_{G P V}^{p w_{u_{_{1}}}} (a d_{2}) = 1) = P r (S u c c e s s_{G a m e 1})

）.同理

P r (E v e n t_{G P V}^{p w'_{u_{_{1}}}} (a d_{2}) = 1) = P r (S u c c e s s_{G a m e 2})

.令ad₂攻击GPV的优势为

A d v_{a d_{2}, G P V}^{I N D - C P A} (n)

，那么

\begin{array}{l} |A d v_{a d_{1}, 2} (n) - A d v_{a d_{1}, 1} (n)| \\ = 2 |P r (S u c c e s s_{G a m e 2}) - P r (S u c c e s s_{G a m e 1})| \\ = 2 |P r (E v e n t_{G P V}^{p w_{u_{_{1}}}} (a d_{2}) = 1) - P r (E v e n t_{G P V}^{p w'_{u_{_{1}}}} (a d_{2}) = 1)| \\ = 2 A d v_{a d_{2}, G P V}^{I N D - C P A} (n) \leq n e g l (n) \end{array}

（30）

根据GPV方案的IND-CPA安全性，式（29）成立.

证毕.

Game3　修改Execute预言机，若双方持有相同的口令，用服从Zipf分布的非法口令

p w {'_{s_{1},}}_{u}_{_{1}} = p w {'_{u}}_{_{1}}

来生成 c_s₁.下证

|A d v_{a d_{1}, 3} (n) - A d v_{a d_{1}, 2} (n)| \leq n e g l (n)

（31）

该证明同Game2类似，不再赘述.

Game4　修改Execute预言机，若双方持有相同的口令，将双方的会话密钥替换为相互独立的随机数.下证

|A d v_{a d_{1}, 4} (n) - A d v_{a d_{1}, 3} (n)| \leq n e g l (n)

（32）

证明因为双方都使用非法密钥计算哈希值，所以

(l a b e l', c_{s_{1}}, p {w_{u}}_{_{1}}) \notin L_{K V}

且

({c_{u}}_{_{1}}, p {w_{s_{1},}}_{u}_{_{1}}) \notin L_{G P V}

.根据KV-S-SPHF和GPV-S-SPHF的平滑性，易知式（32）成立.

证毕.

Game5 修改Execute预言机，若

p {w_{s_{1},}}_{u}_{_{1}} \neq p {w_{u}}_{_{1}}

，那么将协议参与双方的会话密钥替换为相互独立的随机数.下证

|A d v_{a d_{1}, 5} (n) - A d v_{a d_{1}, 4} (n)| \leq n e g l (n)

（33）

证明根据KV-S-SPHF和GPV-S-SPHF的平滑性，易知式（33）成立.

证毕.

Game6 修改Execute，若

p {w_{s_{1},}}_{u}_{_{1}} \neq p {w_{u}}_{_{1}}

，那么将

c_{s_{1}}

和

{c_{u}}_{_{1}}

分别替换为相互独立的非法口令

p w {'_{s}}_{_{1}, u_{1}}

和

p w {'_{u}}_{_{1}}

（满足Zipf分布）的加密值.下证

|A d v_{a d_{1}, 6} (n) - A d v_{a d_{1}, 5} (n)| \leq n e g l (n)

（34）

该证明与Game2类似，不再赘述.

在Game6中，对于Execute预言机询问而言，所有的会话密钥以及传输消息都是随机的，与真实口令无关.

下文开始修改Send预言机，并将Send预言机分为以下三种：（1） Send₀（u_i， Start）：攻击者ad₁初始化u_i 与s_j 之间的协议；模拟器向ad₁返回msg1. （2） Send₁（s_j， msg1）：ad₁向s_j 发送msg1，返回给攻击者msg2，并设置s_j 的会话密钥

K_{s_{j}}

. （3） Send₂（u_i， msg2）：ad₁向u_i 发送msg2；该预言机不向ad₁返回任何消息，只是设置u_i 的会话密钥

K_{u_{i}}

本文用sk_KV表示KV方案的私钥，用sk_GPV表示GPV方案的私钥，注意协议执行本身并不需要私钥.

Game7　如果Execute产生的某个msg1与Send₀预言机产生的某msg1发生了碰撞，那么直接宣布ad₁攻击成功.该变化只会增加ad₁的优势，因此

A d {v_{a d}}_{_{1}, 6} (n) \leq A d {v_{a d}}_{_{1}, 7} (n)

Game8　修改Send₁，若msg1是由预言机产生的，那么Game8与Game7保持一致.否则设置

l a b e l = u_{1} | | s_{1} | | p h_{u_{1}}

，并用sk_GPV对

{c_{u}}_{_{1}}

解密得到

p w_{a d}

，此时可能出现以下两种情况：（1）若

p w_{a d} = p {w_{u}}_{_{1}}

，宣布ad₁攻击成功并中止Game；（2）若

p w_{a d} \neq p {w_{u}}_{_{1}}

，随机设置

H_{s_{1}}

以及

{P_{u}}_{_{1}}

.下证

A d v_{a d_{1}, 7} (n) \leq A d v_{a d_{1}, 8} (n) + n e g l (n)

（35）

证明考虑msg1不是由预言机产生的情况：情况（1）只会增加ad₁的优势；根据SPHF的平滑性，情况（2）变化前后，ad₁所观察到分布是统计上不可区分的，所以式（35）成立.

证毕.

Game9　修改Send₂，令mgs1是由预言机产生的，若msg2也是由预言机产生的，那么可能会出现以下两种情况：（1）若u₁和s₁持有相同的口令，令

K_{u_{1}} = K_{s_{1}}

；（2）否则，为u₁随机选择一个会话密钥

K_{u_{1}}

若msg2不是由预言机产生的，设置

l a b e l' = u_{1} | | s_{1} | | p h_{u_{1}} | | c_{u_{1}} | | p h_{s_{1}}

，并根据sk_KV对

c_{s_{1}}

进行解密，此时可能出现另外两种情况：（3）如果

p w_{a d} = p {w_{s_{1}, u}}_{_{1}}

，直接宣布ad₁成功并中止Game；（4）如果

p w_{a d} \neq p {w_{s_{1}, u}}_{_{1}}

，将

H_{s_{1}}

以及

{P_{u}}_{_{1}}

设置为随机数.下证

A d v_{a d_{1}, 8} (n) \leq A d v_{a d_{1}, 9} (n) + n e g l (n)

（36）

证明如果msg1和msg2是由预言机产生的：上述情况（1）与Game8保持一致；对于上述情况（2），根据SPHF的平滑性，该变化只会带来可忽略的攻击者优势的变化；若msg2不是预言机产生的：上述情况（3）只会增加ad₁优势；根据KV-S-SPHF的平滑性，上述情况（4）只会带来可忽略的优势变化.综上，式（36）成立.

证毕.

Game10 修改Send₀预言机，用非法口令

p w {'_{u}}_{_{1}}

生成

{c_{u}}_{_{1}}

.下证

|A d v_{a d_{1}, 10} (n) - A d v_{a d_{1}, 9} (n)| \leq n e g l (n)

（37）

证明方式同Game2，不再赘述.

Game11 修改Send₁预言机，用非法口令

p w {'_{s}}_{_{1}, u_{1}}

生成

c_{s_{1}}

.下证

|A d v_{a d_{1}, 11} (n) - A d v_{a d_{1}, 10} (n)| \leq n e g l (n)

（38）

该证明方法与Game2类似，但ad₂要检测ad₁是否构造了合法的msg1和msg2.因为ad₂只能通其自己的“挑战”预言机判断msg2的合法性，所以该证明依赖于KV方案的IND-CCA2安全性.

下证

A d v_{a d_{1}, 0} (n) \leq C' \cdot Q {(n)}^{s'} + n e g l (n)

证明记攻击者ad₁猜测出正确口令为事件Guess，攻击者ad₁未能猜测出正确口令为事件NGuess，则

\begin{array}{l} P r (S u c c e s s_{G a m e 11}) \\ = P r (S u c c e s s_{G a m e 11} |N G u e s s) \cdot P r (N G u e s s) \\ + P r (S u c c e s s_{G a m e 11} |G u e s s) \cdot P r (G u e s s) \\ \leq P r (S u c c e s s_{G a m e 11} |N G u e s s) \\ + P r (S u c c e s s_{G a m e 11} |G u e s s) \cdot P r (G u e s s) \\ = P r (S u c c e s s_{G a m e 11} |N G u e s s) \\ + (1 - P r (S u c c e s s_{G a m e 11} |N G u e s s)) \cdot P r (G u e s s) \end{array}

（39）

在Game11中，所有的口令都已经被替换为服从Zipf分布的随机数，所以

P r [S u c c e s s_{G a m e 11} | G u e s s] \leq C' \cdot Q {(n)}^{s'} + n e g l (n)

（40）

若攻击者没有猜测出正确口令，那么其只能通过比特猜测取胜，又在Game11中，会话密钥已经替换为随机数，所以

P r [S u c c e s s_{G a m e_{11}} | N G u e s s] = 1 / 2 \pm n e g l (n)

（41）

根据式（10）、式（39）、式（40）和式（41）可知，

\begin{array}{l} A d v_{a d_{1}, 11} (n) = 2 P r [S u c c e s s_{G a m e_{11}}] - 1 \\ \leq 2 (P r [S u c c e s s_{G a m e 11} | N G u e s s] + (1 - \\ P r [S u c c e s s_{G a m e 11} | N G u e s s]) \cdot P r [G u e s s]) \\ \leq C' \cdot Q {(n)}^{s'} + n e g l (n) \end{array}

（42）

又根据式（28）~（38），及式（42）可知

\begin{array}{l} A d v_{a d_{1}, 0} (n) \leq A d v_{a d_{1}, 11} (n) + n e g l (n) \\ \leq C' \cdot Q {(n)}^{s'} + n e g l (n) \end{array}

（43）

综上，定理2成立.

证毕.

6 协议仿真与性能评估

6.1 协议仿真与效率评估

本文在Intel（R）Core（TM）i5-4590平台上对本文提出的协议以及其他相关协议进行仿真.目标平台为单CPU（四核），操作系统为Windows7，内存为8GB，主频为3.3GHz.本文用python语言实现各种密码原语，其执行时间如表2所示，其中Enc代表加密算法.

表2 密码原语执行时间

操作	执行时间	操作	执行时间
MP.Enc	0.310152048399	MP.SPHF	0.00109302669866
Reg.Enc	0.0433926372716	Reg.SPHF	0.00593389340693
KV.Enc	0.873595026517	KV.SPHF	0.444697060174
SPKE.Enc	13.985888249	SPKE.SPHF	0.00112316393037
GPV.Enc	0.1392346325	GPV.SPHF	0.0097478549383

表3给出了不同协议的计算开销.根据表3，本文协议在客户端具有最优的执行效率，这主要是因为本文协议的客户端加密算法以及GPV.SPHF都具有较高的计算效率，且不需要零知识证明.在服务器端，本文协议的密码原语与K-PAKE-1方案相同，但本文协议在不增加计算开销（表3中K-PAKE-1的计算开销不包括签名验签的时间开销）的同时，解决了K-PAKE-1不能在超多项式模数下应用的问题.

表3 协议效率对比

协议名称	客户端	服务器端
Z-PAKE^［1］	13.9870245578	13.987024017
B-PAKE^［11］	14.6049738586	14.6049722413
L-PAKE-1^［14］	0.316085944235	0.0444856664001
L-PAKE-2^［10］	0.311245077527	0.311245077527
K-PAKE-1^［9］	1.02864704845	1.02864758728
本文方案	0.299152334473	1.16812224452

6.2 协议通信与存储开销评估

为评估协议的通信与存储开销，本文假设l = k = 128 bit，n = 256 bit，m = 6400 bit，log q = 12.表4总结了不同协议的通信、存储复杂度及开销.

表4 通信与存储开销对比

协议名称		Z-PAKE^［1］	B-PAKE^［11］	L-PAKE-1^［14］	L-PAKE-2^［10］	K-PAKE-1^［9］	本文方案
通信复杂度		O（2（4m - 2n₁+ kn₁）logq + k）	O（（8m + 2kn - 4n₁）logq）	O（2（m + kn）logq）	O（2（m + kn）logq）	O（（3mn + 2kn）logq + k）	O（（（mn + 1）+ k（n + 1））logq）
通信开销		1001600	1394688	940032	940032	59769984	20055552
存储复杂度	客户	O（（2mn + k（m + 2n₁） + 8m - 3n₁ + n₂ + 1）logq + 5k）	O（（2mn + k（m + 2n）+ 9m + 3n - 4n₁）logq + k）	O（（mn + k（m + 2n）+ 2m + 3n + 1）logq + 3k）	O（（mn + k（m + 2n）+ 3m + 2n）logq + 3k）	O（（mn（3k + 2n + 6）+ n （2k + 1））logq + 5k）	O（（mn + 2m + 2n + 1 +（m + n + 1）k）logq + 3k）
存储复杂度	服务器	O（（2mn + k（m + 2n₁） + 8m - 3n₁ + n₂ + 1）logq + 5k）	O（（2mn + k（m + 2n）+ 9m + 3n - 4n₁）logq + k）	O（（mn + k（m + 2n）+ 3m + 3n + 1）logq + 3k）	O（（mn + k（m + 2n）+ 3m + 2n）logq + 3k）	O（（mn（3k + 2n + 6）+ n （2k + 1））logq + 5k）	O（（mn（2k+2n+4） + 3n + 1 +（n + 1）k）logq + 3k）
存储开销	客户	50157184	50633088	30440844	30514560	17734832768	30046092
存储开销	服务器	50157184	50633088	30517644	30514560	17734832768	15178541964

本文协议在客户端具有最低的存储开销，这得益于本文的公共参考序列（CRS）及密文长度较短.在服务器端，本文协议与K-PAKE-1协议选用了相同的加密算法，但其存储开销约是本文协议的1.17倍，这主要是因为本文协议在客户端的密文以及投射密钥的长度更低.在通信开销方面，K-PAKE-1协议约是本文协议的2.98倍，这是因为本文协议不需要传递签名公钥及签名，且客户端的密文长度低.此外，本文纠正L-PAKE-1协议设计中的一个错误：在客户端计算 h_C时采用Reg.Hash算法，在服务器端计算 h_S时采用MP.Hash算法，才能保证协议的正确性.

7 总结

本文提出了一种格上基于KV密文标准语言和一种基于GPV密文标准语言的平滑投射哈希函数，解决了基于格的平滑投射哈希函数不能在超多项式模数下应用的问题；且所提出的SPHFs还可以应用在零知识证明、不经意传输和证据加密等领域.在此基础上，本文提出了一种格上可证明安全的两轮PAKE协议，可抵抗量子攻击；不需要基于SS-NIZK，具有较高的计算效率；降低了客户端所需的安全性假设，提高了协议的实际安全性；协议只需要两轮通信，具有更优的通信轮次复杂度，这可以提高协议效率、简化协议设计和安全分析过程.最后，本文基于更准确的标准安全模型对所提出的协议进行了严格的安全性证明，安全性证明不需要随机预言机（基于随机预言机设计协议可能会导致PAKE遭受离线口令猜测攻击）.实验证明，本文协议具有较高的计算效率；且在不增加通信开销和存储开销的前提下解决了协议不能在超多项式模数下应用的问题.

References

Publishing order | Descend order by publishing year | Descend order by cited within

1	ZHANGJ, YUY. Two-round PAKE from approximate SPH and instantiations from lattices[C]//TAKAGI T. Advances in Cryptology-ASIACRYPT2017. Cham, Germany: Springer, 2017: 37-67. Cited in this article [7]

2	KATZJ, VAIKUNTANATHANV. Round-optimal password-based authenticated key exchange[C]//ISHAI Y. Theory of Cryptography Conference. Berlin: Springer, 2011: 293-310. Cited in this article [3]

3	KATZJ, OSTROVSKYR, YUNGM. Efficient password-authenticated key exchange using human-memorable passwords[C]//PFITZMANN B. International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2001: 475-494. Cited in this article [1]

4	JIANGS, GONGG. Password based key exchange with mutual authentication[C]//HANDSCHUH H. International Workshop on Selected Areas in Cryptography. Berlin, Germany: Springer, 2004: 267-279. Cited in this article [1]

5	GROCEA, KATZJ. A new framework for efficient password-based authenticated key exchange[C]//AL-SHAER E S. Proceedings of the 17th ACM Conference on Computer and Communications Security. Chicago, USA: ACM, 2010: 516-525. Cited in this article [2]

6	REGEVO. On lattices, learning with errors, random linear codes, and cryptography[J]. Proceedings of the Annual ACM Symposium on Theory of Computing, 2009, 56(6): 84-93. Cited in this article [2]

7	ATENIESEG, FELICIG, MANCINIL V, et al. Hacking smart machines with smarter ones: how to extract meaningful data from machine learning classifiers[J]. International Journal of Security & Networks, 2015, 10(3): 137-150. Cited in this article [1]

8	BALUJAS, FISCHERI. Learning to attack: adversarial transformation networks[C]//MCILRAITH S. Thirty-Second AAAI Conference on Artificial Intelligence. California, USA: AAAI Press, 2018: 2687-2695. Cited in this article [1]

9	KATZJ, VAIKUNTANATHANV. Smooth projective hashing and password-based authenticated key exchange from lattices[C]//MITSURU M. International Conference on the Theory and Application of Cryptology and Information Security. Berlin, Germany: Springer, 2009: 636- Cited in this article [5]

652

10	LIZ, WANGD. Achieving one-round password-based authenticated key exchange over lattices[J]. IEEE Transactions on Services Computing, 2019, 2019(8): 1-14. Cited in this article [5]

11	BENHAMOUDAF, BLAZYO, LÉOD, et al. Hash proof systems over lattices revisited[C]//ABDALLA M. IACR International Workshop on Public Key Cryptography. Cham, Germany: Springer, 2018: 644-674. Cited in this article [6]

12	GENNAROR, LINDELLY. A framework for password-based authenticated key exchange[J]. ACM Transactions on Information & System Security, 2006, 9(2): 181-234. Cited in this article [1]

13	YINA, GUOY, SONGY, et al. Two-round password-based authenticated key exchange from lattices[J]. Wireless Communications and Mobile Computing, 2020, 2020(17): 1-13. Cited in this article [2]

14	LIZ, WANGD. Two-round PAKE protocol over lattices without NIZK[C]//GUO F. International Conference on Information Security and Cryptology. Cham, Germany: Springer, 2018: 138-159. Cited in this article [5]

15	ZHANGJ, YUY, FANS, et al. Improved lattice-based CCA2-secure PKE in the standard model[J]. Science China Information Sciences, 2020, 63(8): 22-28. Cited in this article [1]

16	于金霞, 廉欢欢, 汤永利, 等. 格上基于口令的三方认证密钥交换协议[J]. 通信学报, 2018, 39(11): 91-101. YUJin-xia, LIANHuan-huan, TANGYong-li, et al. Password-based three-party authenticated key exchange protocol from lattices[J]. Journal on Communications, 2018, 39(11): 91-101. (in Chinese) Cited in this article [1]

17	GENTRYC, PEIKERTC, VAIKUNTANATHANV. Trapdoors for hard lattices and new cryptographic constructions[C]//LADNER R. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. New York, USA: ACM, 2008: 197-206. Cited in this article [2]

18	ALWENJ, PEIKERTC. Generating shorter bases for hard random lattices[J]. Theory of Computing Systems, 2011, 48(3): 535-553. Cited in this article [1]

19	BELLAREM, POINTCHEVALD, ROGAWAYP. Authenticated key exchange secure against dictionary attacks[C]//PRENEEL B. International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2000: 139-155. Cited in this article [4]

20	WANGD, CHENGH, WANGP, et al. Zipf's law in passwords[J]. IEEE Transactions on Information Forensics and Security, 2017, 12(11): 2776-2791. Cited in this article [1]

21	WANGD, WANGP. On the implications of zipf's law in passwords[C]//ASKOXYLAKIS I. European Symposium on Research in Computer Security. Cham, Germany: Springer, 2016: 111-131. Cited in this article [1]

Funding

National Natural Science Foundation of China(61501515)

Open Fund of Key Laboratory of Information Assurance Technology(KJ-15-108)

PDF(911 KB)

1503

Accesses

Citation

Detail

Sections

Recommended

Received	Revised	Published
2021-04-21	2021-09-26	2022-05-25
Online First Date	Issue Date
2022-02-09	2022-05-16

Please choose a citation manager

Content to export

HeighLight

Key words

Cite this article

1 引言

2 预备知识

2.1 符号说明

表1 符号定义

2.2 格及格上的加密方案

2.3 平滑投射哈希函数

3 PAKE协议的安全模型

4 基于密文标准语言的SPHF

4.1 基于KV密文标准语言的SPHF

图1 舍入函数波形图

4.2 基于GPV密文标准语言的SPHF

5 格上可证明安全的两轮PAKE

5.1 两轮协议及正确性分析

5.2 安全性证明

6 协议仿真与性能评估

6.1 协议仿真与效率评估

表2 密码原语执行时间

表3 协议效率对比

6.2 协议通信与存储开销评估

表4 通信与存储开销对比

7 总结

{{custom_sec.title}}

{{custom_sec.title}}

References

{{custom_fnGroup.title_en}}

Footnotes

Funding

模态框（Modal）标题

Please choose a citation manager

Content to export

HeighLight

Key words

Cite this article

1 引言

2 预备知识

2.1 符号说明

表1 符号定义

2.2 格及格上的加密方案

2.3 平滑投射哈希函数

3 PAKE协议的安全模型

4 基于密文标准语言的SPHF

4.1 基于KV密文标准语言的SPHF

图1 舍入函数波形图

4.2 基于GPV密文标准语言的SPHF

5 格上可证明安全的两轮PAKE

5.1 两轮协议及正确性分析

5.2 安全性证明

6 协议仿真与性能评估

6.1 协议仿真与效率评估

表2 密码原语执行时间

表3 协议效率对比

6.2 协议通信与存储开销评估

表4 通信与存储开销对比

7 总结

{{custom_sec.title}}

{{custom_sec.title}}

References

{{custom_fnGroup.title_en}}

Footnotes

Funding