International Association
for Cryptologic Research

We propose definitions and constructions of authenticated encryption (AE) schemes that offer security guarantees even in the presence of side-channel leakages and nonce misuse. This is part of an important ongoing effort to make AE as robust as possible, while preserving appealing efficiency properties. In order to achieve this efficiency, we aim at modes of operation that support leveled implementations such that the encryption and decryption operations require the use of a small constant number of evaluations of an expensive and heavily protected component, while the bulk of the computation can be performed by cheap and weakly protected blocks.

Our definitions offer various insights on the effect of leakages in the security landscape. In particular, we show that, in contrast with the black-box setting, leaking variants of INT-CTXT and CPA security do not imply a leaking variant CCA security, and that leaking variants of INT-PTXT and CCA do not imply a leaking variant of INT-CTXT. Eventually, we propose FEMALE, a new mode of operation that satisfies our security definitions and supports efficient leveled implementations, and AEDT, another efficient mode of operation that offers the strongest form of misuse resistance that can be achieved in the presence of leakages, while not being fully misuse resistant in the black-box setting.

We construct new multi-signature schemes that provide new functionality. Our schemes are designed to reduce the size of the Bitcoin blockchain, but are useful in many other settings where multi-signatures are needed. All our constructions support both signature compression and public-key aggregation. Hence, to verify that a number of parties signed a common message m, the verifier only needs a short multi-signature, a short aggregation of their public keys, and the message m. We give new constructions that are derived from Schnorr signatures and from BLS signatures. Our constructions are in the plain public key model, meaning that users do not need to prove knowledge or possession of their secret key.

In addition, we construct the first short accountable-subgroup multi-signature (ASM) scheme. An ASM scheme enables any subset S of a set of n parties to sign a message m so that a valid signature discloses which subset generated the signature (hence the subset S is accountable for signing m). We construct the first ASM scheme where signature size is only O(k) bits over the description of S, where k is the security parameter. Similarly, the aggregate public key is only O(k) bits, independent of n. The signing process is non-interactive. Our ASM scheme is very practical and well suited for compressing the data needed to spend funds from a t-of-n Multisig Bitcoin address, for any (polynomial size) t and n.

Most multi-party computation protocols allow secure computation of arithmetic circuits over a finite field, such as the integers modulo a prime. In the more natural setting of integer computations modulo $2^{k}$, which are useful for simplifying implementations and applications, no solutions with active security are known unless the majority of the participants are honest.

We present a new scheme for information-theoretic MACs that are homomorphic modulo $2^k$, and are as efficient as the well-known standard solutions that are homomorphic over fields. We apply this to construct an MPC protocol for dishonest majority in the preprocessing model that has efficiency comparable to the well-known SPDZ protocol (Damgård et al., CRYPTO 2012), with operations modulo $2^k$ instead of over a field. We also construct a matching preprocessing protocol based on oblivious transfer, which is in the style of the MASCOT protocol (Keller et al., CCS 2016) and almost as efficient.

We settle the exact round complexity of three-party computation (3PC) in honest-majority setting, for a range of security notions such as selective abort, unanimous abort, fairness and guaranteed output delivery. Selective abort security, the weakest in the lot, allows the corrupt parties to selectively deprive some of the honest parties of the output. In the mildly stronger version of unanimous abort, either all or none of the honest parties receive the output. Fairness implies that the corrupted parties receive their output only if all honest parties receive output and lastly, the strongest notion of guaranteed output delivery implies that the corrupted parties cannot prevent honest parties from receiving their output. It is a folklore that the implication holds from the guaranteed output delivery to fairness to unanimous abort to selective abort. We focus on two network settings-- pairwise-private channels without and with a broadcast channel.

In the minimal setting of pairwise-private channels, 3PC with selective abort is known to be feasible in just two rounds, while guaranteed output delivery is infeasible to achieve irrespective of the number of rounds. Settling the quest for exact round complexity of 3PC in this setting, we show that three rounds are necessary and sufficient for unanimous abort and fairness. Extending our study to the setting with an additional broadcast channel, we show that while unanimous abort is achievable in just two rounds, three rounds are necessary and sufficient for fairness and guaranteed output delivery. Our lower bound results extend for any number of parties in honest majority setting and imply tightness of several known constructions. The fundamental concept of garbled circuits underlies all our upper bounds. Concretely, our constructions involve transmitting and evaluating only constant number of garbled circuits. Assumption-wise, our constructions rely on injective (one-to-one) one-way functions.

Collision resistant hashing is a fundamental concept that is the basis for many of the important cryptographic primitives and protocols. Collision resistant hashing is a family of compressing functions such that no efficient adversary can find any collision given a random function in the family.

In this work we study a relaxation of collision resistance called distributional collision resistance, introduced by Dubrov and Ishai (STOC '06). This relaxation of collision resistance only guarantees that no efficient adversary, given a random function in the family, can sample a pair $(x,y)$ where $x$ is uniformly random and $y$ is uniformly random conditioned on colliding with $x$. Our first result shows that distributional collision resistance can be based on the existence of multi-collision resistance hash (with no additional assumptions). Multi-collision resistance is another relaxation of collision resistance which guarantees that an efficient adversary cannot find any tuple of $k>2$ inputs that collide relative to a random function in the family. The construction is non-explicit, non-black-box, and yields an infinitely-often secure family. This partially resolves a question of Berman et al. (EUROCRYPT '18). We further observe that in a black-box model such an implication (from multi-collision resistance to distributional collision resistance) does not exist.

Our second result is a construction of a distributional collision resistant hash from the average-case hardness of SZK. Previously, this assumption was not known to imply any form of collision resistance (other than the ones implied by one-way functions).

In 2008, Jhanwar and Barua presented an improvement of the Boneh-Gentry-Hamburg (BGH) scheme. In addition to reducing the time complexity of the algorithm to find a solution of the equation $ax^2+Sy^2\equiv 1 \bmod n$, their scheme reduces the number of equations to be solved by combining existing solutions. Susilo et al. extended the Jhanwar-Barua scheme, reducing more the number of equations to be solved. This paper presents a security flaw that appears in both schemes and shows that they are not IND-ID-CPA secure.

Like any other cryptanalytic attack, the success rate of a linear attack is expected to improve as more data becomes available. Bogdanov and Tischhauser (FSE 2013) made the rather surprising claim that the success rate of a linear attack may go down with increasing plaintext amount, after an optimal point. They supported this claim with experimental evidence by an attack on SmallPresent-20. Different explanations have been given to explain this surprising phenomenon. In this note, we give quantitative values regarding when this phenomenon can be observed. We conclude that it should not be an issue for attacks in practice except for those with a tiny bias.

Machine learning has become mainstream across industries. In this work we pose the following question: Is it possible to reverse engineer a neural network by using only side-channel information? We answer the question affirmatively. To this end, we consider a multi layer perceptron as the machine learning architecture of choice and assume a passive attacker capable of measuring only passive side-channels like power, electromagnetic radiation, and timing.

We conduct all experiments on real data and common neural net architectures in order to properly assess the applicability and extendability of such attacks. Our experiments show that the side-channel attacker is able to obtain information about the activation functions, the number of layers and neurons in layers, the number of output classes, and weights in the neural network. Thus, the attacker can efficiently reverse engineer the network using side-channel information.

Next, we show that if the attacker has the knowledge about the neural network architecture, he/she could also recover the inputs to the network with only a single measurement. Finally, we discuss several mitigations one could use to thwart such attacks.

We concentrate on machine learning techniques used for profiled side-channel analysis when having imbalanced data. Such scenarios are realistic and often occurring, for instance in the Hamming weight or Hamming distance leakage models. In order to deal with the imbalanced data, we use various balancing techniques where we show that most of them help in mounting successful attack when the data is highly imbalanced. Especially the results with the SMOTE technique are encouraging since we observe scenarios where it reduces the number of necessary measurements for more than 8 times. Next, we provide extensive results on comparison of machine learning and side-channel metrics where we show that machine learning metrics (and especially accuracy as the most often used one) can be extremely deceptive. This opens a need to revisit the previous works and their findings in order to properly assess the performance of machine learning in side-channel analysis.

Recent work, including ZKBoo, ZKB++, and Ligero, has developed efficient non-interactive zero-knowledge proofs of knowledge (NIZKPoKs) for arbitrary Boolean circuits based on symmetric- key primitives alone using the “MPC-in-the-head” paradigm of Ishai et al. We show how to instantiate this paradigm with MPC protocols in the preprocessing model; once optimized, this results in an NIZKPoK with shorter proofs (and comparable computation) as in prior work for circuits containing roughly 300–100,000 AND gates. In contrast to prior work, our NIZKPoK also supports witness-independent preprocessing, which allows the prover to move most of its work to an offline phase before the witness is known.

We use our NIZKPoK to construct a signature scheme based only on symmetric-key primitives (and hence with “post-quantum” security). The resulting scheme has shorter signatures than the scheme built using ZKB++ (with comparable signing/verification time), and is even competitive with hash-based signature schemes.

To further highlight the flexibility and power of our NIZKPoK, we also use it to build efficient ring and group signatures based on symmetric-key primitives alone. To our knowledge, the resulting schemes are the most efficient constructions of these primitives that offer post-quantum security.

In this paper, we present two new and very communication-efficient protocols for maliciously secure multi-party computation over fields in the honest-majority setting with abort. Our first protocol improves a recent protocol by Lindell and Nof. Using the so far overlooked tool of batchwise multiplication verification, we speed up their technique for checking correctness of multiplications (with some other improvements), reducing communication by 2x to 7x. In particular, in the 3PC setting, each party sends only two field elements per multiplication. We also show how to achieve fairness, which Lindell and Nof left as an open problem. Our second protocol again applies batchwise multiplication verification, this time to perform 3PC by letting two parties perform the SPDZ protocol using triples generated by a third party and verified batchwise. In this protocol, each party sends only 4/3 field elements during the online phase and 53 field elements during the preprocessing phase.

We give a construction of a secure multi-party computation (MPC) protocol from a special type of key agreement, where the distribution of the messages sent by one of the parties is computationally close to the uniform distribution over an efficiently sampleable group, even when the other party is malicious. We term the latter strongly uniform key agreement (SU-KA). First, we show that for any odd t, t-round SU-KA and statistically binding commitments are sufficient for a black-box construction of (t+1)-round maliciously secure oblivious transfer (M-OT). By invoking a recent result of Benhamouda and Lin (Eurocrypt 2017), the latter implies maliciously secure MPC within max(t+1,5) rounds in the plain model. Additionally, we investigate the relationship between SU-KA, and similar types of public-key encryption and semi-honestly secure OT protocols where we also demand strong uniformity. This finally allows us to instantiate our result for t=2 and t=3 under standard assumptions, including any of low-noise LPN, LWE, Subset Sum, DDH, CDH, and RSA (all with polynomial hardness), so that under the same set of assumptions we also obtain 5-round maliciously secure MPC (and 4-round M-OT) in the plain model.

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.