International Association
for Cryptologic Research

We show that the recently introduced notion of round-by-round soundness for interactive proofs (Canetti et al.; STOC 2019) is equivalent to the notion of soundness against state restoration attacks (Ben-Sasson, Chiesa, and Spooner; TCC 2016). We also observe that neither notion is implied by the random-oracle security of the Fiat-Shamir transform.

One of the main motivations behind introducing PUFs was their ability to resist physical attacks. Among them, cloning was the major concern of related scientific literature. Several primitive PUF designs have been introduced to the community, and several machine learning attacks have been shown capable to model such constructions. Although a few works have expressed how to make use of Side-Channel Analysis (SCA) leakage of PUF constructions to significantly improve the modeling attacks, little attention has been payed to provide corresponding countermeasures. In this paper, we present a generic technique to operate any PUF primitive in an SCA-secure fashion. We, for the first time, make it possible to apply a provably-secure masking countermeasure – Threshold Implementation (TI) – on a strong PUF design. As a case study, we concentrate on the Interpose PUF, and based on practical experiments on an FPGA prototype, we demonstrate the ability of our construction to prevent the recovery of intermediate values through SCA measurements.

Within the Transport Layer Security (TLS) Protocol Version 1.3, RFC 7748 specifies elliptic curves targeted at the 128-bit and the 224-bit security levels. For the 128-bit security level, the Montgomery curve Curve25519 and its birationally equivalent twisted Edwards curve Ed25519 are specified, while for the 224-bit security level, the Montgomery curve Curve448 and its birationally equivalent Edwards curve Edwards448 are specified. The contribution of this work is to propose new pairs of Montgomery-Edwards curves at both the 128-bit and the 224-bit security levels. The new curves are nice in the sense that they have very small curve coefficients and base points. Compared to the curves in RFC 7748, the new curves lose two bits of security. The main advantage of the new curves over those in RFC 7748 is that for 64-bit implementation, all the reduction steps on the outputs of additions and subtractions in the ladder algorithm can be omitted. For 64-bit implementations on the Skylake and the Kaby Lake processors, about 21% improvement in speed is achieved at the 128-bit security level and about 28% improvement in speed is obtained at the 224-bit security level.

In recent years, the concept of Internet of Things (IoT) network used to enable everyday objects and electronic devices to communicate with each other has been extensively discussed. There are three main types of communication that can be assumed in an IoT network: unicast, group, and broadcast communication. Apart from that, Hamasaki et al. considered geometric characteristics and proposed a method of geometric group key sharing. Thereafter, a key sharing method suitable for sharing a pairwise key by implementing the method proposed by Hamasaki et al. had been proposed by Nishigami et al. However, testing this method, we found that when a node and its fellow nodes are attacked together, the keys of the rest of the nodes will be leaked. Therefore, in this paper, using the feature introduced in geometric group key sharing, we propose a method that enables a pairwise key to be securely shared. In addition, we extend our method of pairwise key sharing to be applicable for group key sharing to achieve a way to share efficiently pairwise, group, and global keys used in broadcast communication. Finally, we evaluate the efficiency of our proposed method.

Ciphertext-policy attribute-based encryption (CP-ABE) is a desirable scheme to use in cloud-based applications, especially on IoT devices. As most of these devices are battery-limited and memory-limited, leading to a constraint in designing a robust and straightforward mechanism involving less computation and less memory. But none of the systems are secure and based on conventional cryptosystems. Here we propose a constant-size secret key and constant-size ciphertext scheme based on RSA cryptosystem, which performs encryption and decryption in O(1) time complexity. We also prove that the scheme is secure and compare it with already existing schemes.

Event date: 22 June to 26 June 2020
Submission deadline: 15 February 2020
Notification: 1 April 2020

A permuted puzzle problem is defined by a pair of distributions $D_0,D_1$ over $S^n$. The problem is to distinguish samples from $D_0,D_1$, where the symbols of each sample are permuted by a single secret permutation $p$ of $[n]$.

The conjectured hardness of specific instances of permuted puzzle problems was recently used to obtain the first candidate constructions of Doubly Efficient Private Information Retrieval (DE-PIR) (Boyle et al. & Canetti et al., TCC'17). Roughly, in these works the distributions $D_0,D_1$ over $F^n$ are evaluations of either a moderately low-degree polynomial or a random function. This new conjecture seems to be quite powerful, and is the foundation for the first DE-PIR candidates, almost two decades after the question was first posed by Beimel et al. (CRYPTO'00). While permuted puzzles are a natural and general class of problems, their hardness is still poorly understood.

We initiate a formal investigation of the cryptographic hardness of permuted puzzle problems. Our contributions lie in three main directions:

1. Rigorous formalization. We formalize a notion of permuted puzzle distinguishing problems, extending and generalizing the proposed permuted puzzle framework of Boyle et al. (TCC'17).

2. Identifying hard permuted puzzles. We identify natural examples in which a one-time permutation provably creates cryptographic hardness, based on ``standard'' assumptions. In these examples, the original distributions $D_0,D_1$ are easily distinguishable, but the permuted puzzle distinguishing problem is computationally hard. We provide such constructions in the random oracle model, and in the plain model under the Decisional Diffie-Hellman (DDH) assumption. We additionally observe that the Learning Parity with Noise (LPN) assumption itself can be cast as a permuted puzzle.

3. Partial lower bound for the DE-PIR problem. We make progress towards better understanding the permuted puzzles underlying the DE-PIR constructions, by showing that a toy version of the problem, introduced by Boyle et al. (TCC'17), withstands a rich class of attacks, namely those that distinguish solely via statistical queries.

We consider the problem of proving in zero knowledge that an element of a public set satisfies a given property without disclosing the element, i.e. that for some $u$, "$u \in S$ and $P(u)$ holds''. This problem arises in many applications (anonymous cryptocurrencies, credentials or whitelists) where, for privacy or anonymity reasons, it is crucial to hide certain data while ensuring properties of such data. We design new modular and efficient constructions for this problem through new commit-and-prove zero-knowledge systems for set membership, i.e. schemes proving $u \in S$ for a value $u$ that is in a public commitment $c_u$. Being commit-and-prove, our solutions can act as plug-and-play modules in statements of the form "$u \in S$ and $P(u)$ holds'' (by combining our set membership system with any other commit-and-prove scheme for $P(u)$). Also, they work with Pedersen commitments over prime order groups which makes them compatible with popular systems such as Bulletproofs or Groth16. Both public parameters and proofs in our solutions have constant-size (i.e., independent of the size of the sets). Compared to previous work that achieves similar properties---Camenisch and Lysyanskaya (CRYPTO 2002) and the clever techniques combining zkSNARKs and Merkle Trees in Zcash---our protocols offer more flexibility and $2.5 \times$ faster proving time for a set of size $2^{60}$.

We present classical polynomial time attacks against the FRS branching program obfuscator of Fernando-Rasmussen-Sahai (Asiacrypt’17) (with one zerotest parameter), which is robust against all known classical cryptanalyses on obfuscators, when instantiated with the CLT13 multilinear map.

First of all, we (heuristically) reproduce a new zerotest parameter from the original one. The new zerotest parameter mitigates parameter constraints of the message space recovering algorithm proposed by Coron and Notarnicola (Asiacrypt'19), so it enables us to directly apply the algorithm to the FRS obfuscation.

Then, we propose two cryptanalyses of the FRS obfuscation based on the recovered message space. One analysis enables to obtain all secret elements of CLT13, but it requires extra parameter constraints. On the other hand, the other analysis shows that there exist two functionally equivalent programs such that their obfuscated programs are computationally distinguishable. Thus, the FRS scheme does not satisfy the desired security without any additional constraints.

We studied the applicability of differential cryptanalysis to cryptosystems based on operation of addition modulo $2^n$. We obtained an estimate (accurate up to an additive constant) of expected value of entropy $H_n$ in rows of DDT of corresponding mapping. Moreover, the $k$-th moments of $2^{H_n}$ are explored. In particular, asymptotic inequalities that describe the behavior of values $\mathbb{E}2^{H_n}$ and $\mathbb{D}2^{H_n}$ as $n \to \infty$ were obtained. A simple analytical formula for the size of any given equivalence class was obtained. This formula helped to effectively compute the entropy distribution.

The existence of secure indistinguishability obfuscators ($iO$) has far-reaching implications, significantly expanding the scope of problems amenable to cryptographic study. A recent line of work [Ananth, Jain, and Sahai, 2018; Aggrawal, 2018; Lin and Matt, 2018; Jain, Lin, Matt, and Sahai, 2019] has developed a new theory for building $iO$~from simpler building blocks, and represents the state of the art in constructing $iO$~from succinct and instance-independent assumptions. This line of work has culminated in a construction of $iO$~from four assumptions, consisting of two standard assumptions, namely sub-exponentially secure LWE and SXDH over bilinear groups, and two relatively new assumptions: The first assumes weak pseudorandomness properties of generators computable by constant-degree polynomials over the integers, as well as a LWE leakage assumption, introduced by [Jain, Lin, Matt, and Sahai, 2019]. The second assumes the existence of Boolean PRGs with constant block locality [Goldreich 2000, Lin and Tessaro 2017]. In this work, we make the following contributions:

* We completely remove the need of one of the two non-standard assumptions mentioned above; namely we no longer need to assume a constant-block local PRG. This yields a construction of $iO$ based on three assumptions of LWE, SXDH and a constant degree perturbation resilient generator [Jain, Lin, Matt, and Sahai, 2019]

* Our construction is arguably simpler and more direct than previous constructions. We construct the notion of special homomorphic encoding (SHE) for all $P/poly$ from LWE, by adapting techniques from Predicate Encryption [Gorbunov, Vaikunthanathan and Wee, 2015]. Prior to our work, SHE was only known for the class $\mathsf{NC}^1$, from Ring LWE [Agrawal and Rosen, 2017]. Our new SHE allows our construction of $iO$ to avoid an intermediate step of bootstrapping via randomized encodings. Indeed, we construct a functional encryption scheme whose ciphertext grows sublinearly only in the output length of the circuits as opposed to its size. This is first such scheme that does not rely on multilinear maps.

* Finally, we investigate a main technical concept facilitating the line of work on $iO$; namely the notion of partially hiding functional encryption introduced by [Ananth, Jain, and Sahai 2018]. The partially hiding functional encryption used in these $iO$ constructions allows an encryptor to encrypt vectors of the form $\vec{x},\vec{y},\vec{z} \in \mathbb{Z}^n_{p}$ and allows any decrptor with a key for function $f$ to learn $\langle f(\vec{x}), \vec{y}\otimes \vec{z} \rangle$. The encryption is allowed to reveal $\vec{x}$ while keeping $\vec{y},\vec{z}$ hidden. Furthermore, the size of the cipher-text should grow linearly in $n$.

We significantly improve the starte of the art for partially hiding functional encryption: Assuming SXDH over bilinear maps, we construct a partially hiding FE scheme where the function $f$ is allowed to be any polynomial sized arithmetic branching program. Prior to our work, the best partially hiding FE only supported the class of constant degree polynomials over $\mathbb{Z}_{p}$ [Jain, Lin, Matt, and Sahai 2019].

Succinct non-interactive arguments (SNARGs) enable verifying NP computations with substantially lower complexity than that required for classical NP verification. In this work, we construct a zero-knowledge SNARG candidate that relies only on lattice-based assumptions which are claimed to hold even in the presence of quantum computers.

Central to this new construction is the notion of linear-targeted malleability introduced by Bitansky et al. (TCC 2013) and the conjecture that variants of Regev encryption satisfy this property. Then, using the efficient characterization of NP languages as Square Arithmetic Programs we build the first quantum-resilient zk-SNARG for arithmetic circuits with a constant-size proof consisting of only 2 lattice-based ciphertexts.

Our protocol is designated-verifier, achieves zero-knowledge and has shorter proofs and shorter CRS than the previous such schemes, e.g. Boneh et al. (Eurocrypt 2017).

We construct the first actively-secure Multi-Party Computation (MPC) protocols with an arbitrary number of parties in the dishonest majority setting, for an arbitrary field F with constant communication overhead over the “passive-GMW” protocol (Goldreich, Micali and Wigderson, STOC ‘87). Our protocols rely on passive implementations of Oblivious Transfer (OT) in the boolean setting and Oblivious Linear function Evaluation (OLE) in the arithmetic setting. Previously, such protocols were only known over sufficiently large fields (Genkin et al. STOC ‘14) or a constant number of parties (Ishai et al. CRYPTO ‘08).

Conceptually, our protocols are obtained via a new compiler from a passively-secure protocol for a distributed multiplication functionality $F_{mult}$ , to an actively-secure protocol for general functionalities. Roughly, $F_{mult}$ is parameterized by a linear-secret sharing scheme S, where it takes S-shares of two secrets and returns S-shares of their product.

We show that our compilation is concretely efficient for sufficiently large fields, resulting in an over- head of 2 when securely computing natural circuits. Our compiler has two additional benefits: (1) it can rely on any passive implementation of $F_{mult}$, which, besides the standard implementation based on OT (for boolean) and OLE (for arithmetic) allows us to rely on implementations based on threshold cryptosystems (Cramer et al. Eurocrypt ‘01); and (2) it can rely on weaker-than-passive (i.e., imperfect/leaky) implementations, which in some parameter regimes yield actively-secure protocols with overhead less than 2.

Instantiating this compiler with an “honest-majority” implementation of FMULT, we obtain the first honest-majority protocol with optimal corruption threshold for boolean circuits with constant communication overhead over the best passive protocol (Damgård and Nielsen, CRYPTO ‘07).

The first related-key attack on 3-round (of 9) Kuznyechik with 2-round (of 8) key schedule was presented in CTCrypt'18. This article describes a related-key attack on 5-round cipher with the same key schedule. The presented one also has a practical complexity ($2^{32}$ operations, $2^{30}$ memory, $2^{16}$ related keys) and verified in practice. We obtained result due to the simultaneous use of the integral properties of the cipher transformations and the key schedule.

Masking is known as the most widely studied countermeasure against side-channel analysis attacks. Since a masked implementation is based on a certain number of shares (referred to as the order of masking), it still exhibits leakages at higher orders. In order to exploit such leakages, higher-order statistical moments individually at each order need to be estimated reflecting the higher-order attacks. Instead, Mutual Information Analysis (MIA) known for more than 10 years avoids such a moment-based analysis by considering the entire distribution for the key recovery. Recently the $\chi^2$-test has been proposed for leakage detection and as a distinguisher where also the whole distribution of the leakages is analyzed. In this work, we compare these two schemes to examine their dependency. Indeed, one of the goals of this research is to conclude whether one can outperform the other. In addition to a theoretical comparison, we present two case studies and their corresponding practical evaluations. Both case studies are masked hardware implementations; one is an FPGA-based realization of a threshold implementation of PRESENT, and the other is an AES implementation as a coprocessor on a commercial smart card.

Event date: 1 June 2020
Submission deadline: 15 January 2020
Notification: 4 March 2020

Event date: 14 December to 16 December 2020
Submission deadline: 21 June 2020
Notification: 30 August 2020

Masking is a popular countermeasure to protect cryptographic implementations against side-channel attacks (SCA). In the literature, a myriad of proposals of masking schemes can be found. They are typically defined by a masked multiplication, since this can serve as a basic building block for any nonlinear algorithm. However, when masking generic Boolean functions of algebraic degree t, it is very inefficient to construct the implementation from masked multiplications only. Further, it is not immediately clear from the description of a masked multiplication, how to efficiently implement a masked Boolean function. In this work, we fill this gap in the literature with a detailed description and investigation of a generic masking methodology for Boolean functions of any degree t at any security order d.

iDASH is a competition soliciting implementations of cryptographic schemes of interest in the context of biology. In 2019, one track asked for multi-party computation implementations of training of a machine learning model suitable for two datasets from cancer research. In this note, we describe our solution submitted to the competition. We found that the training can be run on three AWS c5.9xlarge instances in less then one minute using MPC tolerating one semi-honest corruption, and less than ten seconds at a slightly lower accuracy.

In this paper, we propose some improved quantum circuits to implement the Sbox of AES. Our improved quantum circuits are based on the following strategies. First, we try to find the minimum set of the intermediate variables that can be used to compute the 8-bit output of the Sbox. Second, we check whether some wires store intermediate variables and remain idle until the end. And we can reduce the number of qubit by reusing some certain wires. Third, we try to compute the output of the Sbox without ancillas qubits, because we do not need to be clean up the wires storing the output of the Sbox. This operation will reduce the number of Toffoli gates. Our first quantum circuit only needs 26 qubits and 46 Toffoli gates, while quantum circuit proposed by Langenberg \emph{et al.} required 32 qubits and 55 Toffoli gates. Furthermore, we can also construct our second quantum circuit with 22 qubits and 60 Toffoli gates.