LWE问题及其公钥密码方案
source link: https://www.jinse.com/blockchain/319959.html?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
错误学习问题(Learning with Errors,简称LWE)由Regev在2005年提出[11],该问题已经成为格密码学中广泛使用的密码学基础。LWE问题是一个平均情况下的问题,Regev在论文[11]中将LWE问题量子归约到格上标准困难问题。因此在LWE问题之上建立的所有密码学方案,都能够将其安全建立在格问题的最坏情况下困难性之上。
本文节选自陈智罡博士的博士论文。
1.1.1 LWE问题
LWE问题就是给出一些关于秘密向量s的“近似”随机线性方程,其目标是恢复秘密向量s。例如给出如下一些“近似”随机线性方程:
14s1+ 15s2+ 5s3+ 2s4≈8 (mod 17)
13s1+ 14s2+ 14s3+ 6s4≈16 (mod 17)
6s1+ 10s2+ 13s3+ 1s4≈3 (mod 17)
10s1+ 4s2+ 12s3+ 16s4≈12 (mod 17)
…………
9s1+ 5s2+ 9s3+ 6s4≈9 (mod17)
在上述每个方程中,加入了一个小的错误,该错误在+1和-1之间,目标是恢复向量s。如果上述方程中没有加入错误,则使用高斯消元法就可以在多项式时间内恢复向量s。但是由于加入了错误,使得该问题变得非常的困难。
LWE问题定义 参数n ≥1,模q ≥ 2,是上的一个错误概率分布。是上的一个概率分布,该分布通过如下方式获得:随机均匀选择一个向量a∈,根据分布选择错误向量e∈,输出(a,b=< a , s > +emod q)。LWE问题是对于s∈,给出任意数量的从取出的独立实例,其目的是输出s。
LWE判定问题 上述LWE问题是一个LWE搜索问题,密码学中更感兴趣的是LWE问题的另外一个版本:平均情况下的LWE判定问题。即对于随机均匀选择的s∈,能够以不可忽略的概率区分分布与均匀分布上的实例。判定LWE问题可以归约到搜索LWE问题。
如果在均匀选择秘密向量s的情况下,判定LWE问题可以被解决,则对于所有秘密向量s,判定LWE问题都可以被解决。
LWE问题与BDD问题 上述LWE问题定义中,对于m个从取出的独立实例,可以用随机均匀矩阵A∈和b=AT s+e表出。所以LWE问题可以看成是随机格上的BDD问题。
参数说明 分布是一个标准偏离是的类似高斯分布,其中,通常取为1/poly(n)。模q一般是关于n的多项式。LWE实例的数量并不重要。
LWE问题的困难性 以下三个原因说明LWE问题是困难的。第一,已知最好的求解LWE问题的算法运行时间是指数级的,即使是对量子计算机也没有任何帮助。第二,LWE问题是LPN问题的自然扩展,而LPN问题在学习理论中被广泛研究而且普遍认为是困难的。此外LPN问题可以形式化为随机线性二元码的解码问题,如果LPN问题的求解算法有一点进步,则意味着编码理论的一个突破。第三,也是最重要的,LWE问题被归约到最坏情况下的格上标准困难问题,例如GapSVP和SIVP[11,85]。
Regev在2005年证明了只要,那么在平均情况下解决LWE问题,其困难性至少与使用量子算法近似格上标准困难问题相同,其中近似因子是。随后Peikert在2009年给出了一个相同近似因子的经典约减而非量子约减,但是需要满足q≥2n/2。最近Brakerski等人在2013年给出了在q为多项式的情况下的一个经典LWE问题的约减,但是在维数上有所损失[120]。
在LWE问题中,s可以随机均匀的取自于。这一方面使得的长度可以更短,另外一方面其困难性不变[111]。
假设根据高斯分布选择的错误向量长度的界是B,则有B≤,得到,从而。该式反映了近似因子与q/B的大小有关,而q/B又与全同态加密方案的计算深度有关,所以当维数n和B固定的情况下,模q越大,全同态加密方案的安全性越低,而全同态加密方案的同态计算能力越高。
Recommend
-
47
第1章sshSSH(22端口)是SecureShellProtocol的简写,安装时的软件包是openssh,有ssh1,和ssh2两个版本-t指定加密类型rsa1是版本1,rsa,dsa,ecdsa是版本2SSH先对联机数据包通过加密技术进行加密处理,加密后在进行数据传输。确保了传递的数据安全telnet(23端口)实...
-
50
-
43
上文《比特币btcd代码之初体验》提到比特币除了主网外,还有Testnet以及Regtest网络。 Testnet是公开的测试网,所有开发都可以访问这个网络,为了避免有人恶意囤积上面的Testnet bitcoin,这个testnet每隔一段时期就会清空并以新...
-
6
信息安全技术主要包括: 信息加密技术 数字签名技术 身份认证技术 访问控制技术 网络安全技术 反病毒技术 数据备份与恢复 信息安全管理这里因为之前搞到了师兄给...
-
3
TCS:One-Time Password 一次性密码及其应用 作者: 张志强 ...
-
6
md5安全吗?有多么地不安全?如何才能安全地存储密码?… md5安全吗? 经过各种安全事件后,很多系统在存放密码的时候不会直接存放明文密码了,大都改成了存放了 md5 加密(hash)后的密码,可是这样真的安全吗?...
-
3
密码是我们保护私密信息所设置的安全认证口令,需妥善保管和使用。 使用无线路由器上网,可能都会涉及到无线密码、路由器管理密码、宽带密码。三个密码对上网设置、网络安全至关重要,各个密码的作用如下图。本文详细描...
-
1
神奇的离散对数问题,老师提出了密钥交换,学生在此基础上提出公钥加密算法。 Diffie-Hellman密钥交换协议
-
2
首页技术宅LinuxXshell配置SSH 密钥公钥 Public key Linux免密码登录
-
3
Computer Science > Cryptography and Security [Submitted on 6 Apr 2022 (
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK