Search for: All records

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). 

Vector Oblivious Linear Evaluation (VOLE) supports fast and scalable interactive Zero-Knowledge (ZK) proofs. Despite recent improvements to VOLE-based ZK, compiling proof statements to a control-flow oblivious form (e.g., a circuit) continues to lead to expensive proofs. One useful setting where this inefficiency stands out is when the statement is a disjunction of clauses $$\mathcal{L}_1 \lor \cdots \lor \mathcal{L}_B$$. Typically, ZK requires paying the price to handle all $$B$$ branches. Prior works have shown how to avoid this price in communication, but not in computation. Our main result, $$\mathsf{Batchman}$$, is asymptotically and concretely efficient VOLE-based ZK for batched disjunctions, i.e. statements containing $$R$$ repetitions of the same disjunction. This is crucial for, e.g., emulating CPU steps in ZK. Our prover and verifier complexity is only $$\bigO(RB+R|\C|+B|\C|)$$, where $$|\C|$$ is the maximum circuit size of the $$B$$ branches. Prior works' computation scales in $$RB|\C|$$. For non-batched disjunctions, we also construct a VOLE-based ZK protocol, $$\mathsf{Robin}$$, which is (only) communication efficient. For small fields and for statistical security parameter $$\lambda$$, this protocol's communication improves over the previous state of the art ($$\mathsf{Mac'n'Cheese}$$, Baum et al., CRYPTO'21) by up to factor $$\lambda$$. Our implementation outperforms prior state of the art. E.g., we achieve up to $$6\times$$ improvement over $$\mathsf{Mac'n'Cheese}$$ (Boolean, single disjunction), and for arithmetic batched disjunctions our experiments show we improve over $$\mathsf{QuickSilver}$$ (Yang et al., CCS'21) by up to $$70\times$$ and over $$\mathsf{AntMan}$$ (Weng et al., CCS'22) by up to $$36\times$$.