關(guān)于非對(duì)稱含錯(cuò)學(xué)習(xí)問(wèn)題的困難性研究
doi: 10.11999/JEIT190685 cstr: 32379.14.JEIT190685
-
密碼科學(xué)技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100878
基金項(xiàng)目: 國(guó)家重點(diǎn)研發(fā)計(jì)劃(2017YFB0802005, 2018YFB0804105)，國(guó)家自然科學(xué)基金(61602046, 61932019)，中國(guó)科協(xié)“青年人才托舉工程”(2016QNRC001)
On the Hardness of the Asymmetric Learning With Errors Problem
-
State Key Laboratory of Cryptology, Beijing 100878, China
Funds: The National Key Research and Development Program of China (2017YFB0802005, 2018YFB0804105), The National Natural Science Foundation of China (61602046, 61932019), The Young Elite Scientists Sponsorship Program by China Association for Science and Technology (2016QNRC001)
-
摘要: 由于基于最壞情況困難假設(shè)等優(yōu)點(diǎn)，基于格的密碼被認(rèn)為是最具前景的抗量子密碼研究方向。作為格密碼的常用的兩個(gè)主要困難問(wèn)題之一，含錯(cuò)學(xué)習(xí)(LWE)問(wèn)題被廣泛用于密碼算法的設(shè)計(jì)。為了提高格密碼算法的性能，Zhang等人(2019)提出了非對(duì)稱含錯(cuò)學(xué)習(xí)問(wèn)題，該文將從理論上詳細(xì)研究非對(duì)稱含錯(cuò)學(xué)習(xí)問(wèn)題和標(biāo)準(zhǔn)含錯(cuò)學(xué)習(xí)問(wèn)題關(guān)系，并證明在特定錯(cuò)誤分布下非對(duì)稱含錯(cuò)學(xué)習(xí)問(wèn)題和含錯(cuò)學(xué)習(xí)問(wèn)題是多項(xiàng)式時(shí)間等價(jià)的，從而為基于非對(duì)稱含錯(cuò)學(xué)習(xí)問(wèn)題設(shè)計(jì)安全的格密碼算法奠定了理論基礎(chǔ)。
-
關(guān)鍵詞:
- 抗量子密碼 /
- 格密碼 /
- 含錯(cuò)學(xué)習(xí)問(wèn)題
Abstract: Due to the advantages such as the worst-case hardness assumption, lattice-based cryptography is believed to the most promising research direction in post-quantum cryptography. As one of the two main hard problems commonly used in lattice-based cryptography, Learning With Errors (LWE) problem is widely used in constructing numerous cryptosystems. In order to improve the efficiency of lattice-based cryptosystems, Zhang et al. (2019) introduced the Asymmetric LWE (ALWE) problem. In this paper, the relation between the ALWE problem and the standard LWE problem is studied, and it shows that for certain error distributions the two problems are polynomially equivent, which paves the way for constructing secure lattice-based cryptosystems from the ALWE problem. -
SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484–1509. doi: 10.1137/S0097539795293172 NSA. National Security Agency. Cryptography today[EB/OL]. https://www.nsa.gov/ia/programs/suiteb_cryptography/, 2015. NIST. Post-quantum cryptography standardization[EB/OL]. http://csrc.nist.gov/groups/ST/post-quantum-crypto/submission-requirements/index.html, 2016. 中國(guó)科學(xué)技術(shù)學(xué)會(huì). 科普時(shí)報(bào): 中國(guó)科協(xié)發(fā)布12個(gè)領(lǐng)域60大科技難題[EB/OL]. http://www.cast.org.cn/art/2018/6/22/art_90_77662.html, 2018. REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]. The 37th Annual ACM Symposium on Theory of Computing, Baltimore, USA, 2005: 84–93. AJTAI M. Generating hard instances of lattice problems (extended abstract)[C]. The 28th Annual ACM Symposium on Theory of Computing, Philadelphia, USA,1996: 99–108. ZHANG Jiang, YU Yu, FAN Shuqin, et al. Tweaking the asymmetry of asymmetric-key cryptography on lattices: KEMs and signatures of smaller sizes[R]. Cryptology ePrint Archive 2019/510, 2019. APPLEBAUM B, CASH D, PEIKERT C, et al. Fast cryptographic primitives and circular-secure encryption based on hard learning problems[C]. The 29th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2009: 595–618. MICCIANCIO D and REGEV O. Worst-case to average-case reductions based on Gaussian measures[C]. The 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004: 372–381. PEIKERT C. An efficient and parallel Gaussian sampler for lattices[C]. The 30th Annual Conference on Advances in Cryptology, Santa Barbara, USA, 2010: 80–97. -
下載:
圖(1)
計(jì)量
- 文章訪問(wèn)數(shù): 2532
- HTML全文瀏覽量: 970
- PDF下載量: 107
- 被引次數(shù): 0
下載:
