当前位置: 华文问答 > 科学

清华大学陈一镭发表量子算法,有望解决世界级算法难题「格密码」,该项工作有怎样的前景和意义?

2024-04-11科学

作为朋友圈已经被刷屏的相关人士,本来想等自己把论文看过一遍之后再回答,但是这个问题的热度似乎有点高,底下也有些回答让我不尽满意,所以还是简单写一点。

disclaimer: 个人对格问题的经典求解略知一二,但是对量子算法所知不多,有说的不对的地方敬请见谅。

首先,十分敬佩陈老师能做出这样的成果,无论最后这个结论是被验证还是被推翻,都极大地推进了我们在格密码量子安全性上的认知。然后,我对这个工作的意义谈一下个人的看法。

(1) 这项工作是否破解了格密码?

正如陈老师在论文中指出的,这项工作对LWE问题的参数选取有一定要求,目前主流的标准算法并不在可破解的范围之内。但是这项工作(如果被验证)会极大地降低人们对格密码的信心,导致人们对格密码作为抗量子密码的前景产生极大的忧虑。

而且,除了标准算法之外,格密码有很多其他的应用,例如属性基加密ABE或全同态加密FHE。这些方案大多都落入了这一工作可攻击的参数选取范围之内。近年来,格密码领域有一个趋势是使用NTRU替代LWE(或RLWE)。至于NTRU是否可以绕过这一攻击,可能还有待进一步的研究。

(2) 这项工作是否意味着我们需要放弃对格密码的研究?

即使格密码最后被证明了不是抗量子的,也不意味着格密码的研究失去意义,毕竟即使是明确无法抗量子攻击的椭圆曲线配对,目前仍有许多的研究工作基于其上展开。格密码的能力比配对密码更强,可以实现例如任意多项式策略的属性基加密、全同态加密等功能,这些都是传统的配对密码无法做到的。因此在可用于破解密码算法的通用量子计算机真正诞生之前,格密码仍然会得到广泛的关注(尽管可能不如现在)。

另外,目前一些研究者正尝试将格密码用代数模型抽象化(正如将配对密码抽象为双线性映射)。如果这一方向可以走通,基于格密码的方案很有可能可以平移到编码等其他困难问题上。因而格密码的研究目前还算不上是死路一条。或者不如说,正是因为出现了这些问题,才有必要把更多的关注投入到格密码的研究上。

(3) 这项工作对密码学的影响?

首先提一下,区块链上的签名和零知识证明是可以基于哈希构造的,而哈希(或广义地说,对称密码)由于不具备代数结构,被认为是最能抗量子的算法。所以除非真的证明了NP in QBP,否则无需太过担忧量子计算出现后,区块链会瞬间倒塌这件事——尽管他们可能需要尽早布局更换链上的算法。

如果陈老师的结果被证明成立,可能会促进密码学中几个领域的成果涌现:

第一,基于其他抗量子问题的密码方案研究。之前由于格密码一家独大,基于编码、多变量等的方案被广泛忽视了。特别地,是否可以基于编码、多变量等假设实现复杂的功能性密码方案,如身份基加密、属性基加密、群签名、环签名,都是尚待研究的蓝海。

第二,用于密码学的量子计算算法的研究。尽管后量子密码已经提了很久,但大多数密码研究者都还是量子计算的外行,对后量子密码的研究也仍是从经典计算的角度。但这一工作的出现,意味着后量子密码研究者如果不懂量子计算,恐怕很难在这个领域作出大的成就了。至少从我个人而言,我感觉自己得开始进入辛苦的补课过程了。

第三,格密码本身的研究。正如SIDH被攻破后,同源密码的论文反而变多了一样,特定参数下的LWE被攻破,反而会有许多研究者,考虑如何基于不满足攻击条件的那些格问题和参数,构造新的格密码算法。如果是已经投入格密码研究的硕士生或博士生,不妨尝试从这个角度出发思考问题,说不定会有新的成果产出。

第四,格方法用于求解其他困难问题的研究。RSA、ECC等经典密码,在有侧信道信息泄露的情况下,都可以用格算法求解。那么,对于编码、多变量等其他目前仍被认为是抗量子的问题,是否存在一种办法,将其转化为格问题,从而实现多项式复杂度的量子求解?以及,不满足攻击条件的那些格密码算法,是否也有可能在存在信息泄露的条件下,可以转化为此类问题,从而能被量子算法求解?这些似乎都是很值得研究的问题。

最后:科学就是在不断的试错中发展起来的。目前国内的科研氛围总地来说有些浮躁,很多人不愿接受失败。当然,这其中有客观原因,但对于科学本身来说,这不算是好事。希望我国研究者能在密码学领域作出更多突破性成果,也和各位共勉。