Paper 2024/1200
DepthAware Arithmetization of Common Primitives in Prime Fields
Abstract
A common misconception is that the computational abilities of circuits composed of additions and multiplications are restricted to simple formulas only. Such arithmetic circuits over finite fields are actually capable of computing any function, including equality checks, comparisons, and other highly nonlinear operations. While all those functions are computable, the challenge lies in computing them efficiently. We refer to this search problem as arithmetization. Arithmetization is a key problem in secure computation, as techniques like homomorphic encryption and secret sharing compute arithmetic circuits rather than the highlevel programs that programmers are used to. The objective in arithmetization has typically been to minimize the number of multiplications (multiplicative size), as multiplications in most secure computation techniques are significantly more expensive to compute than additions. However, the multiplicative depth of a circuit arguably plays an even more important role in deciding the computational cost: For homomorphic encryption, it strongly affects the choice of cryptographic parameters and the number of bootstrapping operations required, which are orders of magnitude more expensive to compute than multiplications. In fact, if we can limit the multiplicative depth of a circuit such that we do not need to perform any bootstrapping, we can omit the large bootstrapping keys required to perform them all together. We argue that arithmetization should be treated as a multiobjective minimization problem, in which a tradeoff can be made between a circuit's multiplicative size and depth. We present efficient depthaware arithmetization methods for many primitive operations such as exponentiation, univariate functions, equality checks, comparisons, and ANDs and ORs, which take into account that squaring can be cheaper than arbitrary multiplications, and we study how to compose them.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 ArithmetizationArithmetic circuitsPolynomial evaluationHomomorphic encryption
 Contact author(s)

J V Vos @ tudelft nl
conti @ math unipd it
Z Erkin @ tudelft nl  History
 20240729: approved
 20240725: received
 See all versions
 Short URL
 https://ia.cr/2024/1200
 License

CC BYNCND
BibTeX
@misc{cryptoeprint:2024/1200, author = {Jelle Vos and Mauro Conti and Zekeriya Erkin}, title = {DepthAware Arithmetization of Common Primitives in Prime Fields}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1200}, year = {2024}, url = {https://eprint.iacr.org/2024/1200} }