International Association
for Cryptologic Research

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.

It is well known, due to the adaptive attack by Galbraith, Petit, Shani, and Ti (GPST), that plain SIDH is insecure in the static setting. Recently, Kayacan's preprint "A Note on the Static-Static Key Agreement Protocol from Supersingular Isogenies", ePrint 2019/815, presented two possible fixes. Protocol A (also known as 2-SIDH, a low-degree instantiation of the more general k-SIDH) has been broken by Dobson, Galbraith, LeGrow, Ti, and Zobernig. In this short note we will show how to break Protocol B in one oracle query per private key bit and $O(1)$ local complexity.

We present distinguishing attacks (based on the Birthday Paradox) which show that the use of $2^{\ell}$ permutations for a block cipher is insufficient to obtain a security of $\ell$ bits in the Ideal Cipher Model.

The context is that of an Oracle that can provide an Adversary the ciphertexts of a very small number of known plaintexts under a large number of (session) keys and IVs/nonces.

Our attacks distinguish an ideal cipher from a ``perfectly ideal'' block cipher, realised as an Oracle that can always produce new permutations up to the cardinality of the symmetric group on the block space.

The result is that in order to guarantee that an Adversary which is time limited to $O(2^{\ell})$ encryption requests has only a negligible advantage, the cipher needs to express $2^{3\ell}$ distinct permutations. This seems to contradict a folklore belief about the security of using a block cipher in the multi-key setting, i.e.\ to obtain $\ell$-bit security it is sufficient to use $\ell$- or $2\,\ell$-bit keys depending on the mode of operation and the use case.

In this paper, we suggest a new format for converting side channel traces to fully utilize the deep learning schemes. Due to the fact that many deep learning schemes have been advanced based on MNIST style datasets, we convert from raw-trace based on float or byte data to picture-formatted trace based on position. This is induced that the best performance can be acquired from deep learning schemes. Although the overfitting cannot be avoided in our suggestion, the accuracy for validation outperforms to previous results of side channel analysis based on deep learning. Additionally, we provide a novel criteria for attack success or fail based on statistical confidence level rather than rule of thumb. Even though the data storage is slightly increased, our suggestion can completely be recovered the correct key compared to previous results. Moreover, our suggestion scheme has a lot of potential to improve side channel attack.

Blockchain, which is a useful tool for providing data integrity, has emerged as an alternative to centralized servers. Concentrating on the integrity of the blockchain, many applications have been developed. Specifically, a blockchain can be utilized in proving the user's identity using its strong integrity. However, since all data in the blockchain is publicly available, it can cause privacy problems if the user's identity is stored in the blockchain unencrypted. Although the encryption of the private information can diminish privacy problems in the blockchain, it is difficult to transparently utilize encrypted user information in the blockchain. To provide integrity and privacy of user information simultaneously in the blockchain, we propose a SIMS (Self-Sovereign Identity Management System) framework based on a zk-SNARK (zero-knowledge Succinct Non-interactive ARgument of Knowledge). In our proposed SIMS, the user information is employed in a privacy-preserving way due to the zero-knowledge property of the zk-SNARK. We construct a SIMS scheme and prove its security. We describe applications of SIMS and demonstrate its practicality through efficient implementations.

Due to its capabilities of searches and updates over the encrypted database, the dynamic searchable symmetric encryption (DSSE) has received considerable attention recently. To resist leakage abuse attacks, a secure DSSE scheme usually requires forward and backward privacy. However, the existing forward and backward private DSSE schemes either only support single keyword queries or require more interactions between the client and the server. In this paper, we first give a new leakage function for range queries, which is more complicated than the one for single keyword queries. Furthermore, we propose a concrete forward and backward private DSSE scheme by using a refined binary tree data structure. Finally, the detailed security analysis and extensive experiments demonstrate that our proposal is secure and efficient, respectively.

User interaction constitutes a largely unexplored field in protocol analysis, even in instances where the user takes an active role as a trusted third party, such as in the Internet of Things (IoT) device initialization protocols. Initializing the study of computational analysis of 3-party authentication protocols where one party is a physical user, this research introduces the 3-party possession user mediated authentication (3-PUMA) model. The 3-PUMA model addresses active user participation in a protocol which is designed to authenticate possession of a fixed data string – such as in IoT device commissioning. To demonstrate the 3-PUMA model in practice, we provide a computational analysis of the ISO/IEC 9798- 6:2010 standard’s Mechanism 7a authentication protocol which includes a user interface and interaction as well as a device-to-device channel. We show that the security of ISO/IEC 9798-6:2010 Mechanism 7a relies upon a non-standard MAC security notion, which we term existential unforgeability under key collision attacks (EUF-KCA). It is unknown if any standardized MAC algorithm achieves EUF-KCA security, indicating a potential vulnerability in the standard.

Developing machine learning models from federated training data, containing many independent samples, is an important task that can significantly enhance the potential applicability and prediction power of learned models. Since single users, like hospitals or individual labs, typically collect data-sets that do not support accurate learning with high confidence, it is desirable to combine data from several users without compromising data privacy. In this paper, we develop a privacy-preserving solution for learning a linear regression model from data collectively contributed by several parties (``data owners''). Our protocol is based on the protocol of Giacomelli et al. (ACNS 2018) that utilized two non colluding servers and Linearly Homomorphic Encryption (LHE) to learn regularized linear regression models. Our methods use a different LHE scheme that allows us to significantly reduce both the number and runtime of homomorphic operations, as well as the total runtime complexity. Another advantage of our protocol is that the underlying LHE scheme is based on a different (and post-quantum secure) security assumption than Giacomelli et al. Our approach leverages the Chinese Remainder Theorem, and Single Instruction Multiple Data representations, to obtain our improved performance. For a 1000 x 40 linear regression task we can learn a model in a total of 3 seconds for the homomorphic operations, compared to more than 100 seconds reported in the literature. Our approach also scales up to larger feature spaces: we implemented a system that can handle a 1000 x 100 linear regression task, investing minutes of server computing time after a more significant offline pre-processing by the data owners. We intend to incorporate our protocol and implementations into a comprehensive system that can handle secure federated learning at larger scales.