CryptoDB
Silent Circuit Relinearisation: Sublinear-Size (Boolean and Arithmetic) Garbled Circuits from DCR
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | We introduce a general template for building garbled circuits with low communication, assuming decisional composite residuosity (DCR) and a circular security assumption. For the case of layered Boolean circuits, we can garble a circuit of size $s$ with communication proportional to $O(s/\log\log s)$ bits, plus an additive factor that is polynomial in the security parameter. For layered arithmetic circuits with $B$-bounded integer computation, we obtain a similar result: the garbled arithmetic circuit has size $O(s/\log\log s) \cdot (\secpar + \log B)$ bits, where $\secpar$ is the security parameter. In both cases, we can remove the circular security assumption by adding a term proportional to the circuit depth. These are the first constructions of general-purpose, garbled circuits with sublinear size, without relying on heavy tools like indistinguishability obfuscation or attribute-based and fully homomorphic encryption. To achieve these results, our main technical tool is a new construction of a form of homomorphic secret sharing (HSS) where some of the inputs are {semi-private}, that is, known to one of the evaluating parties. Through a new {relinearisation} technique that allows performing arbitrary additions and multiplications on semi-private shares, we build such an HSS scheme that supports evaluating any function of the form $C(x) \cdot C'(y)$, where $C$ is any polynomially-sized circuit applied to the semi-private input $y$, and $C'$ is a restricted-multiplication (or, NC1) circuit applied to the private input $x$. This significantly broadens the expressiveness of prior known HSS constructions. |
BibTeX
@inproceedings{crypto-2025-35734,
title={Silent Circuit Relinearisation: Sublinear-Size (Boolean and Arithmetic) Garbled Circuits from DCR},
publisher={Springer-Verlag},
author={Pierre Meyer and Claudio Orlandi and Lawrence Roy and Peter Scholl},
year=2025
}