Embedded Lattice Cryptosystem
Keywords:
Canonical space, Cryptosystem, ELC, Galois field, Lattice, Post quantum cryptography, Turing machineAbstract
This paper proposes the embedded lattice based public cryptosystem (ELC). This achieves the security protocol of post-quantum cryptography with its embedded lattice structure and canonical space transformation properties simultaneously. The proposed ELC also achieves the efficiency norms over the probabilistic reduction mechanism through the average-case and worst case conditions. The computational complexity of ELC also presented in this paper by the asymptotic Turing machine algorithm thorough the canonical space and canonical base reduction in finite order. The key generation algorithm is compact due to use the Galois field through the number filed and canonical base transformation. Encryption of ELC involves the computation of canonical space under the lattice defined in a free Z-module, as well as canonical embedding and isomorphism between number fields and metric spaces.
References
M. Ajtai, “Generating hard instances of lattice problems (extended abstract),” Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC ’96, 1996, doi: https://doi.org/10.1145/237814.237838.
Ş. Alaca and K. S. Williams, “Introductory Algebraic Number Theory,” Cambridge University Press, Nov. 2003, doi: https://doi.org/10.1017/cbo9780511791260.
L. Alcock. How to think about Abstract Algebra. Oxford University Press, 2021, https://agorism.dev/book/math/alg/lara-alcock-how-to-think-about-abstract-algebra-libgen_li.pdf
S. Arora and B. Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. https://theory.cs.princeton.edu/complexity/book.pdf
D. J. Bernstein, J. Buchmann, and E. Dahmen. Post-Quantum Cryptography. Springer, 2009, https://link.springer.com/book/10.1007/978-3-540-88702-7
L. J. Aslett, P. M. Esperanc¸a, and C. C. Holmes. A review of homomorphic encryption and software tools for encrypted statistical machine learning. Arxiv Preprint arXiv:1508.06574, 2015. https://doi.org/10.48550/arXiv.1508.06574
L. Babai, “On Lovász’ lattice reduction and the nearest lattice point problem,” Combinatorica, vol. 6, no. 1, pp. 1–13, Mar. 1986, doi: https://doi.org/10.1007/bf02579403.
Z. Brakerski, “Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP,” 2012. Available: https://eprint.iacr.org/2012/078.pdf
Z. Brakerski and V. Vaikuntanathan, “Efficient Fully Homomorphic Encryption from (Standard) $mathsf {LWE}$,” SIAM Journal on Computing, vol. 43, no. 2, pp. 831–871, Jan. 2014, doi: https://doi.org/10.1137/120868669.
Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(Leveled) Fully Homomorphic Encryption without Bootstrapping,” ACM Transactions on Computation Theory, vol. 6, no. 3, pp. 1–36, Jul. 2014, doi: https://doi.org/10.1145/2633600.
J. Y. Cai and A. P. Nerurkar, “An improved worst-case to average-case connection for lattice problems,” pp. 468–477, Nov. 2002, doi: https://doi.org/10.1109/sfcs.1997.646135. J. Fan and F. Vercauteren. Somewhat practical, fully homomorphic encryption. IACR Cryptol. ePrint Arch., 2012:144, 2012. https://eprint.iacr.org/2012/144
R. Gilad-Bachrach, N. Dowlin, K. Laine, K. Lauter, M. Naehrig, and J. Wernsing, “CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy,” proceedings.mlr.press, Jun. 11, 2016. https://proceedings.mlr.press/v48/gilad-bachrach16.html
H. Chen, K. Laine, and P. Rindal. Fast Private Set Intersection via Homomorphic Encryption. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1243–1255, 2017. https://eprint.iacr.org/2017/299.pdf
D. P. Chi, J. W. Choi, J. S. Kim, and T. Kim. Lattice-based cryptography for beginners. IACR Cryptol. ePrint Arch., page 938, 2015. https://eprint.iacr.org/2015/938.pdf
D. Chialva and A. Dooms. Conditionals in homomorphic encryption and machine learning applications. IACR Cryptol. ePrint Arch., page 1032, 2018. https://eprint.iacr.org/2018/1032.pdf
K. Conrad, “Cyclotomic Extensions.”2025. Available: https://kconrad.math.uconn.edu/blurbs/galoistheory/cyclotomic.pdf
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001, https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
J. Fan and F. Vercauteren. Somewhat practical, fully homomorphic encryption. IACR Cryptol. ePrint Arch., 2012:144, 2012. https://eprint.iacr.org/2012/144
S. Erabelli. Pyfhe-a Python library for fully homomorphic encryption. PhD thesis, Massachusetts Institute of Technology, 2020. https://dspace.mit.edu/handle/1721.1/129204
C. Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pages 169–178, 2009. https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf
C. Gentry. Computing arbitrary functions of encrypted data. Communications of the ACM, 53(3): 97–105, 2010. https://doi.org/10.1145/1666420.1666444
S. Halevi. Homomorphic encryption. In Y. Lindell, editor, Tutorials on the Foundations of Cryptography. Springer, 2017. https://link.springer.com/book/10.1007/978-3-319-57048-8
J. Hoffstein, J. Pipher, and J. H. Silverman. An introduction to mathematical cryptography, volume 1. Springer, 2008. https://link.springer.com/book/10.1007/978-0-387-77993-5
J. Katz and Y. Lindell. Introduction to modern cryptography. CRC press, 2014. https://eclass.uniwa.gr/modules/document/file.php/CSCYB105/Reading%20Material/%5BJonathan_Katz%2C_Yehuda_Lindell%5D_Introduction_to_Mo%282nd%29.pdf
K. Lauter, M. Naehrig, and V. Vaikuntanathan, “Can Homomorphic Encryption be Practical?” 2011. Available: https://eprint.iacr.org/2011/405.pdf
P. Nguyen and B. Vallee. ´The LLL algorithm. Springer, Berlin, Heidelberg, 2010, https://link.springer.com/book/10.1007/978-3-642-02295-1
C. Peikert, “A Decade of Lattice Cryptography,” Foundations and Trends® in Theoretical Computer Science, vol. 10, no. 4, pp. 283–424, 2016, doi: https://doi.org/10.1561/0400000074.
