257 results sorted by ID
Possible spell-corrected query: Garbled circuit
Bounded-Collusion Streaming Functional Encryption from Minimal Assumptions
Kaartik Bhushan, Alexis Korb, Amit Sahai
Public-key cryptography
Streaming functional encryption (sFE), recently introduced by Guan, Korb, and Sahai [Crypto 2023], is an extension of functional encryption (FE) tailored for iterative computation on dynamic data streams. Unlike in regular FE, in an sFE scheme, users can encrypt and compute on the data as soon as it becomes available and in time proportional to just the size of the newly arrived data.
As sFE implies regular FE, all known constructions of sFE and FE for $\mathsf{P/Poly}$ require strong...
A Simple Post-Quantum Oblivious Transfer Protocol from Mod-LWR
Shen Dong, Hongrui Cui, Kaiyi Zhang, Kang Yang, Yu Yu
Cryptographic protocols
Oblivious transfer (OT) is a fundamental cryptographic protocol that plays a crucial role in secure multi-party computation (MPC). Most practical OT protocols by, e.g., Naor and Pinkas (SODA'01) or Chou and Orlandi (Latincrypt'15), are based on Diffie-Hellman (DH)-like assumptions and not post-quantum secure. In contrast, many other components of MPC protocols, including garbled circuits and secret sharings, are post-quantum secure. The reliance on non-post-quantum OT protocols presents a...
Reading It like an Open Book: Single-trace Blind Side-channel Attacks on Garbled Circuit Frameworks
Sirui Shen, Chenglu Jin
Attacks and cryptanalysis
Garbled circuits (GC) are a secure multiparty computation protocol that enables two parties to jointly compute a function using their private data without revealing it to each other. While garbled circuits are proven secure at the protocol level, implementations can still be vulnerable to side-channel attacks. Recently, side-channel analysis of GC implementations has garnered significant interest from researchers.
We investigate popular open-source GC frameworks and discover that the AES...
FaultyGarble: Fault Attack on Secure Multiparty Neural Network Inference
Mohammad Hashemi, Dev Mehta, Kyle Mitard, Shahin Tajik, Fatemeh Ganji
Attacks and cryptanalysis
The success of deep learning across a variety of
applications, including inference on edge devices, has led to
increased concerns about the privacy of users’ data and deep
learning models. Secure multiparty computation allows parties
to remedy this concern, resulting in a growth in the number
of such proposals and improvements in their efficiency. The
majority of secure inference protocols relying on multiparty
computation assume that the client does not deviate from the
protocol and...
Rate-1 Arithmetic Garbling from Homomorphic Secret-Sharing
Pierre Meyer, Claudio Orlandi, Lawrence Roy, Peter Scholl
Cryptographic protocols
We present a new approach to garbling arithmetic circuits using techniques from homomorphic secret sharing, obtaining constructions with high rate that support free addition gates. In particular, we build upon non-interactive protocols for computing distributed discrete logarithms in groups with an easy discrete-log subgroup, further demonstrating the versatility of tools from homomorphic secret sharing. Relying on distributed discrete log for the Damgård-Jurik cryptosystem (Roy and Singh,...
Analysis on Sliced Garbling via Algebraic Approach
Taechan Kim
Foundations
Recent improvements to garbled circuits are mainly focused on reducing their size.
The state-of-the-art construction of Rosulek and Roy~(Crypto~2021) requires $1.5\kappa$ bits for garbling AND gates in the free-XOR setting.
This is below the previously proven lower bound $2\kappa$ in the linear garbling model of Zahur, Rosulek, and Evans~(Eurocrypt~2015).
Recently, Ashur, Hazay, and Satish~(eprint 2024/389) proposed a scheme that requires $4/3\kappa O(1)$ bits for garbling AND...
Can We Beat Three Halves Lower Bound?: (Im)Possibility of Reducing Communication Cost for Garbled Circuits
Chunghun Baek, Taechan Kim
Foundations
Recent improvements to garbled circuits are mainly focused on reducing their size.
The state-of-the-art construction of Rosulek and Roy (Crypto 2021) requires $1.5\kappa$ bits for garbling AND gates in the free-XOR setting.
This is below the previously proven lower bound $2\kappa$ in the linear garbling model of Zahur, Rosulek, and Evans (Eurocrypt 2015).
Whether their construction is optimal in a more inclusive model than the linear garbling model still remains open.
This paper begins...
Extractable Witness Encryption for Signed Vector Digests from Pairings and Trust-Scalable One-Time Programs
Sora Suegami
Cryptographic protocols
Witness encryption (WE) allows a ciphertext to be encrypted under an NP problem such that anyone holding a valid witness for that problem can decrypt it (flexible decryptors), without interaction with others (non-interaction). However, existing schemes are either impractical or achieve only a part of these WE features. We propose a novel WE scheme that 1) is based on bilinear maps such as pairings, 2) achieves the property of flexible decryptors, and 3) still requires the decryptor's...
2024/527
Last updated: 2024-04-07
Slice more? It leaks: Analysis on the paper ``On the Feasibility of Sliced Garbling''
Taechan Kim
Attacks and cryptanalysis
Recent improvements to garbled circuits are mainly focused on reducing their size.
The state-of-the-art construction of Rosulek and Roy (Crypto 2021) requires $1.5\kappa$ bits for garbling AND gates in the free-XOR setting.
This is below the previously proven lower bound $2\kappa$ in the linear garbling model of Zahur, Rosulek, and Evans (Eurocrypt 2015).
Recently, Ashur, Hazay, and Satish (eprint 2024/389) proposed a scheme that requires $4/3\kappa O(1)$ bits for garbling AND...
Column-wise Garbling, and How to Go Beyond the Linear Model
Lei Fan, Zhenghao Lu, Hong-Sheng Zhou
Cryptographic protocols
In the linear garbling model introduced by Zahur, Rosulek, and Evans (Eurocrypt 2015), garbling an AND gate requires at least \(2\kappa\) bits of ciphertext, where $\kappa$ is the security parameter. Though subsequent works, including those by Rosulek and Roy (Crypto 2021) and Acharya et al. (ACNS 2023), have advanced beyond these linear constraints, a more comprehensive design framework is yet to be developed.
Our work offers a novel, unified, and arguably simple perspective on garbled...
On the Feasibility of Sliced Garbling
Tomer Ashur, Carmit Hazay, Rahul Satish
Foundations
Garbling schemes are one of the most fundamental objects in cryptography and have been studied extensively due to their broad applicability. The state-of-the-art is a construction in which XOR gates are free and AND gates require $3\kappa/2 \mathcal{O}(1)$ bits per gate, due to Rosulek and Roy (CRYPTO'21). An important technique in their garbling is slicing, which partitions the labels into two equal-length slices. In this paper, we explore the feasibility of the slicing technique for...
Malicious Security for SCALES: Outsourced Computation with Ephemeral Servers
Anasuya Acharya, Carmit Hazay, Vladimir Kolesnikov, Manoj Prabhakaran
Cryptographic protocols
SCALES (Small Clients And Larger Ephemeral Servers) model is a recently proposed model for MPC (Acharya et al., TCC 2022). While the SCALES model offers several attractive features for practical large-scale MPC, the result of Acharya et al. only offered semi-honest secure protocols in this model.
We present a new efficient SCALES protocol secure against malicious adversaries, for general Boolean circuits. We start with the base construction of Acharya et al. and design and use a suite of...
Garbled Circuit Lookup Tables with Logarithmic Number of Ciphertexts
David Heath, Vladimir Kolesnikov, Lucien K. L. Ng
Cryptographic protocols
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 $\kappa$. 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...
Fuzzy Private Set Intersection with Large Hyperballs
Aron van Baarsen, Sihang Pu
Cryptographic protocols
Traditional private set intersection (PSI) involves a receiver and a sender holding sets $X$ and $Y$, respectively, with the receiver learning only the intersection $X\cap Y$.
We turn our attention to its fuzzy variant, where the receiver holds \(|X|\) hyperballs of radius \(\delta\) in a metric space and the sender has $|Y|$ points.
Representing the hyperballs by their center, the receiver learns the points $x\in X$ for which there exists $y\in Y$ such that $\mathsf{dist}(x,y)\leq...
Threshold Garbled Circuits with Low Overhead
Schuyler Rosefield, abhi shelat, LaKyah Tyner
Cryptographic protocols
The folklore approach to designing a threshold variant of symmetric
cryptographic algorithms involves applying generic MPC methods to se-
cret sharing techniques: the MPC first combines participant input shares
using the secret sharing scheme, and then evaluates the cryptographic
function on the reconstructed key. Hardening this secure against n − 1
malicious parties requires some mechanism to ensure input consistency,
e.g., adding MACs to inputs, which consequently, increases the...
Information-Theoretic 2-Party Computation from Additive Somewhat Homomorphic Encryption
Jonathan Trostle
Cryptographic protocols
Two-party computation has been an active area of research since Yao's breakthrough results on garbled circuits. We present secret key additive somewhat homomorphic schemes where the client has perfect privacy (server can be computationally unbounded). Our basic scheme is additive somewhat homomorphic and we give protocols to handle addition and multiplication. In one scheme, the server handles circuit multiplication gates by returning the multiplicands to the client which does the...
Efficient Arithmetic in Garbled Circuits
David Heath
Cryptographic protocols
Garbled Circuit (GC) techniques usually work with Boolean circuits. Despite intense interest, efficient arithmetic generalizations of GC were only known from heavy assumptions, such as LWE.
We construct arithmetic garbled circuits from circular correlation robust hashes, the assumption underlying the celebrated Free XOR garbling technique. Let $\lambda$ denote a computational security parameter, and consider the integers $\mathbb{Z}_m$ for any $m \geq 2$. Let $\ell = \lceil \log_2 m...
R3PO: Reach-Restricted Reactive Program Obfuscation and its Application to MA-ABE
Kaartik Bhushan, Sai Lakshmi Bhavana Obbattu, Manoj Prabhakaran, Rajeev Raghunath
Foundations
In recent breakthrough results, novel use of garbled circuits yielded constructions for several primitives like Identity-Based Encryption (IBE) and 2-round secure multi-party computation, based on standard assumptions in public-key cryptography. While the techniques in these different results have many common elements, these works did not offer a modular abstraction that could be used across them.
Our main contribution is to introduce a novel notion of obfuscation, called Reach-Restricted...
Adaptive Distributional Security for Garbling Schemes with $\mathcal{O}(|x|)$ Online Complexity
Estuardo Alpírez Bock, Chris Brzuska, Pihla Karanko, Sabine Oechsner, Kirthivaasan Puniamurthy
Foundations
Garbling schemes allow to garble a circuit $C$ and an input $x$ such that $C(x)$ can be computed while hiding both $C$ and $x$. In the context of adaptive security, an adversary specifies the input to the circuit after seeing the garbled circuit, so that one can pre-process the garbling of $C$ and later only garble the input $x$ in the online phase. Since the online phase may be time-critical, it is an interesting question how much information needs to be transmitted in this phase and...
FANNG-MPC: Framework for Artificial Neural Networks and Generic MPC
Najwa Aaraj, Abdelrahaman Aly, Tim Güneysu, Chiara Marcolla, Johannes Mono, Rogerio Paludo, Iván Santos-González, Mireia Scholz, Eduardo Soria-Vazquez, Victor Sucasas, Ajith Suresh
Cryptographic protocols
In this work, we introduce FANNG-MPC, a versatile secure multi-party computation framework capable to offer active security for privacy preserving machine learning as a service (MLaaS). Derived from the now deprecated SCALE-MAMBA, FANNG is a data-oriented fork, featuring novel set of libraries and instructions for realizing private neural networks, effectively reviving the popular framework. To the best of our knowledge, FANNG is the first MPC framework to offer actively secure MLaaS in the...
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices: Garbled Circuits of Optimal Size, Laconic Functional Evaluation, and More
Yao-Ching Hsieh, Huijia Lin, Ji Luo
Public-key cryptography
Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [Gentry, STOC '09; Brakerski–Vaikuntanathan, FOCS '11], there is still a significant gap in understanding related homomorphic primitives supporting all *unrestricted* polynomial-size computations. One prominent example is attribute-based encryption (ABE). The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [Gorbunov–Vaikuntanathan–Wee,...
How to Garble Mixed Circuits that Combine Boolean and Arithmetic Computations
Hanjun Li, Tianren Liu
Foundations
The study of garbling arithmetic circuits is initiated by Applebaum, Ishai, and Kushilevitz [FOCS'11], which can be naturally extended to mixed circuits. The basis of mixed circuits includes Boolean operations, arithmetic operations over a large ring and bit-decomposition that converts an arithmetic value to its bit representation. We construct efficient garbling schemes for mixed circuits.
In the random oracle model, we construct two garbling schemes:
$\bullet$ The first scheme...
Unmodified Half-Gates is Adaptively Secure - So is Unmodified Three-Halves
Xiaojie Guo, Kang Yang, Xiao Wang, Yu Yu, Zheli Liu
Cryptographic protocols
Adaptive security is a crucial property for garbling schemes in pushing the communication of garbled circuits to an offline phase when the input is unknown. In this paper, we show that the popular half-gates scheme by Zahur et al. (Eurocrypt'15), without any modification, is adaptively secure in the non-programmable random permutation model (npRPM). Since real implementations of selective-secure half-gates are already based on npRPM, our result shows that these implementations are already...
Adaptive Garbled Circuits and Garbled RAM from Non-Programmable Random Oracles
Cruz Barnum, David Heath, Vladimir Kolesnikov, Rafail Ostrovsky
Cryptographic protocols
Garbled circuit techniques that are secure in the adaptive setting -- where inputs are chosen after the garbled program is sent -- are motivated by practice, but they are notoriously difficult to achieve. Prior adaptive garbling is either impractically expensive or encrypts the entire garbled program with the output of a programmable random oracle (PRO), a strong assumption.
We present a simple framework for proving adaptive security of garbling schemes in the non-programmable random...
Generalized Fuzzy Password-Authenticated Key Exchange from Error Correcting Codes
Jonathan Bootle, Sebastian Faller, Julia Hesse, Kristina Hostáková, Johannes Ottenhues
Cryptographic protocols
Fuzzy Password-Authenticated Key Exchange (fuzzy PAKE) allows cryptographic keys to be generated from authentication data that is both fuzzy and of low entropy. The strong protection against offline attacks offered by fuzzy PAKE opens an interesting avenue towards secure biometric authentication, typo-tolerant password authentication, and automated IoT device pairing. Previous constructions of fuzzy PAKE are either based on Error Correcting Codes (ECC) or generic multi-party computation...
Constant-Round Private Decision Tree Evaluation for Secret Shared Data
Nan Cheng, Naman Gupta, Aikaterini Mitrokotsa, Hiraku Morita, Kazunari Tozawa
Cryptographic protocols
Decision tree evaluation is extensively used in machine learning to construct accurate classification models. Often in the cloud-assisted communication paradigm cloud servers execute remote evaluations of classification models using clients’ data. In this setting, the need for private decision tree evaluation (PDTE) has emerged to guarantee no leakage of information for the client’s input nor the service provider’s trained model i.e., decision tree. In this paper, we propose a private...
Composable Oblivious Pseudo-Random Functions via Garbled Circuits
Sebastian Faller, Astrid Ottenhues, Johannes Ottenhues
Cryptographic protocols
Oblivious Pseudo-Random Functions (OPRFs) are a central
tool for building modern protocols for authentication and distributed
computation. For example, OPRFs enable simple login protocols that do
not reveal the password to the provider, which helps to mitigate known
shortcomings of password-based authentication such as password reuse
or mix-up. Reliable treatment of passwords becomes more and more
important as we login to a multitude of services with different passwords
in our daily...
Lightweight Authentication of Web Data via Garble-Then-Prove
Xiang Xie, Kang Yang, Xiao Wang, Yu Yu
Cryptographic protocols
Transport Layer Security (TLS) establishes an authenticated and confidential channel to deliver data for almost all Internet applications. A recent work (Zhang et al., CCS'20) proposed a protocol to prove the TLS payload to a third party, without any modification of TLS servers, while ensuring the privacy and originality of the data in the presence of malicious adversaries. However, it required maliciously secure Two-Party Computation (2PC) for generic circuits, leading to significant...
Succinct Computational Secret Sharing
Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, Vinod Vaikuntanathan
Foundations
A secret-sharing scheme enables a dealer to share a secret $s$ among $n$ parties such that only authorized subsets of parties, specified by a monotone access structure $f:\{0,1\}^n\to\{0,1\}$, can reconstruct $s$ from their shares. Other subsets of parties learn nothing about $s$.
The question of minimizing the (largest) share size for a given $f$ has been the subject of a large body of work. However, in most existing constructions for general access structures $f$, the share size is not...
Towards Generic MPC Compilers via Variable Instruction Set Architectures (VISAs)
Yibin Yang, Stanislav Peceny, David Heath, Vladimir Kolesnikov
Cryptographic protocols
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...
Secure Multiparty Computation with Free Branching
Aarushi Goel, Mathias Hall-Andersen, Aditya Hegde, Abhishek Jain
Cryptographic protocols
We study secure multi-party computation (MPC) protocols for branching circuits that contain multiple sub-circuits (i.e., branches) and the output of the circuit is that of a single active branch. Crucially, the identity of the active branch must remain hidden from the protocol participants.
While such circuits can be securely computed by evaluating each branch and then multiplexing the output, such an approach incurs a communication cost linear in the size of the entire circuit. To...
TGh: A TEE/GC Hybrid Enabling Confidential FaaS Platforms
James Choncholas, Ketan Bhardwaj, Ada Gavrilovska
Applications
Trusted Execution Environments (TEEs) suffer from
performance issues when executing certain management instructions, such as creating an enclave, context switching in and out of protected mode, and swapping cached pages. This is especially problematic for short-running, interactive functions in Function-as-a-Service (FaaS) platforms, where existing techniques to address enclave overheads are insufficient. We find FaaS functions can spend more time managing the enclave than executing...
MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More
Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, Divya Ravi
Cryptographic protocols
The bottleneck-complexity (BC) of secure multiparty computation (MPC) protocols is a measure of the maximum number of bits which are sent and received by any party in a protocol. As the name suggests, the goal of studying BC-efficient protocols is to increase overall efficiency by making sure that the workload in the protocol is somehow "amortized'' by the protocol participants.
Orlandi et al. (PKC 2022) initiated the study of BC-efficient protocols from simple assumptions in the...
Unconditionally Secure Multiparty Computation for Symmetric Functions with Low Bottleneck Complexity
Reo Eriguchi
Cryptographic protocols
Bottleneck complexity is an efficiency measure of secure multiparty computation (MPC) introduced by Boyle et al. (ICALP 2018) to achieve load-balancing. Roughly speaking, it is defined as the maximum communication complexity required by any player within the protocol execution. Since it was shown to be impossible to achieve sublinear bottleneck complexity in the number of players $n$ for all functions, a prior work constructed MPC protocols with low bottleneck complexity for specific...
Breaking and Fixing Garbled Circuits when a Gate has Duplicate Input Wires
Raine Nieminen, Thomas Schneider
Cryptographic protocols
Garbled circuits are a fundamental cryptographic primitive that allows two or more parties to securely evaluate an arbitrary Boolean circuit without revealing any information beyond the output using a constant number of communication rounds. Garbled circuits have been introduced by Yao (FOCS’86) and generalized to the multi-party setting by Beaver, Micali and Rogaway (STOC’90). Since then, several works have improved their efficiency by providing different garbling schemes and several...
New Ways to Garble Arithmetic Circuits
Marshall Ball, Hanjun Li, Huijia Lin, Tianren Liu
Foundations
The beautiful work of Applebaum, Ishai, and Kushilevitz [FOCS'11] initiated the study of arithmetic variants of Yao's garbled circuits. An arithmetic garbling scheme is an efficient transformation that converts an arithmetic circuit $C: \mathcal{R}^n \rightarrow \mathcal{R}^m$ over a ring $\mathcal{R}$ into a garbled circuit $\widehat C$ and $n$ affine functions $L_i$ for $i \in [n]$, such that $\widehat C$ and $L_i(x_i)$ reveals only the output $C(x)$ and no other information of $x$. AIK...
Tri-State Circuits: A Circuit Model that Captures RAM
David Heath, Vladimir Kolesnikov, Rafail Ostrovsky
Cryptographic protocols
We introduce tri-state circuits (TSCs). TSCs form a natural model of computation that, to our knowledge, has not been considered by theorists. The model captures a surprising combination of simplicity and power. TSCs are simple in that they allow only three wire values ($0,1,$ and undefined - $\mathcal{Z}$) and three types of fan-in two gates; they are powerful in that their statically placed gates fire (execute) eagerly as their inputs become defined, implying orders of execution that...
Certified Everlasting Secure Collusion-Resistant Functional Encryption, and More
Taiga Hiroka, Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, Tapas Pal, Takashi Yamakawa
Public-key cryptography
We study certified everlasting secure functional encryption (FE) and many other cryptographic primitives in this work.
Certified everlasting security roughly means the following.
A receiver possessing a quantum cryptographic object (such as ciphertext) can issue a certificate showing that the receiver has deleted the cryptographic object and information included in the object (such as plaintext) was lost.
If the certificate is valid, the security is guaranteed even if the receiver becomes...
ORTOA: One Round Trip Oblivious Access
Sujaya Maiyya, Yuval Steinhart, Divyakant Agrawal, Prabhanjan Ananth, Amr El Abbadi
Applications
Many applications relying on cloud storage services typically encrypt their data to ensure data privacy. However, reading or writing the encrypted data to serve client requests reveals the type of client operation to a potentially untrusted cloud. An adversary can exploit this information leak to compromise a user’s privacy by tracking read/write access patterns. Existing approaches such as Oblivious RAM (ORAM) schemes hide the type of client access by always reading and then writing the...
Fast Evaluation of S-boxes with Garbled Circuits
Erik Pohle, Aysajan Abidin, Bart Preneel
Cryptographic protocols
Garbling schemes are vital primitives for privacy-preserving protocols and secure two-party computation. In projective garbling schemes, $n$ values are assigned to each wire in the circuit. Current state-of-the-art schemes project two values.
This paper presents a projective garbling scheme that assigns $2^n$ values to wires in a circuit comprising XOR and unary projection gates. A generalization of FreeXOR allows the XOR of wires with $2^n$ values to be very efficient. We then analyze the...
PEA: Practical private epistasis analysis using MPC
Kay Hamacher, Tobias Kussel, Thomas Schneider, Oleksandr Tkachenko
Applications
Due to the significant drop in prices for genome sequencing in the last decade, genome databases were constantly growing. This enabled genome analyses such as Genome-Wide Association Studies (GWAS) that study associations between a gene and a disease and allow to improve medical treatment. However, GWAS fails at the analysis of complex diseases caused by non-linear gene-gene interactions such as sporadic breast cancer or type 2 diabetes. Epistasis Analysis (EA) is a more powerful approach...
A framework for constructing Single Secret Leader Election from MPC
Michael Backes, Pascal Berrang, Lucjan Hanzlik, Ivan Pryvalov
Cryptographic protocols
The emergence of distributed digital currencies has raised the need for a reliable consensus mechanism. In proof-of-stake cryptocur- rencies, the participants periodically choose a closed set of validators, who can vote and append transactions to the blockchain. Each valida- tor can become a leader with the probability proportional to its stake. Keeping the leader private yet unique until it publishes a new block can significantly reduce the attack vector of an adversary and improve the...
Two-Round MPC without Round Collapsing Revisited -- Towards Efficient Malicious Protocols
Huijia Lin, Tianren Liu
Cryptographic protocols
Recent works have made exciting progress on the construction of round optimal, *two-round*, Multi-Party Computation (MPC) protocols. However, most proposals so far are still complex and inefficient.
In this work, we improve the simplicity and efficiency of two-round MPC in the setting with dishonest majority and malicious security. Our protocols make use of the Random Oracle (RO) and a generalization of the Oblivious Linear Evaluation (OLE) correlated randomness, called tensor OLE, over...
Distributed, Private, Sparse Histograms in the Two-Server Model
James Bell, Adria Gascon, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Mariana Raykova, Phillipp Schoppmann
Cryptographic protocols
We consider the computation of sparse, $(\varepsilon, \delta)$-differentially private~(DP) histograms in the two-server model of secure multi-party computation~(MPC), which has recently gained traction in the context of privacy-preserving measurements of aggregate user data.
We introduce protocols that enable two semi-honest non-colluding servers to compute histograms over the data held by multiple users, while only learning a private view of the data. Our solution achieves the same...
Garbled-Circuits from an SCA Perspective: Free XOR can be Quite Expensive. . .
Itamar Levi, Carmit Hazay
Attacks and cryptanalysis
Garbling schemes, invented in the 80's by Yao (FOCS'86), have been a versatile and fundamental tool in modern cryptography. A prominent application of garbled circuits is constant round secure two-party computation, led to a long line of study of this object, where one of the most influential optimizations is Free-XOR (Kolesnikov and Schneider ICALP'08), introducing a global offset $\Delta$ for all garbled wire values where XOR gates are computed locally without garbling them.
To date,...
Authenticated Garbling from Simple Correlations
Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky
Cryptographic protocols
We revisit the problem of constant-round malicious secure two-party computation by considering the use of simple correlations, namely sources of correlated randomness that can be securely generated with sublinear communication complexity and good concrete efficiency.
The current state-of-the-art protocol of Katz et al. (Crypto 2018) achieves malicious security by realizing a variant of the authenticated garbling functionality of Wang et al. (CCS 2017). Given oblivious transfer...
A 2.1 KHz Zero-Knowledge Processor with BubbleRAM
David Heath, Vladimir Kolesnikov
Cryptographic protocols
Zero-Knowledge (ZK) proofs (ZKP) are foundational in cryptography. Most recent ZK research focuses on non-interactive proofs (NIZK) of small statements, useful in blockchain scenarios. Another line, and our focus, instead targets proofs of large statements that are useful, e.g., in proving properties of programs in ZK.
We specify a zero-knowledge processor that executes arbitrary programs written in a simple instruction set and proves in ZK the correctness of the execution. Such an...
One Hot Garbling
David Heath, Vladimir Kolesnikov
Cryptographic protocols
Garbled Circuit (GC) is the main practical 2PC technique, yet despite great interest in its performance, GC notoriously resists improvement. Essentially, we only know how to evaluate GC functions gate-by-gate using encrypted truth tables; given input labels, the GC evaluator decrypts the corresponding output label.
Interactive protocols enjoy more sophisticated techniques. For example, we can expose to a party a (masked) private value. The party can then perform useful local computation...
Garbled Circuits With Sublinear Evaluator
Abida Haque, David Heath, Vladimir Kolesnikov, Steve Lu, Rafail Ostrovsky, Akash Shah
Cryptographic protocols
Arecentlineofwork, Stacked Garbled Circuit(SGC), showed that Garbled Circuit (GC) can be improved for functions that include conditional behavior. SGC relieves the communication bottleneck of 2PC by only sending enough garbled material for a single branch out of the b total branches. Hence, communication is sublinear in the circuit size. However, both the evaluator and the generator pay in computation and perform at least factor $\log b$ extra work as compared to standard GC.
We extend...
SCALES: MPC with Small Clients and Larger Ephemeral Servers
Anasuya Acharya, Carmit Hazay, Vladimir Kolesnikov, Manoj Prabhakaran
Cryptographic protocols
The recently proposed YOSO model is a groundbreaking approach to MPC, executable on a public blockchain, circumventing adaptive player corruption by hiding the corruption targets until they are worthless. Players are selected unpredictably from a large pool to perform MPC subtasks, in which each selected player sends a single message (and reveals their identity). While YOSO MPC has attractive asymptotic complexity, unfortunately, it is concretely prohibitively expensive due to the cost of...
2022/646
Last updated: 2022-10-17
Faster Non-interactive Verifiable Computing
Pascal Lafourcade, Gael Marcadet, Léo Robert
Cryptographic protocols
In 1986, A.Yao introduced the notion of garbled circuits, designed to verify the correctness of computations performed on an untrusted server. However, correctness is guaranteed for only one input, meaning that a new garbled circuit must be created for each new input. To address this drawback, in 2010 Gennaro et al. performed the evaluation of the garbled circuit homomorphically using Fully Homomorphic Encryption scheme, allowing to reuse the same garbled circuit for new inputs. Their...
Security Against Honorific Adversaries: Efficient MPC with Server-aided Public Verifiability
Li Duan, Yufan Jiang, Yong Li, Jörn Müller-Quade, Andy Rupp
Foundations
Secure multiparty computation (MPC) allows distrustful parties to jointly compute some functions while keeping their private secrets unrevealed. MPC adversaries are often categorized as semi-honest and malicious, depending on whether they follow the protocol specifications or not. Covert security was first introduced by Aumann and Lindell in 2007, which models a third type of active adversaries who cheat but can be caught with a probability. However, this probability is predefined...
Cryptographic Oracle-Based Conditional Payments
Varun Madathil, Sri AravindaKrishnan Thyagarajan, Dimitrios Vasilopoulos, Lloyd Fournier, Giulio Malavolta, Pedro Moreno-Sanchez
Cryptographic protocols
We consider a scenario where two mutually distrustful parties, Alice and Bob, want to perform a payment conditioned on the outcome of some real-world event. A semi-trusted oracle (or a threshold number of oracles, in a distributed trust setting) is entrusted to attest that such an outcome indeed occurred, and only then the payment is successfully made. Such oracle-based conditional (ObC) payments are ubiquitous in many real-world applications, like financial adjudication, pre-scheduled...
Auditable, Available and Resilient Private Computation on the Blockchain via MPC
Christopher Cordi, Michael P. Frank, Kasimir Gabert, Carollan Helinski, Ryan C. Kao, Vladimir Kolesnikov, Abrahim Ladha, Nicholas Pattengale
Cryptographic protocols
Simple but mission-critical internet-based applications that require extremely high reliability, availability, and verifiability (e.g., auditability) could benefit from running on robust public programmable blockchain platforms such as Ethereum. Unfortunately, program code running on such blockchains is normally publicly viewable, rendering these platforms unsuitable for applications requiring strict privacy of application code, data, and results.
In this work, we investigate using MPC...
NanoGRAM: Garbled RAM with $\widetilde{O}(\log N)$ Overhead
Andrew Park, Wei-Kai Lin, Elaine Shi
Cryptographic protocols
We propose a new garbled RAM construction called NanoGRAM, which achieves an amortized cost of $\widetilde{O}(\lambda \cdot (W \log N \log^3 N))$ bits per memory access, where $\lambda$ is the security parameter, $W$ is the block size, and $N$ is the total number of blocks, and $\widetilde{O}(\cdot)$ hides $poly\log\log$ factors. For sufficiently large blocks where $W = \Omega(\log^2 N)$, our scheme achieves $\widetilde{O}(\lambda \cdot W \log N)$ cost per memory access, where the...
Secure Publish-Process-Subscribe System for Dispersed Computing
Weizhao Jin, Bhaskar Krishnamachari, Muhammad Naveed, Srivatsan Ravi, Eduard Sanou, Kwame-Lante Wright
Applications
Publish-subscribe protocols enable real-time multi-point-to-multi-point communications for many dispersed computing systems like Internet of Things (IoT) applications. Recent interest has focused on adding processing to such publish-subscribe protocols to enable computation over real-time streams such that the protocols can provide functionalities such as sensor fusion, compression, and other statistical analysis on raw sensor data. However, unlike pure publish-subscribe protocols, which can...
On the Bottleneck Complexity of MPC with Correlated Randomness
Claudio Orlandi, Divya Ravi, Peter Scholl
Cryptographic protocols
At ICALP 2018, Boyle et al. introduced the notion of the bottleneck complexity of a secure multi-party computation (MPC) protocol.
This measures the maximum communication complexity of any one party in the protocol, aiming to improve load-balancing among the parties.
In this work, we study the bottleneck complexity of MPC in the preprocessing model, where parties are given correlated randomness ahead of time.
We present two constructions of bottleneck-efficient MPC protocols, whose...
Practical Garbled RAM: GRAM with $O(\log^2 n)$ Overhead
David Heath, Vladimir Kolesnikov, Rafail Ostrovsky
Cryptographic protocols
Garbled RAM (GRAM) is a powerful technique introduced by Lu and Ostrovsky that equips Garbled Circuit (GC) with a sublinear cost RAM without adding rounds of interaction. While multiple GRAM constructions are known, none are suitable for practice, due to costs that have high constants and poor scaling.
We present the first GRAM suitable for practice. For computational security parameter $\kappa$ and for a size-$n$ RAM that stores blocks of size $w = \Omega(\log^2 n)$ bits, our GRAM incurs...
Circuit-based PSI for Covid-19 Risk Scoring
Leonie Reichert, Marcel Pazelt, Björn Scheuermann
Applications
—Many solutions have been proposed to improve manual contact tracing for infectious diseases through automation. Privacy is crucial for the deployment of such a system as it greatly influences adoption. Approaches for digital contact tracing like Google Apple Exposure Notification (GAEN) protect the privacy of users by decentralizing risk scoring. But GAEN leaks information about diagnosed users as ephemeral pseudonyms are broadcast to everyone. To combat deanonymisation based on the time of...
A State-Separating Proof for Yao’s Garbling Scheme
Chris Brzuska, Sabine Oechsner
Foundations
Secure multiparty computation enables mutually distrusting parties to compute a public function of their secret inputs. One of the main approaches for designing MPC protocols are garbled circuits whose core component is usually referred to as a garbling scheme. In this work, we revisit the security of Yao’s garbling scheme and provide a modular security proof which composes the security of multiple layer garblings to prove security of the full circuit garbling. We perform our security proof...
A Simple Post-Quantum Non-Interactive Zero-Knowledge Proof from Garbled Circuits
Hongrui Cui, Kaiyi Zhang
Cryptographic protocols
We construct a simple public-coin zero-knowledge proof system solely based on symmetric primitives, from which we can apply the Fiat-Shamir heuristic to make it non-interactive. Our construction can be regarded as a simplified cut-and-choose-based malicious secure twoparty computation for the zero-knowledge functionality. Our protocol is suitable for pedagogical purpose for its simplicity (code is only 728 lines).
Threshold Schnorr with Stateless Deterministic Signing from Standard Assumptions
François Garillot, Yashvanth Kondi, Payman Mohassel, Valeria Nikolaenko
Cryptographic protocols
Schnorr's signature scheme permits an elegant threshold signing protocol due to its linear signing equation. However each new signature consumes fresh randomness, which can be a major attack vector in practice. Sources of randomness in deployments are frequently either unreliable, or require state continuity, i.e. reliable fresh state resilient to rollbacks. State continuity is a notoriously difficult guarantee to achieve in practice, due to system crashes caused by software errors,...
Limits on the Adaptive Security of Yao's Garbling
Chethan Kamath, Karen Klein, Krzysztof Pietrzak, Daniel Wichs
Yao’s garbling scheme is one of the most fundamental cryptographic constructions. Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security in the selective setting where the adversary chooses the challenge inputs before seeing the garbled circuit assuming secure symmetric-key encryption (and hence one-way functions). This was followed by results, both positive and negative, concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto 2013)...
On Treewidth, Separators and Yao's Garbling
Chethan Kamath, Karen Klein, Krzysztof Pietrzak
Foundations
We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size S and treewidth w with only a S^O(w) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical...
Private Signaling
Varun Madathil, Alessandra Scafuro, István András Seres, Omer Shlomovits, Denis Varlakov
Cryptographic protocols
We introduce the problem of private signaling. In this problem, a sender posts a message to a certain location of a public bulletin board, and then computes a signal that allows only the intended recipient (and no one else) to learn that it is the recipient of the posted message. Besides privacy, this problem has the following crucial efficiency requirements. First, the sender and recipient do not participate in any out-of-band communication, and second, the overhead of the recipient should...
Tetrad: Actively Secure 4PC for Secure Training and Inference
Nishat Koti, Arpita Patra, Rahul Rachuri, Ajith Suresh
Cryptographic protocols
Mixing arithmetic and boolean circuits to perform privacy-preserving machine learning has become increasingly popular. Towards this, we propose a framework for the case of four parties with at most one active corruption called Tetrad.
Tetrad works over rings and supports two levels of security, fairness and robustness. The fair multiplication protocol costs 5 ring elements, improving over the state-of-the-art Trident (Chaudhari et al. NDSS'20). A key feature of Tetrad is that robustness...
Three Halves Make a Whole? Beating the Half-Gates Lower Bound for Garbled Circuits
Mike Rosulek, Lawrence Roy
Cryptographic protocols
We describe a garbling scheme for boolean circuits, in which XOR gates are free and AND gates require communication of $1.5\kappa 5$ bits. This improves over the state-of-the-art "half-gates" scheme of Zahur, Rosulek, and Evans (Eurocrypt 2015), in which XOR gates are free and AND gates cost $2\kappa$ bits. The half-gates paper proved a lower bound of $2\kappa$ bits per AND gate, in a model that captured all known garbling techniques at the time. We bypass this lower bound with a novel...
A New Approach to Garbled Circuits
Anasuya Acharya, Tomer Ashur, Efrat Cohen, Carmit Hazay, Avishay Yanai
Foundations
A garbling scheme is a fundamental cryptographic building block with a long list of applications. The study of different techniques for garbling a function, towards optimizing computation and communication complexity, has been an area of active research. Most common garbling techniques work by representing each gate in the circuit as a set of ciphertexts that encrypt its truth table row-by-row.
In this work we present a new garbling scheme in the random oracle (RO) model that garbles...
LogStack: Stacked Garbling with $O(b \log b)$ Computation
David Heath, Vladimir Kolesnikov
Cryptographic protocols
Secure two party computation (2PC) of arbitrary programs can be efficiently achieved using garbled circuits (GC). Until recently, it was widely believed that a GC proportional to the entire program, including parts of the program that are entirely discarded due to conditional branching, must be transmitted over a network. Recent work shows that this belief is false, and that communication proportional only to the longest program execution path suffices (Heath and Kolesnikov, CRYPTO 20,...
Stacking Sigmas: A Framework to Compose $\Sigma$-Protocols for Disjunctions
Aarushi Goel, Matthew Green, Mathias Hall-Andersen, Gabriel Kaptchuk
Cryptographic protocols
Zero-Knowledge (ZK) Proofs for disjunctive statements have been a focus of a long line of research.
Classical results such as Cramer {\em et al.} [CRYPTO'94] and Abe {\em et al.} [AC'02] design generic compilers that transform certain classes of ZK proofs into ZK proofs for disjunctive statements.
However, communication complexity of the resulting protocols in these results ends up being proportional to the complexity of proving all clauses in the disjunction. More recently, Heath {\em et...
Threshold Garbled Circuits and Ad Hoc Secure Computation
Michele Ciampi, Vipul Goyal, Rafail Ostrovsky
Cryptographic protocols
Garbled Circuits (GCs) represent fundamental and powerful tools in cryptography, and many variants of GCs have been considered since their introduction. An important property of the garbled circuits is that they can be evaluated securely if and only if exactly 1 key for each input wire is obtained: no less and no more.
In this work we study the case when: 1) some of the wire-keys are missing, but we are still interested in computing the output of the garbled circuit and 2) the evaluator of...
Gage MPC: Bypassing Residual Function Leakage for Non-Interactive MPC
Ghada Almashaqbeh, Fabrice Benhamouda, Seungwook Han, Daniel Jaroslawicz, Tal Malkin, Alex Nicita, Tal Rabin, Abhishek Shah, Eran Tromer
Cryptographic protocols
Existing models for non-interactive MPC cannot provide full privacy for inputs, because they inherently leak the residual function (i.e., the output of the function on the honest parties’ input together with all possible values of the adversarial inputs). For example, in any non-interactive sealed-bid auction, the last bidder can figure out what was the highest previous bid.
We present a new MPC model which avoids this privacy leak. To achieve this, we utilize a blockchain in a novel way,...
Manticore: Efficient Framework for Scalable Secure Multiparty Computation Protocols
Sergiu Carpov, Kevin Deforth, Nicolas Gama, Mariya Georgieva, Dimitar Jetchev, Jonathan Katz, Iraklis Leontiadis, M. Mohammadi, Abson Sae-Tang, Marius Vuille
Implementation
We propose a novel MPC framework, Manticore, in the multiparty setting, with full threshold and semi-honest security model, supporting a combination of real number arithmetic (arithmetic shares), Boolean arithmetic (Boolean shares) and garbled circuits (Yao shares). In contrast to prior work [MZ17, MR18], Manticore never overflows, an important feature for machine learning applications. It achieves this without compromising efficiency or security. Compared to other overflow-free...
Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled Circuits
Aner Ben-Efraim, Kelong Cong, Eran Omri, Emmanuela Orsini, Nigel P. Smart, Eduardo Soria-Vazquez
Cryptographic protocols
We present a secure multiparty computation (MPC) protocol based on garbled circuits which is both actively secure and supports the free-XOR technique, and which has communication complexity $O(n)$ per party. This improves on a protocol of Ben-Efraim, Lindell and Omri which only achieved passive security, without support for free-XOR. Our construction is based on a new variant of LPN-based encryption, but has the drawback of requiring a rather expensive garbling phase. To address this issue...
An Embedded Domain-Specific Language for Logical Circuit Descriptions with Applications to Garbled Circuits
Andrei Lapets, Wyatt Howe, Ben Getchell, Frederick Jansen
Implementation
Contemporary libraries and frameworks that make it possible to incorporate secure multi-party computation protocols and capabilities into production software systems and applications must sometimes deliver underlying capabilities (such as logical circuit synthesis) to new kinds of environments (such as web browsers or serverless cloud computing platforms). In order to illustrate some of the benefits of addressing this challenge by building a solution from the ground up that leverages the...
Witness Encryption from Garbled Circuit and Multikey Fully Homomorphic Encryption Techniques
Kamil Kluczniak
Public-key cryptography
In a witness encryption scheme, to decrypt a ciphertext associated with an NP statement, the decrypter takes as input a witness testifying that the statement is in the language. When the statement is not in the language, then the message is hidden. Thus far, the only provably secure constructions assume the existence of indistinguishability obfuscation (iO) and multilinear maps (MMaps).
We make progress towards building polynomially efficient witness encryption for NP without resorting to...
Quantum Garbled Circuits
Zvika Brakerski, Henry Yuen
Foundations
We present a garbling scheme for quantum circuits, thus achieving a decomposable randomized encoding scheme for quantum computation. Specifically, we show how to compute an encoding of a given quantum circuit and quantum input, from which it is possible to derive the output of the computation and nothing else.
In the classical setting, garbled circuits (and randomized encodings in general) are a versatile cryptographic tool with many applications such as secure multiparty computation,...
Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation
Elette Boyle, Nishanth Chandran, Niv Gilboa, Divya Gupta, Yuval Ishai, Nishant Kumar, Mayank Rathee
Cryptographic protocols
Boyle et al. (TCC 2019) proposed a new approach for secure computation in the preprocessing model building on function secret sharing (FSS), where a gate $g$ is evaluated using an FSS scheme for the related offset family $g_r(x)=g(x r)$. They further presented efficient FSS schemes based on any pseudorandom generator (PRG) for the offset families of several useful gates $g$ that arise in "mixed-mode'' secure computation. These include gates for zero test, integer comparison, ReLU, and spline...
Correlated Randomness Teleportation via Semi-trusted Hardware - Enabling Silent Multi-party Computation
Yibiao Lu, Bingsheng Zhang, Hong-Sheng Zhou, Weiran Liu, Lei Zhang, Kui Ren
Cryptographic protocols
With the advancement of the trusted execution environment (TEE) technologies, hardware-supported secure computing becomes increasingly popular due to its efficiency. During the protocol execution, typically, the players need to contact a third-party server for remote attestation, ensuring the validity of the involved trusted hardware component, such as Intel SGX, as well as the integrity of the computation result. When the hardware manufacturer is not fully trusted, sensitive information may...
Stacked Garbling: Garbled Circuit Proportional to Longest Execution Path
David Heath, Vladimir Kolesnikov
Cryptographic protocols
Secure two party computation (2PC) of arbitrary programs can be efficiently achieved using garbled circuits (GC). The bottleneck of GC efficiency is communication. It is widely believed that for direct 2PC evaluation of a Boolean circuit, it is necessary to transmit the entire GC, including garbled truth tables corresponding to subcomputations whose output is ultimately discarded by conditional logic.
This folklore belief is false.
We propose a novel GC technique, stacked garbling, that...
Self-Processing Private Sensor Data via Garbled Encryption
Nathan Manohar, Abhishek Jain, Amit Sahai
Cryptographic protocols
We introduce garbled encryption, a relaxation of secret-key multi-input functional encryption (MiFE) where a function key can be used to jointly compute upon only a particular subset of all possible tuples of ciphertexts. We construct garbled encryption for general functionalities based on one-way functions.
We show that garbled encryption can be used to build a self-processing private sensor data system where after a one-time trusted setup phase, sensors deployed in the field can...
Efficient Constant-Round MPC with Identifiable Abort and Public Verifiability
Carsten Baum, Emmanuela Orsini, Peter Scholl, Eduardo Soria-Vazquez
Cryptographic protocols
Recent years have seen a tremendous growth in the interest in secure multiparty computation (MPC) and its applications. While much progress has been made concerning its efficiency, many current, state-of-the-art protocols are vulnerable to Denial of Service attacks, where a cheating party may prevent the honest parties from learning the output of the computation, whilst remaining anonymous. The security model of identifiable abort aims to prevent these attacks, by allowing honest parties to...
Mixed-Technique Multi-Party Computations Composed of Two-Party Computations
Erik-Oliver Blass, Florian Kerschbaum
Applications
Protocols for secure multi-party computation are commonly composed
of different sub-protocols, combining techniques such as homomorphic
encryption, secret or Boolean sharing, and garbled circuits. In
this paper, we design a new class of multi-party computation
protocols which themselves are composed out of two-party protocols.
We integrate both types of compositions, compositions of fully
homomorphic encryption and garbled circuits with compositions of
multi-party protocols from two-party...
Private Identity Agreement for Private Set Functionalities
Ben Kreuter, Sarvar Patel, Ben Terner
Applications
Private set intersection and related functionalities are among the most prominent real-world applications of secure multiparty computation. While such protocols have attracted significant attention from the research community, other functionalities are often required to support a PSI application in practice. For example, in order for two parties to run a PSI over the unique users contained in their databases, they might first invoke on a support functionality to agree on the primary keys to...
MP-SPDZ: A Versatile Framework for Multi-Party Computation
Marcel Keller
Implementation
Multi-Protocol SPDZ (MP-SPDZ) is a fork of SPDZ-2 (Keller et al., CCS
'13), an implementation of the multi-party computation (MPC) protocol
called SPDZ (Damgård et al., Crypto '12). MP-SPDZ extends SPDZ-2
to 34 MPC protocol variants, all of which can be used with the same
high-level programming interface based on Python. This considerably
simplifies comparing the cost of different protocols and security
models.
The protocols cover all commonly used security models
(honest/dishonest...
Secure Two-Party Computation in a Quantum World
Niklas Büscher, Daniel Demmler, Nikolaos P. Karvelas, Stefan Katzenbeisser, Juliane Krämer, Deevashwer Rathee, Thomas Schneider, Patrick Struck
Cryptographic protocols
Secure multi-party computation has been extensively studied in the past years and has reached a level that is considered practical for several applications. The techniques developed thus far have been steadily optimized for performance and were shown to be secure in the classical setting, but are not known to be secure against quantum adversaries.
In this work, we start to pave the way for secure two-party computation in a quantum world where the adversary has access to a quantum computer....
Stacked Garbling for Disjunctive Zero-Knowledge Proofs
David Heath, Vladimir Kolesnikov
Cryptographic protocols
Zero-knowledge (ZK) proofs receive wide attention, especially with respect to non-interactivity, small proof size, and fast verification. We instead focus on fast total proof time, in particular for large Boolean circuits. Under this metric, Garbled Circuit (GC)-based ZK, originally proposed by Jawurek et al. ([JKO], CCS 2013), remains state-of-the-art due to the low-constant linear scaling of garbling.
We improve GC-ZK for proof statements with conditional clauses. Our communication is...
Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning
Harsh Chaudhari, Rahul Rachuri, Ajith Suresh
Cryptographic protocols
Machine learning has started to be deployed in fields such as healthcare and finance, which involves dealing with a lot of sensitive data. This propelled the need for and growth of privacy-preserving machine learning (PPML). We propose an actively secure four-party protocol (4PC), and a framework for PPML, showcasing its applications on four of the most widely-known machine learning algorithms -- Linear Regression, Logistic Regression, Neural Networks, and Convolutional Neural Networks.
Our...
Full-Threshold Actively-Secure Multiparty Arithmetic Circuit Garbling
Eleftheria Makri, Tim Wood
Cryptographic protocols
In this work, we show how to garble arithmetic circuits with full active security in the general multiparty setting, secure in the full-threshold setting (that is, when only one party is assumed honest). Our solution allows interfacing Boolean garbled circuits with arithmetic garbled circuits. Previous works in the arithmetic circuit domain focused on the 2-party setting, or on semi-honest security and assuming an honest majority -- notably, the work of Ben-Efraim (Asiacrypt 2018) in the...
Sharing the LUOV: Threshold Post-Quantum Signatures
Daniele Cozzo, Nigel P. smart
Cryptographic protocols
We examine all of the signature submissions to Round-2 of the NIST PQC ``competition'' in the context of whether one can transform them into threshold signature schemes in a relatively straight forward manner. We conclude that all schemes, except the ones in the MQ family, have significant issues when one wishes to convert them using relatively generic MPC techniques. The lattice based schemes are hampered by requiring a mix of operations which are suited to both linear secret shared schemes...
Zaphod: Efficiently Combining LSSS and Garbled Circuits in SCALE
Abdelrahaman Aly, Emmanuela Orsini, Dragos Rotaru, Nigel P. Smart, Tim Wood
We present modifications to the MPC system SCALE-MAMBA to enable the evaluation of garbled circuit (GC) based MPC functionalities and Linear Secret Sharing (LSSS) based MPC functionalities along side each other. This allows the user to switch between different MPC paradigms to achieve the best performance. To do this we present modifications to the GC-based MPC protocol of Hazay et al. (Asiacrypt 2017) (to enable it to support reactive computation), and combine different aspects of their...
Blockchain-enabled Cryptographically-secure Hardware Obfuscation
Fatemeh Ganji, Shahin Tajik, Jean-Pierre Seifert, Domenic Forte
Applications
Among numerous applications, besides cryptocurrencies, the Blockchain offers inherent properties beneficial for the management of supply chains, where data is shared between trusted and untrusted parties. Electronics supply chain serves as a prime example of such chains, where one of the major players, i.e., a foundry, can be untrusted. Hardware obfuscation techniques, namely logic locking, and IC camouflaging have been developed to mislead an adversary aiming at reverse- engineering and...
Fast Actively Secure Five-Party Computation with Security Beyond Abort
Megha Byali, Carmit Hazay, Arpita Patra, Swati Singla
Cryptographic protocols
Secure Multi-party Computation (MPC) with small population and honest majority has drawn focus specifically due to customization in techniques and resulting efficiency that the constructions can offer. In this work, we investigate a wide range of security notions in the five-party setting, tolerating two active corruptions. Being constant-round, our protocols are best suited for real-time, high latency networks such as the Internet.
In a minimal setting of pairwise-private channels, we...
Optimal Transport Layer for Secure Computation
Markus Brandt, Claudio Orlandi, Kris Shrishak, Haya Shulman
We explore two main issues in the performance of Secure Two- Party Computation (2PC): (1) interaction of 2PC with the transport layer and (2) evaluation of 2PC implementations.
Transport layer: Although significantly improved, the performance of 2PC is still prohibitive for practical systems. Contrary to the common belief that bandwidth is the remaining bottleneck for 2PC implementation, we show that the network is under-utilised due to the use of standard TCP sockets. Nevertheless, using...
Attribute Based Encryption (and more) for Nondeterministic Finite Automata from LWE
Shweta Agrawal, Monosij Maitra, Shota Yamada
Public-key cryptography
Constructing Attribute Based Encryption (ABE) [SW05] for uniform models of computation from standard assumptions, is an important problem, about which very little is known. The only known ABE schemes in this setting that i) avoid reliance on multilinear maps or indistinguishability obfuscation, ii) support unbounded length inputs and iii) permit unbounded key requests to the adversary in the security game, are by Waters from Crypto, 2012 [Wat12] and its variants.
Waters provided the first...
Mobile Private Contact Discovery at Scale
Daniel Kales, Christian Rechberger, Thomas Schneider, Matthias Senker, Christian Weinert
Cryptographic protocols
Mobile messengers like WhatsApp perform contact discovery by uploading the user's entire address book to the service provider. This allows the service provider to determine which of the user's contacts are registered to the messaging service. However, such a procedure poses significant privacy risks and legal challenges. As we find, even messengers with privacy in mind currently do not deploy proper mechanisms to perform contact discovery privately.
The most promising approaches addressing...
A Single Shuffle Is Enough for Secure Card-Based Computation of Any Circuit
Kazumasa Shinagawa, Koji Nuida
Cryptographic protocols
Secure computation enables a number of players each holding a secret input value to compute a function of the inputs without revealing the inputs. It is known that secure computation is possible physically when the inputs are given as a sequence of physical cards. This research area is called card-based cryptography. One of the important problems in card-based cryptography is to minimize the number of cards and shuffles, where a shuffle is the most important (and somewhat heavy) operation in...
SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Search
Hao Chen, Ilaria Chillotti, Yihe Dong, Oxana Poburinnaya, Ilya Razenshteyn, M. Sadegh Riazi
Applications
The $k$-Nearest Neighbor Search ($k$-NNS) is the backbone of several cloud-based services such as recommender systems, face recognition, and database search on text and images. In these services, the client sends the query to the cloud server and receives the response in which case the query and response are revealed to the service provider. Such data disclosures are unacceptable in several scenarios due to the sensitivity of data and/or privacy laws.
In this paper, we introduce SANNS, a...
Garbled Neural Networks are Practical
Marshall Ball, Brent Carmer, Tal Malkin, Mike Rosulek, Nichole Schimanski
Applications
We show that garbled circuits are a practical choice for secure evaluation of neural network classifiers. At the protocol level, we start with the garbling scheme of Ball, Malkin & Rosulek (ACM CCS 2016) for arithmetic circuits and introduce new optimizations for modern neural network activation functions. We develop fancy-garbling, the first implementation of the BMR16 garbling scheme along with our new optimizations, as part of heavily optimized garbled-circuits tool that is driven by a...
MArBled Circuits: Mixing Arithmetic and Boolean Circuits with Active Security
Dragos Rotaru, Tim Wood
Cryptographic protocols
Most modern actively-secure multiparty computation (MPC) protocols involve generating random data that is secret-shared and
authenticated, and using it to evaluate arithmetic or Boolean circuits in different ways. In this work we present a generic method for converting authenticated secret-shared data between different fields, and show how to use it to evaluate so-called ``mixed'' circuits with active security and in the full-threshold setting. A mixed circuit is one in which parties...
Streaming functional encryption (sFE), recently introduced by Guan, Korb, and Sahai [Crypto 2023], is an extension of functional encryption (FE) tailored for iterative computation on dynamic data streams. Unlike in regular FE, in an sFE scheme, users can encrypt and compute on the data as soon as it becomes available and in time proportional to just the size of the newly arrived data. As sFE implies regular FE, all known constructions of sFE and FE for $\mathsf{P/Poly}$ require strong...
Oblivious transfer (OT) is a fundamental cryptographic protocol that plays a crucial role in secure multi-party computation (MPC). Most practical OT protocols by, e.g., Naor and Pinkas (SODA'01) or Chou and Orlandi (Latincrypt'15), are based on Diffie-Hellman (DH)-like assumptions and not post-quantum secure. In contrast, many other components of MPC protocols, including garbled circuits and secret sharings, are post-quantum secure. The reliance on non-post-quantum OT protocols presents a...
Garbled circuits (GC) are a secure multiparty computation protocol that enables two parties to jointly compute a function using their private data without revealing it to each other. While garbled circuits are proven secure at the protocol level, implementations can still be vulnerable to side-channel attacks. Recently, side-channel analysis of GC implementations has garnered significant interest from researchers. We investigate popular open-source GC frameworks and discover that the AES...
The success of deep learning across a variety of applications, including inference on edge devices, has led to increased concerns about the privacy of users’ data and deep learning models. Secure multiparty computation allows parties to remedy this concern, resulting in a growth in the number of such proposals and improvements in their efficiency. The majority of secure inference protocols relying on multiparty computation assume that the client does not deviate from the protocol and...
We present a new approach to garbling arithmetic circuits using techniques from homomorphic secret sharing, obtaining constructions with high rate that support free addition gates. In particular, we build upon non-interactive protocols for computing distributed discrete logarithms in groups with an easy discrete-log subgroup, further demonstrating the versatility of tools from homomorphic secret sharing. Relying on distributed discrete log for the Damgård-Jurik cryptosystem (Roy and Singh,...
Recent improvements to garbled circuits are mainly focused on reducing their size. The state-of-the-art construction of Rosulek and Roy~(Crypto~2021) requires $1.5\kappa$ bits for garbling AND gates in the free-XOR setting. This is below the previously proven lower bound $2\kappa$ in the linear garbling model of Zahur, Rosulek, and Evans~(Eurocrypt~2015). Recently, Ashur, Hazay, and Satish~(eprint 2024/389) proposed a scheme that requires $4/3\kappa O(1)$ bits for garbling AND...
Recent improvements to garbled circuits are mainly focused on reducing their size. The state-of-the-art construction of Rosulek and Roy (Crypto 2021) requires $1.5\kappa$ bits for garbling AND gates in the free-XOR setting. This is below the previously proven lower bound $2\kappa$ in the linear garbling model of Zahur, Rosulek, and Evans (Eurocrypt 2015). Whether their construction is optimal in a more inclusive model than the linear garbling model still remains open. This paper begins...
Witness encryption (WE) allows a ciphertext to be encrypted under an NP problem such that anyone holding a valid witness for that problem can decrypt it (flexible decryptors), without interaction with others (non-interaction). However, existing schemes are either impractical or achieve only a part of these WE features. We propose a novel WE scheme that 1) is based on bilinear maps such as pairings, 2) achieves the property of flexible decryptors, and 3) still requires the decryptor's...
Recent improvements to garbled circuits are mainly focused on reducing their size. The state-of-the-art construction of Rosulek and Roy (Crypto 2021) requires $1.5\kappa$ bits for garbling AND gates in the free-XOR setting. This is below the previously proven lower bound $2\kappa$ in the linear garbling model of Zahur, Rosulek, and Evans (Eurocrypt 2015). Recently, Ashur, Hazay, and Satish (eprint 2024/389) proposed a scheme that requires $4/3\kappa O(1)$ bits for garbling AND...
In the linear garbling model introduced by Zahur, Rosulek, and Evans (Eurocrypt 2015), garbling an AND gate requires at least \(2\kappa\) bits of ciphertext, where $\kappa$ is the security parameter. Though subsequent works, including those by Rosulek and Roy (Crypto 2021) and Acharya et al. (ACNS 2023), have advanced beyond these linear constraints, a more comprehensive design framework is yet to be developed. Our work offers a novel, unified, and arguably simple perspective on garbled...
Garbling schemes are one of the most fundamental objects in cryptography and have been studied extensively due to their broad applicability. The state-of-the-art is a construction in which XOR gates are free and AND gates require $3\kappa/2 \mathcal{O}(1)$ bits per gate, due to Rosulek and Roy (CRYPTO'21). An important technique in their garbling is slicing, which partitions the labels into two equal-length slices. In this paper, we explore the feasibility of the slicing technique for...
SCALES (Small Clients And Larger Ephemeral Servers) model is a recently proposed model for MPC (Acharya et al., TCC 2022). While the SCALES model offers several attractive features for practical large-scale MPC, the result of Acharya et al. only offered semi-honest secure protocols in this model. We present a new efficient SCALES protocol secure against malicious adversaries, for general Boolean circuits. We start with the base construction of Acharya et al. and design and use a suite of...
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 $\kappa$. 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...
Traditional private set intersection (PSI) involves a receiver and a sender holding sets $X$ and $Y$, respectively, with the receiver learning only the intersection $X\cap Y$. We turn our attention to its fuzzy variant, where the receiver holds \(|X|\) hyperballs of radius \(\delta\) in a metric space and the sender has $|Y|$ points. Representing the hyperballs by their center, the receiver learns the points $x\in X$ for which there exists $y\in Y$ such that $\mathsf{dist}(x,y)\leq...
The folklore approach to designing a threshold variant of symmetric cryptographic algorithms involves applying generic MPC methods to se- cret sharing techniques: the MPC first combines participant input shares using the secret sharing scheme, and then evaluates the cryptographic function on the reconstructed key. Hardening this secure against n − 1 malicious parties requires some mechanism to ensure input consistency, e.g., adding MACs to inputs, which consequently, increases the...
Two-party computation has been an active area of research since Yao's breakthrough results on garbled circuits. We present secret key additive somewhat homomorphic schemes where the client has perfect privacy (server can be computationally unbounded). Our basic scheme is additive somewhat homomorphic and we give protocols to handle addition and multiplication. In one scheme, the server handles circuit multiplication gates by returning the multiplicands to the client which does the...
Garbled Circuit (GC) techniques usually work with Boolean circuits. Despite intense interest, efficient arithmetic generalizations of GC were only known from heavy assumptions, such as LWE. We construct arithmetic garbled circuits from circular correlation robust hashes, the assumption underlying the celebrated Free XOR garbling technique. Let $\lambda$ denote a computational security parameter, and consider the integers $\mathbb{Z}_m$ for any $m \geq 2$. Let $\ell = \lceil \log_2 m...
In recent breakthrough results, novel use of garbled circuits yielded constructions for several primitives like Identity-Based Encryption (IBE) and 2-round secure multi-party computation, based on standard assumptions in public-key cryptography. While the techniques in these different results have many common elements, these works did not offer a modular abstraction that could be used across them. Our main contribution is to introduce a novel notion of obfuscation, called Reach-Restricted...
Garbling schemes allow to garble a circuit $C$ and an input $x$ such that $C(x)$ can be computed while hiding both $C$ and $x$. In the context of adaptive security, an adversary specifies the input to the circuit after seeing the garbled circuit, so that one can pre-process the garbling of $C$ and later only garble the input $x$ in the online phase. Since the online phase may be time-critical, it is an interesting question how much information needs to be transmitted in this phase and...
In this work, we introduce FANNG-MPC, a versatile secure multi-party computation framework capable to offer active security for privacy preserving machine learning as a service (MLaaS). Derived from the now deprecated SCALE-MAMBA, FANNG is a data-oriented fork, featuring novel set of libraries and instructions for realizing private neural networks, effectively reviving the popular framework. To the best of our knowledge, FANNG is the first MPC framework to offer actively secure MLaaS in the...
Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [Gentry, STOC '09; Brakerski–Vaikuntanathan, FOCS '11], there is still a significant gap in understanding related homomorphic primitives supporting all *unrestricted* polynomial-size computations. One prominent example is attribute-based encryption (ABE). The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [Gorbunov–Vaikuntanathan–Wee,...
The study of garbling arithmetic circuits is initiated by Applebaum, Ishai, and Kushilevitz [FOCS'11], which can be naturally extended to mixed circuits. The basis of mixed circuits includes Boolean operations, arithmetic operations over a large ring and bit-decomposition that converts an arithmetic value to its bit representation. We construct efficient garbling schemes for mixed circuits. In the random oracle model, we construct two garbling schemes: $\bullet$ The first scheme...
Adaptive security is a crucial property for garbling schemes in pushing the communication of garbled circuits to an offline phase when the input is unknown. In this paper, we show that the popular half-gates scheme by Zahur et al. (Eurocrypt'15), without any modification, is adaptively secure in the non-programmable random permutation model (npRPM). Since real implementations of selective-secure half-gates are already based on npRPM, our result shows that these implementations are already...
Garbled circuit techniques that are secure in the adaptive setting -- where inputs are chosen after the garbled program is sent -- are motivated by practice, but they are notoriously difficult to achieve. Prior adaptive garbling is either impractically expensive or encrypts the entire garbled program with the output of a programmable random oracle (PRO), a strong assumption. We present a simple framework for proving adaptive security of garbling schemes in the non-programmable random...
Fuzzy Password-Authenticated Key Exchange (fuzzy PAKE) allows cryptographic keys to be generated from authentication data that is both fuzzy and of low entropy. The strong protection against offline attacks offered by fuzzy PAKE opens an interesting avenue towards secure biometric authentication, typo-tolerant password authentication, and automated IoT device pairing. Previous constructions of fuzzy PAKE are either based on Error Correcting Codes (ECC) or generic multi-party computation...
Decision tree evaluation is extensively used in machine learning to construct accurate classification models. Often in the cloud-assisted communication paradigm cloud servers execute remote evaluations of classification models using clients’ data. In this setting, the need for private decision tree evaluation (PDTE) has emerged to guarantee no leakage of information for the client’s input nor the service provider’s trained model i.e., decision tree. In this paper, we propose a private...
Oblivious Pseudo-Random Functions (OPRFs) are a central tool for building modern protocols for authentication and distributed computation. For example, OPRFs enable simple login protocols that do not reveal the password to the provider, which helps to mitigate known shortcomings of password-based authentication such as password reuse or mix-up. Reliable treatment of passwords becomes more and more important as we login to a multitude of services with different passwords in our daily...
Transport Layer Security (TLS) establishes an authenticated and confidential channel to deliver data for almost all Internet applications. A recent work (Zhang et al., CCS'20) proposed a protocol to prove the TLS payload to a third party, without any modification of TLS servers, while ensuring the privacy and originality of the data in the presence of malicious adversaries. However, it required maliciously secure Two-Party Computation (2PC) for generic circuits, leading to significant...
A secret-sharing scheme enables a dealer to share a secret $s$ among $n$ parties such that only authorized subsets of parties, specified by a monotone access structure $f:\{0,1\}^n\to\{0,1\}$, can reconstruct $s$ from their shares. Other subsets of parties learn nothing about $s$. The question of minimizing the (largest) share size for a given $f$ has been the subject of a large body of work. However, in most existing constructions for general access structures $f$, the share size is not...
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...
We study secure multi-party computation (MPC) protocols for branching circuits that contain multiple sub-circuits (i.e., branches) and the output of the circuit is that of a single active branch. Crucially, the identity of the active branch must remain hidden from the protocol participants. While such circuits can be securely computed by evaluating each branch and then multiplexing the output, such an approach incurs a communication cost linear in the size of the entire circuit. To...
Trusted Execution Environments (TEEs) suffer from performance issues when executing certain management instructions, such as creating an enclave, context switching in and out of protected mode, and swapping cached pages. This is especially problematic for short-running, interactive functions in Function-as-a-Service (FaaS) platforms, where existing techniques to address enclave overheads are insufficient. We find FaaS functions can spend more time managing the enclave than executing...
The bottleneck-complexity (BC) of secure multiparty computation (MPC) protocols is a measure of the maximum number of bits which are sent and received by any party in a protocol. As the name suggests, the goal of studying BC-efficient protocols is to increase overall efficiency by making sure that the workload in the protocol is somehow "amortized'' by the protocol participants. Orlandi et al. (PKC 2022) initiated the study of BC-efficient protocols from simple assumptions in the...
Bottleneck complexity is an efficiency measure of secure multiparty computation (MPC) introduced by Boyle et al. (ICALP 2018) to achieve load-balancing. Roughly speaking, it is defined as the maximum communication complexity required by any player within the protocol execution. Since it was shown to be impossible to achieve sublinear bottleneck complexity in the number of players $n$ for all functions, a prior work constructed MPC protocols with low bottleneck complexity for specific...
Garbled circuits are a fundamental cryptographic primitive that allows two or more parties to securely evaluate an arbitrary Boolean circuit without revealing any information beyond the output using a constant number of communication rounds. Garbled circuits have been introduced by Yao (FOCS’86) and generalized to the multi-party setting by Beaver, Micali and Rogaway (STOC’90). Since then, several works have improved their efficiency by providing different garbling schemes and several...
The beautiful work of Applebaum, Ishai, and Kushilevitz [FOCS'11] initiated the study of arithmetic variants of Yao's garbled circuits. An arithmetic garbling scheme is an efficient transformation that converts an arithmetic circuit $C: \mathcal{R}^n \rightarrow \mathcal{R}^m$ over a ring $\mathcal{R}$ into a garbled circuit $\widehat C$ and $n$ affine functions $L_i$ for $i \in [n]$, such that $\widehat C$ and $L_i(x_i)$ reveals only the output $C(x)$ and no other information of $x$. AIK...
We introduce tri-state circuits (TSCs). TSCs form a natural model of computation that, to our knowledge, has not been considered by theorists. The model captures a surprising combination of simplicity and power. TSCs are simple in that they allow only three wire values ($0,1,$ and undefined - $\mathcal{Z}$) and three types of fan-in two gates; they are powerful in that their statically placed gates fire (execute) eagerly as their inputs become defined, implying orders of execution that...
We study certified everlasting secure functional encryption (FE) and many other cryptographic primitives in this work. Certified everlasting security roughly means the following. A receiver possessing a quantum cryptographic object (such as ciphertext) can issue a certificate showing that the receiver has deleted the cryptographic object and information included in the object (such as plaintext) was lost. If the certificate is valid, the security is guaranteed even if the receiver becomes...
Many applications relying on cloud storage services typically encrypt their data to ensure data privacy. However, reading or writing the encrypted data to serve client requests reveals the type of client operation to a potentially untrusted cloud. An adversary can exploit this information leak to compromise a user’s privacy by tracking read/write access patterns. Existing approaches such as Oblivious RAM (ORAM) schemes hide the type of client access by always reading and then writing the...
Garbling schemes are vital primitives for privacy-preserving protocols and secure two-party computation. In projective garbling schemes, $n$ values are assigned to each wire in the circuit. Current state-of-the-art schemes project two values. This paper presents a projective garbling scheme that assigns $2^n$ values to wires in a circuit comprising XOR and unary projection gates. A generalization of FreeXOR allows the XOR of wires with $2^n$ values to be very efficient. We then analyze the...
Due to the significant drop in prices for genome sequencing in the last decade, genome databases were constantly growing. This enabled genome analyses such as Genome-Wide Association Studies (GWAS) that study associations between a gene and a disease and allow to improve medical treatment. However, GWAS fails at the analysis of complex diseases caused by non-linear gene-gene interactions such as sporadic breast cancer or type 2 diabetes. Epistasis Analysis (EA) is a more powerful approach...
The emergence of distributed digital currencies has raised the need for a reliable consensus mechanism. In proof-of-stake cryptocur- rencies, the participants periodically choose a closed set of validators, who can vote and append transactions to the blockchain. Each valida- tor can become a leader with the probability proportional to its stake. Keeping the leader private yet unique until it publishes a new block can significantly reduce the attack vector of an adversary and improve the...
Recent works have made exciting progress on the construction of round optimal, *two-round*, Multi-Party Computation (MPC) protocols. However, most proposals so far are still complex and inefficient. In this work, we improve the simplicity and efficiency of two-round MPC in the setting with dishonest majority and malicious security. Our protocols make use of the Random Oracle (RO) and a generalization of the Oblivious Linear Evaluation (OLE) correlated randomness, called tensor OLE, over...
We consider the computation of sparse, $(\varepsilon, \delta)$-differentially private~(DP) histograms in the two-server model of secure multi-party computation~(MPC), which has recently gained traction in the context of privacy-preserving measurements of aggregate user data. We introduce protocols that enable two semi-honest non-colluding servers to compute histograms over the data held by multiple users, while only learning a private view of the data. Our solution achieves the same...
Garbling schemes, invented in the 80's by Yao (FOCS'86), have been a versatile and fundamental tool in modern cryptography. A prominent application of garbled circuits is constant round secure two-party computation, led to a long line of study of this object, where one of the most influential optimizations is Free-XOR (Kolesnikov and Schneider ICALP'08), introducing a global offset $\Delta$ for all garbled wire values where XOR gates are computed locally without garbling them. To date,...
We revisit the problem of constant-round malicious secure two-party computation by considering the use of simple correlations, namely sources of correlated randomness that can be securely generated with sublinear communication complexity and good concrete efficiency. The current state-of-the-art protocol of Katz et al. (Crypto 2018) achieves malicious security by realizing a variant of the authenticated garbling functionality of Wang et al. (CCS 2017). Given oblivious transfer...
Zero-Knowledge (ZK) proofs (ZKP) are foundational in cryptography. Most recent ZK research focuses on non-interactive proofs (NIZK) of small statements, useful in blockchain scenarios. Another line, and our focus, instead targets proofs of large statements that are useful, e.g., in proving properties of programs in ZK. We specify a zero-knowledge processor that executes arbitrary programs written in a simple instruction set and proves in ZK the correctness of the execution. Such an...
Garbled Circuit (GC) is the main practical 2PC technique, yet despite great interest in its performance, GC notoriously resists improvement. Essentially, we only know how to evaluate GC functions gate-by-gate using encrypted truth tables; given input labels, the GC evaluator decrypts the corresponding output label. Interactive protocols enjoy more sophisticated techniques. For example, we can expose to a party a (masked) private value. The party can then perform useful local computation...
Arecentlineofwork, Stacked Garbled Circuit(SGC), showed that Garbled Circuit (GC) can be improved for functions that include conditional behavior. SGC relieves the communication bottleneck of 2PC by only sending enough garbled material for a single branch out of the b total branches. Hence, communication is sublinear in the circuit size. However, both the evaluator and the generator pay in computation and perform at least factor $\log b$ extra work as compared to standard GC. We extend...
The recently proposed YOSO model is a groundbreaking approach to MPC, executable on a public blockchain, circumventing adaptive player corruption by hiding the corruption targets until they are worthless. Players are selected unpredictably from a large pool to perform MPC subtasks, in which each selected player sends a single message (and reveals their identity). While YOSO MPC has attractive asymptotic complexity, unfortunately, it is concretely prohibitively expensive due to the cost of...
In 1986, A.Yao introduced the notion of garbled circuits, designed to verify the correctness of computations performed on an untrusted server. However, correctness is guaranteed for only one input, meaning that a new garbled circuit must be created for each new input. To address this drawback, in 2010 Gennaro et al. performed the evaluation of the garbled circuit homomorphically using Fully Homomorphic Encryption scheme, allowing to reuse the same garbled circuit for new inputs. Their...
Secure multiparty computation (MPC) allows distrustful parties to jointly compute some functions while keeping their private secrets unrevealed. MPC adversaries are often categorized as semi-honest and malicious, depending on whether they follow the protocol specifications or not. Covert security was first introduced by Aumann and Lindell in 2007, which models a third type of active adversaries who cheat but can be caught with a probability. However, this probability is predefined...
We consider a scenario where two mutually distrustful parties, Alice and Bob, want to perform a payment conditioned on the outcome of some real-world event. A semi-trusted oracle (or a threshold number of oracles, in a distributed trust setting) is entrusted to attest that such an outcome indeed occurred, and only then the payment is successfully made. Such oracle-based conditional (ObC) payments are ubiquitous in many real-world applications, like financial adjudication, pre-scheduled...
Simple but mission-critical internet-based applications that require extremely high reliability, availability, and verifiability (e.g., auditability) could benefit from running on robust public programmable blockchain platforms such as Ethereum. Unfortunately, program code running on such blockchains is normally publicly viewable, rendering these platforms unsuitable for applications requiring strict privacy of application code, data, and results. In this work, we investigate using MPC...
We propose a new garbled RAM construction called NanoGRAM, which achieves an amortized cost of $\widetilde{O}(\lambda \cdot (W \log N \log^3 N))$ bits per memory access, where $\lambda$ is the security parameter, $W$ is the block size, and $N$ is the total number of blocks, and $\widetilde{O}(\cdot)$ hides $poly\log\log$ factors. For sufficiently large blocks where $W = \Omega(\log^2 N)$, our scheme achieves $\widetilde{O}(\lambda \cdot W \log N)$ cost per memory access, where the...
Publish-subscribe protocols enable real-time multi-point-to-multi-point communications for many dispersed computing systems like Internet of Things (IoT) applications. Recent interest has focused on adding processing to such publish-subscribe protocols to enable computation over real-time streams such that the protocols can provide functionalities such as sensor fusion, compression, and other statistical analysis on raw sensor data. However, unlike pure publish-subscribe protocols, which can...
At ICALP 2018, Boyle et al. introduced the notion of the bottleneck complexity of a secure multi-party computation (MPC) protocol. This measures the maximum communication complexity of any one party in the protocol, aiming to improve load-balancing among the parties. In this work, we study the bottleneck complexity of MPC in the preprocessing model, where parties are given correlated randomness ahead of time. We present two constructions of bottleneck-efficient MPC protocols, whose...
Garbled RAM (GRAM) is a powerful technique introduced by Lu and Ostrovsky that equips Garbled Circuit (GC) with a sublinear cost RAM without adding rounds of interaction. While multiple GRAM constructions are known, none are suitable for practice, due to costs that have high constants and poor scaling. We present the first GRAM suitable for practice. For computational security parameter $\kappa$ and for a size-$n$ RAM that stores blocks of size $w = \Omega(\log^2 n)$ bits, our GRAM incurs...
—Many solutions have been proposed to improve manual contact tracing for infectious diseases through automation. Privacy is crucial for the deployment of such a system as it greatly influences adoption. Approaches for digital contact tracing like Google Apple Exposure Notification (GAEN) protect the privacy of users by decentralizing risk scoring. But GAEN leaks information about diagnosed users as ephemeral pseudonyms are broadcast to everyone. To combat deanonymisation based on the time of...
Secure multiparty computation enables mutually distrusting parties to compute a public function of their secret inputs. One of the main approaches for designing MPC protocols are garbled circuits whose core component is usually referred to as a garbling scheme. In this work, we revisit the security of Yao’s garbling scheme and provide a modular security proof which composes the security of multiple layer garblings to prove security of the full circuit garbling. We perform our security proof...
We construct a simple public-coin zero-knowledge proof system solely based on symmetric primitives, from which we can apply the Fiat-Shamir heuristic to make it non-interactive. Our construction can be regarded as a simplified cut-and-choose-based malicious secure twoparty computation for the zero-knowledge functionality. Our protocol is suitable for pedagogical purpose for its simplicity (code is only 728 lines).
Schnorr's signature scheme permits an elegant threshold signing protocol due to its linear signing equation. However each new signature consumes fresh randomness, which can be a major attack vector in practice. Sources of randomness in deployments are frequently either unreliable, or require state continuity, i.e. reliable fresh state resilient to rollbacks. State continuity is a notoriously difficult guarantee to achieve in practice, due to system crashes caused by software errors,...
Yao’s garbling scheme is one of the most fundamental cryptographic constructions. Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security in the selective setting where the adversary chooses the challenge inputs before seeing the garbled circuit assuming secure symmetric-key encryption (and hence one-way functions). This was followed by results, both positive and negative, concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto 2013)...
We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size S and treewidth w with only a S^O(w) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical...
We introduce the problem of private signaling. In this problem, a sender posts a message to a certain location of a public bulletin board, and then computes a signal that allows only the intended recipient (and no one else) to learn that it is the recipient of the posted message. Besides privacy, this problem has the following crucial efficiency requirements. First, the sender and recipient do not participate in any out-of-band communication, and second, the overhead of the recipient should...
Mixing arithmetic and boolean circuits to perform privacy-preserving machine learning has become increasingly popular. Towards this, we propose a framework for the case of four parties with at most one active corruption called Tetrad. Tetrad works over rings and supports two levels of security, fairness and robustness. The fair multiplication protocol costs 5 ring elements, improving over the state-of-the-art Trident (Chaudhari et al. NDSS'20). A key feature of Tetrad is that robustness...
We describe a garbling scheme for boolean circuits, in which XOR gates are free and AND gates require communication of $1.5\kappa 5$ bits. This improves over the state-of-the-art "half-gates" scheme of Zahur, Rosulek, and Evans (Eurocrypt 2015), in which XOR gates are free and AND gates cost $2\kappa$ bits. The half-gates paper proved a lower bound of $2\kappa$ bits per AND gate, in a model that captured all known garbling techniques at the time. We bypass this lower bound with a novel...
A garbling scheme is a fundamental cryptographic building block with a long list of applications. The study of different techniques for garbling a function, towards optimizing computation and communication complexity, has been an area of active research. Most common garbling techniques work by representing each gate in the circuit as a set of ciphertexts that encrypt its truth table row-by-row. In this work we present a new garbling scheme in the random oracle (RO) model that garbles...
Secure two party computation (2PC) of arbitrary programs can be efficiently achieved using garbled circuits (GC). Until recently, it was widely believed that a GC proportional to the entire program, including parts of the program that are entirely discarded due to conditional branching, must be transmitted over a network. Recent work shows that this belief is false, and that communication proportional only to the longest program execution path suffices (Heath and Kolesnikov, CRYPTO 20,...
Zero-Knowledge (ZK) Proofs for disjunctive statements have been a focus of a long line of research. Classical results such as Cramer {\em et al.} [CRYPTO'94] and Abe {\em et al.} [AC'02] design generic compilers that transform certain classes of ZK proofs into ZK proofs for disjunctive statements. However, communication complexity of the resulting protocols in these results ends up being proportional to the complexity of proving all clauses in the disjunction. More recently, Heath {\em et...
Garbled Circuits (GCs) represent fundamental and powerful tools in cryptography, and many variants of GCs have been considered since their introduction. An important property of the garbled circuits is that they can be evaluated securely if and only if exactly 1 key for each input wire is obtained: no less and no more. In this work we study the case when: 1) some of the wire-keys are missing, but we are still interested in computing the output of the garbled circuit and 2) the evaluator of...
Existing models for non-interactive MPC cannot provide full privacy for inputs, because they inherently leak the residual function (i.e., the output of the function on the honest parties’ input together with all possible values of the adversarial inputs). For example, in any non-interactive sealed-bid auction, the last bidder can figure out what was the highest previous bid. We present a new MPC model which avoids this privacy leak. To achieve this, we utilize a blockchain in a novel way,...
We propose a novel MPC framework, Manticore, in the multiparty setting, with full threshold and semi-honest security model, supporting a combination of real number arithmetic (arithmetic shares), Boolean arithmetic (Boolean shares) and garbled circuits (Yao shares). In contrast to prior work [MZ17, MR18], Manticore never overflows, an important feature for machine learning applications. It achieves this without compromising efficiency or security. Compared to other overflow-free...
We present a secure multiparty computation (MPC) protocol based on garbled circuits which is both actively secure and supports the free-XOR technique, and which has communication complexity $O(n)$ per party. This improves on a protocol of Ben-Efraim, Lindell and Omri which only achieved passive security, without support for free-XOR. Our construction is based on a new variant of LPN-based encryption, but has the drawback of requiring a rather expensive garbling phase. To address this issue...
Contemporary libraries and frameworks that make it possible to incorporate secure multi-party computation protocols and capabilities into production software systems and applications must sometimes deliver underlying capabilities (such as logical circuit synthesis) to new kinds of environments (such as web browsers or serverless cloud computing platforms). In order to illustrate some of the benefits of addressing this challenge by building a solution from the ground up that leverages the...
In a witness encryption scheme, to decrypt a ciphertext associated with an NP statement, the decrypter takes as input a witness testifying that the statement is in the language. When the statement is not in the language, then the message is hidden. Thus far, the only provably secure constructions assume the existence of indistinguishability obfuscation (iO) and multilinear maps (MMaps). We make progress towards building polynomially efficient witness encryption for NP without resorting to...
We present a garbling scheme for quantum circuits, thus achieving a decomposable randomized encoding scheme for quantum computation. Specifically, we show how to compute an encoding of a given quantum circuit and quantum input, from which it is possible to derive the output of the computation and nothing else. In the classical setting, garbled circuits (and randomized encodings in general) are a versatile cryptographic tool with many applications such as secure multiparty computation,...
Boyle et al. (TCC 2019) proposed a new approach for secure computation in the preprocessing model building on function secret sharing (FSS), where a gate $g$ is evaluated using an FSS scheme for the related offset family $g_r(x)=g(x r)$. They further presented efficient FSS schemes based on any pseudorandom generator (PRG) for the offset families of several useful gates $g$ that arise in "mixed-mode'' secure computation. These include gates for zero test, integer comparison, ReLU, and spline...
With the advancement of the trusted execution environment (TEE) technologies, hardware-supported secure computing becomes increasingly popular due to its efficiency. During the protocol execution, typically, the players need to contact a third-party server for remote attestation, ensuring the validity of the involved trusted hardware component, such as Intel SGX, as well as the integrity of the computation result. When the hardware manufacturer is not fully trusted, sensitive information may...
Secure two party computation (2PC) of arbitrary programs can be efficiently achieved using garbled circuits (GC). The bottleneck of GC efficiency is communication. It is widely believed that for direct 2PC evaluation of a Boolean circuit, it is necessary to transmit the entire GC, including garbled truth tables corresponding to subcomputations whose output is ultimately discarded by conditional logic. This folklore belief is false. We propose a novel GC technique, stacked garbling, that...
We introduce garbled encryption, a relaxation of secret-key multi-input functional encryption (MiFE) where a function key can be used to jointly compute upon only a particular subset of all possible tuples of ciphertexts. We construct garbled encryption for general functionalities based on one-way functions. We show that garbled encryption can be used to build a self-processing private sensor data system where after a one-time trusted setup phase, sensors deployed in the field can...
Recent years have seen a tremendous growth in the interest in secure multiparty computation (MPC) and its applications. While much progress has been made concerning its efficiency, many current, state-of-the-art protocols are vulnerable to Denial of Service attacks, where a cheating party may prevent the honest parties from learning the output of the computation, whilst remaining anonymous. The security model of identifiable abort aims to prevent these attacks, by allowing honest parties to...
Protocols for secure multi-party computation are commonly composed of different sub-protocols, combining techniques such as homomorphic encryption, secret or Boolean sharing, and garbled circuits. In this paper, we design a new class of multi-party computation protocols which themselves are composed out of two-party protocols. We integrate both types of compositions, compositions of fully homomorphic encryption and garbled circuits with compositions of multi-party protocols from two-party...
Private set intersection and related functionalities are among the most prominent real-world applications of secure multiparty computation. While such protocols have attracted significant attention from the research community, other functionalities are often required to support a PSI application in practice. For example, in order for two parties to run a PSI over the unique users contained in their databases, they might first invoke on a support functionality to agree on the primary keys to...
Multi-Protocol SPDZ (MP-SPDZ) is a fork of SPDZ-2 (Keller et al., CCS '13), an implementation of the multi-party computation (MPC) protocol called SPDZ (Damgård et al., Crypto '12). MP-SPDZ extends SPDZ-2 to 34 MPC protocol variants, all of which can be used with the same high-level programming interface based on Python. This considerably simplifies comparing the cost of different protocols and security models. The protocols cover all commonly used security models (honest/dishonest...
Secure multi-party computation has been extensively studied in the past years and has reached a level that is considered practical for several applications. The techniques developed thus far have been steadily optimized for performance and were shown to be secure in the classical setting, but are not known to be secure against quantum adversaries. In this work, we start to pave the way for secure two-party computation in a quantum world where the adversary has access to a quantum computer....
Zero-knowledge (ZK) proofs receive wide attention, especially with respect to non-interactivity, small proof size, and fast verification. We instead focus on fast total proof time, in particular for large Boolean circuits. Under this metric, Garbled Circuit (GC)-based ZK, originally proposed by Jawurek et al. ([JKO], CCS 2013), remains state-of-the-art due to the low-constant linear scaling of garbling. We improve GC-ZK for proof statements with conditional clauses. Our communication is...
Machine learning has started to be deployed in fields such as healthcare and finance, which involves dealing with a lot of sensitive data. This propelled the need for and growth of privacy-preserving machine learning (PPML). We propose an actively secure four-party protocol (4PC), and a framework for PPML, showcasing its applications on four of the most widely-known machine learning algorithms -- Linear Regression, Logistic Regression, Neural Networks, and Convolutional Neural Networks. Our...
In this work, we show how to garble arithmetic circuits with full active security in the general multiparty setting, secure in the full-threshold setting (that is, when only one party is assumed honest). Our solution allows interfacing Boolean garbled circuits with arithmetic garbled circuits. Previous works in the arithmetic circuit domain focused on the 2-party setting, or on semi-honest security and assuming an honest majority -- notably, the work of Ben-Efraim (Asiacrypt 2018) in the...
We examine all of the signature submissions to Round-2 of the NIST PQC ``competition'' in the context of whether one can transform them into threshold signature schemes in a relatively straight forward manner. We conclude that all schemes, except the ones in the MQ family, have significant issues when one wishes to convert them using relatively generic MPC techniques. The lattice based schemes are hampered by requiring a mix of operations which are suited to both linear secret shared schemes...
We present modifications to the MPC system SCALE-MAMBA to enable the evaluation of garbled circuit (GC) based MPC functionalities and Linear Secret Sharing (LSSS) based MPC functionalities along side each other. This allows the user to switch between different MPC paradigms to achieve the best performance. To do this we present modifications to the GC-based MPC protocol of Hazay et al. (Asiacrypt 2017) (to enable it to support reactive computation), and combine different aspects of their...
Among numerous applications, besides cryptocurrencies, the Blockchain offers inherent properties beneficial for the management of supply chains, where data is shared between trusted and untrusted parties. Electronics supply chain serves as a prime example of such chains, where one of the major players, i.e., a foundry, can be untrusted. Hardware obfuscation techniques, namely logic locking, and IC camouflaging have been developed to mislead an adversary aiming at reverse- engineering and...
Secure Multi-party Computation (MPC) with small population and honest majority has drawn focus specifically due to customization in techniques and resulting efficiency that the constructions can offer. In this work, we investigate a wide range of security notions in the five-party setting, tolerating two active corruptions. Being constant-round, our protocols are best suited for real-time, high latency networks such as the Internet. In a minimal setting of pairwise-private channels, we...
We explore two main issues in the performance of Secure Two- Party Computation (2PC): (1) interaction of 2PC with the transport layer and (2) evaluation of 2PC implementations. Transport layer: Although significantly improved, the performance of 2PC is still prohibitive for practical systems. Contrary to the common belief that bandwidth is the remaining bottleneck for 2PC implementation, we show that the network is under-utilised due to the use of standard TCP sockets. Nevertheless, using...
Constructing Attribute Based Encryption (ABE) [SW05] for uniform models of computation from standard assumptions, is an important problem, about which very little is known. The only known ABE schemes in this setting that i) avoid reliance on multilinear maps or indistinguishability obfuscation, ii) support unbounded length inputs and iii) permit unbounded key requests to the adversary in the security game, are by Waters from Crypto, 2012 [Wat12] and its variants. Waters provided the first...
Mobile messengers like WhatsApp perform contact discovery by uploading the user's entire address book to the service provider. This allows the service provider to determine which of the user's contacts are registered to the messaging service. However, such a procedure poses significant privacy risks and legal challenges. As we find, even messengers with privacy in mind currently do not deploy proper mechanisms to perform contact discovery privately. The most promising approaches addressing...
Secure computation enables a number of players each holding a secret input value to compute a function of the inputs without revealing the inputs. It is known that secure computation is possible physically when the inputs are given as a sequence of physical cards. This research area is called card-based cryptography. One of the important problems in card-based cryptography is to minimize the number of cards and shuffles, where a shuffle is the most important (and somewhat heavy) operation in...
The $k$-Nearest Neighbor Search ($k$-NNS) is the backbone of several cloud-based services such as recommender systems, face recognition, and database search on text and images. In these services, the client sends the query to the cloud server and receives the response in which case the query and response are revealed to the service provider. Such data disclosures are unacceptable in several scenarios due to the sensitivity of data and/or privacy laws. In this paper, we introduce SANNS, a...
We show that garbled circuits are a practical choice for secure evaluation of neural network classifiers. At the protocol level, we start with the garbling scheme of Ball, Malkin & Rosulek (ACM CCS 2016) for arithmetic circuits and introduce new optimizations for modern neural network activation functions. We develop fancy-garbling, the first implementation of the BMR16 garbling scheme along with our new optimizations, as part of heavily optimized garbled-circuits tool that is driven by a...
Most modern actively-secure multiparty computation (MPC) protocols involve generating random data that is secret-shared and authenticated, and using it to evaluate arithmetic or Boolean circuits in different ways. In this work we present a generic method for converting authenticated secret-shared data between different fields, and show how to use it to evaluate so-called ``mixed'' circuits with active security and in the full-threshold setting. A mixed circuit is one in which parties...