【LWE问题简介】

2024-07-01 10:36| 来源: 网络整理| 查看: 265

文章目录解线性方程组问题LWE问题搜索LWE问题判定LWE问题两个LWE问题之间的规约LWE问题的复杂性结论平均情况下的复杂性结论其他版本的LWE问题其他信息论文索引容错学习(learning with errors, LWE)问题就是求解带噪声的线性方程组问题, 由Oded Regev在[Reg05] 中提出, 他也因此结果荣获2018年的哥德尔奖. LWE问题的困难性基于的复杂性假设非常弱, 但是功能却异常强大, 由于LWE问题尚无有效的量子求解算法, 因此基于LWE假设的加密方案被认为是抗量子的.

LWE问题是求解带噪声的线性方程组问题. LWE问题的困难性基于的复杂性假设非常弱, 但是功能却异常强大, 由于LWE问题尚无有效的量子求解算法, 因此基于LWE假设的加密方案被认为是抗量子的.

终于到了介绍LWE的时间. LWE几乎是每个当代密码学学者\学生必须要有所了解的工具, 基于LWE, 我们能够构造一大批功能强大且安全的加密方案, 如选择密钥攻击安全的公钥加密方案(IND-CCA2 PKE), 有损加密方案(Lossy PKE), 基于属性加密(ABE), 全同态加密(FHE), 密钥交换(Key Exchange), 非交互零知识证明(NIZK), 程序混淆(Obfuscation)….

本文中, 我们将介绍LWE相关知识, 包括Basic Idea, 两种基本问题和他们之间的规约, 变体问题及其困难性规约, LWE算法的复杂性结论.

解线性方程组问题

没有什么可以说的呀, 求兼容的线性方程组的特解或者通解都是 P \mathbf P P问题. 我们说的方程之间不兼容, 实际上是就是以下一种情况:

没有几个相互矛盾的方程, 比如一会儿又让 x 1 + x 2 = 1 x_1+x_2=1 x1+x2=1, 一会儿又让 x 1 + x 2 = 2 x_1+x_2=2 x1+x2=2.

但是产生这种情况的情形, 可能是多种的:

消元消除了 c = 0 c=0 c=0, 其中 c c c是一个非零常数两个方程系数有公约数, 模出来之后左边相同了右边又不同

不过, 大体上对于一个随机的 m m m元 n n n个方程组成的模 q q q方程组, 只要参数得当(比如不要作死选 m < n m

【本文地址】

公司简介

联系我们