Monotonic Optimization with Application to the Selection of Parameters for LWE-Based Encryption Schemes
摘要
Monotonic optimization is a special class of global optimization with applications cross fields. It addresses problems in which the objective and constraint functions are increasing w.r.t. each of the variables. In this work, the authors extend to the case where the objective and constraint functions are monotonic. The authors present a general framework to address such problems, and especially propose a complete algorithm that is guaranteed to terminate in finitely many steps for problems in a special form. Different from traditional optimization algorithms based on gradient descent, the proposed algorithm does not require closed-form expressions of the functions. As an important application, the functions involved in the parameter optimization problem of LWE-based encryption scheme exhibit monotonicity w.r.t. each of the variables (but may not be increasing), and certain functions involved have no closed-form expression. Inspired by the idea of mathematics mechanization, the authors formalize practical problems into mathematical models and provide a framework for developing automatic and systematic approaches to tackle the parameter optimization problems in lattice-based cryptography. As an illustrative example, the authors consider the parameter optimization of BGV scheme in the context of minimizing communication overhead, without considering homomorphic operations, and provide optimal parameters for it under specified security levels and correctness probabilities.