International Association
for Cryptologic Research

Tremendous growth in the cryptocurrency usage is exposing the inherent scalabilty issues with the permissionless blockchain technology. Among few alternatives, payment-channel networks (PCNs) have emerged as the most popular and practically deployed solution to overcome the scalability issues, allowing the bulk of payments between any two users to be carried out off-chain. Unfortunately, as reported in the literature and further demonstrated in this paper, current PCNs do not provide meaningful security and privacy guarantees.

In this work, we lay the foundations for the design of secure and privacy-preserving PCNs. For that, we formally define multi-hop locks, a novel cryptographic primitive that serves as a cornerstone for the design of secure and privacy-preserving PCNs, and design several provably secure cryptographic instantiations that make multi-hop locks compatible with the vast majority of cryptocurrencies. In particular, we show that (partial) homomorphic one-way functions suffice to construct multi-hop locks for PCNs supporting a script language (e.g., Bitcoin and Ethereum), and offer two constructions based on Schnorr and ECDSA that allow for the development of PCNs even without scripts. Further multi-hop locks constitute a generic primitive whose usefulness goes beyond regular PCNs and use those to realize atomic swaps and interoperable PCNs. Finally, our performance evaluation on a commodity machine finds that multi-hop locks operations can be performed in less than 100 milliseconds and require less than 500 bytes, even in the worst case. This shows the practicality of our approach towards enhancing security, privacy, interoperability, and scalability of today’s cryptocurrencies.

Oblivious RAM protocols (ORAMs) allow a client to access data from an untrusted storage device without revealing to that device any information about their access pattern. Typically this is accomplished through shuffling the data into random positions such that the storage device is not sure where individual blocks are located, resulting in an access pattern on the device which is highly randomized. However, storage devices are usually optimized for \emph{sequential} accesses, meaning that ORAMs can often induce a substantial overhead (in addition to their increased bandwidth) due to large numbers of disk seeks (Blass et al., CCS 2014).

In this paper, we present an ORAM construction specifically suited for accessing ranges of sequential logical blocks while minimizing disk seeks. Our construction obtains better asymptotic efficiency than prior work with similar security guarantees (Asharov et al., 2017), achieving $\mathbb{O}(r\cdot\log^2 N)$ communication cost (where $r$ is the size of the range) and $\mathbb{O}(\log^2 N)$ seeks per access, regardless of $r$. This is an improvement of more than a $\mathbb{O}(\log N)$ factor in both metrics when compared to prior work. In evaluation, we find that our construction is 30-50x times faster than Path ORAM for similar workloads on local HDDs, almost 30x faster for local SSDs, and 10x faster for network block devices.

We consider the problem of removing subexponential assumptions from cryptographic constructions based on indistinguishability obfuscation (iO). Specifically, we show how to apply complexity absorption (Zhandry, Crypto 2016) to the recent notion of probabilistic indistinguishability obfuscation (piO, Canetti et al., TCC 2015). As a result, we obtain a variant of piO which allows to obfuscate a large class of probabilistic programs, from polynomially secure indistinguishability obfuscation and extremely lossy functions. We then revisit several (direct or indirect) applications of piO, and obtain

- a fully homomorphic encryption scheme (without circular security assumptions),

- a multi-key fully homomorphic encryption scheme with threshold decryption,

- an encryption scheme secure under arbitrary key-dependent messages,

- a spooky encryption scheme for all circuits,

- a function secret sharing scheme with additive reconstruction for all circuits,

all from polynomially secure iO, extremely lossy functions, and, depending on the scheme, also other (but polynomial and comparatively mild) assumptions. All of these assumptions are implied by polynomially secure iO and the (non-polynomial, but very well-investigated) exponential DDH assumption. Previously, all the above applications required to assume the *subexponential* security of iO (and more standard assumptions).

In [1], an abstract accounting model for UTXO-based cryptocurrencies has been presented. However, that model considered only the simplest kind of transaction (known in Bitcoin as pay-to-pubkey-hash) and also abstracted away all aspects related to authorization. This paper extends that model to the general case where the transaction contains validator (a.k.a. scriptPubKey) scripts and redeemer (a.k.a. scriptSig) scripts, which together determine whether the transac- tion’s fund transfers have been authorized.

The international standard ISO/IEC 9797-1:2011 specifies six versions of MACs, called MAC Algorithm 1-6, and many of these MACs enjoy widespread use in practical applications. However, security guarantees of these MACs are all capped at birthday bound since they all use single CBC-MAC computations. It is recommended in this standard to improve the security level by concatenating outputs of two MACs with independent keys rather than XORing them.$\\$

In this paper, we show such claim is wrong by giving birthday forgery attacks on concatenations of two MACs with independent keys in this standard. Furthermore, we revisit the impact of XORing of two MACs in ISO/IEC 9797-1:2011 and show this operation can only lift up the security level. We give the first two provable-security bounds for XORing of two MAC Algorithm 1 (XMAC1) in ISO/IEC 9797-1:2011 with either padding scheme 3 or 2. We prove that XMAC1 with padding scheme 3 is secure beyond birthday bound with $O(\sigma q^2\ell/2^{2n})$. Note that our result implies that this is the first CBC-type MAC that provably goes beyond birthday barrier with only two secret keys. When instantiated with padding scheme 2, we prove that XMAC1 is secure with birthday bound $O(\sigma^2/2^n)$. Illustrated with Joux et al's attack, this bound is tight up to a constant factor. We also prove that XORing of two MAC Algorithm 5 (XMAC5) is secure with a bound $O(\sigma q^2\ell/2^{2n})$.$\\$

Finally, together with previous results, we give a summary of the impact of XORing of two MACs on ISO/IEC 9797-1:2011 and conclude that such operation can only lift up the security bound.

Recent improvements in the state-of-the-art of MPC for non-full-threshold access structures introduced the idea of using a collision-resistant hash functions and redundancy in the secret-sharing scheme to construct a communication-efficient MPC protocol which is computationally-secure against malicious adversaries, with abort. The prior work is based on replicated secret-sharing; in this work we extend this methodology to any multiplicative LSSS implementing a $Q_2$ access structure. To do so we need to establish a folklore property of error detection for such LSSS and their associated Monotone Span Programs. In doing so we obtain communication-efficient online and offline protocols for MPC in the pre-processing model.

In this paper, we present a cryptographic technique for an authenticated, end-to-end verifiable and secret ballot election. Voters should receive assurance that their vote is cast as intended, recorded as cast and tallied as recorded. The election system as a whole should ensure that voter coercion is unlikely, even when voters are willing to be influenced. Currently, almost all verifiable e-voting systems require trusted authorities to perform the tallying process. An exception is the DRE-i and DRE-ip system. The DRE-ip system removes the requirement of tallying authorities by encrypting ballot in such a way that the election tally can be publicly verified without decrypting cast ballots. However, the DRE-ip system necessitates a secure bulletin board (BB) for storing the encrypted ballot as without it the integrity of the system may be lost and the result can be compromised without detection during the audit phase. In this paper, we have modified the DRE-ip system so that if any recorded ballot is tampered by an adversary before the tallying phase, it will be detected during the tallying phase. In addition, we have described a method using zero knowledge based public blockchain to store these ballots so that it remains tamper proof. To the best of our knowledge, it is the first end-to-end verifiable Direct-recording electronic (DRE) based e-voting system using blockchain. In our case, we assume that the bulletin board is insecure and an adversary has read and write access to the bulletin board. We have also added a secure biometric with government provided identity card based authentication mechanism for voter authentication. The proposed system is able to encrypt ballot in such a way that the election tally can be publicly verified without decrypting cast ballots maintaining end-to-end verifiability and without requiring the secure bulletin board.

Secure multiparty computation (MPC) addresses the challenge of evaluating functions on secret inputs without compromising their privacy. An central question in multiparty communication is to understand the amount of communication needed to securely evaluate a circuit of size s. In this work, we revisit this fundamental question, in the setting of information-theoretically secure MPC in the correlated randomness model, where a trusted dealer distributes correlated random coins, independent of the inputs, to all parties before the start of the protocol. This setting is of strong theoretical interest, and has led to the most practically efficient MPC protocols known to date. While it is known that protocols with optimal communication (proportional to input plus output size) can be obtained from the LWE assumption, and that protocols with sublinear communication o(s) can be obtained from the DDH assumption, the question of constructing protocols with o(s) communication remains wide open for the important case of information-theoretic MPC in the correlated randomness model. All known protocols in this model require O(s) communication in the online phase; improving this state of affairs is a long standing open question. In this work, we exhibit the first generic multiparty computation protocol in the correlated randomness model with communication sublinear in the circuit size, for a large class of circuits. More precisely, we show the following: any size-s layered circuit (whose nodes can be partitioned into layers so that any edge connects adjacent layers) can be evaluated with O(s/log log s) communication. Our result holds for both boolean and arithmetic circuits, and security holds with respect to malicious corruption, without honest majority.

MORUS is a high-performance authenticated encryption algorithm submitted to the CAESAR competition, and recently selected as a finalist.There are three versions of MORUS: MORUS-640 with a 128-bit key, and MORUS-1280 with 128-bit or 256-bit keys. For all versions the security claim for confidentiality matches the key size.In this paper, we analyze the components of this algorithm (initialization, state update and tag generation), and report several results.

As our main result, we present a linear correlation in the keystream of full MORUS, which can be used to distinguish its output from random and to recover some plaintext bits in the broadcast setting.For MORUS-1280, the correlation is $2^{-76}$, which can be exploited after around $2^{152}$ encryptions, less than would be expected for a 256-bit secure cipher. For MORUS-640, the same attack results in a correlation of $2^{-73}$, which does not violate the security claims of the cipher.

To identify this correlation, we make use of rotational symmetries in MORUS using linear masks that are invariant by word-rotations of the state.This motivates us to introduce single-word versions of MORUS called MiniMORUS, which simplifies the analysis. The attack has been implemented and verified on MiniMORUS, where it yields a correlation of $2^{-16}$.

We also study reduced versions of the initialization and finalization of MORUS, aiming to evaluate the security margin of these components.We show a forgery attack when finalization is reduced from 10 steps to 3, and a key-recovery attack in the nonce-misuse setting when initialization is reduced from 16 steps to 10.These additional results do not threaten the full MORUS, but studying all aspects of the design is useful to understand its strengths and weaknesses.

In this paper, we study the generic hardness of the inversion problem on a ring, which is a problem to compute the inverse of a given prime $c$ by just using additions, subtractions and multiplications on the ring. If the characteristic of an underlying ring is public and coprime to $c$, then it is easy to compute the inverse of $c$ by using the extended Euclidean algorithm. On the other hand, if the characteristic is hidden, it seems difficult to compute it. For discussing the generic hardness of the inversion problem, we first extend existing generic ring models to capture a ring of an unknown characteristic. Then we prove that there is no generic algorithm to solve the inversion problem in our model when the underlying ring is isomorphic to $\mathbb{Z}_p$ for a randomly chosen prime $p$ assuming the hardness of factorization of an unbalanced modulus. We also study a relation between the inversion problem on a ring and a self-bilinear map. We give a ring-based construction of a self-bilinear map, and prove that natural complexity assumptions including the multilinear computational Diffie-Hellman (MCDH) assumption hold w.r.t the resulting sef-bilinear map if the inversion problem is hard on the underlying ring.

One of the tasks in the $2017$ iDASH secure genome analysis competition was to enable training of logistic regression models over encrypted genomic data. More precisely, given a list of approximately $1500$ patient records, each with $18$ binary features containing information on specific mutations, the idea was for the data holder to encrypt the records using homomorphic encryption, and send them to an untrusted cloud for storage. The cloud could then apply a training algorithm on the encrypted data to obtain an encrypted logistic regression model, which can be sent to the data holder for decryption. In this way, the data holder could successfully outsource the training process without revealing either her sensitive data, or the trained model, to the cloud. Our solution to this problem has several novelties: we use a multi-bit plaintext space in fully homomorphic encryption together with fixed point number encoding; we combine bootstrapping in fully homomorphic encryption with a scaling operation in fixed point arithmetic; we use a minimax polynomial approximation to the sigmoid function and the $1$-bit gradient descent method to reduce the plaintext growth in the training process. As a result, our training over encrypted data takes $0.4$ -- $3.2$ hours per iteration of gradient descent.

Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a high-entropy source into the same uniformly distributed key. The ideal functionality of a fuzzy extractor outputs the key when provided with a value close to the original reading of the source. A necessary condition for security, called fuzzy min-entropy, is that the probability of every ball of values of the noisy source is small.

Noisy sources are measured from physical phenomena many of which best modeled by continuous metric spaces. To build continuous-source fuzzy extractors, prior work assumes that the system designer has a good model of the high (fuzzy) entropy distribution (Verbitskiy et al., IEEE TIFS 2010). However, it is impossible to build an accurate model of a high entropy distribution with oracle access to the distribution.

We show that model inaccuracy is a major hurdle to constructing a continuous-source fuzzy extractors. Namely, there exists a family of continuous distributions $\mathcal{W}$ such that each element $W\in\mathcal{W}$ has fuzzy min-entropy but no fuzzy extractor can produce a three bit key for an average element of $\mathcal{W}$. Our family is built from random $p$-ary lattices.

We also show a stronger negative result for secure sketches, which are used to construct most fuzzy extractors. Our results are for the Euclidean metric and are information-theoretic in nature. To the best of our knowledge all continuous-source fuzzy extractors argue information-theoretic security.

Fuller, Reyzin, and Smith showed negative results for a discrete metric space equipped with the Hamming metric (Asiacrypt 2016). The geometry of Euclidean space necessitates new techniques.

A major approach to overcoming the performance and scalability limitations of current blockchain protocols is to use sharding, which is to split the overheads of processing transactions among multiple, smaller groups of nodes. These groups work in parallel to maximize performance while requiring significantly smaller communication, computation, and storage per node, allowing the system to scale to large networks. However, existing sharding-based blockchain protocols still require a linear amount of communication (in the number of participants) per transaction, and hence, attain only partially the potential benefits of sharding. We show that this introduces a major bottleneck to the throughput and latency of these protocols. Aside from the limited scalability, these protocols achieve weak security guarantees due to either a small fault resiliency (e.g., $1/8$ and $1/4$) or high failure probability, or they rely on strong assumptions (e.g., trusted setup) that limit their applicability to mainstream payment systems.

We propose RapidChain, the first sharding-based public blockchain protocol that is resilient to Byzantine faults from up to a $1/3$ fraction of its participants, and achieves complete sharding of the communication, computation, and storage overhead of processing transactions without assuming any trusted setup. We introduce an optimal intra-committee consensus algorithm that can achieve very high throughputs via block pipelining, a novel gossiping protocol for large blocks, and a provably-secure reconfiguration mechanism to ensure robustness. Using an efficient cross-shard transaction verification technique, RapidChain avoids gossiping transactions to the entire network. Our empirical evaluations suggest that RapidChain can process (and confirm) more than 7,300 tx/sec with an expected confirmation latency of roughly 8.7 seconds in a network of 4,000 nodes with an overwhelming time-to-failure of more than 4,500 years.

We present an oblivious transfer (OT) protocol that combines the OT scheme of Chou and Orlandi together with the supersingular isogeny Diffie-Hellman (SIDH) primitive of De Feo, Jao, and Plût. Our construction is a candidate for post-quantum secure OT and demonstrates that SIDH naturally supports OT functionality. We consider the protocol in the simplest configuration of $\binom{2}{1}$-OT and analyze the protocol to verify its security.

Linicrypt (Carmer & Rosulek, Crypto 2016) refers to the class of algorithms that make calls to a random oracle and otherwise manipulate values via fixed linear operations. We give a characterization of collision-resistance and second-preimage resistance for a significant class of Linicrypt programs (specifically, those that achieve domain separation on their random oracle queries via nonces). Our characterization implies that collision-resistance and second-preimage resistance are equivalent, in an asymptotic sense, for this class. Furthermore, there is a polynomial-time procedure for determining whether such a Linicrypt program is collision/second-preimage resistant.

Functional encryption (FE) has incredible applications towards computing on encrypted data. However, constructing the most general form of this primitive has remained elusive. Although some candidate constructions exist, they rely on nonstandard assumptions, and thus, their security has been questioned. An FE combiner attempts to make use of these candidates while minimizing the trust placed on any individual FE candidate. Informally, an FE combiner takes in a set of FE candidates and outputs a secure FE scheme if at least one of the candidates is secure.

Another fundamental area in cryptography is secure multi-party computation (MPC), which has been extensively studied for several decades. In this work, we initiate a formal study of the relationship between functional encryption (FE) combiners and secure multi-party computation (MPC). In particular, we show implications in both directions between these primitives. As a consequence of these implications, we obtain the following main results.

1) A two round semi-honest MPC protocol in the plain model secure against up to (n-1) corruptions with communication complexity proportional only to the depth of the circuit being computed assuming LWE. Prior two round protocols that achieved this communication complexity required a common reference string.

2) A functional encryption combiner based on pseudorandom generators (PRGs) in NC^1. Such PRGs can be instantiated from assumptions such as DDH and LWE. Previous constructions of FE combiners were known only from the learning with errors assumption. Using this result, we build a universal construction of functional encryption: an explicit construction of functional encryption based only on the assumptions that functional encryption exists and PRGs in NC^1.

We present an efficient key recovery attack on code based encryption schemes using some quasi–dyadic alternant codes with extension degree 2. This attack permits to break the proposal DAGS recently submitted to NIST.

We consider single and multiple attacker scenarios in guessing and obtain bounds on various success parameters in terms of Renyi entropies. We also obtain a new derivation of the union bound.

Cryptocurrencies and blockchains are set to play a major role in the financial and supply-chain systems. Their presence and acceptance across different geopolitical corridors, including in repressive regimes, have been one of their striking features. In this work, we leverage this popularity for bootstrapping censorship resistant (CR) communication. We formalize the notion of stego-bootstrapping scheme and formally describe the security notions of the scheme in terms of rareness and security against chosen-covertext attacks. We present R3C3, a Cryptographically secure Censorship-Resistant Rendezvous using Cryptocurrencies. R3C3 allows a censored user to interact with a decoder entity outside the censored region, through blockchain transactions as rendezvous, to obtain bootstrapping information such as a CR proxy and its public key. Unlike the usual bootstrapping approaches (e.g., emailing) with heuristic security if any, R3C3 employs public-key steganography over blockchain transactions to ensure cryptographic security, while the blockchain transaction costs may deter the entry-point harvesting attacks. We develop bootstrapping rendezvous over Bitcoin, Zcash, Monero and Ethereum as well as the typical mining process, and analyze their effectivity in terms of cryptocurrency network volume and introduced monetary cost. With its highly cryptographic structure, Zcash is an outright winner for normal users with 1168 byte bandwidth per transaction costing only 0.03 USD as the fee, while mining pool managers have a free, extremely high bandwidth rendezvous when they mine a block.

We present the first lattice-based group signature scheme whose cryptographic artifacts are of size small enough to be usable in practice: for a group of $2^{25}$ users, signatures take 910 kB and public keys are 501 kB. Our scheme builds upon two recently proposed lattice-based primitives: the verifiable encryption scheme by Lyubashevsky and Neven (Eurocrypt 2017) and the signature scheme by Boschini, Camenisch, and Neven (IACR ePrint 2017). To achieve such short signatures and keys, we first re-define verifiable encryption to allow one to encrypt a function of the witness, rather than the full witness. This definition enables more efficient realizations of verifiable encryption and is of independent interest. Second, to minimize the size of the signatures and public keys of our group signature scheme, we revisit the proof of knowledge of a signature and the proofs in the verifiable encryption scheme provided in the respective papers.