Paper 2024/1532

Bitwise Garbling Schemes --- A Model with $\frac{3}{2}\kappa$-bit Lower Bound of Ciphertexts

Abstract

At Eurocrypt 2015, Zahur, Rosulek, and Evans proposed the model of Linear Garbling Schemes. This model proved a $2\kappa$-bit lower bound of ciphertexts for a broad class of garbling schemes. At Crypto 2021, Rosulek and Roy presented the innovative "three-halves" garbling scheme in which AND gates cost $1.5\kappa+5$ bits and XOR gates are free. A noteworthy aspect of their scheme is the slicing-and-dicing technique, which is applicable universally to all AND gates when garbling a boolean circuit. Following this revelation, Rosulek and Roy presented several open problems. Our research primarily addresses one of them: ``Is $1.5\kappa$ bits optimal for garbled AND gates in a more inclusive model than Linear Garbling Schemes?'' In this paper, we propose theBitwise Garbling Schemes. Our key revelation is that $1.5\kappa$ bits is indeed optimal for arbitrary garbled AND gates in our model. Moreover, we prove the necessity of the free-XOR technique: If free-XOR is forbidden, we prove a $2\kappa$-bit lower bound. As an extension, we apply our idea to construct a model for fan-in 3 gates. Somewhat unexpectedly, we prove a $\frac{7}{4}\kappa$-bit lower bound. Unfortunately, the corresponding construction is not suitable for 3-input AND gates. This construction may be of independent interest.