Robustly Reusable Fuzzy Extractor from Isogeny

基于同源的鲁棒可重用模糊提取器

Yu Zhou, Shengli Liu*, Shuai Han*

研究目标

模糊提取器作为一种重要的密码工具，能够以可重复的方式将高熵模糊源的噪声采样转化为均匀随机的密钥，被广泛用在密钥生成与身份识别等现实场景。为了适应复杂的应用场景和安全地处理任务，模糊提取器需要具备一些额外的性质，其中最主要的就是可重用性和鲁棒性。可重用性保证了即使从同一模糊源进行多次提取，密钥依然拥有过伪随机特性；鲁棒性则保证了模糊提取器在重现密钥的过程中可以检测到主动攻击。同时拥有这两种性质的模糊提取器就称为鲁棒可重用模糊提取器（rrFE）。此外，模糊提取器的纠错能力也体现了其应用价值。最好的模糊提取器拥有线性纠错的能力，也就是说，如果错误数量是输入长度的线性级别，那么模糊提取器可以完美地重现出密钥。

随着量子技术的飞速发展，研究后量子安全的密码方案成为迫在眉睫的问题。因此，设计具有后量子安全的rrFE方案就成为模糊提取器研究领域最前沿的课题。到目前为止，唯一实现了后量子安全的rrFE方案是基于LWE假设的。然而，该方案仅仅拥有亚线性的纠错能力，无法处理线性级别的错误。

针对上述问题，我们的研究目标就是设计具有线性纠错能力并实现后量子安全的rrFE方案。

关键问题

我们注意到，在之前基于LWE假设的方案里，LWE假设本身对于参数的特定要求会限制用于纠错的校验部分的长度，从而减低了纠错能力。因此，我们尝试利用别的后量子困难假设来构造rrFE方案。为此，我们将注意力放到了椭圆曲线同源（简称同源）假设上。在某些密码系统中，基于同源假设的方案与以往基于离散对数等问题的方案较为相似，这就提供了一种思路，即将传统的密码方案迁移到比较相像的同源场景中来。我们尝试将同源假设融入到之前到rrFE方案的构造框架中，然而却并不顺利，其中最关键的问题是：

为了模拟rrFE的安全性证明中涉及同态计算的部分，以往的rrFE方案都依赖群元素之间的运算。但是在同源假设下，这些群元素的角色变成了椭圆曲线，而据我们所知，椭圆曲线集合并没有类似的群运算操作。因此，如何解决这个障碍，就成为了构造基于同源假设的rrFE的最重要的问题。

研究内容

我们围绕：“如何在标准模型下基于椭圆曲线同源假设构造具有线性纠错能力的鲁棒可重用模糊提取器”这一主题展开研究。

技术路线

首先，我们重新完善了rrFE的定义。在我们的新定义中，使用rrFE需要先调用一次初始化算法，用来生成一个初始的公开辅助字符串。在后续每一次使用生成算法或者重构算法时，都需要将这个初始的公开辅助字符串作为输入。新定义保证了只要新的采样结果能正确恢复，那么一定会计算出相同的中间密钥，而这一步原本需要通过群元素之间的同态计算得到。因为现在每一次调用算法都会产生相同的中间密钥，所以就避免了群元素间的同态计算，这样就消除了应用同源假设的障碍。

其次，我们提出了一个新的密码工具，称为增强型有效群作用（EEGA），并为其赋予了两个重要的安全性。我们利用EEGA和安全梗概（SS）、提取器（Ext）、消息认证码（PRG）和伪随机数生成器（PRG）提出了一个rrFE的通用构造。实际上，EEGA可以基于同源假设实现，并且它的两种安全性都可以归约到同源假设的困难性上。我们基于同源假设实现了具体的EEGA方案，并最终由此得到了基于同源的rrFE方案。此外，因为我们的方案对用于纠错的部分没有额外的限制，所以基于同源的rrFE方案的纠错能力完全由安全梗概的纠错能力决定。而安全梗概是可以实现线性纠错的，因此我们最终实现的基于同源假设的rrFE也拥有线性纠错能力。

研究意义

我们的基于椭圆曲线同源假设实现的rrFE方案，是首个支持线性纠错的后量子安全的rrFE。我们不但解决了以往后量子安全rrFE方案纠错能力差的缺点，还创新性地将同源假设和模糊提取器联系起来，增加了彼此的研究方向。此外，我们新提出的密码工具EEGA，也可以基于其他困难假设实现，因此有着良好的泛用性和适配性，未来也许可以充当其他密码方案的强力组件。