Paper 2024/1787

An Efficient and Secure Boolean Function Evaluation Protocol

Vikas Srivastava

Tapaswini Mohanty

Nibedita Kundu

Sumit Kumar Debnath

Pantelimon Stanica

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.

@misc{cryptoeprint:2024/1787,
      author = {Sushmita Sarkar and Vikas Srivastava and Tapaswini Mohanty and Nibedita Kundu and Sumit Kumar Debnath and Pantelimon Stanica},
      title = {An Efficient and Secure Boolean Function Evaluation Protocol},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1787},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1787}
}