Paper 2023/844
Inferring Bivariate Polynomials for Homomorphic Encryption Application
Abstract
Inspired by the advancements in (fully) homomorphic encryption during the last decades and its practical applications, we conduct 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 where a set of objects with specific weights and values is involved. Finally, we give recommendations on how to run our algorithms in order to obtain better results in terms of precision.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. MDPI Cryptography
- DOI
- 10.3390/cryptography7020031
- Keywords
- bivariate polynomialLagrange interpolationmodular knapsack problemlattice reduction
- Contact author(s)
-
maimut diana @ gmail com
george teseleanu @ yahoo com - History
- 2023-06-06: approved
- 2023-06-06: received
- See all versions
- Short URL
- https://ia.cr/2023/844
- License
-
CC BY-NC-SA
BibTeX
@misc{cryptoeprint:2023/844,
author = {Diana Maimut and George Teseleanu},
title = {Inferring Bivariate Polynomials for Homomorphic Encryption Application},
howpublished = {Cryptology ePrint Archive, Paper 2023/844},
year = {2023},
doi = {10.3390/cryptography7020031},
note = {\url{https://eprint.iacr.org/2023/844}},
url = {https://eprint.iacr.org/2023/844}
}
