More Like this

1. Garbled Circuit Lookup Tables with Logarithmic Number of Ciphertexts

   Heath, David; Kolesnikov, Vladimir; Ng, Lucien KL (May 2024, Springer)

   Garbled Circuit (GC) is a basic technique for practical secure computation. GC handles Boolean circuits; it consumes significant network bandwidth to transmit encoded gate truth tables, each of which scales with the computational security parameter κ. GC optimizations that reduce bandwidth consumption are valuable. It is natural to consider a generalization of Boolean two-input one-output gates (represented by 4-row one-column lookup tables, LUTs) to arbitrary N-row m-column LUTs. Known techniques for this do not scale, with na¨ıve size-O(Nmκ) garbled LUT being the most practical approach in many scenarios. Our novel garbling scheme – logrow – implements GC LUTs while sending only a logarithmic in N number of ciphertexts! Specifically, let n = ⌈log2 N⌉. We allow the GC parties to evaluate a LUT for (n−1)κ+nmκ+Nm bits of communication. logrow is compatible with modern GC advances, e.g. half gates and free XOR. Our work improves state-of-the-art GC handling of several interesting applications, such as privacypreserving machine learning, floating-point arithmetic, and DFA evaluation. 

   more » « less
2. Towards Generic MPC Compilers via Variable Instruction Set Architectures (VISAs)

   Yibin Yang, Stanislav Peceny (November 2023, ACM CCS 2023)

   Cas Cremers and Engin Kirda (Ed.)

   In MPC, we usually represent programs as circuits. This is a poor fit for programs that use complex control flow, as it is costly to compile control flow to circuits. This motivated prior work to emulate CPUs inside MPC. Emulated CPUs can run complex programs, but they introduce high overhead due to the need to evaluate not just the program, but also the machinery of the CPU, including fetching, decoding, and executing instructions, accessing RAM, etc. Thus, both circuits and CPU emulation seem a poor fit for general MPC. The former cannot scale to arbitrary programs; the latter incurs high per-operation overhead. We propose \emph{variable instruction set architectures} (VISAs), an approach that inherits the best features of both circuits and CPU emulation. Unlike a CPU, a VISA machine repeatedly executes entire program \emph{fragments}, not individual instructions. By considering larger building blocks, we avoid most of the machinery associated with CPU emulation: we directly handle each fragment as a circuit. We instantiated a VISA machine via garbled circuits (GC), yielding constant-round 2PC for arbitrary assembly programs. We use improved branching (Stacked Garbling, Heath and Kolesnikov, Crypto 2020) and recent Garbled RAM (GRAM) (Heath et al., Eurocrypt 2022). Composing these securely and efficiently is intricate, and is one of our main contributions. We implemented our approach and ran it on common programs, including Dijkstra's and Knuth-Morris-Pratt. Our 2PC VISA machine executes assembly instructions at $300$Hz to $4000$Hz, depending on the target program. We significantly outperform the state-of-the-art CPU-based approach (Wang et al., ESORICS 2016, whose tool we re-benchmarked on our setup). We run in constant rounds, use $$6\times$$ less bandwidth, and run more than $$40\times$$ faster on a low-latency network. With $50$ms (resp. $100$ms) latency, we are $$898\times$$ (resp. $$1585\times$$) faster on the same setup. While our focus is MPC, the VISA model also benefits CPU-emulation-based Zero-Knowledge proof compilers, such as ZEE and EZEE (Heath et al., Oakland'21 and Yang et al., EuroS\&P'22). 

   more » « less
3. Accelerating Large Garbled Circuits on an FPGA-enabled Cloud

   https://doi.org/10.1109/H2RC49586.2019.00008  

   Leeser, Miriam; Gungor, Mehmet; Huang, Kai; Ioannidis, Stratis (November 2019, 2019 IEEE/ACM International Workshop on Heterogeneous High-performance Reconfigurable Computing (H2RC))

   Garbled Circuits (GC) is a technique for ensuring the privacy of inputs from users and is particularly well suited for FPGA implementations in the cloud where data analytics is frequently run. Secure Function Evaluation, such as that enabled by GC, is orders of magnitude slower than processing in the clear. We present our best implementation of GC on Amazon Web Services (AWS) that implements garbling on Amazon's FPGA enabled F1 instances. In this paper we present the largest problems garbled to date on FPGA instances, which includes problems that are represented by over four million gates. Our implementation speeds up garbling 20 times over software over a range of different circuit sizes. 

   more » « less
4. Efficiently Compiling Secure Computation Protocols From Passive to Active Security: Beyond Arithmetic Circuits

   https://doi.org/10.56553/popets-2024-0006  

   Blanton, Marina; Murphy, Dennis; Yuan, Chen (January 2024, Proceedings on Privacy Enhancing Technologies)

   This work studies compilation of honest-majority semi-honest secure multi-party protocols secure up to additive attacks to maliciously secure computation with abort. Prior work concentrated on arithmetic circuits composed of addition and multiplication gates, while many practical protocols rely on additional types of elementary operations or gates to achieve good performance. In this work we revisit the notion of security up to additive attacks in the presence of additional gates such as random element generation and opening. This requires re-evaluation of functions that can be securely evaluated, extending the notion of protocols secure up to additive attacks, and re-visiting the notion of delayed verification that points to weaknesses in its prior use and designing a mitigation strategy. We transform the computation using dual execution to achieve security in the malicious model with abort and experimentally evaluate the difference in performance of semi-honest and malicious protocols to demonstrate the low cost. 

   more » « less
5. Two-server Distributed ORAM with Sublinear Computation and Constant Rounds

   https://doi.org/10.1007/978-3-030-75248-4_18  

   Hamlin, Ariel; Varia, Mayank (May 2021, International Conference on Practice and Theory of Public-Key Cryptography (PKC))

   null (Ed.)

   Distributed ORAM (DORAM) is a multi-server variant of Oblivious RAM. Originally proposed to lower bandwidth, DORAM has recently been of great interest due to its applicability to secure computation in the RAM model, where circuit complexity and rounds of communication are equally important metrics of efficiency. In this work, we construct the first DORAM schemes in the 2-server, semi-honest setting that simultaneously achieve sublinear server computation and constant rounds of communication. We provide two constant-round constructions, one based on square root ORAM that has O(sqrt(N) log(N)) local computation and another based on secure computation of a doubly efficient PIR that achieves local computation of O(N^ϵ) for any ϵ>0 but that allows the servers to distinguish between reads and writes. As a building block in the latter construction, we provide secure computation protocols for evaluation and interpolation of multivariate polynomials based on the Fast Fourier Transform, which may be of independent interest. 

   more » « less