Paper 2024/1787

An Efficient and Secure Boolean Function Evaluation Protocol

Abstract

The secure evaluation of Boolean functions or Secure Boolean Evaluation (SBE) is a fundamental component in this area of research. SBE allows parties to jointly compute Boolean functions without exposing their private inputs. SBE finds applications in privacy-preserving protocols and secure multi-party computations. The existing schemes need at least $(1.5\lambda+5)$-bit strings to garble an AND gate with security parameter $\lambda$, where $\lambda$ is the length of arbitrary bit strings associated with inputs $0$ and $1$. In this manuscript, we discuss how we circumvent the communication cost of non-input gates independent of $\lambda$. We present an efficient and generic two-party protocol (namely $\mathsf{BooleanEval}$) for the secure evaluation of Boolean functions by utilizing a 1-out-of-2 Oblivious Transfer (OT) as a building block. We introduce randomized Bloom filter (namely, $\mathsf{ RBF}_S$) associated with a set $S$ to compute non-input $\mathsf{AND}$ gates. Moreover, $\mathsf{BooleanEval}$ only employs hash evaluations and XOR operations as the core computational step, making it lightweight and fast. Unlike other lightweight state-of-the-art designs of SBE, $\mathsf{BooleanEval}$ avoids the use of additional cryptographic primitives, such as commitment schemes, to reduce the computational overhead.