International Association
for Cryptologic Research

By revisiting recent neural-network based modeling attacks on XOR Arbiter PUFs from the literature, we show that XOR Arbiter PUFs and Interpose PUFs can be attacked faster, up to larger security parameters, and with orders of magnitude fewer challenge-response pairs than previously known. To support our claim, we discuss the differences and similarities of recently proposed modeling attacks and offer a fair comparison of the performance of these attacks by implementing all of them using the popular machine learning framework Keras and comparing their performance against the well-studied Logistic Regression attack. Our findings show that neural-network-based modeling attacks have the potential to outperform traditional modeling attacks on PUFs and must hence become part of the standard toolbox for PUF security analysis; the code and discussion in this paper can serve as a basis for the extension of our results to PUF designs beyond the scope of this work.

Quantum computers can solve or accelerate specific problems that were not possible with classical computers. Grover's search algorithm, a representative quantum algorithm, finds a specific solution from $N$ unsorted data with $O(\sqrt{N})$ queries. This quantum algorithm can be used to recover the key of symmetric cryptography. In this paper, we present a practical quantum attack using Grover's search to recover the key of ciphers (Caesar and Vigenère). The proposed quantum attack is simulated with quantum programming tools (ProjectQ and Qiskit) provided by IBM. Finally, we minimize the use of quantum resources and recover the key with a high probability.

Protocols for password-based authenticated key exchange (PAKE) allow two users sharing only a short, low-entropy password to establish a secure session with a cryptographically strong key. The challenge in designing such protocols is that they must resist offline dictionary attacks in which an attacker exhaustively enumerates the dictionary of likely passwords in an attempt to match the used password. In this paper, we study the resilience of one particular PAKE against these attacks. Indeed, we focus on the Secure Remote Password (SRP) protocol that was designed by T. Wu in 1998. Despite its lack of formal security proof, SRP has become a de-facto standard. For more than 20 years, many projects have turned towards SRP for their authentication solution, thanks to the availability of open-source implementations with no restrictive licenses. Of particular interest, we mention the Stanford reference implementation (in C and Java) and the OpenSSL one (in C).

In this paper, we analyze the security of the SRP implementation inside the OpenSSL library. In particular, we identify that this implementation is vulnerable to offline dictionary attacks. Indeed, we exploit a call for a function computing modular exponentiation of big numbers in OpenSSL. In the SRP protocol, this function leads to the call of a non-constant time function, thereby leaking some information about the used password when leveraging cache-based \textsc{Flush+Reload} timing attack. Then, we show that our attack is practical, since it only requires one single trace, despite the noise of cache measurements. In addition, the attack is quite efficient as the reduction of some common dictionaries is very fast using modern resources at negligible cost. We also prove that the scope of our vulnerability is not only limited to OpenSSL, since many other projects, including Stanford's, ProtonMail and Apple Homekit, rely on OpenSSL, which makes them vulnerable. We find that our flaw might also impact projects written in Python, Erlang, JavaScript and Ruby, as long as they load the OpenSSL dynamic library for their big number operations. We disclosed our attack to OpenSSL who acknowledged the attack and timely fixed the vulnerability.

The security of code-based cryptography usually relies on the hardness of the syndrome decoding (SD) problem for the Hamming weight. The best generic algorithms are all improvements of an old algorithm by Prange, and they are known under the name of Information Set Decoding (ISD) algorithms. This work aims to extend ISD algorithms’ scope by changing the underlying weight function and alphabet size of SD. More precisely, we show how to use Wagner’s algorithm in the ISD framework to solve SD for a wide range of weight functions. We also calculate the asymptotic complexities of ISD algorithms, both for the classical and quantum case. We then apply our results to the Lee metric, which is currently receiving a significant amount of attention. By providing the parameters of SD for the Lee weight for which decoding seems to be the hardest, our study could have several applications for designing code-based cryptosystems and their security analysis, especially against quantum adversaries.

In this study, we propose an efficient sorting method for encrypted data using fully homomorphic encryption (FHE). The proposed method extends the existing 2-way sorting method by applying the $k$-way sorting network for any prime $k$ to reduce the depth in terms of comparison operation from $O(\log_2^2 n)$ to $O(k\log_k^2 n)$, thereby improving performance. We apply this method to approximate FHE which is widely used due to its efficiency of homomorphic arithmetic operations. In order to build up the $k$-way sorting network, the $k$-sorter, which sorts $k$-numbers with a minimal comparison depth, is used as a building block.

The approximate homomorphic comparison, which is the only type of comparison working on approximate FHE, cannot be used for the construction of the $k$-sorter as it is because the result of the comparison is not binary, unlike the comparison in conventional bit-wise FHEs. To overcome this problem, we propose an efficient $k$-sorter construction utilizing the features of approximate homomorphic comparison. Also, we propose an efficient construction of a $k$-way sorting network using cryptographic SIMD operations. To use the proposed method most efficiently, we propose an estimation formula that finds the appropriate $k$ that is expected to reduce the total time cost when the parameters of the approximating comparisons and the performance of the operations provided by the approximate FHE are given. We also show the implementation results of the proposed method, and it shows that sorting $5^6=15625$ data using $5$-way sorting network can be about $23.3\%$ faster than sorting $2^{14}=16384$ data using $2$-way.

Quadratic AB (almost bent) functions are characterized by the property that the duals of their component functions are bent functions. We prove that these duals are also quadratic and illustrate that these bent duals may give rise to vectorial bent functions (in certain cases having a maximal output dimension). It is then natural to investigate when the linear combinations of quadratic bent duals again yield quadratic bent functions. A necessary and sufficient condition for ensuring the bentness of these linear combinations is provided, by introducing a useful transform that acts on the Walsh spectrum of dual functions. Moreover, we provide a rather detailed analysis related to the structure of quadratic AB functions in the spectral domain, more precisely with respect to their Walsh supports, their intersection, and restrictions of these bent duals to suitable subspaces. It turns out that the AB property is quite complicated even in the quadratic case. However, using the established facts in this article, we could for the first time provide the design of quadratic AB functions in the spectral domain by identifying (using computer simulations) suitable sets of bent dual functions which give rise to possibly new quadratic AB functions in a generic manner. Using a simple non-exhaustive search for suitable sets of defining bent duals $f_1, \ldots,f_5$ on $\mathbb{F}_2^4$, we could easily identify 60 quadratic AB functions $F:\mathbb{F}_2^5 \rightarrow \mathbb{F}_2^5$. It turns out that all these functions are CCZ-equivalent to the Gold AB function but none of these functions is a permutation. On the other hand, when $n=7$, the same approach provides several AB functions which are {\bf not} CCZ-equivalent to Gold functions.

Modern cryptography must satisfy a myriad of security properties, ranging from sound hardness assumptions to correct and secure implementations that resist side-channel cryptanalysis. Curve-based cryptography is not different in this regard, and substantial progress in the last few decades has been achieved in both selecting parameters and devising secure implementation strategies. In this context, the security of implementations of field inversion is sometimes overlooked in the research literature, because (i) the approach based on Fermat's Little Theorem (FLT) suffices performance-wise for many parameters used in practice; (ii) it is typically invoked only at the very end of scalar multiplication or pairing computation, with a small impact in performance; (iii) it is challenging to implement securely for general parameters without a significant performance penalty. However, field inversion can process sensitive information and must be protected with side-channel countermeasures like any other cryptographic operation, as illustrated by recent attacks. In this work, we focus on timing attacks against field inversion for primes of cryptographic interest, both in the case when FLT-based inversion can be efficiently implemented or not. We extend the Fiat-Cryptography framework, which synthesizes provably correct-by-construction implementations, to implement the Bernstein-Yang constant-time inversion algorithm as a step toward this goal. This allows a correct implementation of prime field inversion to be conveniently synthesized for any prime. We benchmark the implementations across a range of primes for curve-based cryptography and they outperform traditional FLT-based approaches in most cases, with observed speedups up to 2.5 for the largest parameters.

Typically, unconditionally secure computation using a (k,n) threshold secret sharing scheme is considered impossible when n<2k-1. Therefore, in our previous work, we first took the approach of finding the conditions required for secure computation under the setting of n<2k-1 and showed that secure computation using a secret sharing scheme can be realized with a semi-honest adversary under the following three preconditions: (1) the result of secure computation does not include 0; (2) random numbers reconstructed by each server are fixed; and (3) each server holds random numbers unknown to the adversary and holds shares of random numbers that make up the random numbers unknown to the adversary. In this paper, we show that by leaving condition (3), secure computation with information-theoretic security against a semi-honest adversary is possible with k&#8804;n<2k-1. In addition, we clarify the advantage of using secret information that has been encrypted with a random number as input to secure computation. One of the advantages is the acceleration of the computation time. Namely, we divide the computation process into a preprocessing phase and an online phase and shift the cost of communication to the preprocessing phase. Thus, for computations such as inner product operations, we realize a faster online phase, compared with conventional methods.

Cube attack has recently been proved as the most effective approach of attacking Trivium. So far, the attack against the highest round-reduced Trivium was given in EUROCRYPT 2020, where key-recovery attacks on 840-, 841-, and 842-round Trivium were presented. By revealing the relation between three-subset division property without unknown subset and the monomials of superpolys, Hu et al. obtained more attacks on 840-, 841-, and 842-round Trivium with lower complexities in ASIACRYPT 2020. In this short paper, we will present a key-recovery cube attack against 843-round Trivium.

This paper proposes distinguishing and key recovery attacks on the reduced-round versions of the SNOW-V stream cipher. First, we construct a MILP model to search for integral characteristics using the division property, and find the best integral distinguisher in the 3-, 4-, and 5-round versions with time complexities of \(2^8\), \(2^{16}\), and \(2^{48}\), respectively. Next, we construct a bit-level MILP model to efficiently search for differential characteristics, and find the best differential characteristics in the 3- and 4-round versions. These characteristics lead to the 3- and 4-round differential distinguishers with time complexities of \(2^{48}\) and \(2^{103}\), respectively. Then, we consider single-bit and dual-bit differential cryptanalysis, which is inspired by the existing study on Salsa and ChaCha. By carefully choosing the IV values and differences, we observe the best bit-wise differential biases with \(2^{&#8722;1.733}\) and \(2^{&#8722;17.934}\) in the 4- and 5-round versions, respectively. This is feasible to construct a very practical distinguisher with a time complexity of \(2^{4.466}\) for the 4-round version, and a distinguisher with a time complexity of at least \(2^{36.868}\) for the 5-round version. Finally, we improve the existing differential attack based on probabilistic neutral bits, which is also inspired by the existing study on Salsa and ChaCha. As a result, we present the best key recovery attack on the 4-round version with a time complexity of \(2^{153.97}\) and data complexity of \(2^{26.96}\). Consequently, we significantly improve the existing best attacks in the initialization phase by the designers.

We introduce MatRiCT+, a practical private blockchain payment protocol based on ``post-quantum'' lattice assumptions. MatRiCT+ builds on MatRiCT due to Esgin et al. (ACM CCS'19) and, in general, follows the Ring Confidential Transactions (RingCT) approach used in Monero, the largest privacy-preserving cryptocurrency. In terms of the practical aspects, MatRiCT+ has 2-17x shorter proofs (depending on the number of input accounts, M) and runs 3-8x faster (for a typical transaction) in comparison to MatRiCT. A significant advantage of MatRiCT+ is that the proof length's dependence on M is very minimal (only O(log M)), while MatRiCT has a proof length linear in M.

To support its efficiency, we devise several novel techniques in our design of MatRiCT+ to achieve compact lattice-based zero-knowledge proof systems, exploiting the algebraic properties of power-of-2 cyclotomic rings commonly used in practical lattice-based cryptography. Along the way, we design an ``optimal'' challenge space with minimal $\ell_1$-norm and invertible challenge differences (with overwhelming probability), while supporting highly-splitting power-of-2 cyclotomic rings. We believe all these results to be widely applicable and of independent interest.

In this paper, we investigate the security of SNOW-V, the new member of the SNOW family proposed in response to the new requirements of confidentiality and integrity protection in 5G. Specifically, we demonstrate two guess-and-determine (GnD) attacks against the full SNOW-V with complexities $2^{384}$ and $2^{378}$ using seven and eight keystream words, respectively, and one distinguishing attack against a reduced variant with complexity $2^{303}$. Our guess-and-determine attacks use enumeration with recursion to explore valid guessing paths, and try to truncate as many guessing paths as possible on early stages of the recursion by carefully designing the order of guessing, and fully exploiting the equation constraints. In our first GnD attack, we guess three 128-bit state variables, and determine the other three using three consecutive keystream words. We use a fourth keystream word to efficiently enumerate solutions of the last state variable and the next three for verification of the correct guess. The second GnD attack is similar but exploits one more keystream word as a side information to truncate more guessing paths. In our distinguishing attack, we consider a reduced version where all 32-bit adders are replaced with exclusive-OR and find a 16-bit linear approximation with the SEI bias $2^{-303}$ using three consecutive keystream words. The main advantage of our distinguishing attack is that we can cancel out the contribution from the linear part locally, without a need to combine keystream words very far away, which is typically required in a classical distinguishing attack against stream ciphers. Thus we are able to give a distinguishing attack requiring $2^{303}$ samples, while these samples can be collected from multiple short keystreams under different (Key, IV) pairs. These attacks do not threaten SNOW-V, but provide more in-depth details for understanding its security and give new ideas for cryptanalysis of other ciphers.

To mark the 10-year anniversary of supersingular isogeny Diffie-Hellman, I will touch on 10 points in defense and support of the SIKE protocol, including the rise of classical hardness, the fact that quantum computers do not seem to offer much help in solving the underlying problem, and the importance of concrete cryptanalytic clarity.

In the final section I will discuss the upcoming SIKE challenges: over $50k USD will be up for grabs for the solutions of mini instances that, according to the SIKE team's security analysis, provide significantly less than 64 bits of classical security. I conclude by urging the proponents of other schemes to construct analogous challenge instances.

The three body problem is the founding problem of deterministic chaos theory. In this article is proposed a new stream cipher algorithm based on a mathematical structure similar to that underlying the 3 body poblem. Is also proposed to use said structure for the design of new bloc ciphers and hash functions algorithms.

In this work, we present a small architecture for quantum-safe hybrid key exchange targeting ECDH and SIKE. This is the first known hardware implementation of ECDH/SIKE-based hybrid key exchange in the literature. We propose new ECDH and EdDSA parameter sets defined over the SIKE primes. As a proof-of-concept, we evaluate SIKEX434, a hybrid PQC scheme composed of SIKEp434 and our proposed ECDH scheme X434 over a new, low-footprint architecture. Both schemes utilize the same 434-bit prime to save area. With only 1663 slices on a small Artix-7 device, our SIKE architecture can compute an entire hybrid key exchange in 320 ms. This is the smallest SIKE architecture in the literature. The hybrid SIKEX434 adds approximately 16% communication overhead and 10% latency overhead over SIKEp434. The additional overhead to support multiple primes indicates the need for new standardized ECC parameters for area-efficient designs in the future.

We introduce a new approach for constructing range proofs. Our approach is modular, and leads to highly competitive range proofs under standard assumption, using less communication and (much) less computation than the state of the art methods, without relying on a trusted setup. Our range proofs can be used as a drop-in replacement in a variety of protocols such as distributed ledgers, anonymous transaction systems, and many more, leading to significant reductions in communication and computation for these applications. At the heart of our result is a new method to transform any commitment over a finite field into a commitment scheme which allows to commit to and efficiently prove relations about bounded integers. Combining these new commitments with a classical approach for range proofs based on square decomposition, we obtain several new instantiations of a paradigm which was previously limited to RSA-based range proofs (with high communication and computation, and trusted setup). More specifically, we get: – Under the discrete logarithm assumption, we obtain the most compact and efficient range proof among all existing candidates (with or without trusted setup). Our proofs are 12% to 20% shorter than the state of the art Bulletproof (Bootle et al., CRYPTO’18) for standard choices of range size and security parameter, and are more efficient (both for the prover and the verifier) by more than an order of magnitude. – Under the LWE assumption, we obtain range proofs that improve over the state of the art in a batch setting when at least a few dozen range proofs are required. The amortized communication of our range proofs improves by up to two orders of magnitudes over the state of the art when the number of required range proofs grows. – Eventually, under standard class group assumptions, we obtain the first concretely efficient standard integer commitment scheme (without bounds on the size of the committed integer) which does not assume trusted setup.

Revocable hierarchical identity-based encryption (RHIBE) is a variant of the standard hierarchical identity-based encryption (HIBE) satisfying the key revocation functionality. Recently, the first adaptively secure RHIBE scheme with compact ciphertexts was proposed by Emura et al. by sacrificing the efficiency of the schemes for achieving adaptive security so that the secret keys are much larger than Seo and Emura's selectively secure scheme with compact ciphertexts. In this paper, we propose a more efficient adaptively secure RHIBE scheme with compact ciphertexts. Our scheme has much shorter secret keys and key updates than Emura et al.'s scheme. Moreover, our scheme has much shorter key updates than Seo and Emura's selectively secure scheme. Emura et al. proved the adaptive security of their scheme by reducing the security of the underlying HIBE schemes to that of their proposed RHIBE scheme, where the adaptive security of the HIBE scheme is inherently proven through the dual system encryption methodology. In contrast, we prove the adaptive security of the proposed RHIBE scheme directly through the dual system encryption methodology. Furthermore, our security proof achieves a tighter reduction than that of Emura et al.

Event date: to
Submission deadline: 31 May 2021

Event date: to
Submission deadline: 30 November 2021

Event date: 11 October to 12 October 2021
Submission deadline: 11 June 2021
Notification: 2 July 2021