Efficient Asymmetric PAKE Compiler from KEM and AE

基于KEM与AE的高效非对称PAKE编译器

You Lyu, Shengli Liu*, Shuai Han

研究目标

非对称口令认证密钥协商协议（aPAKE）是PAKE协议在用户-服务器这一具体场景下的拓展。在aPAKE协议中，服务器仅需存储口令的一个哈希值，无需存储明文口令。即使敌手偷取到了服务器中存储的关于口令的信息，它也必须通过暴力枚举的方式从哈希值里寻找口令。目前针对aPAKE协议的研究多数基于传统的离散对数相关假设，基于格上相关假设的aPAKE协议只有通过利用数字签名方案的编译器来实现，而后量子安全的数字签名方案往往效率较低。我们的研究目标为：设计一个具有后量子高效性的aPAKE协议。

关键问题

在设计aPAKE协议时，我们往往需要实现额外的服务器对用户身份的认证，而这一步往往需要使用签名。在标准化的后量子算法中，数字签名的效率远低于具有对应安全性的密钥封装算法。因此，如何避免使用数字签名，设计一个高效的aPAKE协议，是我们面临的一个关键问题。

研究内容

我们对以下内容进行研究

  1. 设计高效的aPAKE协议，并且能够基于格上的假设导出高效实例化。

  2. 在UC框架下给出安全性证明，给出规约后的安全损失。

技术路线

我们基于密钥封装机制（KEM）和认证加密方案（AE）设计了一个aPAKE编译器。我们的编译器可以将任意的UC安全的PAKE协议，转换成一个UC安全的aPAKE协议。我们给出了KEM与AE所需的安全性质。我们证明了，只要底层的KEM具有OW-PCA安全性，AE具有一次认证性和一次的CCA安全性，那么我们的编译器就是安全的。同时，具有一次认证性和一次CCA安全性的AE可以使用具有信息论意义安全的方案实例化，因此，我们的aPAKE协议的损失依赖于底层OW-PCA安全的KEM方案，以及UC安全的PAKE协议。同时，目前存在具有紧致安全的OW-PCA安全的KEM方案和PAKE协议。因此，我们的编译器也可以得到一个紧致安全的aPAKE协议。

4. 高效通用的aPAKE编译器

研究意义

我们的aPAKE编译器可以实现显示认证，并且只需在底层PAKE协议的基础上额外增加一轮的通信代价。如果使用信息论意义上安全的一次性AE方案和基于格的Kyber作为底层的KEM方案对我们的aPAKE编译器进行实例化，就能得到一个目前最高效的，基于格的aPAKE编译器。与目前已知的所有能够基于格的编译器相比，我们的编译器可以节省61.1%-63.8%的运算时间，以及41.5%-84.3%的通信传输。此外，由于我们的aPAKE编译器是通用构造，如果使用一个在多用户多挑战情况下紧致安全的KEM方案和一个紧致安全的PAKE协议进行实例化，我们就可以得到一个紧致安全的aPAKE协议。通过我们的格上的高效编译器，可以得到目前基于格的最高效的aPAKE协议。