AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (876.1 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

An Automatic Analysis Approach Toward Indistinguishability of Sampling on the LWE Problem

College of Cryptography Engineering, Engineering University of People’s Armed Police, Xi’an 710086, China.
Key Laboratory of Network and Information Security under the People’s Armed Police, Engineering University of People’s Armed Police, Xi’an 710086, China.
Show Author Information

Abstract

Learning With Errors (LWE) is one of the Non-Polynomial (NP)-hard problems applied in cryptographic primitives against quantum attacks. However, the security and efficiency of schemes based on LWE are closely affected by the error sampling algorithms. The existing pseudo-random sampling methods potentially have security leaks that can fundamentally influence the security levels of previous cryptographic primitives. Given that these primitives are proved semantically secure, directly deducing the influences caused by leaks of sampling algorithms may be difficult. Thus, we attempt to use the attack model based on automatic learning system to identify and evaluate the practical security level of a cryptographic primitive that is semantically proved secure in indistinguishable security models. In this paper, we first analyzed the existing major sampling algorithms in terms of their security and efficiency. Then, concentrating on the Indistinguishability under Chosen-Plaintext Attack (IND-CPA) security model, we realized the new attack model based on the automatic learning system. The experimental data demonstrates that the sampling algorithms perform a key role in LWE-based schemes with significant disturbance of the attack advantages, which may potentially compromise security considerably. Moreover, our attack model is achievable with acceptable time and memory costs.

Keywords

lattice-based cryptographylearning with errorssecurity modelNon-Polynomial (NP)-hard problems

References

[1]
NIST CSRC of Information Technology Laboratory. Post-quantum cryptography round 2 submissions, https:csrc.nist.gov/Projects/post-quantum-cryptography/round-2-submissions, 2019.
[2]
J. H. Liu, Y. Yu, J. W. Jia, S. J. Wang, P. R. Fan, H. Z. Wang, and H. G. Zhang, Lattice-based double-authentication-preventing ring signature for security and privacy in vehicular ad-hoc networks, Tsinghua Science and Technology, vol. 24, no. 5, pp. 575-584, 2019
Crossref Google Scholar
[3]
J. H. Cheon, K. Han, J. Kim, C. Lee, and Y. Son, A practical post-quantum public-key cryptosystem based on spLWE, in Proc. 19th Int. Conf. Information Security and Cryptology, Seoul, Korea, 2016, pp. 51-74.
Crossref
[4]
D. Dachman-Soled, H. J. Gong, M. Kulkarni, and A. Shahverdi, On the leakage resilience of ideal-lattice based public key encryption, IACR Cryptology ePrint Archive, Report 2017/1127, 2017.
[5]
O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM, vol. 56, no. 6, p. 34, 2009.
Crossref Google Scholar
[6]
O. Regev, The learning with errors problem (invited survey), in Proc. 2010 IEEE 25th Annu. Conf. Computational Complexity, Cambridge, MA, USA, 2010, pp. 191-204.
Crossref
[7]
D. D. Zhang, J. Li, B. Li, X. H. Lu, H. Y. Xue, D. D. Jia, and Y. M. Liu, Deterministic identity-based encryption from lattice-based programmable hash functions with high min-entropy, Cryptology ePrint Archive, Report 2019/051, 2019.
Crossref
[8]
J. Zhang, Y. Yu, S. Q. Fan, and Z. F. Zhang, Improved lattice-based CCA2-secure PKE in the standard model, Cryptology ePrint Archive, Report 2019/149, 2019.
Crossref
[9]
M. Tang, M. X. Luo, J. F. Zhou, Z. Yang, Z. P. Guo, F. Yan, and L. Liu, Side-channel attacks in a real scenario, Tsinghua Science and Technology, vol. 23, no. 5, pp. 586-598, 2018.
Crossref Google Scholar
[10]
C. Sun, Z. S. Fei, D. Jia, C. Z. Cao, and X. Y. Wang, Secure transmission scheme for parallel relay channels based on polar coding, Tsinghua Science and Technology, vol. 23, no. 3, pp. 357-365, 2018.
Crossref Google Scholar
[11]
F. Yan and K. Wang, Leakage is prohibited: Memory protection extensions protected address space randomization, Tsinghua Science and Technology, vol. 24, no. 5, pp. 546-556, 2019.
Crossref Google Scholar
[12]
M. R. Albrecht, R. Player, and S. Scott, On the concrete hardness of learning with errors, Journal of Mathematical Cryptology, vol. 9, no. 3, pp. 169-203, 2015.
Crossref Google Scholar
[13]
J. Buchmann, D. Cabarcas, F. Göpfert, A. Hülsing, and P. Weiden, Discrete ziggurat: A time-memory trade-off for sampling from a Gaussian distribution over the integers, in Int. Conf. Selected Areas in Cryptography, Burnaby, Canada, 2013, pp. 402-417.
Crossref
[14]
C. H. Du and G. Q. Ba, High-performance software implementation of discrete gaussian sampling for lattice-based cryptography, in 2016 IEEE Information Technology, Networking, Electronic and Automation Control Conf., Chongqing, China, 2016, pp. 220-224.
Crossref
[15]
C. Gentry, C. Peikert, and V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in Proc. 14th Annu. ACM Symp. Theory of Computing, Victoria, Canada, 2008, pp. 197-206.
Crossref
[16]
J. Howe, A. Khalid, C. Rafferty, Fr. Regazzoni, and M. O’Neill, On practical discrete gaussian samplers for lattice-based cryptography, IEEE Transactions on Computers, vol. 67, no. 3, pp. 322-334, 2018.
Crossref Google Scholar
[17]
C. Peikert, An efficient and parallel gaussian sampler for lattices, in Annu. Cryptology Conf., Santa Barbara, CA, USA, 2010, pp. 80-97.
Crossref
[18]
N. C. Dwarakanath and S. D. Galbraith, Sampling from discrete gaussians for lattice-based cryptography on a constrained device, Applicable Algebra in Engineering, Communication and Computing, vol. 25, no. 3, pp. 159-180, 2014.
Crossref Google Scholar
[19]
A. Karmakar, S. S. Roy, O. Reparaz, F. Vercauteren, and I. Verbauwhede, Constant-time discrete gaussian sampling, IEEE Transactions on Computers, vol. 67, no. 11, pp. 1561-1571, 2018.
Crossref Google Scholar
[20]
S. S. Roy, F. Vercauteren, and I. Verbauwhede, High precision discrete gaussian sampling on FPGAs, in Int. Conf. Selected Areas in Cryptography, Burnaby, Canada, 2013, pp. 383-401.
[21]
A. Pellet-Mary, G. Hanrot, and D. Stehlé, Approx-SVP in ideal lattices with pre-processing, Cryptology ePrint Archive, Report 2019/215, 2019.
Crossref
[22]
S. Agrawal, D. Boneh, and X. Boyen, Efficient lattice (H)IBE in the standard model, in Proc. 29th Annu. Int. Conf. Theory and Applications of Cryptographic Techniques, French Riviera, France, 2010, pp. 553-572.
Crossref
[23]
B. Applebaum, D. Cash, C. Peikert, and A. Sahai, Fast cryptographic primitives and circular-secure encryption based on hard learning problems, in Proc. 29th Annu. Int. Cryptology Conf. Advances in Cryptology, Santa Barbara, CA, USA, 2009, pp. 595-618.
Crossref
[24]
V. Cherkassky and Y. Q. Ma, Practical selection of SVM parameters and noise estimation for SVM regression, Neural Networks, vol. 17, no. 1, pp. 113-126, 2004.
Crossref Google Scholar
[25]
H. Zhang, A. C. Berg, M. Maire, and J. Malik, SVM-KNN: Discriminative nearest neighbor classification for visual category recognition, in 2006 IEEE Computer Society Conf. Computer Vision and Pattern Recognition (CVPR-06), New York, NY, USA, 2006, pp. 2126-2136.
[26]
J. M. Hilbe, Logistic Regression Models. Boca Raton, FL, USA: Chapman and Hall/CRC, 2009.
Crossref
[27]
D. W. Hosmer Jr, S. Lemeshow, and R. X. Sturdivant, Applied Logistic Regression. 3rd ed. New York, NY, USA: John Wiley & Sons, 2013.
Crossref
[28]
T. Roska and L. O. Chua, The CNN universal machine: An analogic array computer, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 40, no. 3, pp. 163-173, 1993.
Crossref Google Scholar
[29]
H. C. Shin, H. R. Roth, M. C. Gao, L. Lu, Z. Y. Xu, I. Nogues, J. H. Yao, D. Mollura, and R. M. Summers, Deep convolutional neural networks for computer-aided detection: CNN architectures, dataset characteristics and transfer learning, IEEE Transactions on Medical Imaging, vol. 35, no. 5, pp. 1285-1298, 2016.
Crossref Google Scholar
[30]
K. Zhang, W. M. Zuo, Y. J. Chen, D. Y. Meng, and L. Zhang, Beyond a gaussian denoiser: Residual learning of deep CNN for image denoising, IEEE Transactions on Image Processing, vol. 26, no. 7, pp. 3142-3155, 2017.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 25 Issue 5,
October 2020
Pages 553-563
DOI: 10.26599/TST.2019.9010063
Cite this article:
Zhu S, Han Y, Yang X. An Automatic Analysis Approach Toward Indistinguishability of Sampling on the LWE Problem. Tsinghua Science and Technology, 2020, 25(5): 553-563. https://doi.org/10.26599/TST.2019.9010063

822

Views

30

Downloads

1

Crossref

N/A

Web of Science

1

Scopus

0

CSCD

Altmetrics
Received: 29 September 2019
Accepted: 29 October 2019
Published: 16 March 2020
© The author(s) 2020

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return