舒 琴，王圣宝，胡 斌，路凡义

(杭州师范大学信息科学与技术学院，浙江 杭州 311121)

0 绪论

口令认证密钥交换(password-based authenticated key exchange，PAKE)协议假设通信实体之间预先共享一个低熵口令(password)，并通过该口令使通信双方或多方在不安全的信道上相互认证并协商出一个可在之后的会话中使用的会话密钥.由于口令便于记忆，具有良好的用户友好性，PAKE协议被广泛研究和部署.

随着量子计算机的发展，理论上，传统基于数论的底层困难问题大多可在多项式时间内被解决[1-3]，因此基于这些困难问题构造的PAKE协议将不再安全，构建后量子PAKE协议迫在眉睫.基于格(lattice)上难题构造的PAKE协议具有较高的渐进效率、可并行计算以及抗量子攻击等优点，因此格上PAKE协议具有非常大的研究价值.

根据协议参与方的数目，可将PAKE协议分为两方PAKE(two-party，2PAKE)协议、三方PAKE协议以及群组PAKE协议.本文主要归纳和总结近年来格上2PAKE协议的研究和发展现状，并着重从安全性和效率两方面对现有协议进行分析与比较.

1 背景知识

1.1 标准格和理想格

格理论最初作为一种密码分析工具被引入到密码学中.格，又称标准格，是线性空间Rn上n个线性无关向量v1,…,vn组成的点的集合，表示为L={a1v1+…+anvn|ai为整数}，其中v1,…,vn被称为格基.

1.2 LWE和RLWE

2005年，Regev[5]提出了带误差学习(learning with errors，LWE)问题，指出求解LWE问题可以规约到求解格上最坏情况困难问题，如最短线性向量无关问题.

定义1(LWE分布)：对于正整数n≥1，q≥2，设为n维q阶整数群，χγ为q上以γ为标准差，0为分布中心，r为半径的高斯离散分布.设固定矩阵s∈为秘密值……