DOI : https://doi.org/10.18517/ijaseit.14.3.19890

A Study on the Average Number of LLL-based Using Statistical Learning

Kyunghwan Song (1), Yun Am Seo (2)
(1) Department of Mathematics, Jeju National University,Jeju-si, 63243, Republic of Korea
(2) Department of Data Science, Jeju National University,Jeju-si, 63243, Republic of Korea
Fulltext View | Download
How to cite (IJASEIT) :
Song, Kyunghwan, and Yun Am Seo. “A Study on the Average Number of LLL-Based Using Statistical Learning”. International Journal on Advanced Science, Engineering and Information Technology, vol. 14, no. 3, June 2024, pp. 906-11, doi:10.18517/ijaseit.14.3.19890.
Citation Format :
Lattice-based Cryptography is known as one of the key technologies in modern cryptography. This encryption scheme has the basis vectors from the lattice as the public key and a short-length vector in the lattice consisting of an integer combination of the basis vectors as the secret key. To break this encryption, we need to solve the Shortest Vector Problem (SVP), known as NP-hard. Therefore, instead of finding the shortest vector, LLL algorithm is often used to find a vector of sufficiently short length to break the encryption. The LLL algorithm is a well-known method for breaking this encryption, but there is still no clear answer to the question of how many times the LLL algorithm needs to be used to obtain the desired level of secret key, the average number of the (, )-LLL bases in dimension n is a tool to measure the probability that the LLL algorithm solves the SVP. We can expect that this number indicates how many times the appropriate algorithm should run. There is a formula for this, but it contains some functions that take a long time to compute. We apply linear regression to the formula of the average number of the (, )-LLL bases in dimension n, and therefore we obtain some formulas to approximate the average number of the (, )-LLL is based on dimension n, which contains simple functions. When the dimensions are high, our model is much better regarding the computation time.

M. Ajtai, "Generating hard instances of lattice problems", Proc. Electron. Colloq. Comput. Complexity, 1996.

H. Nejatollahi, N. Dutt, S. Ray, F. Regazzoni, I. Banerjee, R. Cammarota, “Software and hardware implementation of lattice-cased cryptography schemes”, Center for Embedded Cyber-Physical Systems, pp. 1-43, 2017.

A. Khalid, S. McCarthy, M. O’Neill, and W. Liu, “Lattice-based Cryptography for IoT in A Quantum World: Are We Ready?,” 2019 IEEE 8th International Workshop on Advances in Sensors and Interfaces (IWASI), Jun. 2019, doi: 10.1109/iwasi.2019.8791343.

Ö Kocabaş and T Soyata, “Medical data analytics in the cloud using homomorphic encryption”, In E-Health and Telemedicine: Concepts, Methodologies, Tools, and Applications. IGI Global, 2016.

M. N. John, O. G. Udoaka, I. U. Udoakpan “Group Theory in Lattice-Based Cryptography.”, Int. J. Math. And Appl., vol. 11, no. 4, pp. 111–125, Dec. 2023.

M. F. Esgin, R. Steinfeld, J. K. Liu, and D. Liu, “Lattice-Based Zero-Knowledge Proofs: New Techniques for Shorter and Faster Constructions and Applications,” Lecture Notes in Computer Science, pp. 115–146, 2019, doi: 10.1007/978-3-030-26948-7_5.

C. Baum and A. Nof, “Concretely-Efficient Zero-Knowledge Arguments for Arithmetic Circuits and Their Application to Lattice-Based Cryptography,” Public-Key Cryptography – PKC 2020, pp. 495–526, 2020, doi: 10.1007/978-3-030-45374-9_17.

V. Lyubashevsky, N. K. Nguyen, and M. Plançon, “Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General,” Lecture Notes in Computer Science, pp. 71–101, 2022, doi:10.1007/978-3-031-15979-4_3.

L. Ducas and W. van Woerden, “On the Lattice Isomorphism Problem, Quadratic Forms, Remarkable Lattices, and Cryptography,” Lecture Notes in Computer Science, pp. 643–673, 2022, doi: 10.1007/978-3-031-07082-2_23.

S. Lyu, L. Liu, C. Ling, J. Lai, and H. Chen, “Lattice codes for lattice-based PKE,” Designs, Codes and Cryptography, vol. 92, no. 4, pp. 917–939, Nov. 2023, doi: 10.1007/s10623-023-01321-6.

N. Alkeilani Alkadri, R. El Bansarkhani, and J. Buchmann, “BLAZE: Practical Lattice-Based Blind Signatures for Privacy-Preserving Applications,” Lecture Notes in Computer Science, pp. 484–502, 2020, doi: 10.1007/978-3-030-51280-4_26.

D. F. Aranha, C. Baum, K. Gjøsteen, T. Silde, and T. Tunge, “Lattice-Based Proof of Shuffle and Applications to Electronic Voting,” Lecture Notes in Computer Science, pp. 227–251, 2021, doi:10.1007/978-3-030-75539-3_10.

C. Ma and M. Jiang, “Practical Lattice-Based Multisignature Schemes for Blockchains,” IEEE Access, vol. 7, pp. 179765–179778, 2019, doi:10.1109/access.2019.2958816.

D. Heinz and T. Pöppelmann, “Combined Fault and DPA Protection for Lattice-Based Cryptography,” IEEE Transactions on Computers, vol. 72, no. 4, pp. 1055–1066, Apr. 2023, doi:10.1109/tc.2022.3197073.

T. Oder, “Efficient and side-channel resistant implementation of lattice-based cryptography”, Doctoral dissertation, Dissertation, Bochum, Ruhr-Universität Bochum, 2019.

J.-P. D’Anvers, D. Heinz, P. Pessl, M. Van Beirendonck, and I. Verbauwhede, “Higher-Order Masked Ciphertext Comparison for Lattice-Based Cryptography,” IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 115–139, Feb. 2022, doi:10.46586/tches.v2022.i2.115-139.

W. Tan, A. Wang, Y. Lao, X. Zhang, K. K. Parhi, “Low-latency VLSI architectures for modular polynomial multiplication via fast filtering and applications to lattice-based cryptography”, arXiv preprint arXiv:2110.12127, 2021.

W. Wang, S. Tian, B. Jungk, N. Bindel, P. Longa, and J. Szefer, “Parameterized Hardware Accelerators for Lattice-Based Cryptography and Their Application to the HW/SW Co-Design of qTESLA,” IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 269–306, Jun. 2020, doi:10.46586/tches.v2020.i3.269-306.

E. Alkim, P. S. L. M. Barreto, N. Bindel, J. Krämer, P. Longa, and J. E. Ricardini, “The Lattice-Based Digital Signature Scheme qTESLA,” Lecture Notes in Computer Science, pp. 441–460, 2020, doi:10.1007/978-3-030-57808-4_22.

J. Hoffstein, J. Pipher, J.H. Silverman, “An introduction to mathematical cryptography”, vol. 1, New York: Springer, 2008, doi:10.1007/978-0-387-77993-5.

A. K. Lenstra, H. W. Lenstra, and L. Lovász, “Factoring polynomials with rational coefficients,” Mathematische Annalen, vol. 261, no. 4, pp. 515–534, Dec. 1982, doi: 10.1007/bf01457454.

L. Chen, Z. Xing, Y. Li, and S. Qiu, “Efficient MIMO Preprocessor With Sorting-Relaxed QR Decomposition and Modified Greedy LLL Algorithm,” IEEE Access, vol. 8, pp. 54085–54099, 2020, doi:10.1109/access.2020.2980922.

L. Chen, Y. Wang, Z. Xing, S. Qiu, Q. Wang, and Y. Zhang, “A Paralleled Greedy LLL Algorithm for 16×16 MIMO Detection,” 2020 IEEE International Symposium on Circuits and Systems (ISCAS), Oct. 2020, doi: 10.1109/iscas45731.2020.9181195.

A. Goldberger and Y. Strassler, “A practical algorithm for completing half-Hadamard matrices using LLL,” Journal of Algebraic Combinatorics, vol. 55, no. 1, pp. 217–244, Nov. 2021, doi:10.1007/s10801-021-01077-z.

J.-S. Coron and A. Gini, “A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem,” Lecture Notes in Computer Science, pp. 3–31, 2020, doi: 10.1007/978-3-030-56880-1_1.

J. Frauendiener, C. Jaber, and C. Klein, “Efficient computation of multidimensional theta functions,” Journal of Geometry and Physics, vol. 141, pp. 147–158, Jul. 2019, doi:10.1016/j.geomphys.2019.03.011.

G. H. Cho, H.-S. Lee, S. Lim, and Y. Kim, “Storage efficient algorithm for Hermite Normal Form using LLL,” Linear Algebra and its Applications, vol. 613, pp. 183–200, Mar. 2021, doi:10.1016/j.laa.2020.12.022.

L. Hajdu, B. Harangi, A. Tiba, and A. Hajdu, “Detecting Periodicity in Digital Images by the LLL Algorithm,” Mathematics in Industry, pp. 613–619, 2019, doi: 10.1007/978-3-030-27550-1_78.

K. Ryan, "Return of the hidden number problem.: A widespread and novel key extraction attack on ecdsa and dsa", vol. 2019, pp. 146-168, Nov. 2018, [online] Available: https://tches.iacr.org/index.php/TCHES/article/view/7337.

Kim S. “On the shape of a high-dimensional random lattice.” Ph.D. thesis, Stanford University, 2015.

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
    2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
    3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).