期刊
JOURNAL OF THE ACM
卷 56, 期 6, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1568318.1568324
关键词
Algorithms; Theory; Lattice; cryptography; quantum computation; public key encryption; average-case hardness
类别
资金
- Alon Fellowship
- Binational Science Foundation
- Israel Science Foundation
- Army Research Office [DAAD19-03-1-0082]
- IST directorate [015848]
- European Research Council (ERC)
Our main result is a reduction from worst-case lattice problems such as GAPSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the learning from parity with error problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for GAPSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., nonquantum). We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GAPSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size (O) over tilde (n(2)) and encrypting a message increases its size by a factor of (O) over tilde (n) (in previous cryptosystems these values are (O) over tilde (n(4)) and (O) over tilde (n(2)), respectively). In fact, under the assumption that all parties share a random bit string of length (O) over tilde (n(2)), the size of the public key can be reduced to (O) over tilde (n).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据