International Association
for Cryptologic Research

Recently, Bar-On et al. introduced at Eurocrypt’19 a new tool, called the differential-linear connectivity table (DLCT), which allows for taking into account the dependency between the two subciphers E_0 and E_1 involved in differential-linear attacks.

This paper presents a theoretical characterization of the DLCT, which corresponds to an autocorrelation table (ACT) of a vectorial Boolean function. We further provide some new theoretical results on ACTs of vectorial Boolean functions.

In 2012, Aaronson and Christiano introduced the idea of hidden subspace states to build public-key quantum money [STOC '12]. Since then, this idea has been applied to realize several other cryptographic primitives which enjoy some form of unclonability. In this work, we study a generalization of hidden subspace states to hidden coset states. This notion was considered independently by Vidick and Zhang [Eurocrypt '21], in the context of proofs of quantum knowledge from quantum money schemes. We explore unclonable properties of coset states and several applications:

* We show that, assuming indistinguishability obfuscation (iO), hidden coset states possess a certain direct product hardness property, which immediately implies a tokenized signature scheme in the plain model. Previously, a tokenized signature scheme was known only relative to an oracle, from a work of Ben-David and Sattath [QCrypt '17].

* Combining a tokenized signature scheme with extractable witness encryption, we give a construction of an unclonable decryption scheme in the plain model. The latter primitive was recently proposed by Georgiou and Zhandry [ePrint '20], who gave a construction relative to a classical oracle.

* We conjecture that coset states satisfy a certain natural (information-theoretic) monogamy-of-entanglement property. Assuming this conjecture is true, we remove the requirement for extractable witness encryption in our unclonable decryption construction, by relying instead on compute-and-compare obfuscation for the class of unpredictable distributions. As potential evidence in support of the monogamy conjecture, we prove a weaker version of this monogamy property, which we believe will still be of independent interest.

* Finally, we give a construction of a copy-protection scheme for pseudorandom functions (PRFs) in the plain model. Our scheme is secure either assuming iO, OWF and extractable witness encryption, or assuming iO, OWF, compute-and-compare obfuscation for the class of unpredictable distributions, and the conjectured monogamy property mentioned above. This is the first example of a copy-protection scheme with provable security in the plain model for a class of functions that is not evasive.

Yao’s garbling scheme is one of the most fundamental cryptographic constructions. Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security in the selective setting where the adversary chooses the challenge inputs before seeing the garbled circuit assuming secure symmetric-key encryption (and hence one-way functions). This was followed by results, both positive and negative, concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto 2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s scheme (where the output mapping is sent in the online phase, together with the garbled input) that circumvents this negative result, and proved that it is adaptively secure, at least for shallow circuits. In particular, they showed that for the class of circuits of depth $\delta$, the loss in security is at most exponential in $\delta$. The above results all concern the simulation-based notion of security.

In this work, we show that the upper bound of Jafargholi and Wichs is basically optimal in a strong sense. As our main result, we show that there exists a family of Boolean circuits, one for each depth $\delta\in\mathbb{N}$, such that any black-box reduction proving the adaptive indistinguishability of the natural adaptation of Yao’s scheme from any symmetric-key encryption has to lose a factor that is exponential in $\sqrt(\delta)$. Since indistinguishability is a weaker notion than simulation, our bound also applies to adaptive simulation.

To establish our results, we build on the recent approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction with oracle separations to prove fine-grained lower bounds on loss in cryptographic security.

Profiling attacks, especially those based on machine learning, proved to be very successful techniques in recent years when considering the side-channel analysis of symmetric-key crypto implementations. At the same time, the results for implementations of asymmetric-key cryptosystems are very sparse.

This paper considers several machine learning techniques to mount side-channel attacks on two implementations of scalar multiplication on the elliptic curve Curve25519. The first implementation follows the baseline implementation with complete formulae as used for EdDSA in WolfSSl, where we exploit power consumption as a side-channel. The second implementation features several countermeasures, and in this case, we analyze electromagnetic emanations to find side-channel leakage.

Most techniques considered in this work result in potent attacks, and especially the method of choice appears to be convolutional neural networks (CNNs), which can break the first implementation with only a single measurement in the attack phase. The same convolutional neural network demonstrated excellent performance for attacking AES cipher implementations.

Our results show that some common grounds can be established when using deep learning for profiling attacks on very different cryptographic algorithms and their corresponding implementations.

In this work we introduce a new (circuit-dependent) homomorphic secret sharing (HSS) scheme for any $\log/\log\log$-local circuit, with communication proportional only to the width of the circuit and polynomial computation, which is secure assuming the super-polynomial hardness of learning parity with noise (LPN). At the heart of our new construction is a pseudorandom correlation generator (PCG) which allows two parties to locally stretch short seeds into pseudorandom instances of an arbitrary $\log/\log\log$-local additive correlation.

Our main application, and the motivation behind this work, is a generic two-party secure computation protocol for every layered (boolean or arithmetic) circuit of size $s$ with total communication $O(s/\log\log s)$ and polynomial computation, assuming the super-polynomial hardness of the standard learning parity with noise assumption (a circuit is layered if its nodes can be partitioned in layers, such that any wire connects adjacent layers). This expands the set of assumptions under which the `circuit-size barrier' can be broken, for a large class of circuits. The strength of the underlying assumption is tied to the sublinearity factor: we achieve communication $O(s/k(s))$ under the $s^{2^{k(s)}}$-hardness of LPN, for any $k(s) \leq (\log\log s) / 4$.

Previously, the set of assumptions known to imply a PCG for correlations of degree $\omega(1)$ or generic secure computation protocols with sublinear communication was restricted to LWE, DDH, and a circularly secure variant of DCR.

Ring signatures allow a user to sign a message on behalf of a ``ring'' of signers, while hiding the true identity of the signer. As the degree of anonymity guaranteed by a ring signature is directly proportional to the size of the ring, an important goal in cryptography is to study constructions that minimize the size of the signature as a function of the number of ring members.

In this work, we present the first compact ring signature scheme (i.e., where the size of the signature grows logarithmically with the size of the ring) from the (plain) learning with errors (LWE) problem. The construction is in the standard model and it does not rely on a common random string or on the random oracle heuristic. In contrast with the prior work of Backes et al. [EUROCRYPT'2019], our scheme does not rely on bilinear pairings, which allows us to show that the scheme is post-quantum secure assuming the quantum hardness of LWE.

At the heart of our scheme is a new construction of compact and statistically witness indistinguishable ZAP arguments for NP $\cap$ coNP, that we show to be sound based on the plain LWE assumption. Prior to our work, statistical ZAPs (for all of NP) were known to exist only assuming sub-exponential LWE. We believe that this scheme might find further applications in the future.

Cryptographic software is particularly vulnerable to side-channel attacks when programmed in embedded devices. Indeed, the leakage is particularly intense compared to the noise level, making it mandatory for the developer to implement side-channel attack protections. Random masking is a customary option, but in this case, the countermeasure must be high-order, meaning that each sensitive variable is splitted into multiple (at least two) shares. Attacks therefore become computationally challenging.

In this paper, we show that high-order template attacks can be expressed under the form of a convolution. This formulation allows for a considerable speed-up in their computation thanks to fast Fourier transforms. To further speed-up the attack, we also provide an interesting multi-threading implementation of this approach. This strategy naturally applies to template attacks where the leakage of each share is multivariate. We show that this strategy can be adapted to several masking schemes, inherently to the way the splitting is realized. This technique allows us to validate multiple very high-order attacks (order of some tens). In particular, it revealed a non-trivial flaw (hard to detect otherwise) in a multivariate extension of the DSM masking (and subsequently to fix it, and validate its rationale).

Data secrecy is a major concern in many domains. Nowadays, the data are kept in tight security with high privacy. Users do not want to share their secret information with anyone; however, the users' confidential data are not protected from the administrators. Administrators can read the users' data. Why should any Administrator read users' data? To address this issue, we propose a new secrecy protocol to store data secretly, named Secret Cloud Storage, SecretStore for short, to enable Secrecy as a Service model over the Cloud Computing paradigm. This article demonstrates how to protect users' data from any unintended users, including the data administrators. Moreover, we introduce tight security using the client-side symmetric cryptography method. In addition, we devise a forgetful private key to generate or regenerate a private key to encrypt or decrypt based on a secret word. We also show how to strengthen the weak password. Finally, we demonstrate how to implement the Secrecy as a Service model in Cloud Storage using highly unpredictable private keys.

We propose OmniLytics, a blockchain-based secure data trading marketplace for machine learning applications. Utilizing OmniLytics, many distributed data owners can contribute their private data to collectively train a ML model requested by some model owners, and get compensated for data contribution. OmniLytics enables such model training while simultaneously providing 1) model security against curious data owners; 2) data security against curious model and data owners; 3) resilience to malicious data owners who provide faulty results to poison model training; and 4) resilience to malicious model owner who intents to evade the payment. OmniLytics is implemented as a smart contract on the Ethereum blockchain to guarantee the atomicity of payment. In OmniLytics, a model owner publishes encrypted initial model on the contract, over which the participating data owners compute gradients using their private data, and securely aggregate the gradients through the contract. Finally, the contract reimburses the data owners, and the model owner decrypts the aggregated model update. We implement a working prototype of OmniLytics on Ethereum, and perform extensive experiments to measure its gas cost and execution time under various parameter combinations, demonstrating its high computation and cost efficiency and strong practicality.

Plactic signatures use the plactic monoid (Knuth multiplication of semistandard tableaus) and full-domain hashing (SHAKE).

Crypto 2021 will be held virtually August 16-20 2021.

The registration is now open and all relevant information can be found here:https://crypto.iacr.org/2021/registration.php

Information about the program and affiliated events can be found here: https://crypto.iacr.org/2021/

Event date: to
Submission deadline: 2 August 2021

The IACR Fellows Program recognizes outstanding IACR members for technical and professional contributions to the field of cryptology. Today we are pleased to announce five members that have been elevated to the rank of Fellow for 2021:

• Craig Gentry, for breakthrough research on fully homomorphic encryption and other fundamental contributions to cryptography.
• Yehuda Lindell, for fundamental contributions to theory and practice of secure multiparty computation, for sustained educational leadership, and for service to the IACR.
• Josef Pieprzyk, for significant contributions to design and analysis of cryptosystems, and for exceptional service to the IACR and the Asia-Pacific cryptographic community.
• Leonid Reyzin, for fundamental contributions to theory and practice of cryptography, and for service to the IACR.
• Ingrid Verbauwhede, for pioneering and sustained contributions to cryptographic hardware and embedded systems, and for service to the IACR.

Congratulations to the new fellows! More information about the IACR Fellows Program can be found at https://iacr.org/fellows/.

Licensing of software that will run in offline environments introduces constraints on the licensing model that can be supported. The difficulty arises in cases where information needs to be recorded about the usage of the software, for example in a consumption-based licensing model. We describe a method that makes it harder for an adversary to tamper with the recorded data as well as ways for software vendors to detect if tampering with this information would still occur.

Fault Injection Analysis is seen as a powerful attack against implementations of cryptographic algorithms. Over the last two decades, researchers proposed a plethora of countermeasures to secure such implementations. However, the design process and implementation are still error-prone, complex, and manual tasks which require long-standing experience in hardware design and physical security. Moreover, the validation of the claimed security is often only done by empirical testing in a very late stage of the design process. To prevent such empirical testing strategies, approaches based on formal verification are applied instead providing the designer early feedback.

In this work, we present a fault verification framework to validate the security of countermeasures against fault-injection attacks designed for ICs. The verification framework works on netlist-level, parses the given digital circuit into a model based on Binary Decision Diagrams, and performs symbolic fault injections. This verification approach constitutes a novel strategy to evaluate protected hardware designs against fault injections offering new opportunities as performing full analyses under a given fault models.

Eventually, we apply the proposed verification framework to real-world implementations of well-established countermeasures against fault-injection attacks. Here, we consider protected designs of the lightweight ciphers CRAFT and LED-64 as well as AES. Due to several optimization strategies, our tool is able to perform more than 90 million fault injections in a single-round CRAFT design and evaluate the security in under 50 min while the symbolic simulation approach considers all $2^128$ primary inputs.

Oblivious Transfer (OT) is a fundamental primitive in cryptography, supporting protocols such as Multi-Party Computation and Private Set Intersection (PSI), that are used in applications like contact discovery, remote diagnosis and contact tracing. Due to its fundamental nature, it is utterly important that its execution is secure even if arbitrarily composed with other instances of the same, or other protocols. This property can be guaranteed by proving its security under the Universal Composability model. Herein, a 3-round Random Oblivious Transfer (ROT) protocol is proposed, which achieves high computational efficiency, in the Random Oracle Model. The security of the protocol is based on the Ring Learning With Errors assumption (for which no quantum solver is known). ROT is the basis for OT extensions and, thus, achieves wide applicability, without the overhead of compiling ROTs from OTs. Finally, the protocol is implemented in a server-class Intel processor and four application-class ARM processors, all with different architectures. The usage of vector instructions provides on average a 40% speedup. The implementation shows that our proposal is at least one order of magnitude faster than the state-of-the-art, and is suitable for a wide range of applications in embedded systems, IoT, desktop, and servers. From a memory footprint perspective, there is a small increase (16%) when compared to the state-of-the-art. This increase is marginal and should not prevent the usage of the proposed protocol in a multitude of devices. In sum, the proposal achieves up to 37k ROTs/s in an Intel server-class processor and up to 5k ROTs/s in an ARM application-class processor. A PSI application, using the proposed ROT, is up to 6.6 times faster than related art.

We provide new constructions for zero-knowledge commit-and-prove SNARKs (CP-SNARKs) with a universal updatable SRS. Informally, a commit-and-prove argument system is one that can efficiently prove relations over committed inputs. They have many applications, including allowing for efficient composition of proof systems with different strength points.

We first show a general technique to compile Algebraic Holographic Proofs (AHP) with special ``decomposition'' properties into an efficient CP-SNARK with universal and updatable SRS. We require that the polynomials in an AHP can be easily decomposed into components that refer to the committed part of the witness and the rest of the witness respectively.

We then show that some of the most efficient AHP constructions---Marlin, PLONK, and Sonic---satisfy our compilation requirements. To obtain succinct instantiations of our protocols we rely on recent advancements in compressed $\Sigma$-protocol theory (Attema and Cramer, Crypto '20). Our constructions retain the succinct proof size of the underlying AHP and only impose an additional proof size that grows logarithmically with the size of the committed component of the witness.

To factor an integer $N$ we construct $n$ triples of $p_n$-smooth integers $u,v,|u-vN|$ for the $n$-th prime $p_n$. Denote such triple a fac-relation. We get fac-relations from a nearly shortest vector of the lattice $\mathcal L(\mathbf R_{n, f})$ with basis matrix $\mathbf R_{n, f} \in \mathbb R^{(n+1)\times(n+1)}$ where $f\colon [1, n]\to[1, n]$ is a permutation of $[1, 2, \ldots, n]$ and $(f(1),\ldots,f(n),N'\ln N)$ is the diagonal and $(N' \ln p_1,\ldots, N' \ln p_n,N' \ln N)$ for $N' = N^{\frac{1}{n+1}}$ is the last line of $\mathbf R_{n, f}$. An independent permutation $f'$ yields an independent fac-relation. We find sufficiently short lattice vectors by strong primal-dual reduction of $\mathbf R_{n, f}$. We factor $N\approx 2^{400}$ by $n = 47$ and $N\approx 2^{800}$ by $n = 95$. Our accelerated strong primal-dual reduction of [GN08] factors integers $N\approx 2^{400}$ and $N\approx 2^{800}$ by $4.2\cdot 10^9$ and $8.4\cdot 10^{10}$ arithmetic operations, much faster then the quadratic sieve and the number field sieve and using much smaller primes $p_n$. This destroys the RSA cryptosystem.

A succinct functional commitment (SFC) scheme for a circuit class $\mathbf{CC}$ enables, for any circuit $\mathcal{C} \in \mathbf{CC}$, the committer to first succinctly commit to a vector $\vec{\alpha}$, and later succinctly open the commitment to $\mathcal{C} (\vec{\alpha}, \vec{\beta})$, where the verifier chooses $\vec{\beta}$ at the time of opening. Unfortunately, SFC commitment schemes are known only for severely limited function classes like the class of inner products. By making non-black-box use of SNARK-construction techniques, we propose an SFC scheme for the large class of semi-sparse polynomials. The new SFC scheme can be used to, say, efficiently (1) implement sparse polynomials, and (2) aggregate various interesting SFC (e.g., vector commitment and polynomial commitment) schemes. The new scheme is evaluation-binding under a new instantiation of the computational uber-assumption. We provide a thorough analysis of the new assumption.

FlexAEAD is a block cipher candidate submitted to the NIST Lightweight Cryptography standardization project, based on repeated application of an Even-Mansour construction. In order to optimize performance, the designers chose a relatively small number of rounds, using properties of the mode and bounds on differential and linear characteristics to substantiate their security claims. Due to a forgery attack with complexity $2^{46}$, FlexAEAD was not selected to the second round of evaluation in the NIST project.

In this paper we present a practical key recovery attack on FlexAEAD, using clusters of differentials for the internal permutation and the interplay between different parts of the mode. Our attack, which was fully verified in practice, allows recovering the secret subkeys of FlexAEAD-64 with a time complexity of less than $2^{31}$ encryptions (with an experimental success rate of $75\,\%$). This is the first practical key recovery attack on a candidate of the NIST standardization project.