SoK: Cryptographic Confidentiality of Data on Mobile Devices
Maximilian Zinkus, Tushar Jois, Matthew Green
PETS 2022
[preprint] [proceedings] [bibTeX]
abstract Mobile devices have become an indispensable component of modern life. Their high storage capacity gives these devices the capability to store vast amounts of sensitive personal data, which makes them a high-value target: these devices are routinely stolen by criminals for data theft, and are increasingly viewed by law enforcement agencies as a valuable source of forensic data. Over the past several years, providers have deployed a number of advanced cryptographic features intended to protect data on mobile devices, even in the strong setting where an attacker has physical access to a device. Many of these techniques draw from the research literature, but have been adapted to this entirely new problem setting. This involves a number of novel challenges, which are incompletely addressed in the literature. In this work, we outline those challenges, and systematize the known approaches to securing user data against extraction attacks. Our work proposes a methodology that researchers can use to analyze cryptographic data confidentiality for mobile devices. We evaluate the existing literature for securing devices against data extraction adversaries with powerful capabilities including access to devices and to the cloud services they rely on. We then analyze existing mobile device confidentiality measures to identify research areas that have not received proper attention from the community and represent opportunities for future research.

Order-C Secure Multiparty Computation for Highly Repetitive Circuits
Gabrielle Beck, Aarushi Goel, Abhishek Jain, Gabriel Kaptchuk
[preprint] [proceedings] [bibTeX]
abstract Running secure multiparty computation (MPC) protocols with hundreds or thousands of players would allow leveraging large volunteer networks (such as blockchains and Tor) and help justify honest majority assumptions. However, most existing protocols have at least a linear (multiplicative)dependence on the number of players, making scaling difficult. Known protocols with asymptotic efficiency independent of the number of parties (excluding additive factors) require expensive circuit transformations that induce large overheads. We observe that the circuits used in many important applications of MPC such as training algorithms used to create machine learning models have a highly repetitive structure. We formalize this class of circuits and propose an MPC protocol that achieves O(|C|) total complexity for this class. We implement our protocol and show that it is practical and outperforms O(n|C|) protocols for modest numbers of players.

Abuse Resistant Law Enforcement Access Systems
Matthew Green, Gabriel Kaptchuk, Gijs Van Laer
[preprint] [proceedings] [bibTeX]
abstract The increasing deployment of end-to-end encrypted communications services has ignited a debate between technology firms and law enforcement agencies over the need for lawful access to encrypted communications. Unfortunately, existing solutions to this problem suffer from serious technical risks, such as the possibility of operator abuse and theft of escrow key material. In this work we investigate the problem of constructing law enforcement access systems that mitigate the possibility of unauthorized surveillance. We first define a set of desirable properties for an abuse-resistant law enforcement access system (ARLEAS), and motivate each of these properties. We then formalize these definitions in the Universal Composability (UC) framework, and present two main constructions that realize this definition. The first construction enables prospective access, allowing surveillance only if encryption occurs after a warrant has been issued and activated. The second, more powerful construction, allows retrospective access to communications that occurred prior to a warrant’s issuance. To illustrate the technical challenge of constructing the latter type of protocol, we conclude by investigating the minimal assumptions required to realize these systems.

Non-Interactive Zero Knowledge from Sub-exponential DDH
Abhishek Jain, Zhengzhong Jin
[preprint] [proceedings] [bibTeX]
abstract We provide the first constructions of non-interactive zero-knowledge and Zap arguments for NP based on the sub-exponential hardness of Decisional Diffie-Hellman against polynomial time adversaries (without use of groups with pairings).

Central to our results, and of independent interest, is a new notion of interactive trapdoor hashing protocols.

Unbounded Multi-Party Computation from Learning with Errors
Prabhanjan Ananth, Abhishek Jain, Zhengzhong Jin, Giulio Malavolta
[preprint] [proceedings] [bibTeX]
abstract We consider the problem of round-optimal unbounded MPC: in the first round, parties publish a message that depends only on their input. In the second round, any subset of parties can jointly and securely compute any function f over their inputs in a single round of broadcast. We do not impose any a-priori bound on the number of parties nor on the size of the functions that can be computed.

Our main result is a semi-honest two-round protocol for unbounded MPC in the plain model from the hardness of the standard learning with errors (LWE) problem. Prior work in the same setting assumes the hardness of problems over bilinear maps. Thus, our protocol is the first example of unbounded MPC that is post-quantum secure.

The central ingredient of our protocol is a new scheme of attribute-based secure function evaluation (AB-SFE) with public decryption. Our construction combines techniques from the realm of homomorphic commitments with delegation of lattice basis. We believe that such a scheme may find further applications in the future.

Fluid MPC: Secure Multiparty Computation with Dynamic Participants
Arka Rai Choudhuri, Aarushi Goel, Matthew Green, Abhishek Jain, Gabriel Kaptchuk
[preprint] [proceedings] [bibTeX]
abstract Existing approaches to secure multiparty computation (MPC) require all participants to commit to the entire duration of the protocol. As interest in MPC continues to grow, it is inevitable that there will be a desire to use it to evaluate increasingly complex functionalities, resulting in computations spanning several hours or days.

Such scenarios call for a dynamic participation model for MPC where participants have the flexibility to go offline as needed and (re)join when they have available computational resources. Such a model would also democratize access to privacy-preserving computation by facilitating an “MPC-as-a-service” paradigm—the deployment of MPC in volunteer-operated networks (such as blockchains, where dynamism is inherent) that perform computation on behalf of clients.

In this work, we initiate the study of fluid MPC, where parties can dynamically join and leave the computation. The minimum commitment required from each participant is referred to as fluidity, measured in the number of rounds of communication that it must stay online. Our contributions are threefold:

-We provide a formal treatment of fluid MPC, exploring various possible modeling choices.

-We construct information-theoretic fluid MPC protocols in the honest-majority setting. Our protocols achieve maximal fluidity, meaning that a party can exit the computation after receiving and sending messages in one round.

-We implement our protocol and test it in multiple network settings.

Non-Interactive Batch Arguments for NP from Standard Assumptions
Arka Rai Choudhuri, Abhishek Jain, Zhengzhong Jin
[preprint] [proceedings] [bibTeX]
abstract We study the problem of designing non-interactive batch arguments for 𝖭𝖯. Such an argument system allows an efficient prover to prove multiple 𝖭P statements, with size smaller than the combined witness length.

We provide the first construction of such an argument system for 𝖭𝖯 in the common reference string model based on standard cryptographic assumptions. Prior works either require non-standard assumptions (or the random oracle model) or can only support private verification.

At the heart of our result is a new dual mode interactive batch argument system for 𝖭𝖯. We show how to apply the correlation-intractability framework for Fiat-Shamir – that has primarily been applied to proof systems – to such interactive arguments.

On Actively-Secure Elementary MPC Reductions
Benny Applebaum, Aarushi Goel
TCC 2021
[preprint] [proceedings] [bibTeX]
abstract We introduce the notion of elementary MPC reductions that allow us to securely compute a functionality $f$ by making a single call to a constant-degree “non-cryptographic” functionality $g$ without requiring any additional interaction. Roughly speaking, “non-cryptographic” means that $g$ does not make use of cryptographic primitives, though the parties can locally call such primitives.Classical

MPC results yield such elementary reductions in various cases including

the setting of passive security with full corruption threshold 𝑡<𝑛 (Yao, FOCS’86; Beaver, Micali, and Rogaway, STOC’90), the setting of full active security against a corrupted minority 𝑡<𝑛/2 (Damgård and Ishai, Crypto’05), and, for 𝖭𝖢1 functionalities, even for the setting of full active (information-theoretic) security with full corruption threshold of 𝑡<𝑛

(Ishai and Kushilevitz, FOCS’00). This leaves open the existence of an

elementary reduction that achieves full active security in the dishonest

majority setting for all efficiently computable functions.Our

main result shows that such a reduction is unlikely to exist.

Specifically, the existence of a computationally secure elementary

reduction that makes black-box use of a PRG and achieves a very weak

form of partial fairness (e.g., that holds only when the first party is

not corrupted) would allow us to realize any efficiently-computable

function by a constant-round

protocol that achieves a non-trivial notion of information-theoretic

passive security. The existence of the latter is a well-known 3-decade

old open problem in information-theoretic cryptography (Beaver, Micali,

and Rogaway, STOC’90).On the positive

side, we observe that this barrier can be bypassed under any of the

following relaxations: (1) non-black-box use of a pseudorandom

generator; (2) weaker security guarantees such as security with

identifiable abort; or (3) an additional round of communication with the

functionality $g$.

Oblivious Transfer from Trapdoor Permutations in Minimal Rounds
Arka Rai Choudhuri, Michele Ciampi, Vipul Goyal, Abhishek Jain, Rafail Ostrovsky
TCC 2021
[preprint] [proceedings] [bibTeX]
abstract Oblivious transfer (OT) is a foundational primitive within cryptography

owing to its connection with secure computation. One of the oldest

constructions of oblivious transfer was from certified

trapdoor permutations (TDPs). However several decades later, we do not

know if a similar construction can be obtained from TDPs in general.

In this work, we study the problem of constructing round optimal oblivious

transfer from trapdoor permutations. In particular, we obtain the

following new results (in the plain model) relying on TDPs in a black-box manner:

–Three-round oblivious transfer protocol that guarantees

indistinguishability-security against malicious senders (and semi-honest


– Four-round oblivious transfer protocol secure against malicious adversaries with black-box simulation-based security.

By combining our second result with an already known compiler we obtain

the first round-optimal 2-party computation protocol that relies in a

black-box way on TDPs.

A key technical tool underlying our results is a new primitive we call dual witness

encryption (DWE) that may be of independent interest.

On Communication Models and Best-Achievable Security in Two-Round MPC
Aarushi Goel, Abhishek Jain, Manoj Prabhakaran, Rajeev Raghunath
TCC 2021
[preprint] [proceedings] [bibTeX]
abstract Recently, a sequence of works have made strong advances in two-round

(i.e., round-optimal) secure multi-party computation (MPC). In the honest-majority

setting – the focus of this work – Ananth et al. [CRYPTO’18, EC’19],

Applebaum et al. [TCC’18, EC’19] and Garg et al. [TCC’18] have

established the feasibility of general two-round MPC in standard

communication models involving broadcast (BC) and private point-to-point (P2P) channels.

In this work, we set out to understand what features of the communication

model are necessary for these results, and more broadly the design of

two-round MPC. Focusing our study on the plain model – the most natural

model for honest-majority MPC – we obtain the following results:

-Dishonest majority from Honest majority: In the two round setting, honest-majority MPC and dishonest-majority MPC are surprisingly close, and often equivalent.

This follows from our results that the former implies 2-message

oblivious transfer, in many settings. (i) We show that without private

point-to-point (P2P) channels, i.e., when we use only broadcast (BC) channels, honest-majority MPC implies 2-message oblivious transfer. (ii) Furthermore, this implication holds even when we use both P2P and BC channels, provided that the MPC protocol is robust against “fail-stop” adversaries.

-Best-Achievable Security: While security with guaranteed output delivery (and even fairness) against malicious adversaries is impossible in two rounds, nothing is known with regards to the “next best” security notion, namely, security with identifiable abort (IA). We show that IA is also impossible to achieve with honest-majority even if we use both P2P and BC channels. However, if we replace P2P channels with a “bare” (i.e., untrusted) public-key infrastructure (PKI), then even security with guaranteed output delivery (and hence 𝙸𝙰) is possible to achieve.

These results “explain” that the reliance on P2P channels (together with BC) in the recent two-round protocols in the plain model was in fact necessary, and that these protocols couldn’t have achieved a stronger security guarantee, namely, 𝙸𝙰.

Overall, our results (put together with prior works) fully determine

the best-achievable security for honest-majority MPC in different

communication models in two rounds. As a consequence, they yield the

following hierarchy of communication models: BC<P2P<BC+P2P<BC+PKI.

This shows that BC channel is the weakest communication model, and that BC+PKI model is strictly stronger than BC+P2P model.

Meteor: Cryptographically Secure Steganography for Realistic Distributions
Gabriel Kaptchuk, Tushar Jois, Matthew Green, Avi Rubin
CCS 2021
[preprint] [proceedings] [bibTeX]
abstract Despite a long history of research and wide-spread applications to censorship resistant systems, prac-

tical steganographic systems capable of embedding messages into realistic communication distributions,

like text, do not exist. We identify two primary impediments to deploying universal steganography: (1)

prior work leaves the dicult problem of finding samplers for non-trivial distributions unaddressed, and

(2) prior constructions have impractical minimum entropy requirements. We investigate using genera-

tive models as steganographic samplers, as they represent the best known technique for approximating

human communication. Additionally, we study methods to overcome the entropy requirement, including

evaluating existing techniques and designing a new steganographic protocol, called Meteor. The result-

ing protocols are provably indistinguishable from honest model output and represent an important step

towards practical steganographic communication for mundane communication channels. We implement

Meteor and evaluate it on multiple computation environments with multiple generative models.

Fuzzy Message Detection
Gabrielle Beck, Julia Len, Ian Miers, Matthew Green
CCS 2021
[preprint] [proceedings] [bibTeX]
abstract Many privacy-preserving protocols employ a primitive that allows a sender to "flag" a message to a recipient's public key, such that only the recipient (who possesses the corresponding secret key) can detect that the message is intended for their use. Examples of such protocols include anonymous messaging, privacy-preserving payments, and anonymous tracing. A limitation of the existing techniques is that recipients cannot easily outsource the detection of messages to a remote server, without revealing to the server the exact set of matching messages. In this work we propose a new class of cryptographic primitives called fuzzy message detection schemes. These schemes allow a recipient to derive a specialized message detection key that can identify correct messages, while also incorrectly identifying non-matching messages with a specific and chosen false positive rate p. This allows recipients to outsource detection work to an untrustworthy server, without revealing precisely which messages belong to the receiver. We show how to construct these schemes under a variety of assumptions; describe several applications of the new technique; and show that our schemes are efficient enough to use in real applications.

SNARGs for P from LWE
Arka Rai Choudhuri, Abhishek Jain, Zhengzhong Jin
FOCS 2021
[preprint] [proceedings] [bibTeX]
abstract We provide the first construction of a succinct non-interactive

argument (SNARG) for *all* polynomial time deterministic

computations based on standard assumptions. For T

steps of computation, the size of the proof and the common

random string (CRS) as well as the verification time are

poly-logarithmic in T.

The security of our scheme relies on the hardness of the

Learning with Errors (LWE) problem against polynomial-time

adversaries. Previously, SNARGs based on standard assumptions

could support bounded-depth computations and required

sub-exponential hardness assumptions [Jawale-Kalai-Khurana-Zhang,


Along the way, we also provide the first construction of non-interactive batch arguments for NP based solely on the LWE assumption.

Breaking the O(\sqrt(n)) Bits Barrier: Byzantine Agreement with Polylog Bits per Party
Elette Boyle, Ran Cohen, Aarushi Goel
PODC 2021
[preprint] [proceedings] [bibTeX]
abstract Byzantine agreement (BA), the task of n parties to agree on one of their input bits in the face of malicious agents, is a powerful primitive that lies at the core of a vast range of distributed protocols. Interestingly, in BA protocols with the best overall communication, the demands of the parties are highly unbalanced: the amortized cost is Õ(1) bits per party, but some parties must send Ω(n) bits. In best known balanced protocols, the overall communication is sub-optimal, with each party communicating Õ(√n).

In this work, we ask whether asymmetry is inherent for optimizing total communication. In particular, is BA possible where each party communicates only Õ(1) bits? Our contributions in this line are as follows: We define a cryptographic primitive---succinctly reconstructed distributed signatures (SRDS)---that suffices for constructing Õ(1) balanced BA. We provide two constructions of SRDS from different cryptographic and Public-Key Infrastructure (PKI) assumptions. The SRDS-based BA follows a paradigm of boosting from almost-everywhere agreement to full agreement, and does so in a single round. Complementarily, we prove that PKI setup and cryptographic assumptions are necessary for such protocols in which every party sends o(n) messages. We further explore connections between a natural approach toward attaining SRDS and average-case succinct non-interactive argument systems (SNARGs) for a particular type of NP-Complete problems (generalizing Subset-Sum and Subset-Product). Our results provide new approaches forward, as well as limitations and barriers, towards minimizing per-party communication of BA. In particular, we construct the first two BA protocols with Õ(1) balanced communication, offering a tradeoff between setup and cryptographic assumptions, and answering an open question presented by King and Saia (DISC'09).

Multi-key Fully-Homomorphic Encryption in the Plain Model
Prabhanjan Ananth, Abhishek Jain, Zhengzhong Jin, Giulio Malavolta
TCC 2020
[preprint] [proceedings] [bibTeX]
abstract The notion of multi-key fully homomorphic encryption (multi-key FHE) [López-Alt, Tromer, Vaikuntanathan, STOC'12] was proposed as a generalization of fully homomorphic encryption to the multiparty setting. In a multi-key FHE scheme for $n$ parties, each party can individually choose a key pair and use it to encrypt its own private input. Given $n$ ciphertexts computed in this manner, the parties can homomorphically evaluate a circuit $C$ over them to obtain a new ciphertext containing the output of $C$, which can then be decrypted via a decryption protocol. The key efficiency property is that the size of the (evaluated) ciphertext is independent of the size of the circuit.

Multi-key FHE with one-round decryption [Mukherjee and Wichs, Eurocrypt'16], has found several powerful applications in cryptography over the past few years. However, an important drawback of all such known schemes is that they require a trusted setup.

In this work, we address the problem of constructing multi-key FHE in the plain model. We obtain the following results:

- A multi-key FHE scheme with one-round decryption based on the hardness of learning with errors (LWE), ring LWE, and decisional small polynomial ratio (DSPR) problems.

- A variant of multi-key FHE where we relax the decryption algorithm to be non-compact -- i.e., where the decryption complexity can depend on the size of $C$ -- based on the hardness of LWE. We call this variant multi-homomorphic encryption (MHE). We observe that MHE is already sufficient for some applications of multi-key FHE.

Characterizing Deterministic-Prover Zero Knowledge
Nir Bitansky, Arka Rai Choudhuri
TCC 2020
[preprint] [proceedings] [bibTeX]
abstract Randomness is typically thought to be essential for zero knowledge protocols. Following this intuition, Goldreich and Oren (Journal of Cryptology 94) proved that auxiliary-input zero knowledge cannot be achieved with a deterministic prover. On the other hand, positive results are only known in the honest-verifier setting, or when the prover is given at least a restricted source of entropy.

We prove that removing (or just bounding) the verifier's auxiliary input, deterministic-prover zero knowledge becomes feasible:

- Assuming non-interactive witness-indistinguishable proofs and subexponential indistinguishability obfuscation and one-way functions, we construct deterministic-prover zero-knowledge arguments for $\mathsf{NP}\cap \mathsf{coNP}$ against verifiers with bounded non-uniform auxiliary input.

- Assuming also keyless hash functions that are collision-resistant against bounded-auxiliary-input quasipolynomial-time attackers, we construct similar arguments for all of $\mathsf{NP}$.

Together with the result of Goldreich and Oren, this characterizes when deterministic-prover zero knowledge is feasible. We also demonstrate the necessity of strong assumptions, by showing that deterministic prover zero knowledge arguments for a given language imply witness encryption for that language. We further prove that such arguments can always be collapsed to two messages and be made laconic. These implications rely on a more general connection with the notion of predictable arguments by Faonio, Nielsen, and Venturi (PKC 17)

Round Optimal Secure Multiparty Computation from Minimal Assumptions
Arka Rai Choudhuri, Michele Ciampi, Vipul Goyal, Abhishek Jain, Rafail Ostrovsky
TCC 2020
[preprint] [proceedings] [bibTeX]
abstract We construct a four round secure multip arty computation (MPC) protocol in the plain model that achieves security against any dishonest majority. The security of our protocol relies only on the existence of four round oblivious transfer. This culminates the long line of research on constructing round-efficient MPC from minimal assumptions (at least w.r.t. black-box simulation).

Towards Efficiency-Preserving Round Compression in MPC: Do fewer rounds mean more computation?
Prabhanjan Ananth, Arka Rai Choudhuri, Aarushi Goel, Abhishek Jain
[preprint] [proceedings] [bibTeX]
abstract Reducing the rounds of interaction in secure multiparty computation (MPC) protocols has been the topic of study of many works. One popular approach to reduce rounds is to construct *round compression compilers*. A round compression compiler is one that takes a highly interactive protocol and transforms it into a protocol with far fewer rounds. The design of round compression compilers has traditionally focused on preserving the security properties of the underlying protocol and in particular, not much attention has been given towards preserving their computational and communication efficiency. Indeed, the recent round compression compilers that yield round-optimal MPC protocols incur large computational and communication overhead.

In this work, we initiate the study of *efficiency-preserving* round compression compilers, i.e. compilers that translate the efficiency benefits of the underlying highly interactive protocols to the fewer round setting. Focusing on the honest majority setting (with near-optimal corruption threshold $\frac{1}{2} - \varepsilon$, for any $\varepsilon > 0$), we devise a new compiler that yields two round (i.e., round optimal) semi-honest MPC with similar communication efficiency as the underlying (arbitrary round) protocol. By applying our compiler on the most efficient known MPC protocols, we obtain a two-round semi-honest protocol based on one-way functions, with total communication (and per-party computation) cost $\widetilde{O}(s+n^4)$ -- a significant improvement over prior two-round protocols with cost $\widetilde{O}(n^\tau s+n^{\tau+1}d)$, where $\tau\geq 2$, $s$ is the size of the circuit computing the function and $d$ the corresponding depth. Our result can also be extended to handle malicious adversaries, either using stronger assumptions in the public key infrastructure (PKI) model, or in the plain model using an extra round.

An artifact of our approach is that the resultant protocol is "unbalanced'' in the amount of computation performed by different parties. We give evidence that this is *necessary* in our setting. Our impossibility result makes novel use of the "MPC-in-the-head" paradigm which has typically been used to demonstrate feasibility results.

Self-Processing Private Sensor Data via Garbled Encryption
Nathan Manohar, Abhishek Jain, Amit Sahai
PETS 2020
[preprint] [proceedings] [bibTeX]
abstract 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 periodically broadcast encrypted readings of private data that can be computed upon by anyone holding function keys to learn processed output, without any interaction. Such a system can be used to periodically check, e.g., whether a cluster of servers are in an “alarm” state.

We implement our garbled encryption scheme and find that it performs quite well, with function evaluations in the microseconds. The performance of our scheme was tested on a standard commodity laptop.

ZEXE: Enabling Decentralized Private Computation
Sean Bowe, Alessandro Chiesa, Matthew Green, Ian Miers, Pratyush Mishra, Howard Wu
IEEE Symposium on Security and Privacy 2020
[preprint] [proceedings] [bibTeX]
abstract Ledger-based systems that support rich applications often suffer from two limitations. First, validating a transaction requires re-executing the state transition that it attests to. Second, transactions not only reveal which application had a state transition but also reveal the application's internal state.

We design, implement, and evaluate ZEXE, a ledger-based system where users can execute offline computations and subsequently produce transactions, attesting to the correctness of these computations, that satisfy two main properties. First, transactions *hide all information* about the offline computations. Second, transactions can be *validated in constant time* by anyone, regardless of the offline computation.

The core of ZEXE is a construction for a new cryptographic primitive that we introduce, *decentralized private computation* (DPC) schemes. In order to achieve an efficient implementation of our construction, we leverage tools in the area of cryptographic proofs, including succinct zero knowledge proofs and recursive proof composition. Overall, transactions in ZEXE are 968 bytes regardless of the offline computation, and generating them takes less than a minute plus a time that grows with the offline computation.

We demonstrate how to use ZEXE to realize privacy-preserving analogues of popular applications: private decentralized exchanges for user-defined fungible assets and regulation-friendly private stablecoins.

New Methods and Abstractions for RSA-Based Forward Secure Signatures
Susan Hohenberger, Brent Waters
ACNS 2020
[preprint] [proceedings] [bibTeX]
abstract We put forward a new abstraction for achieving forward-secure signatures that are (1) short, (2) have fast update and signing and (3) have

small private key size. Prior work that achieved these parameters was pioneered by the pebbling techniques of Itkis and Reyzin (CRYPTO 2001) which showed a process for generating a sequence of roots $h^{1/e_1}, h^{1/e_2}, \dots, h^{1/e_T}$ for a group element $h$ in $\mathbb{Z}_N^*$. However, the current state of the art has limitations.

First, while many works claim that Itkis-Reyzin pebbling can be applied, it is seldom shown how this non-trivial step is concretely done. Second, setting up the pebbling data structure takes $T$ time which makes key generation using this approach expensive. Third, many past works require either random oracles and/or the Strong RSA assumption; we will work in the standard model under the RSA assumption.

We introduce a new abstraction that we call an RSA sequencer. Informally, the job of an RSA sequencer is to store roots of a public key $U$, so that at time period $t$, it can provide $U^{1/e_t}$, where the value $e_t$ is an RSA exponent computed from a certain function. This separation allows us to focus on building

a sequencer that efficiently stores such values, in a forward-secure manner and with better setup times than other comparable solutions. Our sequencer abstraction

also has certain re-randomization properties that allow for constructing forward-secure signatures with a single trusted setup that takes $T$ time and individual key generation takes $\lg(T)$ time.

We demonstrate the utility of our abstraction by using it to provide concrete forward-secure signature schemes. We first give a random-oracle construction that closely matches the performance and structure of the Itkis-Reyzin scheme with the important exception that key generation is much faster (after the one-time setup). We then move on to designing a standard model scheme. This abstraction and illustration of how to use it may be useful for other future works.

We include a detailed performance evaluation of our constructions, with an emphasis on the time and space costs for large caps on the maximum number of time periods $T$ supported. Our philosophy is that frequently updating forward secure keys should be part of ``best practices'' in key maintenance. To make this practical, even for bounds as high as $T=2^{32}$, we show that after an initial global setup, it takes only seconds to generate a key pair, and only milliseconds to update keys, sign messages and verify signatures. The space requirements for the public parameters and private keys are also a modest number of kilobytes, with signatures being a single element in $\mathbb{Z}_N$ and one smaller value.

Chosen Ciphertext Security from Injective Trapdoor Functions
Susan Hohenberger, Venkata Koppula, Brent Waters
[preprint] [proceedings] [bibTeX]
abstract We provide a construction of chosen ciphertext secure public-key encryption from (injective) trapdoor functions. Our construction is black box and assumes no special properties (e.g. ``lossy'', ``correlated product secure'') of the trapdoor function.

The Round Complexity of Secure Computation Against Covert Adversaries
Arka Rai Choudhuri, Vipul Goyal, Abhishek Jain
SCN 2020
[preprint] [proceedings] [bibTeX]
abstract We investigate the exact round complexity of secure multiparty computation (MPC) against *covert* adversaries who may attempt to cheat, but do not wish to be caught doing so. Covert adversaries lie in between semi-honest adversaries who follow protocol specification and malicious adversaries who may deviate arbitrarily.

Recently, two round protocols for semi-honest MPC and four round protocols for malicious-secure MPC were constructed, both of which are optimal. While these results can be viewed as constituting two end points of a security spectrum, we investigate the design of protocols that potentially span the spectrum.

Our main result is an MPC protocol against covert adversaries with variable round complexity: when the detection probability is set to the lowest setting, our protocol requires two rounds and offers same security as semi-honest MPC. By increasing the detecting probability, we can increase the security guarantees, with round complexity five in the extreme case. The security of our protocol is based on standard cryptographic assumptions.

We supplement our positive result with a negative result, ruling out *strict* three round protocols with respect to black-box simulation.

BlockSci: Design and applications of a blockchain analysis platform
Harry Kalodner, Malte Möser, and Kevin Lee, Steven Goldfeder, Martin Plattner, Alishah Chator, Arvind Narayanan
Usenix Security 2020
[preprint] [proceedings] [bibTeX]
abstract Analysis of blockchain data is useful for both scientific research and commercial applications. We present BlockSci, an open-source software platform for blockchain analysis. BlockSci is versatile in its support for different blockchains and analysis tasks. It incorporates an in-memory, analytical (rather than transactional) database, making it orders of magnitudes faster than using general-purpose graph databases. We describe BlockSci's design and present four analyses that illustrate its capabilities, shedding light on the security, privacy, and economics of cryptocurrencies.

Automating the Development of Chosen Ciphertext Attacks
Gabrielle Beck, Maximilian Zinkus, Matthew Green
Usenix Security 2020
[preprint] [proceedings] [bibTeX]
abstract In this work we investigate the problem of automating the development of adaptive chosen ciphertext attacks on systems that contain vulnerable format oracles. Unlike pre- vious attempts, which simply automate the execution of known attacks, we consider a more challenging problem: to programmatically derive a novel attack strategy, given only a machine-readable description of the plaintext veri- fication function and the malleability characteristics of the encryption scheme. We present a new set of algorithms that use SAT and SMT solvers to reason deeply over the design of the system, producing an automated attack strategy that can entirely decrypt protected messages. Developing our algorithms required us to adapt techniques from a diverse range of research fields, as well as to explore and develop new ones. We implement our algorithms using existing theory solvers. The result is a practical tool called Delphinium that succeeds against real-world and contrived format oracles. To our knowledge, this is the first work to automatically derive such complex chosen ciphertext attacks.

Statistical Zaps and New Oblivious Transfer Protocols
Vipul Goyal, Abhishek Jain, Zhengzhong Jin, Giulio Malavolta
[preprint] [proceedings] [bibTeX]
abstract We study the problem of achieving statistical privacy in interactive proof systems and oblivious transfer – two of the most well studied two-party protocols – when limited rounds of interaction are available.

- Statistical Zaps: We give the first construction of statistical Zaps, namely, two-round statistical witness-indistinguishable (WI) protocols with a public-coin verifier. Our construction achieves computational soundness based on the quasi-polynomial hardness of learning with errors assumption.

- Three-Round Statistical Receiver-Private Oblivious Transfer: We give the first construction of a three-round oblivious transfer (OT) protocol – in the plain model – that achieves statistical privacy for receivers and computational privacy for senders against malicious adversaries, based on polynomial-time assumptions. The round-complexity of our protocol is optimal.

We obtain our first result by devising a public-coin approach to compress sigma protocols, without relying on trusted setup. To obtain our second result, we devise a general framework via a new notion of statistical hash commitments that may be of independent interest.

The Broadcast Message Complexity of Secure Multiparty Computation
Sanjam Garg, Aarushi Goel, Abhishek Jain
[preprint] [proceedings] [bibTeX]
abstract We study the broadcast message complexity of secure multiparty computation (MPC), namely, the total number of messages that are required for securely computing any functionality in the broadcast model of communication.

MPC protocols are traditionally designed in the simultaneous broadcast model, where each round consists of every party broadcasting a message to the other parties. We show that this method of communication is sub-optimal; specifically, by eliminating simultaneity, it is, in fact, possible to reduce the broadcast message complexity of MPC.

More specifically, we establish tight lower and upper bounds on the broadcast message complexity of $n$-party MPC for every $t<n$ corruption threshold, both in the plain model as well as common setup models. For example, our results show that the optimal broadcast message complexity of semi-honest MPC can be much lower than 2n, but necessarily requires at least three rounds of communication. We also extend our results to the malicious setting in setup models.

UC-Secure Multiparty Computation from One-Way Functions using Stateless Tokens
Saikrishna Badrinarayanan, Abhishek Jain, Rafail Ostrovsky, Ivan Visconti
[preprint] [proceedings] [bibTeX]
abstract We revisit the problem of universally composable (UC) secure multiparty computation in the stateless hardware token model.

- We construct a three round multi-party computation protocol for general functions based on one-way functions where each party sends two tokens to every other party. Relaxing to the two-party case, we also construct a two round protocol based on one-way functions where each party sends a single token to the other party, and at the end of the protocol, both parties learn the output.

- One of the key components in the above constructions is a new two-round oblivious transfer protocol based on one-way functions using only one token, which can be reused an unbounded polynomial number of times.

All prior constructions required either stronger complexity assumptions, or larger number of rounds, or a larger number of tokens.

Public-Key Function-Private Hidden Vector Encryption (and More)
James Bartusek, Brent Carmer, Abhishek Jain, Zhengzhong Jin, Tancrède Lepoint, Fermi Ma, Tal Malkin, Alex Malozemoff, Mariana Raykova
[preprint] [proceedings] [bibTeX]
abstract We construct public-key function-private predicate encryption for the ``small superset functionality,'' recently introduced by Beullens and Wee (PKC 2019). This functionality captures several important classes of predicates:

- Point functions. For point function predicates, our construction is equivalent to public-key function-private anonymous identity-based encryption.

- Conjunctions. If the predicate computes a conjunction, our construction is a public-key function-private hidden vector encryption scheme. This addresses an open problem posed by Boneh, Raghunathan, and Segev (ASIACRYPT 2013).

- $d$-CNFs and read-once conjunctions of $d$-disjunctions for constant-size $d$.

Our construction extends the group-based obfuscation schemes of Bishop et al. (CRYPTO 2018), Beullens and Wee (PKC 2019), and Bartusek et al. (EUROCRYPT 2019) to the setting of public-key function-private predicate encryption. We achieve an average-case notion of function privacy, which guarantees that a decryption key $\mathsf{sk}_f$ reveals nothing about $f$ as long as $f$ is drawn from a distribution with sufficient entropy. We formalize this security notion as a generalization of the (enhanced) real-or-random function privacy definition of Boneh, Raghunathan, and Segev (CRYPTO 2013). Our construction relies on bilinear groups, and we prove security in the generic bilinear group model.

Interactive Non-Malleable Codes
Nils Fleishhacker, Abhishek Jain, Vipul Goyal, Anat Paskin-Cherniavsky, Slava Radune
TCC 2019
[preprint] [proceedings] [bibTeX]
abstract Non-malleable codes (NMC) introduced by Dziembowski et al. [ICS’10] allow one to encode “passive” data in such a manner that when a codeword is tampered, the original data either remains completely intact or is essentially destroyed.

In this work, we initiate the study of interactive non-malleable codes (INMCs) that allow for encoding “active communication” rather than passive data. An INMC allows two parties to engage in an interactive protocol such that an adversary who is able to tamper with the protocol messages either leaves the original transcript intact (i.e., the parties are able to reconstruct the original transcript) or the transcript is completely destroyed and replaced with an unrelated one.

We formalize a tampering model for interactive protocols and put forward the notion of INMCs. Since constructing INMCs for general adversaries is impossible (as in the case of non-malleable codes), we construct INMCs for several specific classes of tampering functions. These include bounded state, split state, and fragmented sliding window tampering functions. We also obtain lower bounds for threshold tampering functions via a connection to interactive coding. All of our results are unconditional.

Are These Pairing Elements Correct?: Automated Verification and Applications
Susan Hohenberger, Satyanarayana Vusirikala
CCS 2019
[preprint] [proceedings] [bibTeX]
abstract Using a set of pairing product equations (PPEs) to verify the correctness of an untrusted set of pairing elements with respect to another set of trusted elements has numerous cryptographic applications. These include the design of basic and structure-preserving signature schemes, building oblivious transfer schemes from “blind” IBE, finding new verifiable random functions and keeping the IBE/ABE authority “accountable” to the user.

A natural question to ask is: are all trusted-untrusted pairing element groups in the literature PPE testable? We provide original observations demonstrating that the answer is no, and moreover, it can be non-trivial to determine whether or not there exists a set of PPEs that can verify some pairing elements with respect to others. Many IBE schemes have PPE-testable private keys (with respect to the public parameters), while others, such as those based on dual-system encryption, provably do not.

To aid those wishing to use PPE-based element verification in their cryptosystems, we devised rules to systematically search for a set of PPEs that can verify untrusted elements with respect to a set of trusted elements. We prove the correctness of each rule and combine them into a main searching algorithm for which we also prove correctness. We implemented this algorithm in a new software tool, called AutoPPE. Tested on over two dozen case studies, AutoPPE found a set of PPEs (on schemes where they exist) usually in just a matter of seconds. This work represents an important step towards the larger goal of improving the speed and accuracy of pairing-based cryptographic design via computer automation.

Finding a Nash Equilibrium is No Easier than Breaking Fiat-Shamir
Arka Rai Choudhuri, Pavel Hubáček, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum
STOC 2019
[preprint] [proceedings] [bibTeX]
abstract The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.

We show that solving the End-of-Metered-Line problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD.

Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n).

Combining our construction with a hash family proposed by Canetti et al. [STOC 2019] gives rise to a distribution in the class CLS, which is provably hard under the assumption that any one of a class of fully homomorphic encryption (FHE) schemes has almost-optimal security against quasi-polynomial time adversaries, and under the additional worst-case assumption that there is no polynomial time algorithm for counting the number of satisfying assignments for formulas over a polylogarithmic number of variables.

Founding Secure Computation on Blockchains
Arka Rai Choudhuri, Vipul Goyal, Abhishek Jain
[preprint] [proceedings] [bibTeX]
abstract We study the foundations of secure computation in the blockchain-hybrid model, where a blockchain -- modeled as a global functionality -- is available as an Oracle to all the participants of a cryptographic protocol. We demonstrate both destructive and constructive applications of blockchains:

- We show that classical rewinding-based simulation techniques used in many security proofs fail against blockchain-active adversaries that have read and post access to a global blockchain. In particular, we show that zero-knowledge (ZK) proofs with black-box simulation are impossible against blockchain-active adversaries.

- Nevertheless, we show that achieving security against blockchain-active adversaries is possible if the honest parties are also blockchain active. We construct an $\omega(1)$-round ZK protocol with black-box simulation. We show that this result is tight by proving the impossibility of constant-round ZK with black-box simulation.

- Finally, we demonstrate a novel application of blockchains to overcome the known impossibility results for concurrent secure computation in the plain model. We construct a concurrent self-composable secure computation protocol for general functionalities in the blockchain-hybrid model based on standard cryptographic assumptions.

We develop a suite of techniques for constructing secure protocols in the blockchain-hybrid model that we hope will find applications to future research in this area.

Two Round Information-Theoretic MPC with Malicious Security
Prabhanjan Ananth, Arka Rai Choudhuri, Aarushi Goel, Abhishek Jain
[preprint] [proceedings] [bibTeX]
abstract We provide the first constructions of two round information-theoretic (IT) secure multiparty computation (MPC) protocols in the plain model that tolerate any $t<n/2$ malicious corruptions. Our protocols satisfy the strongest achievable standard notions of security in two rounds in different communication models. Previously, IT-MPC protocols in the plain model either required a larger number of rounds, or a smaller minority of corruptions.

Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes
Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu
ICALP 2019
[preprint] [proceedings] [bibTeX]
abstract Document exchange and error correcting codes are two fundamental problems regarding communications. In the first problem, Alice and Bob each holds a string, and the goal is for Alice to send a short sketch to Bob, so that Bob can recover Alice's string. In the second problem, Alice sends a message with some redundant information to Bob through a channel that can add adversarial errors, and the goal is for Bob to correctly recover the message despite the errors.

In a recent work [CJLW18], the authors constructed explicit deterministic document exchange protocols and binary error correcting codes for edit errors with almost optimal parameters. Unfortunately, the constructions in [CJLW18] do not work for other common errors such as block transpositions.

In this paper, we generalize the constructions in \cite{CJLW18} to handle a much larger class of errors. These include bursts of insertions and deletions, as well as block transpositions. Specifically, we consider document exchange and error correcting codes where the total number of block insertions, block deletions, and block transpositions is at most $k≤\alpha n/\log n$ for some constant $0<\alpha<1$. In addition, the total number of bits inserted and deleted by the first two kinds of operations is at most $t≤\beta n$ for some constant $0<\beta<1$, where $n$ is the length of Alice's string or message. We construct explicit, deterministic document exchange protocols with sketch size $O((k \log n+t)\log^2\frac{n}{k\log n+t})$ and explicit binary error correcting code with $O(k\log n\log\log\log n+t)$ redundant bits.

Generic and Practical Key Establishment from Lattice
Zhengzhong Jin, Yunlei Zhao
ACNS 2019
[preprint] [proceedings] [bibTeX]
abstract In this work, we abstract some key ingredients in previous key establishment and public-key encryption schemes from LWE and its variants. Specifically, we explicitly formalize the building tool, referred to as key consensus (KC) and its asymmetric variant AKC. KC and AKC allow two communicating parties to reach consensus from close values, which plays the fundamental role in lattice-based cryptography. We then prove the upper bounds on parameters for any KC and AKC, which reveal the inherent constraints on the parameters among security, bandwidth, error probability, and consensus range. As a conceptual contribution, this simplifies the design and analysis of these cryptosystems in the future. Guided by the proved upper bounds, we design and analyze both generic and highly practical KC and AKC schemes, which are referred to as OKCN and AKCN respectively for presentation simplicity. We present a generic protocol structure for key establishment from learning with rounding (LWR), which can be instantiated with either KC or AKC. We then provide an analysis breaking the correlation between the rounded deterministic noise and the secret, and design an algorithm to calculate the error probability numerically. When applied to LWE-based key establishment, OKCN and AKCN can result in more practical or well-balanced schemes, compared to existing LWE-based protocols in the literature.

Giving State to the Stateless: Augmenting Trustworthy Computation with Ledgers
Gabriel Kaptchuk, Ian Miers, Matthew Green
NDSS 2019
[preprint] [proceedings] [bibTeX]
abstract In this work we investigate the problem of achieving secure computation by combining stateless trusted devices with public ledgers. We consider a hybrid paradigm in which a client-side device (such as a co-processor or trusted enclave) performs secure computation, while interacting with a public ledger via a possibly malicious host computer. We explore both the constructive and potentially destructive implications of such systems. We first show that this combination allows for the construction of stateful interactive functionalities (including general computation) even when the device has no persistent storage; this allows us to build sophisticated applications using inexpensive trusted hardware or even pure cryptographic obfuscation techniques. We further show how to use this paradigm to achieve censorship-resistant communication with a network, even when network communications are mediated by a potentially malicious host. Finally we describe a number of practical applications that can be achieved today. These include the synchronization of private smart contracts; rate limited mandatory logging; strong encrypted backups from weak passwords; enforcing fairness in multi-party computation; and destructive applications such as autonomous ransomware, which allows for payments without an online party.

Non-Interactive Secure Computation from One-Way Functions
Saikrishna Badrinarayanan, Abhishek Jain, Rafail Ostrovsky, Ivan Visconti
[preprint] [proceedings] [bibTeX]
abstract The notion of non-interactive secure computation (NISC) first introduced in the work of Ishai et al. [EUROCRYPT 2011] studies the following problem: Suppose a receiver $R$ wishes to publish an encryption of her secret input $y$ so that any sender $S$ with input $x$ can then send a message $m$ that reveals $f(x,y)$ to $R$ (for some function $f$). Here, $m$ can be viewed as an encryption of $f(x,y)$ that can be decrypted by $R$. NISC requires security against both malicious senders and receivers, and also requires the receiver's message to be reusable across multiple computations (w.r.t. a fixed input of the receiver).

All previous solutions to this problem necessarily rely upon OT (or specific number-theoretic assumptions) even in the common reference string model or the random oracle model or to achieve weaker notions of security such as super-polynomial-time simulation.

In this work, we construct a NISC protocol based on the minimal assumption of one way functions, in the stateless hardware token model. Our construction achieves UC security and requires a single token sent by the receiver to the sender.

Practical State Recovery Attacks against Legacy RNG Implementations
Shaanan N. Cohney, Matthew Green, Nadia Heninger
CCS 2018
[preprint] [proceedings] [bibTeX]
abstract The ANSI X9.17/X9.31 pseudorandom number generator design was first standardized in 1985, with variants incorporated into numerous cryptographic standards over the next three decades. The design uses timestamps together with a statically keyed block cipher to produce pseudo-random output. It has been known since 1998 that the key must remain secret in order for the output to be secure. However, neither the FIPS 140-2 standardization process nor NIST's later descriptions of the algorithm specified any process for key generation.

We performed a systematic study of publicly available FIPS 140- 2 certifications for hundreds of products that implemented the ANSI X9.31 random number generator, and found twelve whose certification documents use of static, hard-coded keys in source code, leaving the implementation vulnerable to an attacker who can learn this key from the source code or binary. In order to demonstrate the practicality of such an attack, we develop a full passive decryption attack against FortiGate VPN gateway products using FortiOS v4 that recovers the private key in seconds. We measure the prevalence of this vulnerability on the visible Internet using active scans, and demonstrate state recovery and full private key recovery in the wild. Our work highlights the extent to which the validation and certification process has failed to provide even modest security guarantees.

Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors
Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu
FOCS 2018
[preprint] [proceedings] [bibTeX]
abstract We study two basic problems regarding edit error, i.e. document exchange and error correcting codes for edit errors (insdel codes). For message length $n$ and edit error upper bound $k$, it is known that in both problems the optimal sketch size or the optimal number of redundant bits is $\Theta(k \log \frac{n}{k})$. However, known constructions are far from achieving these bounds.

We significantly improve previous results on both problems. For document exchange, we give an efficient deterministic protocol with sketch size $O(k\log^2 \frac{n}{k})$. This significantly improves the previous best known deterministic protocol, which has sketch size $O(k^2 + k \log^2 n)$ (Belazzougui15). For binary insdel codes, we obtain the following results:

1. An explicit binary insdel code which encodes an $n$-bit message $x$ against $k$ errors with redundancy $O(k \log^2 \frac{n}{k})$. In particular this implies an explicit family of binary insdel codes that can correct $\varepsilon$ fraction of insertions and deletions with rate $1-O(\varepsilon \log^2 (\frac{1}{\varepsilon}))=1-\widetilde{O}(\varepsilon)$.

2. An explicit binary insdel code which encodes an $n$-bit message $x$ against $k$ errors with redundancy $O(k \log n)$. This is the first explicit construction of binary insdel codes that has optimal redundancy for a wide range of error parameters $k$, and this brings our understanding of binary insdel codes much closer to that of standard binary error correcting codes.

In obtaining our results we introduce the notion of \emph{$\varepsilon$-self matching hash functions} and \emph{$\varepsilon$-synchronization hash functions}. We believe our techniques can have further applications in the literature.

Round-Optimal Secure Multiparty Computation with Honest Majority
Prabhanjan Ananth, Arka Rai Choudhuri, Aarushi Goel, Abhishek Jain
[preprint] [proceedings] [bibTeX]
abstract We study the exact round complexity of secure multiparty computation (MPC) in the honest majority setting. We construct several round-optimal n-party protocols, tolerating any $t< \frac{n}{2}$ corruptions.

- Security with abort: We give the first construction of two round MPC for general functions that achieves security with abort against malicious adversaries in the plain model. The security of our protocol only relies on one-way functions.

- Guaranteed output delivery: We also construct protocols that achieve security with guaranteed output delivery: (i) Against fail-stop adversaries, we construct two round MPC either in the (bare) public-key infrastructure model with no additional assumptions, or in the plain model assuming two-round semi-honest oblivious transfer. In three rounds, however, we can achieve security assuming only one-way functions. (ii) Against malicious adversaries, we construct three round MPC in the plain model, assuming public-key encryption and Zaps. Previously, such protocols were only known based on specific learning assumptions and required the use of common reference strings.

All of our results are obtained via general compilers that may be of independent interest.

Promise Zero Knowledge and its Applications to Round-Optimal MPC
Saikrishna Badrinarayanan, Vipul Goyal, Abhishek Jain, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai
[preprint] [proceedings] [bibTeX]
abstract We devise a new partitioned simulation technique for MPC where the simulator uses different strategies for simulating the view of aborting adversaries and non-aborting adversaries. The protagonist of this technique is a new notion of promise zero knowledge (ZK) where the ZK property only holds against non-aborting verifiers. We show how to realize promise ZK in three rounds in the simultaneous-message model assuming polynomially hard DDH (or QR or $N^{th}$-Residuosity).

We demonstrate the following applications of our new technique:

- We construct the first round-optimal (i.e., four round) MPC protocol for general functions based on polynomially hard DDH (or QR or $N^{th}$-Residuosity).

- We further show how to overcome the four-round barrier for MPC by constructing a three-round protocol for ``list coin-tossing'' -- a slight relaxation of coin-tossing that suffices for most conceivable applications -- based on polynomially hard DDH (or QR or $N^{th}$-Residuosity). This result generalizes to randomized input-less functionalities.

Previously, four round MPC protocols required sub-exponential-time hardness assumptions and no multi-party three-round protocols were known for any relaxed security notions with polynomial-time simulation against malicious adversaries.

In order to base security on polynomial-time standard assumptions, we also rely upon a leveled rewinding security technique that can be viewed as a polynomial-time alternative to leveled complexity leveraging for achieving ``non-malleability'' across different primitives.

The Bottleneck Complexity of Secure Multiparty Computation
Elette Boyle, Abhishek Jain, Manoj Prabhakaran, Ching-Hua Yu
ICALP 2018
[preprint] [proceedings] [bibTeX]
abstract In this work, we initiate the study of bottleneck complexity as a new communication efficiency measure for secure multiparty computation (MPC). Roughly, the bottleneck complexity of an MPC protocol is defined as the maximum communication complexity required by any party within the protocol execution.

We observe that even without security, bottleneck communication complexity is an interesting measure of communication complexity for (distributed) functions and propose it as a fundamental area to explore. While achieving $O(n)$ bottleneck complexity (where n is the number of parties) is straightforward, we show that: (1) achieving sublinear bottleneck complexity is not always possible, even when no security is required. (2) On the other hand, several useful classes of functions do have $o(n)$ bottleneck complexity, when no security is required.

Our main positive result is a compiler that transforms any (possibly insecure) efficient protocol with fixed communication-pattern for computing any functionality into a secure MPC protocol while preserving the bottleneck complexity of the underlying protocol (up to security parameter overhead). Given our compiler, an efficient protocol for any function $f$ with sublinear bottleneck complexity can be transformed into an MPC protocol for $f$ with the same bottleneck complexity.

Along the way, we build cryptographic primitives - incremental fully-homomorphic encryption, succinct non-interactive arguments of knowledge with ID-based simulation-extractability property and verifiable protocol execution - that may be of independent interest.

On the Existence of Three Round Zero-Knowledge Proofs
Nils Fleischhacker, Vipul Goyal, Abhishek Jain
[preprint] [proceedings] [bibTeX]
abstract We study the round complexity of zero-knowledge (ZK) proof systems. While five round ZK proofs for NP are known from standard assumptions [Goldreich-Kahan, J. Cryptology'96], Katz [TCC'08] proved that four rounds are insufficient for this task w.r.t. black-box simulation.

In this work, we study the feasibility of ZK proofs using non-black-box simulation. Our main result is that three round private-coin ZK proofs for NP do not exist (even w.r.t. non-black-box simulation), under certain assumptions on program obfuscation. Our approach builds upon the recent work of Kalai et al. [Crypto'17] who ruled out constant round public-coin ZK proofs under the same assumptions as ours.

Synchronized Aggregate Signatures from the RSA Assumption
Susan Hohenberger, Brent Waters
[preprint] [proceedings] [bibTeX]
abstract In this work we construct efficient aggregate signatures from the RSA assumption in the synchronized setting. In this setting, the signing algorithm takes as input a (time) period $t$ as well the secret key and message. A signer should sign at most once for each $t$. A set of signatures can be aggregated so long as they were all created for the same period $t$. Synchronized aggregate signatures are useful in systems where there is a natural reporting period such as log and sensor data, or for signatures embedded in a blockchain protocol where the creation of an additional block is a natural synchronization event.

We design a synchronized aggregate signature scheme that works for a bounded number of periods $T$ that is given as a parameter to a global system setup. The big technical question is whether we can create solutions that will perform well with the large $T$ values that we might use in practice. For instance, if one wanted signing keys to last up to ten years and be able to issue signatures every second, then we would need to support a period bound of upwards of $2^{28}$.

We build our solution in stages where we start with an initial solution that establishes feasibility, but has an impractically large signing time where the number of exponentiations and prime searches grows linearly with $T$. We prove this scheme secure in the standard model under the RSA assumption with respect to honestly-generated keys. We then provide a tradeoff method where one can tradeoff the time to create signatures with the space required to store private keys. One point in the tradeoff is where each scales with $\sqrt{T}$.

Finally, we reach our main innovation which is a scheme where both the signing time and storage scale with $\lg{T}$ which allows for us to keep both computation and storage costs modest even for large values of $T$. Conveniently, our final scheme uses the same verification algorithm, and has the same distribution of public keys and signatures as the first scheme. Thus we are able to recycle the existing security proof for the new scheme.

We also show how to extend our results to the identity-based setting in the random oracle model, which can further reduce the overall cryptographic overhead. We conclude with a detailed evaluation of the signing time and storage requirements for various practical settings of the system parameters.

How to Squeeze a Crowd: Reducing Bandwidth in Mixing Cryptocurrencies
Alishah Chator, Matthew Green
IEEE S&B 2018
[preprint] [proceedings] [bibTeX]
abstract Several popular cryptocurrencies incorporate privacy features that “mix” real transactions with cover traffic in order to obfuscate the public transaction graph. The underlying protocols, which include CryptoNote and Monero’s RingCT, work by first identifying a real transaction output (TXO), sampling a number of cover outputs, and transmitting the entire resulting set to verifiers, along with a zero knowledge (or WI) proof that hides the identity of the real transaction. Unfortunately, many of these schemes suffer from a practical limitation: the description of the combined input set grows linearly with size of the anonymity set.

In this work we propose a simple technique for efficiently sampling cover traffic from a finite (and public) set of known values, while deriving a compact description of the resulting transaction set. This technique, which is based on programmable hash functions, allows us to dramatically reduce transaction bandwidth when large cover sets are used. We refer to our construction as a recoverable sampling scheme, and note that it may be of independent interest for other privacy applications. We present formal security definitions; prove our constructions secure; and show how these constructions can be integrated with various currencies and different cover sampling distributions.

Don’t Talk to Strangers: On the Challenges of Intelligent Vehicle Authentication
Alishah Chator, Matthew Green
[preprint] [proceedings] [bibTeX]
abstract Vehicle-to-vehicle (V2V) communications offer an unprecedented opportunity to increase driver safety. At the same time, the use of computer networking technologies raises new concerns around information security and privacy. Specifically, V2V communications systems provide the opportunity for malicious individuals to transmit false data, with unknown effects on future vehicle systems. A number of proposals have been advanced in order to add authenticity guarantees to V2V systems using cryptographic techniques. Unfortunately, many of these proposals have a number of side effects related to efficiency and driver privacy. In this work we discuss these tradeoffs and explain why it is challenging to achieve all desired properties in a single system. We then suggest alternative approaches that may be more realistic than current proposals.

Non-Interactive Multiparty Computation without Correlated Randomness
Shai Halevi, Yuval Ishai, Abhishek Jain, Ilan Komargodski, Amit Sahai, Eylon Yogev
[preprint] [proceedings] [bibTeX]
abstract We study the problem of non-interactive multiparty computation (NI-MPC) where a group of completely asynchronous parties can evaluate a function over their joint inputs by sending a single message to an evaluator who computes the output. Previously, the only general solutions to this problem that resisted collusions between the evaluator and a set of parties were based on multi-input functional encryption and required the use of complex correlated randomness setup.

In this work, we present a new solution for NI-MPC against arbitrary collusions using a public-key infrastructure (PKI) setup supplemented with a common random string. A PKI is, in fact, the minimal setup that one can hope for in this model in order to achieve a meaningful ``best possible'' notion of security, namely, that an adversary that corrupts the evaluator and an arbitrary set of parties only learns the residual function obtained by restricting the function to the inputs of the uncorrupted parties. Our solution is based on indistinguishability obfuscation and DDH both with sub-exponential security. We extend this main result to the case of general interaction patterns, providing the above best possible security that is achievable for the given interaction.

Our main result gives rise to a novel notion of (public-key) multiparty obfuscation, where $n$ parties can independently obfuscate program modules $M_i$ such that the obfuscated modules, when put together, exhibit the functionality of the program obtained by ``combining'' the underlying modules $M_i$. This notion may be of independent interest.

A Generic Approach to Constructing and Proving Verifiable Random Functions
Rishab Goyal, Susan Hohenberger, Venkata Koppula, Brent Waters
TCC 2017
[preprint] [proceedings] [bibTeX]
abstract Verifiable Random Functions (VRFs) as introduced by Micali, Rabin and Vadhan are a special form of Pseudo Random Functions (PRFs) wherein a secret key holder can also prove validity of the function evaluation relative to a statistically binding commitment. Prior works have approached the problem of constructing VRFs by proposing a candidate under specific number theoretic setting --- mostly in bilinear groups --- and then grapple with the challenges of proving security in the VRF environments. These constructions achieved different results and tradeoffs in practical efficiency, tightness of reductions and cryptographic assumptions.

In this work we take a different approach. Instead of tackling the VRF problem as a whole we demonstrate a simple and generic way of building Verifiable Random Functions from more basic and narrow cryptographic primitives. Then we can turn to exploring solutions to these primitives with a more focused mindset. In particular, we show that VRFs can be constructed generically from the ingredients of: (1) a 1-bounded constrained pseudo random function for a functionality that is ``admissible hash friendly" , (2) a non-interactive statistically binding commitment scheme (without trusted setup) and (3) a non-interactive witness indistinguishable proofs or NIWIs. The first primitive can be replaced with a more basic puncturable PRF constraint if one is willing to settle for selective security or assume sub-exponential hardness of assumptions.

In the second half of our work we support our generic approach by giving new constructions of the underlying primitives. We first provide new constructions of perfectly binding commitments from the Learning with Errors (LWE) and Learning Parity with Noise (LPN) assumptions. Second, we give give two new constructions of 1-bounded constrained PRFs for admissible hash friendly constructions. Our first construction is from the $n\mathsf{-powerDDH}$ assumption. The next is from the $\phi$ hiding assumption.

On Secure Two-Party Computation in Three Rounds
Prabhanjan Ananth, Abhishek Jain
TCC 2017
[preprint] [proceedings] [bibTeX]
abstract We revisit the exact round complexity of secure two-party computation. While four rounds are known to be sufficient for securely computing general functions that provide output to one party [Katz-Ostrovsky, CRYPTO’04], Goldreich-Krawczyk [SIAM J. Computing’96] proved that three rounds are insufficient for this task w.r.t. black-box simulation.

In this work, we study the feasibility of secure computation in three rounds using non-black-box simulation. Our main result is a three-round two-party computation protocol for general functions against adversaries with auxiliary inputs of a priori bounded size. This result relies on a new two round input-extraction protocol based on succinct randomized encodings.

We also provide a partial answer to the question of achieving security against non-uniform adversaries. Assuming sub-exponentially secure iO and one-way functions, we rule out three-round protocols that achieve polynomial simulation-based security against the output party and exponential indistinguishability-based security against the other party.

Round Optimal Concurrent MPC via Strong Simulation
Saikrishna Badrinarayanan, Vipul Goyal, Abhishek Jain, Dakshita Khurana, Amit Sahai
TCC 2017
[preprint] [proceedings] [bibTeX]
abstract In this paper, we study the round complexity of concurrently secure multi-party computation (MPC) with super-polynomial simulation (SPS) in the plain model. In the plain model, there are known explicit attacks that show that concurrently secure MPC with polynomial simulation is impossible to achieve; SPS security is the most widely studied model for concurrently secure MPC in the plain model.

We obtain the following results:

– Three-round concurrent MPC with SPS security against Byzantine adversaries, assuming sub-exponentially secure DDH and LWE.

– Two-round concurrent MPC with SPS security against Byzantine adversaries for input-less randomized functionalities, assuming sub- exponentially secure indistinguishability obfuscation and DDH. In particular, this class includes sampling functionalities that allow parties to jointly sample a secure common reference string for cryptographic applications.

Prior to our work, to the best of our knowledge, concurrent MPC with SPS security required roughly 20 rounds, although we are not aware of any work that even gave an approximation of the constant round complexity sufficient for the multi-party setting. We also improve over the previous best round complexity for the two-party setting, where 5 rounds were needed (Garg, Kiyoshima, and Pandey, Eurocrypt 2017).

To obtain our results, we compile protocols that already achieve security against “semi-malicious” adversaries, to protocols secure against fully malicious adversaries, additionally assuming sub-exponential DDH. Our protocols develop new techniques to use two-round zero-knowledge with super-polynomial strong simulation, defined by Pass (Eurocrypt 2003) and very recently realized by Khurana and Sahai (FOCS 2017). These remain zero-knowledge against adversaries running in time larger than the running time of the simulator.

Verified Correctness and Security of mbedTLS HMAC-DRBG
Katherine Q. Ye, Matthew Green, Naphat Sanguansin, Lennart Beringer, Adam Petcher, Andrew W. Appel
CCS 2017
[preprint] [proceedings] [bibTeX]
abstract We have formalized the functional specification of HMAC-DRBG (NIST 800-90A), and we have proved its cryptographic security-that its output is pseudorandom--using a hybrid game-based proof. We have also proved that the mbedTLS implementation (C program) correctly implements this functional specification. That proof composes with an existing C compiler correctness proof to guarantee, end-to-end, that the machine language program gives strong pseudorandomness. All proofs (hybrid games, C program verification, compiler, and their composition) are machine-checked in the Coq proof assistant. Our proofs are modular: the hybrid game proof holds on any implementation of HMAC-DRBG that satisfies our functional specification. Therefore, our functional specification can serve as a high-assurance reference.

Bolt: Anonymous Payment Channels for Decentralized Currencies
Matthew Green, Ian Miers
CCS 2017
[preprint] [proceedings] [bibTeX]
abstract Bitcoin owes its success to the fact that transactions are transparently recorded in the blockchain, a global public ledger that removes the need for trusted parties. Unfortunately, recording every transaction in the blockchain causes privacy, latency, and scalability issues. Building on recent proposals for "micropayment channels" --- two party associations that use the ledger only for dispute resolution --- we introduce techniques for constructing anonymous payment channels. Our proposals allow for secure, instantaneous and private payments that substantially reduce the storage burden on the payment network. Specifically, we introduce three channel proposals, including a technique that allows payments via untrusted intermediaries. We build a concrete implementation of our scheme and show that it can be deployed via a soft fork to existing anonymous currencies such as ZCash.

Fairness in an Unfair World: Fair Multiparty Computation from Public Bulletin Boards
Arka Rai Choudhuri, Matthew Green, Abhishek Jain, Gabriel Kaptchuk, Ian Miers
CCS 2017
[preprint] [proceedings] [bibTeX]
abstract Secure multiparty computation allows mutually distrusting parties to compute a function on their private inputs such that nothing but the function output is revealed. Achieving fairness --- that all parties learn the output or no one does -- is a long studied problem with known impossibility results in the standard model if a majority of parties are dishonest.

We present a new model for achieving fairness in MPC against dishonest majority by using public bulletin boards implemented via existing infrastructure such as blockchains or Google's certificate transparency logs. We present both theoretical and practical constructions using either witness encryption or trusted hardware (such as Intel SGX).

Unlike previous works that either penalize an aborting party or achieve weaker notions such as $\Delta$-fairness, we achieve complete fairness using existing infrastructure.

A New Approach to Round-Optimal Secure Multiparty Computation
Prabhanjan Ananth, Arka Rai Choudhuri, Abhishek Jain
[preprint] [proceedings] [bibTeX]
abstract We present a new approach towards constructing round-optimal secure multiparty computation (MPC) protocols against malicious adversaries without trusted setup assumptions. Our approach builds on ideas previously developed in the context of covert multiparty computation [Chandran et al., FOCS'07] even though we do not seek covert security. Using our new approach, we obtain the following results:

1. A five round MPC protocol based on the Decisional Diffie-Hellman (DDH) assumption.

2. A four round MPC protocol based on one-way permutations and sub-exponentially secure DDH. This result is *optimal* in the number of rounds.

Previously, no four-round MPC protocol for general functions was known and five-round protocols were only known based on indistinguishability obfuscation (and some additional assumptions) [Garg et al., EUROCRYPT'16].

Distinguisher Dependent Simulation in Two Rounds and its Applications
Abhishek Jain, Yael Tauman Kalai, Dakshita Khuarana, Ron Rothblum
[preprint] [proceedings] [bibTeX]
abstract We devise a novel simulation technique that makes black-box use of the adversary as well as the distinguisher. Using this technique we construct several round-optimal protocols, many of which were previously unknown even using non-black-box simulation techniques:

- Two-round witness indistinguishable (WI) arguments for NP from different assumptions than previously known.

- Two-round arguments and three-round arguments of knowledge for NP that achieve strong WI, witness hiding (WH) and distributional weak zero knowledge (WZK) properties in a setting where the instance is only determined by the prover in the last round of the interaction. The soundness of these protocols is guaranteed against adaptive provers.

- Three-round two-party computation satisfying input-indistinguishable security as well as a weaker notion of simulation security against malicious adversaries.

- Three-round extractable commitments with guaranteed correctness of extraction from polynomial hardness assumptions.

Our three-round protocols can be based on DDH or QR or N^th residuosity and our two-round protocols require quasi-polynomial hardness of the same assumptions. In particular, prior to this work, two-round WI arguments for NP were only known based on assumptions such as the existence of trapdoor permutations, hardness assumptions on bilinear maps, or the existence of program obfuscation; we give the first construction based on (quasi-polynomial) DDH.

Our simulation technique bypasses known lower bounds on black-box simulation [Goldreich-Krawcyzk'96] by using the distinguisher's output in a meaningful way. We believe that this technique is likely to find more applications in the future.

Indistinguishability Obfuscation for Turing Machines: Constant Overhead and Amortization
Prabhanjan Ananth, Abhishek Jain, Amit Sahai
[preprint] [proceedings] [bibTeX]
abstract We study the asymptotic efficiency of indistinguishability obfuscation (iO) on two fronts:

- Obfuscation size: Present constructions of indistinguishability obfuscation (iO) create obfuscated programs where the size of the obfuscated program is at least a multiplicative factor of security parameter larger than the size of the original program.

In this work, we construct the first iO scheme for (bounded-input) Turing machines that achieves only a constant multiplicative overhead in size. The constant in our scheme is, in fact, 2.

- Amortization: Suppose we want to obfuscate an arbitrary polynomial number of (bounded-input) Turing machines $M_1,...,M_n$. We ask whether it is possible to obfuscate $M_1,...,M_n$ using a single application of an iO scheme for a circuit family where the size of any circuit is independent of n as well the size of any Turing machine $M_i$.

In this work, we resolve this question in the affirmative, obtaining a new bootstrapping theorem for obfuscating arbitrarily many Turing machines.

Our results rely on the existence of sub-exponentially secure iO for circuits and re-randomizable encryption schemes.

In order to obtain these results, we develop a new template for obfuscating Turing machines that is of independent interest and has recently found application in subsequent work on patchable obfuscation [Ananth et al, EUROCRYPT'17].

Signature Schemes with Randomized Verification
Cody Freitag, Rishab Goyal, Susan Hohenberger, Venkata Koppula, Eysa Lee, Tatsuaki Okamoto, Jordan Tran, Brent Waters
ACNS 2017
[preprint] [proceedings] [bibTeX]
abstract A signature scheme consists of a setup, signing and verification algorithms. In most existing works, the verification algorithm is assumed to be deterministic. However, there could be signature schemes where the verification algorithm is randomized. In this work, we study signature schemes with randomized verification. Our results can be summarized as follows.

First, we present a security definition for signature schemes with randomized verification. The standard EUFCMA notion of security for signature schemes with deterministic verification is very restrictive when we consider randomized verification. Therefore, we propose a new security definition called $\chi$ -EUFCMA which captures a broad class of signature schemes with randomized verification.

Next, we analyse the security of Naor’s transformation from Identity Based Encryption to signature schemes. Such a transformation results in a scheme with randomized verification. We show that this transformation can be proven $\chi$-EUFCMA secure by choosing $\chi$ appropriately.

Finally, we show how a scheme with randomized verification can be generically transformed to one with deterministic verification.

Decentralized Anonymous Micropayments
Alessandro Chiesa, Matthew Green, Jingcheng Liu, Peihan Miao, Ian Miers, Pratyush Mishra
[preprint] [proceedings] [bibTeX]
abstract Micropayments (payments worth a few pennies) have numerous potential applications. A challenge in achieving them is that payment networks charge fees that are high compared to “micro” sums of money.

Wheeler (1996) and Rivest (1997) proposed probabilistic payments as a technique to achieve micropayments: a merchant receives a macro-value payment with a given probability so that, in expectation, he receives a micro-value payment. Despite much research and trial deployment, micropayment schemes have not seen adoption, partly because a trusted party is required to process payments and resolve disputes.

The widespread adoption of decentralized currencies such as Bitcoin (2009) suggests that decentralized micropayment schemes are easier to deploy. Pass and Shelat (2015) proposed several micropayment schemes for Bitcoin, but their schemes provide no more privacy guarantees than Bitcoin itself, whose transactions are recorded in plaintext in a public ledger.

We formulate and construct *decentralized anonymous micropayment* (DAM) schemes, which enable parties with access to a ledger to conduct offline probabilistic payments with one another, directly and privately. Our techniques extend those of Zerocash (2014) with a new probabilistic payment scheme; we further provide an efficient instantiation based on a new fractional message transfer protocol.

Double spending in our setting cannot be prevented. Our second contribution is an economic analysis that bounds the additional utility gain of any cheating strategy, and applies to virtually any probabilistic payment scheme with offline validation. In our construction, this bound allows us to deter double spending by way of advance deposits that are revoked when cheating is detected.

Cryptography with Updates
Prabhanjan Ananth, Aloni Cohen, Abhishek Jain
[preprint] [proceedings] [bibTeX]
abstract Starting with the work of Bellare, Goldreich and Goldwasser [CRYPTO’94], a rich line of work has studied the design of updatable cryptographic primitives. For example, in an updatable signature scheme, it is possible to efficiently transform a signature over a message into a signature over a related message without recomputing a fresh signature.

In this work, we continue this line of research, and perform a systematic study of updatable cryptography. We take a unified approach towards adding updatability features to recently studied cryptographic objects such as attribute-based encryption, functional encryption, witness encryption, indistinguishability obfuscation, and many others that support non-interactive computation over inputs. We, in fact, go further and extend our approach to classical protocols such as zero-knowledge proofs and secure multiparty computation.

To accomplish this goal, we introduce a new notion of updatable randomized encodings that extends the standard notion of randomized encodings to incorporate updatability features. We show that updatable randomized encodings can be used to generically transform cryptographic primitives to their updatable counterparts.

We provide various definitions and constructions of updatable randomized encodings based on varying assumptions, ranging from one-way functions to compact functional encryption.

Patchable Indistinguishability Obfuscation: iO for Evolving Software
Prabhanjan Ananth, Abhishek Jain, Amit Sahai
[preprint] [proceedings] [bibTeX]
abstract In this work, we introduce patchable indistinguishability obfuscation: our notion adapts the notion of indistinguishability obfuscation (${i\mathcal {O}}$) to a very general setting where obfuscated software evolves over time. We model this broadly by considering software patches $P$ as arbitrary Turing Machines that take as input the description of a Turing Machine $M$, and output a new Turing Machine description $M′=P(M)$. Thus, a short patch $P$ can cause changes everywhere in the description of $M$ and can even cause the description length of the machine to increase by an arbitrary polynomial amount. We further considermulti-program patchable indistinguishability obfuscation where a patch is applied not just to a single machine $M$, but to an unbounded set of machines $M_1,…,M_n$ to yield $P(M_1),…,P(M_n)$.

We consider both single-program and multi-program patchable indistinguishability obfuscation in a setting where there are an unbounded number of patches that can be adaptively chosen by an adversary. We show that sub-exponentially secure ${i\mathcal {O}}$ for circuits and sub-exponentially secure re-randomizable encryption schemes (Re-randomizable encryption schemes can be instantiated under standard assumptions such as DDH, LWE.) imply single-program patchable indistinguishability obfuscation; and we show that sub-exponentially secure ${i\mathcal {O}}$ for circuits and sub-exponentially secure DDH imply multi-program patchable indistinguishability obfuscation.

At the our heart of results is a new notion of splittable ${i\mathcal {O}}$ that allows us to transform any ${i\mathcal {O}}$ scheme into a patchable one. Finally, we exhibit some simple applications of patchable indistinguishability obfuscation, to demonstrate how these concepts can be applied.

Outsourcing Medical Dataset Analysis: A Possible Solution
Gabriel Kaptchuk, Matthew Green, Aviel D. Rubin
Financial Cryptography and Data Security 2017
[preprint] [proceedings] [bibTeX]
abstract We explore the possible ways modern cryptographic methods can be applied to the field of medical data analysis. Current systems require large computational facilities owned by the data owners or excessive trust given to the researchers. We implement one possible solution in which researchers operate directly on homomorphically encrypted data and the data owner decrypts the results. We test our implementation on large datasets and show that it is suciently practical that it could be a helpful tool for modern researchers. We also perform a heuristic analysis of the security of our system.

Significantly Improved Multi-bit Differentials for Reduced Round Salsa and ChaCha
Arka Rai Choudhuri, Subhamoy Maitra
FSE 2017/ ToSC 2016
[preprint] [proceedings] [bibTeX]
abstract ChaCha and Salsa are two software oriented stream ciphers that have attracted serious attention in academic as well as commercial domain. The most important cryptanalysis of reduced versions of these ciphers was presented by Aumasson et al. in FSE 2008. One part of their attack was to apply input difference(s) to investigate biases after a few rounds. So far there have been certain kind of limited exhaustive searches to obtain such biases. For the first time, in this paper, we show how to theoretically choose the combinations of the output bits to obtain significantly improved biases. The main idea here is to consider the multi-bit differentials as extension of suitable single-bit differentials with linear approximations, which is essentially a differential-linear attack. As we consider combinations of many output bits (for example 19 for Salsa and 21 for ChaCha), exhaustive search is not possible here. By this method we obtain very high biases for linear combinations of bits in Salsa after 6 rounds and in ChaCha after 5 rounds. These are clearly two rounds of improvement for both the ciphers over the existing works. Using these biases we obtain several significantly improved cryptanalytic results for reduced round Salsa and ChaCha that could not be obtained earlier. In fact, with our results it is now possible to cryptanalyse 6-round Salsa and 5-round ChaCha in practical time.