以前,我们介绍了椭圆曲线对密码学的好处。基于格子的密码学在学术界已开始变得非常流行。基于格的加密的主要好处是对量子算法的抵抗。基于格的加密还有其他好处吗?例如速度,密文/密钥大小等?

#1 楼


后量子安全性:如您所知,量子攻击不会破坏基于晶格的密码系统。但是,诸如McEliece之类的其他建议以及大多数对称原语在量子计算机上都不是可折时的。
最坏情况下的安全性:在密码系统的安全性证明中,我们通常认为某些问题很难解决平均而言,或更确切地说,很难解决从某些特定分布中得出的随机实例。例如,我们可能假设分解乘以两个随机质数的乘积不能通过多重时间算法完成。尽管通常这是安全的,但原则上可能有人会发现一种有效的分解算法,该算法通常适用于随机实例,但不适用于所有实例。基于格的加密不会遭受此缺点的影响:这些方案被证明是安全的,前提是在最坏的情况下晶格问题很难解决,这意味着只要没有人能找到一种近似最短向量的多重时间算法,它们就很安全。在每个晶格中,不仅是随机晶格。这是理论上的巨大进步,但是我很难说出确切的含义。
效率改进:我在这一点上有点sheep琐,但通常会注意到基于格的方案具有可并行化的结构,这可能会使它们在某些情况下更快。这是因为所涉及的算法通常是具有相对较小的模块化算术(即,不是密码大小的数字)的简单矩阵乘法。但是,我的理解是,基于格的方案的实现将具有更大的密钥,而且我也没有发现任何将基于格的方案与传统方案进行绝对比较的研究。
新的原语:我们只知道如何从晶格或非常相似的技术构建完全同态加密。这里蕴藏着巨大的潜力,我们不知道如何从分解或其他传统假设中构建这种东西。