International Association
for Cryptologic Research

Motivated by applications like verifiable computation and privacy-preserving cryptocurrencies, many efficient pairing-based SNARKs were recently proposed. However, the most efficient SNARKs like the one by Groth (EUROCRYPT 2016) have a very brittle and difficult-to-verify knowledge-soundness proof in the generic model. Due to that, it is difficult to modify such SNARKs to, e.g., satisfy simulation-extractability or to implement some other language instead of QAP (Quadratic Arithmetic Program).

We propose a template for constructing knowledge-sound and non-black-box any-simulation-extractable NBBASE SNARKs for QAP. This template is designed so that the knowledge-soundness and even NBBASE proofs of the new SNARKs are quite simple. The new knowledge-sound SNARK for QAP is very similar to the mentioned SNARK of Groth, except it has fewer trapdoors. To achieve NBBASE, we add to the knowledge-sound SNARK a few well-motivated extra steps, while its security proof is even simpler due to the use of a second verification equation. Moreover, we give a simple characterization of languages like SAP, SSP, and QSP in the terms of QAP and show how to modify the SNARK for QAP correspondingly. The only prior published efficient simulation-extractable SNARK was for SAP.

In the Bitcoin consensus network, all nodes come to agreement on the set of Unspent Transaction Outputs (The “UTXO” set). The size of this shared state is a scalability constraint for the network, as the size of the set expands as more users join the system, increasing resource requirements of all nodes. Decoupling the network’s state size from the storage requirements of individual machines would reduce hardware requirements of validating nodes. We introduce a hash based accumulator to locally represent the UTXO set, which is logarithmic in the size of the full set. Nodes attach and propagate inclusion proofs to the inputs of transactions, which along with the accumulator state, give all the information needed to validate a transaction. While the size of the inclusion proofs results in an increase in network traffic, these proofs can be discarded after verification, and aggregation methods can reduce their size to a manageable level of overhead. In our simulations of downloading Bitcoin’s blockchain up to early 2019 with 500MB of RAM allocated for caching, the proofs only add approximately 25% to the amount otherwise downloaded.

At Crypto 2018, Aggarwal, Joux, Prakash and Santha (AJPS) described a new public-key encryption scheme based on Mersenne numbers. Shortly after the publication of the cryptosystem, Beunardeau et al. described an attack with complexity O(2^(2h)). In this paper, we describe an improved attack with complexity O(2^(1.75h)).

We show that chosen plaintext attacks (CPA) security is equivalent to chosen ciphertext attacks (CCA) security for key-dependent message (KDM) security. Concretely, we show how to construct a public-key encryption (PKE) scheme that is KDM-CCA secure with respect to all functions computable by circuits of a-priori bounded size, based only on a PKE scheme that is KDM-CPA secure with respect to projection functions. Our construction works for KDM security in the single user setting.

Our main result is achieved by combining the following two steps. First, we observe that by combining the results and techniques from the recent works by Lombardi et al. (CRYPTO 2019), and by Kitagawa et al. (CRYPTO 2019), we can construct a reusable designated-verifier non-interactive zero-knowledge (DV-NIZK) argument system based on an IND-CPA secure PKE scheme and a secret-key encryption (SKE) scheme satisfying one-time KDM security with respect to projection functions. This observation leads to the first reusable DV-NIZK argument system under the learning-parity-with-noise (LPN) assumption. Then, as the second and main technical step, we show a generic construction of a KDM-CCA secure PKE scheme using an IND-CPA secure PKE scheme, a reusable DV-NIZK argument system, and an SKE scheme satisfying one-time KDM security with respect to projection functions. Since the classical Naor-Yung paradigm (STOC 1990) with a DV-NIZK argument system does not work for proving KDM security, we propose a new construction methodology to achieve this generic construction.

Moreover, we show how to extend our generic construction and achieve KDM-CCA security in the multi-user setting, by additionally requiring the underlying SKE scheme in our generic construction to satisfy a weak form of KDM security against related-key attacks (RKA-KDM security) instead of one-time KDM security. From this extension, we obtain the first KDM-CCA secure PKE schemes in the multi-user setting under the CDH or LPN assumption.

Securely managing encrypted data on an untrusted party is a challenging problem that has motivated the study of a variety of cryptographic primitives. A special class of such primitives allows an untrusted party to transform a ciphertext encrypted under one key to a ciphertext under another key, using some auxiliary information that does not leak the underlying data. Prominent examples of such primitives in the symmetric-key setting are key-homomorphic PRFs, updatable encryption, and proxy re-encryption. Although these primitives differ significantly in terms of their constructions and security requirements, they share two important properties: (a) they have secrets with structure or extra functionality, and (b) all known constructions of these primitives satisfying reasonably strong definitions of security are based on concrete public-key assumptions, e.g., DDH and LWE.

This raises the question of whether these objects inherently belong to the world of public-key primitives, or they can potentially be built from simple symmetric-key objects such as pseudorandom functions. In this work, we show that the latter possibility is unlikely. More specifically, we show that:

• Any (bounded) key-homomorphic weak PRF with an abelian output group implies a (bounded) input-homomorphic weak PRF, which has recently been shown to imply not only public-key encryption (PKE), but also a variety of primitives such as PIR, lossy TDFs, and even IBE.

• Any ciphertext-independent updatable encryption scheme that is forward and post-compromise secure implies PKE. Moreover, any symmetric-key proxy re-encryption scheme with reasonably strong security guarantees implies a forward and post-compromise secure ciphertext-independent updatable encryption, and hence PKE.

In addition, we show that unbounded (or exact) key-homomorphic weak PRFs over abelian groups are impossible in the quantum world. In other words, over abelian groups, bounded key-homomorphism is the best that we can hope for in terms of post-quantum security. Our attack also works over other structured primitives with abelian groups and exact homomorphisms, including homomorphic one-way functions and input-homomorphic weak PRFs.

Hashing modes are ways to convert a block cipher into a hash function, and those with AES as the underlying block cipher are referred to as AES hashing modes. Sasaki in 2011 introduced the first preimage attack against AES hashing modes with the AES block cipher reduced to 7 rounds, by the method of meet-in-the-middle. In his attack, the key schedules are not taken into account, hence the same attack applies to all three versions of AES. In this paper, by introducing neutral bits from key, extra degrees of freedom are gained, which are utilized in two ways, i.e., to reduce the time complexity and to extend the attack to more rounds. As an immediate result, the complexities of 7-round pseudo-preimage attacks are reduced from $2^{120}$ to $2^{112}$, $2^{96}$, and $2^{96}$ for AES-128, AES-192, and AES-256, respectively. By carefully choosing the neutral bits from key to cancel those from state, the attack is extended to 8 rounds for AES-192 and AES-256 with complexities $2^{120}$ and $2^{96}$. Similar results are obtained for Kiasu-BC, a tweakable block cipher based on AES-128, and interestingly the additional input tweak helps reduce the attack complexities further. To the best of our knowledge, these are the first preimage attacks against 8-round AES hashing modes.

Now that the NIST's post-quantum cryptography competition has entered in its second phase, the time has come to focus more closely on practical aspects of the candidates. While efficient implementations of the proposed schemes are somewhat included in the submission packages, certain issues like the threat of side-channel attacks are often lightly touched upon by the authors. Hence, the community is encouraged by the NIST to join the war effort to treat those peripheral, but nonetheless crucial, topics. In this paper, we study the lattice-based signature scheme qTESLA in the context of the masking countermeasure. Continuing a line of research opened by Barthe et al. at Eurocrypt 2018 with the masking of the GLP signature scheme, we extend and modify their work to mask qTESLA . The masking can be done at any order and specialized gadgets are used to get maximal efficiency at order 1. We implemented our countermeasure in the original code of the submission and did tests at different orders to assess the feasibility of our technique.

Ransomware are malware whose purpose is to generate income for the attacker. The first of these malware made intense use of cryptography, specifically for file encryption. They encrypt some or most files on the computer before asking a ransom for the decryption. Since they appeared, however, ransomware have evolved into different types which fulfill their task in different ways. Some encrypt files and data from the hard drive, others block access to the OS or use private user data to blackmail the user, some aren’t even a real threat, but they scare the user into paying for some fake service or software. The software security industry is well aware of these threats and is constantly analyzing the new versions and types to determine how dangerous they are and to provide an updated protection solution. This article tries to investigate and compare the way these malware work and how they affect the victims computer. Our analysis will provide interesting insight into how they work, it will highlight the particularities of ransomware and will give some information about why some of these malware are more dangerous than others.

The Modular Inversion Hidden Number Problem (MIHNP), introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001, is briefly described as follows: Let ${\mathrm{MSB}}_{\delta}(z)$ refer to the $\delta$ most significant bits of $z$. Given many samples $\left(t_{i}, {\mathrm{MSB}}_{\delta}((\alpha+ t_{i})^{-1} \bmod{p})\right)$ for random $t_i \in \mathbb{Z}_p$, the goal is to recover the hidden number $\alpha \in \mathbb{Z}_p$. MIHNP is an important class of Hidden Number Problem.

In this paper, we revisit the Coppersmith technique for solving a class of modular polynomial equations, which is respectively derived from the recovering problem of the hidden number $\alpha$ in MIHNP. For any positive integer constant $d$, let integer $n=d^{3+o(1)}$. Given a sufficiently large modulus $p$, $n+1$ samples of MIHNP, we present a heuristic algorithm to recover the hidden number $\alpha$ with a probability close to 1 when $\delta/\log_2 p>\frac{1}{d+1}+o(\frac{1}{d})$. The overall time complexity of attack is polynomial in $\log_2 p$, where the complexity of the LLL algorithm grows as $d^{\mathcal{O}(d)}$ and the complexity of the Gr\"{o}bner basis computation grows as $(2d)^{\mathcal{O}(n^2)}$. When $d> 2$, this asymptotic bound outperforms $\delta/\log_2 p>\frac{1}{3}$ which is the asymptotic bound proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. It is the first time that a better bound for solving MIHNP is given, which implies that the conjecture that MIHNP is hard whenever $\delta/\log_2 p<\frac{1}{3}$ is broken. Moreover, we also get the best result for attacking the Inversive Congruential Generator (ICG) up to now.

We construct a delegation scheme for all polynomial time computations. Our scheme is publicly verifiable and completely non-interactive in the common reference string (CRS) model.

Our scheme is based on an efficiently falsifiable decisional assumption on groups with bilinear maps. Prior to this work, publicly verifiable non-interactive delegation schemes were only known under knowledge assumptions (or in the Random Oracle model) or under non-standard assumptions related to obfuscation or multilinear maps.

We obtain our result in two steps. First, we construct a scheme with a long CRS (polynomial in the running time of the computation) by following the blueprint of Paneth and Rothblum (TCC 2017). Then we bootstrap this scheme to obtain a short CRS. Our bootstrapping theorem exploits the fact that our scheme can securely delegate certain non-deterministic computations.

We study leakage-resilient continuously non-malleable secret sharing, as recently intro- duced by Faonio and Venturi (CRYPTO 2019). In this setting, an attacker can continuously tamper and leak from a target secret sharing of some message, with the goal of producing a modified set of shares that reconstructs to a message related to the originally shared value. Our contributions are two fold.

- In the plain model, assuming one-to-one one-way functions, we show how to obtain noisy-leakage-resilient continuous non-malleability for arbitrary access structures, in case the attacker can continuously leak from and tamper with all of the shares inde- pendently.

- In the common reference string model, we show how to obtain a new flavor of secu- rity which we dub bounded-leakage-resilient continuous non-malleability under joint k-selective partitioning. In this model, the attacker is allowed to partition the target n shares into k non-overlapping subsets, and then can continuously leak from and tamper with the shares within each subset jointly. Our construction works for arbitrary ac- cess structures, and assuming (doubly enhanced) trapdoor permutations and collision- resistant hash functions, we achieve a concrete instantiation for $k \in O(n/ \log n)$.

Prior to our work, there was no secret sharing scheme achieving continuous non-malleability against joint tampering, and the only known scheme for independent tampering was tailored to threshold access structures.

Using ideas from the recent Aurora zk-STARK of Ben-Sasson et al. [BCRSVW, Eurocrypt 2019], we present a zk-SNARK with a universal and updatable SRS similar to the recent construction of Maller et al. [MBKM, 2019], called $\mathsf{Sonic}$. Compared to $\mathsf{Sonic}$, our construction achieves significantly better prover run time (less than half) and smaller SRS size (one sixth). However, we only achieve amortized succinct verification time for batches of proofs, either when the proofs are generated in parallel or in [MBKM]'s helper setting, and our proofs are longer than those of [MBKM] (but still contain a $\mathit{constant}$ number of field and group elements).

We define ZOCB and ZOTR for nonce-based authenticated encryption with associated data, and analyze their provable security. These schemes use a tweakable blockcipher (TBC) as the underlying primitive, and fully utilize its input to process a plaintext and associated data (AD). This property is commonly referred to as full absorption, and this has been explored for schemes based on a permutation or a pseudorandom function (PRF). Our schemes improve the efficiency of TBC-based counterparts of OCB and OTR called $\Theta$CB3 (Krovetz and Rogaway, FSE 2011) and $\mathbb{OTR}$ (Minematsu, EUROCRYPT 2014). Specifically, $\Theta$CB3 and $\mathbb{OTR}$ have an independent part to process AD, and our schemes integrate this process into the encryption part of a plaintext by using the tweak input of the TBC. Up to a certain length of AD, ZOCB and ZOTR completely eliminate the independent process for it. Even for longer AD, our schemes process it efficiently by fully using the tweak input of the TBC. For this purpose, based on previous tweak extension schemes for TBCs, we introduce a scheme called $\mathsf{XTX}^{\ast}$. To our knowledge, ZOCB and ZOTR are the first efficiency improvement of $\Theta$CB3 and $\mathbb{OTR}$ in terms of the number of TBC calls. Compared to Sponge-based and PRF-based schemes, ZOCB and ZOTR allow fully parallel computation of the underlying primitive, and have a unique design feature that an authentication tag is independent of a part of AD. We present experimental results illustrating the practical efficiency gain and clarifying the efficiency cost for it with a concrete instantiation. The results show that for long input data, our schemes have gains, while we have efficiency loss for short input data.

At CRYPTO 2018 Cramer et al. presented SPDZ2k, a new secret-sharing based protocol for actively secure multi-party computation against a dishonest majority, that works over rings instead of fields. Their protocol uses slightly more communication than competitive schemes working over fields. However, their approach allows for arithmetic to be carried out using native 32 or 64-bit CPU operations rather than modulo a large prime. The authors thus conjectured that the increased communication would be more than made up for by the increased efficiency of implementations.

In this work we answer their conjecture in the affirmative. We do so by implementing their scheme, and designing and implementing new efficient protocols for equality test, comparison, and truncation over rings. We further show that these operations find application in the machine learning domain, and indeed significantly outperform their field-based competitors. In particular, we implement and benchmark oblivious algorithms for decision tree and support vector machine (SVM) evaluation.

Information ratio of an access structure is an important measure for efficiency of the best secret sharing scheme realizing it. The most common notion of secret sharing security is that of total (perfect) realization. Two well-known relaxations are the notions of statistical and quasi-total secret sharing. In this paper, we study the relation between different security notions. The most significant and technical result of this paper is that quasi-total and total information ratios coincide for linear schemes. To this end, we employ some tools from linear algebra in companion with a newly introduced relaxed security notion, called partial realization. We provide some intuition that why proving coincidence/separation between total and quasi-total information ratios for the class of abelian schemes is probably much more challenging.

We also present some additional results which shed further light on our understanding of different security notions. In particular, one of our results, in combination with a recent result, shows that statistical and total security notions coincide for the class of group-homomorphic schemes, or maybe even a larger class.

The contribution vector (convec) of a secret sharing scheme is the vector of all share sizes divided by the secret size. A measure on the convec (e.g., its maximum or average) is considered as a criterion of efficiency of secret sharing schemes, which is referred to as the information ratio.

It is generally believed that there exists a family of access structures such that the information ratio of any secret sharing scheme realizing it is $2^{\mathrm{\Omega}(n)}$, where the parameter $n$ stands for the number of participants. The best known lower bound, due to Csirmaz (1994), is $\mathrm{\Omega}(n/\log n)$. Closing this gap is a long-standing open problem in cryptology.

Using a technique called \emph{substitution}, we recursively construct a family of access structures by starting from that of Csirmaz, which might be a candidate for super-polynomial information ratio. We provide support for this possibility by showing that our family has information ratio ${n^{\mathrm{\Omega}(\frac{\log n}{\log \log n})}}$, assuming the truth of a well-stated information-theoretic conjecture, called the \emph{substitution conjecture}. The substitution method is a technique for composition of access structures, similar to the so called block composition of Boolean functions, and the substitution conjecture is reminiscent of the Karchmer-Raz-Wigderson conjecture on depth complexity of Boolean functions. It emerges after introducing the notion of convec set for an access structure, a subset of $n$-dimensional real space, which includes all achievable convecs. We prove some topological properties about convec sets and raise several open problems.

A statistical framework applicable to Ring-LWE was outlined by Murphy and Player (IACR eprint 2019/452). Its applicability was demonstrated with an analysis of the decryption failure probability for degree-1 and degree-2 ciphertexts in the homomorphic encryption scheme of Lyubashevsky, Peikert and Regev (IACR eprint 2013/293). In this paper, we clarify and extend results presented by Murphy and Player. Firstly, we make precise the approximation of the discretisation of a Normal random variable as a Normal random variable, as used in the encryption process of Lyubashevsky, Peikert and Regev. Secondly, we show how to extend the analysis given by Murphy and Player to degree-k ciphertexts, by precisely characterising the distribution of the noise in these ciphertexts.

Monero has emerged as one of the leading cryptocurrencies with privacy by design. However, this comes at the price of reduced expressiveness and interoperability as well as severe scalability issues. First, Monero is restricted to coin exchanges among individual addresses and no further functionality is supported. Second, transactions are authorized by linkable ring signatures, a digital signature scheme only available in Monero, hindering thereby the interoperability with the rest of cryptocurrencies. Third, Monero transactions require high on-chain footprint, which leads to a rapid ledger growth and thus scalability issues.

In this work, we extend Monero expressiveness and interoperability while mitigating its scalability issues. We present \emph{Dual Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups (DLSAG)}, a novel linkable ring signature scheme that enables for the first time \emph{refund transactions} natively in Monero: DLSAG can seamlessly be implemented along with other cryptographic tools already available in Monero such as commitments and range proofs. We formally prove that DLSAG achieves the same security and privacy notions introduced in the original linkable ring signature~\cite{Liu2004} namely, unforgeability, signer ambiguity, and linkability. We have evaluated DLSAG and showed that it imposes even slightly lower computation and similar communication overhead than the current digital signature scheme in Monero, demonstrating its practicality. We further show how to leverage DLSAG to enable off-chain scalability solutions in Monero such as payment channels and payment-channel networks as well as atomic swaps and interoperable payments with virtually all cryptocurrencies available today. DLSAG is currently being discussed within the Monero community as an option for possible adoption as a key building block for expressiveness, interoperability, and scalability.

We analyze the structure of finite commutative rings with respect to its idempotent and nilpotent elements. Based on this analysis we provide a quantum-classical IND-CCA^1 attack for ring homomorphic encryption schemes. Moreover, when the plaintext space is a finite reduced ring, i.e. a product of finite fields, we present a key-recovery attack based on representation problem in black-box finite fields. In particular, if the ciphertext space has smooth characteristic the key-recovery attack is effectively computable. We also extend the work of Maurer and Raub on representation problem in black-box finite fields to the case of a black-box product of finite fields of equal characteristic.

Noncommutative cryptography is based on applications of algebraic structures like noncommutative groups, semigroups and non-commutative rings. Its inter-section with Multivariate cryptography contains studies of cryptographic applications of subsemigroups and subgroups of affine Cremona semigroups defined overfinite commutative rings. Efficiently computed homomorphisms between stable subsemigroups of affine Cremona semigroups can be used in tame homomorphisms protocols schemes and their inverse versions. The implementation scheme with the sequence of subgroups of affine Cremona group, which defines projective limit was already suggested. We present the implementation of other scheme which uses two projective limits which define two different infinite groups and the homomorphism between them. The security of corresponding algorithm is based on a complexity of decomposition problem for an element of affine Cremona semigroup into product of given generators. These algorithms may be used in postquantum technologies.