Inferring Bivariate Polynomials for Homomorphic Encryption Application

Cryptography

article

Diana Maimuţ¹  George Teşeleanu¹ 

[1] Advanced Technologies Institute;Faculty of Computer Systems and Cybersecurity;Simion Stoilow Institute of Mathematics of the Romanian Academy

关键词: bivariate polynomial;    Lagrange interpolation;    modular knapsack problem;    lattice reduction;   

DOI  :  10.3390/cryptography7020031

学科分类：社会科学、人文和艺术（综合）

来源: mdpi

【 摘 要 】

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.

【 授权许可】

CC BY