International Association
for Cryptologic Research

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.

The functionality of classically-instructed remotely prepared random secret qubits was introduced in (Cojocaru et al 2018) as a way to enable classical parties to participate in secure quantum computation and communications protocols. The idea is that a classical party (client) instructs a quantum party (server) to generate a qubit to the server's side that is random, unknown to the server but known to the client. Such task is only possible under computational assumptions. In this contribution we define a simpler (basic) primitive consisting of only BB84 states, and give a protocol that realizes this primitive and that is secure against the strongest possible adversary (an arbitrarily deviating malicious server). The specific functions used, were constructed based on known trapdoor one-way functions, resulting to the security of our basic primitive being reduced to the hardness of the Learning With Errors problem. We then give a number of extensions, building on this basic module: extension to larger set of states (that includes non-Clifford states); proper consideration of the abort case; and verifiablity on the module level. The latter is based on ``blind self-testing'', a notion we introduced, proved in a limited setting and conjectured its validity for the most general case.

In this paper, we propose that countermeasures against instruction-related timing attack would be vulnerable to single-trace attacks, which are presented at ISPEC 2017 and CHES 2019. The countermeasures use determiner to make operations, which leak timing side-channel information, perform in a constant-time. Since determiner is divided into two groups according to secret credentials, it is possible to recover secret credentials by clustering determiner into two groups.

We recall a series of physical cryptography solutions and provide the reader with relevant security analyses. We mostly turn our attention to describing attack scenarios against schemes solving Yao's millionaires' problem, protocols for comparing information without revealing it and public key cryptosystems based on physical properties of systems.

Comparison of two numbers is one of the most frequently used operations, but it has been a challenging task to efficiently compute the comparison function in homomorphic encryption (HE) which basically support addition and multiplication. Recently, Cheon et al. (Asiacrypt 2019) introduced a new approximate representation of the comparison function with a rational function, and showed that this rational function can be evaluated by an iterative algorithm. Due to this iterative feature, their method achieves a logarithmic computational complexity compared to previous polynomial approximation methods; however, the computational complexity is still not optimal, and the algorithm is quite slow for large-bit inputs in HE implementation.

In this work, we propose new comparison methods with optimal asymptotic complexity based on composite polynomial approximation. The main idea is to systematically design a constant-degree polynomial $f$ by identifying the core properties to make a composite polynomial $f\circ f \circ \cdots \circ f$ get close to the sign function (equivalent to the comparison function) as the number of compositions increases. Utilizing the devised polynomial $f$, our new comparison algorithms only require $\Theta(\log(1/\epsilon)) + \Theta(\log\alpha)$ computational complexity to obtain an approximate comparison result of $a,b\in[0,1]$ satisfying $|a-b|\ge \epsilon$ within $2^{-\alpha}$ error. The asymptotic optimality results in substantial performance enhancement: our comparison algorithm on encrypted $20$-bit integers for $\alpha = 20$ takes $1.43$ milliseconds in amortized running time, which is $30$ times faster than the previous work.

Homomorphic encryption (HE) is one of the main tools in secure multiparty computation (MPC), and the (elliptic-curve) lifted-ElGamal cryptosystem is certainly the most efficient among the existing HE schemes. However, the combination of MPC with this most efficient HE has rarely appeared in the literature. This is mainly because the major known techniques for (additively) HE-based MPC are not available for this scheme due to its typical restriction that only a plaintext in a small range can be efficiently decrypted.

In this paper, we resolve this problem. By our technique, a Server having a lifted-ElGamal ciphertext $[[m]]$ with unknown small plaintext $m$ can obtain a ciphertext $[[ \varphi(m) ]]$ for an arbitrary function $\varphi$ by just one-round communication with a semi-honest Client (and also two-rounds with a malicious Client) having a decryption key, where $m$ is kept secret for both parties. This property enlarges much the variations of MPC based on the most efficient lifted-ElGamal cryptosystem. As an application, we implemented MPC for exact edit distance between two encrypted strings; our experiment for strings of length $1024$ shows that the protocol takes only $45$ seconds in LAN environments and about $3$ minutes even in WAN environments. Moreover, our technique is also available with other "lifted-ElGamal type" HE schemes and admits different keys/schemes for the original and the resulting ciphertexts. For example, we can securely convert a level-2 (i.e., after multiplication) ciphertext for some two-level HE schemes into a level-1 (i.e., before multiplication) ciphertext, and securely apply arbitrary functions $\varphi(m)$ to encrypted plaintexts for some attribute-based HE schemes. This is the first result (even by using communication) on realizing these two functionalities.

Nominative signature is a cryptographic primitive where two parties collude to produce a signature. It is a user certification system and has applications in variety of sectors where nominee cannot trust heavily on the nominator to validate nominee’s certificate and only targeted entities are allowed to verify signature on sensitive data. We provide a new construction for nominative signature from standard assumptions on lattice. Our construction relies on collision resistant preimage sampleable function and symmetric key primitives like collision resistant pseudorandom function and zero knowledge proof system ZKB++ for Boolean circuits. We provide a detailed security analysis and show that our construction achieves security under unforgeability, invisibility, impersonation and non-repudiation in existing model. Furthermore, our construction exhibits non-transferability. The security under non-repudiation is achieved in the quantum random oracle model using Unruh transform of ZKB++.

As a fundamental tool in lattice-based cryptosystems, discrete Gaussian samplers play important roles in both efficiency and security of lattice-based schemes. Approximate discrete rounded Gaussian sampler, central binomial sampler and bounded uniform sampler are three types of error samplers that are commonly used in the designs of various schemes. However, known cryptanalytics about error samplers concentrate on their standard deviations and no analysis about distinct structures of distributions have been proposed. In this paper, we address this problem by considering the dual attack for LWE instances and investigating Fourier transforms of these distributions. We introduce the concept of local width which enables us to get a more detailed look of these distributions and the distinguish advantages. We make an analysis of dual attack for different distributions and provide a novel measure model to describe the differences. Within this refined framework, we also propose a novel type of error sampler which can achieve high efficiency, security as well as flexibility.

We study the problem of delegating computations via interactive proofs that can be probabilistically checked. Known as *interactive oracle proofs* (IOPs), these proofs extend probabilistically checkable proofs (PCPs) to multi-round protocols, and have received much attention due to their application to constructing cryptographic proofs (such as succinct non-interactive arguments).

We prove that a rich class of NEXP-complete problems, which includes machine computations over large fields and succinctly-described arithmetic circuits, has constant-query IOPs with O(T)-size proofs and polylog(T)-time verification for T-size computations. This is the first construction that simultaneously achieves linear-size proofs and fast verification, regardless of query complexity.

An important metric when using IOPs to delegate computations is the cost of producing the proof. The highly-optimized proof length in our construction enables a very efficient prover, with arithmetic complexity O(T log T). Hence this construction is also the first to simultaneously achieve prover complexity O(T log T) and verifier complexity polylog(T).

We construct a new polynomial commitment scheme for univariate and multivariate polynomials over finite fields, with public-coin evaluation proofs that have logarithmic communication and verification cost in the number of coefficients of the polynomial. The underlying technique is a Diophantine Argument of Knowledge (DARK), leveraging integer representations of polynomials and groups of unknown order. Security is shown from the strong RSA and the adaptive root assumption. Moreover, the scheme does not require a trusted setup if instantiated with class groups. We apply this new cryptographic compiler to a restricted class of algebraic linear IOPs in order to obtain doubly-efficient public-coin IPs with succinct communication and witness-extended emulation for any NP relation. Allowing for linear preprocessing, the online verifier's work is logarithmic in the circuit complexity of the relation.

In particular, we obtain quasi-linear prover time when compiling the IOP employed in Sonic (MBKM, CCS 19). Applying the Fiat-Shamir transform in the random oracle model results in a SNARK system with quasi-linear preprocessing, quasi-linear (online) prover time, logarithmic proof size, and logarithmic (online) verification time for arbitrary circuits. The SNARK is also concretely efficient with $7.8$KB proofs ($70\times$ reduction over state of the art) and $75$ms verification time for circuits with 1 million gates. Most importantly, this SNARK is transparent: it does not require a trusted setup. We also obtain zk-SNARKs by applying a variant of our polynomial commitment scheme that is hiding and offers zero-knowledge evaluation proofs. This construction is the first transparent zk-SNARK that has both a practical prover time as well as asymptotically logarithmic proof size and verification time. We call this system *Supersonic*.

We (once again) refute recurring claims about a public-key encryption scheme that allegedly provides unconditional security. This is approached from two angles: We give an information-theoretic proof of impossibility, as well as a concrete attack breaking the proposed scheme in essentially no time.