Universal Composable Password Authenticated Key Exchange for the Post-Quantum World
后量子安全的通用可组合口令认证密钥协商协议
You Lyu, Shengli Liu*, Shuai Han
研究目标
口令认证密钥协商协议（PAKE）可以利用交互双方提前共享的低熵口令来协商一个均匀随机的安全密钥。然而，目前的后量子安全的PAKE协议要么无法实现更强的通用可组合（UC）安全性，要么无法在量子随机预言机模型（QROM）下证明协议的安全性。针对上述的研究现状，我们希望能够提出一个在QROM下能够实现UC安全性的PAKE协议。
关键问题
目前已有的PAKE协议十分依赖ROM下的可提取特性和重编程特性，然而这些性质在考虑量子敌手时不一定成立。同时，通用可组合模型也限制了我们在证明时无法使用倒带技术（Rewinding）。因此，如何在QROM下实现UC安全性的证明，是我们面临的一个关键问题。
研究内容
我们对以下内容进行研究
基于格上假设设计PAKE协议，并在ROM下证明其UC安全性
基于同源假设设计PAKE协议，并在ROM下证明其UC安全性
基于格上假设设计PAKE协议，并在QROM下证明其UC安全性
基于同源假设设计PAKE协议，并在QROM下证明其UC安全性
技术路线
我们首先提出了有损公钥加密这一原语，并且给出了所需安全性质的定义。之后，我们在ROM下证明了一个满足安全定义的有损加密方案，和一个具有CCA安全性的PKE方案，可以构造出一个UC安全的PAKE协议。有损公钥加密方案和CCA安全的公钥加密方案既可以通过格上的LWE假设构造，也可以通过同源上的GA-DDH假设构造。因此，我们的通用构造给出了第一个基于同源的UC安全的PAKE协议。此外，为了在QROM下实现UC安全性的证明，我们提出了具有更强安全性质的可提取有损公钥加密这一概念。我们在QROM下证明了一个可提取有损公钥加密方案和一个CCA安全的公钥加密方案可以构造出一个UC安全的PAKE协议。最后，我们给出了基于格上LWE假设和基于同源的GA-DDH假设的可提取有损加密方案的实例化，实现了第一个在UC框架下基于格上假设的QROM下安全的PAKE协议，和第一个在UC框架下基于同源假设的QROM下安全的PAKE协议。
研究意义
我们实现了第一个在UC框架下基于格上假设的QROM下安全的PAKE协议，和第一个在UC框架下基于同源假设的QROM下安全的PAKE协议。我们所设计的PAKE协议为通用构造，可以导出一个三轮的、具有显示认证的PAKE协议。我们所设计的协议在UC框架下具有可证明安全，可以和任意协议进行通用组合，是国内外标准制定中优先考虑的安全性。我们的协议基于后量子假设在QROM下实现了可证明安全，可以真正抵御量子计算机的攻击，是第一个实现，也是目前唯一的在QROM下具有可证明安全的PAKE协议。