International Association
for Cryptologic Research

At Eurocrypt 2015, Zahur, Rosulek, and Evans proposed the model of Linear Garbling Schemes. This model proved a $2\lambda$-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\lambda+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: ``\textit{Is $1.5\lambda$ bits optimal for garbled AND gates in a more inclusive model than Linear Garbling Schemes?}'' In this paper, we propose the \textbf{Bitwise Garbling Schemes}. Our key revelation is that $1.5\lambda$ 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\lambda$-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}\lambda$-bit lower bound. Unfortunately, the corresponding construction is not suitable for 3-input AND gates.