{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:13:16Z","timestamp":1760148796151,"version":"build-2065373602"},"reference-count":56,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2023,6,5]],"date-time":"2023-06-05T00:00:00Z","timestamp":1685923200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>Inspired by the advancements in (fully) homomorphic encryption in recent decades and its practical applications, we conducted a preliminary study on the underlying mathematical structure of the corresponding schemes. Hence, this paper focuses on investigating the challenge of deducing bivariate polynomials constructed using homomorphic operations, namely repetitive additions and multiplications. To begin with, we introduce an approach for solving the previously mentioned problem using Lagrange interpolation for the evaluation of univariate polynomials. This method is well-established for determining univariate polynomials that satisfy a specific set of points. Moreover, we propose a second approach based on modular knapsack resolution algorithms. These algorithms are designed to address optimization problems in which a set of objects with specific weights and values is involved. Finally, we provide recommendations on how to run our algorithms in order to obtain better results in terms of precision.<\/jats:p>","DOI":"10.3390\/cryptography7020031","type":"journal-article","created":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T02:08:15Z","timestamp":1686017295000},"page":"31","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Inferring Bivariate Polynomials for Homomorphic Encryption Application"],"prefix":"10.3390","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9541-5705","authenticated-orcid":false,"given":"Diana","family":"Maimu\u0163","sequence":"first","affiliation":[{"name":"Advanced Technologies Institute, 10 Dinu Vintil\u0103, 021102 Bucharest, Romania"},{"name":"Faculty of Computer Systems and Cybersecurity, Military Technical Academy, 39-49 George Co\u015fbuc, 050141 Bucharest, Romania"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3953-2744","authenticated-orcid":false,"given":"George","family":"Te\u015feleanu","sequence":"additional","affiliation":[{"name":"Advanced Technologies Institute, 10 Dinu Vintil\u0103, 021102 Bucharest, Romania"},{"name":"Simion Stoilow Institute of Mathematics of the Romanian Academy, 21 Calea Grivitei, 010702 Bucharest, Romania"}]}],"member":"1968","published-online":{"date-parts":[[2023,6,5]]},"reference":[{"key":"ref_1","unstructured":"Dertouzos, M.L., Rivest, R.L., and Adleman, L. (1978). Foundations of Secure Computation, Academia Press."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A Method for Obtaining Digital Signatures and Public-Key Cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Gentry, C. (2009). A Fully Homomorphic Encryption Scheme. [Ph.D. Thesis, Stanford University].","DOI":"10.1145\/1536414.1536440"},{"key":"ref_4","first-page":"24","article-title":"Fully Homomorphic Encryption over the Integers","volume":"Volume 6110","author":"Gentry","year":"2010","journal-title":"Proceedings of the EUROCRYPT\u201910"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Gentry, C., and Vaikuntanathan, V. (2023, May 25). Fully Homomorphic Encryption without Bootstrapping. Available online: https:\/\/eprint.iacr.org\/2011\/277.pdf.","DOI":"10.1145\/2090236.2090262"},{"key":"ref_6","unstructured":"Fan, J., and Vercauteren, F. (2023, May 25). Somewhat Practical Fully Homomorphic Encryption. Available online: https:\/\/eprint.iacr.org\/2012\/144.pdf."},{"key":"ref_7","first-page":"868","article-title":"Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP","volume":"Volume 7417","author":"Brakerski","year":"2012","journal-title":"Proceedings of the CRYPTO\u201912"},{"key":"ref_8","first-page":"45","article-title":"Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme","volume":"Volume 8308","author":"Bos","year":"2013","journal-title":"Proceedings of the IMACC\u201913"},{"key":"ref_9","first-page":"75","article-title":"Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based","volume":"Volume 8042","author":"Gentry","year":"2013","journal-title":"Proceedings of the CRYPTO\u201913"},{"key":"ref_10","unstructured":"Brakerski, Z., and Vaikuntanathan, V. (2014). Proceedings of the ITCS\u201914, Association for Computing Machinery."},{"key":"ref_11","unstructured":"Carpov, S., Chillotti, I., Gama, N., Georgieva, M., and Izabachene, M. (2023, May 25). TFHE: Fast Fully Homomorphic Encryption Library. Available online: https:\/\/tfhe.github.io\/tfhe."},{"key":"ref_12","first-page":"409","article-title":"Homomorphic Encryption for Arithmetic of Approximate Numbers","volume":"Volume 10624","author":"Cheon","year":"2017","journal-title":"Proceedings of the ASIACRYPT\u201917"},{"key":"ref_13","first-page":"648","article-title":"On the Security of Homomorphic Encryption on Approximate Numbers","volume":"Volume 12696","author":"Li","year":"2021","journal-title":"Proceedings of the EUROCRYPT\u201921"},{"key":"ref_14","unstructured":"(2023, May 25). A Curated List of Amazing Homomorphic Encryption Libraries, Software and Resources. Available online: https:\/\/github.com\/jonaschn\/awesome-he."},{"key":"ref_15","unstructured":"Williams, E.A. (2023, May 25). Driven by Privacy, Homomorphic Encryption Is Changing the Way We Do Business. Available online: https:\/\/www.forbes.com\/sites\/forbestechcouncil\/2021\/05\/19\/driven-by-privacy-homomorphic-encryption-is-changing-the-way-we-do-business\/?sh=60d688004cbf."},{"key":"ref_16","unstructured":"Jackson, A. (2023, May 25). 20 Use Cases of Homomorphic Encryption Every CISO Must Know. Available online: https:\/\/www.linkedin.com\/pulse\/20-use-cases-homomorphic-encryption-every-ciso-must-know-jackson-\/."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1016\/j.jbi.2014.04.003","article-title":"Private Predictive Analysis on Encrypted Medical Data","volume":"50","author":"Bos","year":"2014","journal-title":"J. Biomed. Inform."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.future.2017.09.002","article-title":"PPDP: An Efficient and Privacy-Preserving Disease Prediction Scheme in Cloud-Based e-Healthcare System","volume":"79","author":"Zhang","year":"2018","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Munjal, K., and Bhatia, R. (2022). A Systematic Review of Homomorphic Encryption and its Contributions in Healthcare Industry. Complex Intell. Syst., 1\u201328.","DOI":"10.1007\/s40747-022-00756-z"},{"key":"ref_20","first-page":"328","article-title":"Cryptographic Solutions for Genomic Privacy","volume":"Volume 9604","author":"Ayday","year":"2016","journal-title":"Proceedings of the FC 2016"},{"key":"ref_21","first-page":"1","article-title":"ML Confidential: Machine Learning on Encrypted Data","volume":"Volume 7839","author":"Graepel","year":"2012","journal-title":"Proceedings of the ICISC 2012"},{"key":"ref_22","first-page":"53","article-title":"Privacy-Preserving Computations of Predictive Medical Models with Minimax Approximation and Non-Adjacent Form","volume":"Volume 10323","author":"Cheon","year":"2017","journal-title":"Proceedings of the FC 2017"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1572","DOI":"10.1109\/JPROC.2022.3205665","article-title":"Survey on Fully Homomorphic Encryption, Theory, and Applications","volume":"110","author":"Marcolla","year":"2022","journal-title":"Proc. IEEE"},{"key":"ref_24","first-page":"124","article-title":"Homomorphic Proxy Re-Authenticators and Applications to Verifiable Multi-User Data Aggregation","volume":"Volume 10322","author":"Derler","year":"2017","journal-title":"Proceedings of the FC 2017"},{"key":"ref_25","first-page":"319","article-title":"CallForFire: A Mission-Critical Cloud-Based Application Built Using the Nomad Framework","volume":"Volume 9604","author":"Diallo","year":"2016","journal-title":"Proceedings of the FC 2016"},{"key":"ref_26","first-page":"288","article-title":"On-the-fly Homomorphic Batching\/Unbatching","volume":"Volume 9604","author":"Sunar","year":"2016","journal-title":"Proceedings of the FC 2016"},{"key":"ref_27","unstructured":"Kincaid, D., Kincaid, D.R., and Cheney, E.W. (2009). Numerical Analysis: Mathematics of Scientific Computing, American Mathematical Society."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1145\/2455.2461","article-title":"Solving Low-Density Subset Sum Problems","volume":"32","author":"Lagarias","year":"1985","journal-title":"J. ACM"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01201999","article-title":"Improved Low-Density Subset Sum Algorithms","volume":"2","author":"Coster","year":"1992","journal-title":"Comput. Complex."},{"key":"ref_30","unstructured":"Gilbert, H. (2010). Proceedings of the EUROCRYPT\u201910, Springer."},{"key":"ref_31","unstructured":"Becker, A., Coron, J.S., and Joux, A. (2011). Proceedings of the EUROCRYPT\u201911, Springer. Lecture Notes in Computer Science."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1137\/070705702","article-title":"An LLL Algorithm with Quadratic Complexity","volume":"39","author":"Nguyen","year":"2009","journal-title":"SIAM J. Comput."},{"key":"ref_33","first-page":"760","article-title":"Towards Faster Polynomial-Time Lattice Reduction","volume":"Volume 12826","author":"Kirchner","year":"2021","journal-title":"Proceedings of the CRYPTO\u201921"},{"key":"ref_34","unstructured":"Koy, H., and Schnorr, C.P. (2001). Proceedings of the Cryptography and Lattices, Springer."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ic.2005.04.004","article-title":"Fast LLL-type lattice reduction","volume":"204","author":"Schnorr","year":"2006","journal-title":"Inf. Comput."},{"key":"ref_36","first-page":"41","article-title":"Adapting Density Attacks to Low-Weight Knapsacks","volume":"Volume 3788","author":"Nguyen","year":"2005","journal-title":"Proceedings of the ASIACRYPT"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1090\/psapm\/036\/864367","article-title":"Algebraic Aspects of Interpolation","volume":"Volume 36","author":"Micchelli","year":"1986","journal-title":"Proceedings of Symposia in Applied Mathematics"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/08S010025","article-title":"A Simple Expression for Multivariate Lagrange Interpolation","volume":"1","author":"Saniee","year":"2008","journal-title":"SIAM Undergrad. Res. Online"},{"key":"ref_39","unstructured":"Garey, M.R., and Johnson, D.S. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co."},{"key":"ref_40","unstructured":"Martello, S., and Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, Inc."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1109\/TIT.1978.1055927","article-title":"Hiding Information and Signatures in Trapdoor Knapsacks","volume":"24","author":"Merkle","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/3-540-69053-0_3","article-title":"A New Public-Key Cryptosystem","volume":"Volume 1233","author":"Naccache","year":"1997","journal-title":"Proceedings of the EUROCRYPT \u201997"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0304-3975(91)90077-F","article-title":"A Deterministic Algorithm for Modular Knapsack Problems","volume":"88","author":"Salomaa","year":"1991","journal-title":"Theor. Comput. Sci."},{"key":"ref_44","first-page":"204","article-title":"The Cryptanalysis of a New Public-Key Cryptosystem Based on Modular Knapsacks","volume":"Volume 576","author":"Chee","year":"1991","journal-title":"Proceedings of the CRYPTO\u201991"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Hoffstein, J., Pipher, J., and Silverman, J. (2008). An Introduction to Mathematical Cryptography, Springer. Undergraduate Texts in Mathematics.","DOI":"10.1007\/978-0-387-77993-5_6"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/2421119.2421122","article-title":"Review of Algorithmic Cryptanalysis, by Antoine Joux","volume":"43","year":"2012","journal-title":"SIGACT News"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra","year":"1982","journal-title":"Math. Ann."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1137\/0210033","article-title":"A T = O(2n\/2), S = O(2n\/4) Algorithm for Certain NP-Complete Problems","volume":"10","author":"Schroeppel","year":"1981","journal-title":"SIAM J. Comput."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","article-title":"A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms","volume":"53","author":"Schnorr","year":"1987","journal-title":"Theor. Comput. Sci."},{"key":"ref_50","unstructured":"(2023, May 25). fpLLL. Available online: https:\/\/github.com\/fplll\/fplll."},{"key":"ref_51","first-page":"155","article-title":"Fast Reduction of Algebraic Lattices over Cyclotomic Fields","volume":"Volume 12171","author":"Kirchner","year":"2020","journal-title":"Proceedings of the CRYPTO\u201920"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Ryan, K., and Heninger, N. (2023, May 25). Fast Practical Lattice Reduction through Iterated Compression. Available online: https:\/\/eprint.iacr.org\/2023\/237.","DOI":"10.1007\/978-3-031-38548-3_1"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1080\/00150517.1973.12430815","article-title":"Some Doubly Exponential Sequences","volume":"11","author":"Aho","year":"1973","journal-title":"Fibonacci Q."},{"key":"ref_54","unstructured":"(2023, May 25). Sequence A007018. Available online: https:\/\/oeis.org\/A007018."},{"key":"ref_55","unstructured":"Press, W.H., Teukolsky, S.A., Vetterling, W.T., and Flannery, B.P. (2007). Numerical Recipes: The Art of Scientific Computing, Cambridge University Press."},{"key":"ref_56","unstructured":"Ferguson, H.R.P., Bailey, D.H., and Kutler, P. (2023, May 25). A Polynomial Time, Numerically Stable Integer Relation Algorithm; NASA Technical Report RNR\u201391\u2013032, Available online: https:\/\/ntrs.nasa.gov\/citations\/20020052399."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/7\/2\/31\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:48:29Z","timestamp":1760125709000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/7\/2\/31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,5]]},"references-count":56,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,6]]}},"alternative-id":["cryptography7020031"],"URL":"https:\/\/doi.org\/10.3390\/cryptography7020031","relation":{},"ISSN":["2410-387X"],"issn-type":[{"type":"electronic","value":"2410-387X"}],"subject":[],"published":{"date-parts":[[2023,6,5]]}}}