International Association
for Cryptologic Research

New Number Field Sieves (NFS) attacks on the discrete logarithm problem have led to increase the key size of pairing-based cryptography and more precisely pairings on most popular curves like BN. To ensure 128-bit security level, recent costs estimations recommand to switch for BLS24 curves. However, using BLS24 curves for pairing requires to have an efficient arithmetic in Fp4.

In this paper, we transposed previous work on multiplication over extesnsion fields using Newton's interpolation to construct a new formula for multiplication in Fp4 and propose time x area efficient hardware implementation of this operation.

This co-processor is implemented on Kintex-7 Xilinx FPGA. The efficiency of our design in terms of time x area is almost 3 times better than previous specific architecture for multiplication in Fp4. Our architecture is used to estimate the efficiency of hardware implementations of full pairings on BLS12 and BLS24 curves with a 128-bit security level. This co-processeur can be easily modified to anticipate further curve changes.

Point randomization is an important countermeasure to protect Elliptic Curve Cryptography (ECC) implementations against side-channel attacks. In this paper, we revisit its worst-case security in front of advanced side-channel adversaries taking advantage of analytical techniques in order to exploit all the leakage samples of an implementation. Our main contributions in this respect are the following: first, we show that due to the nature of the attacks against the point randomization (which can be viewed as Simple Power Analyses), the gain of using analytical techniques over simpler divide-and-conquer attacks is limited. Second, we take advantage of this observation to evaluate the theoretical noise levels necessary for the point randomization to provide strong security guarantees and compare different elliptic curve coordinates systems. Then, we turn this simulated analysis into actual experiments and show that reasonable security levels can be achieved by implementations even on low-cost (e.g. 8-bit) embedded devices. Finally, we are able to bound the security on 32-bit devices against worst-case adversaries.

Bitcoin is a blockchain whose immutability relies on Proof-of-Work: Before appending a new block, some so-called miner has to solve a cryptographic challenge by brute force. The blockchain is spread over a network of faithful miners, whose cumulated computing power is assumed to be so large that, among other things, it should be too expensive for an attacker to mine a secret fork $n$ blocks longer than the main blockchain, provided that $n$ is big enough. For a given targeted advance of $n$ blocks, we investigate the expected time for the attacker to mine such a secret fork, the underlying cumulative distribution function, and some related optimization problems.

By design, TLS (Transport Layer Security) is a 2-party, end-to-end protocol. Yet, in practice, TLS delegation is often deployed: that is, middlebox proxies inspect and even modify TLS traffic between the endpoints. Recently, industry-leaders (e.g., Akamai, Cloudflare, Telefonica, Ericcson), standardization bodies (e.g., IETF, ETSI), and academic researchers have proposed numerous ways of achieving safer TLS delegation. We present LURK the LURK (Limited Use of Remote Keys) extension for TLS~1.2, a suite of designs for TLS delegation, where the TLS-server is aware of the middlebox. We implement and test LURK. We also cryptographically prove and formally verify, in Proverif, the security of LURK. Finally, we comprehensively analyze how our designs balance (provable) security and competitive performance.

The security of cryptosystems based on Chebyshev recursive relation, T_n(x)=2xT_{n-1}(x)-T_{n-2}(x), relies on the difficulty of finding the large degree of Chebyshev polynomials from given parameters. The relation cannot be used to evaluate T_n(x) if n is very large. We will investigate other three methods: matrix-multiplication-based evaluation, halve-and-square evaluation, and root-extraction-based evaluation. Though they have the same theoretical complexity O(\log n\log^2p), we find in some cases the root-extraction-based method is more efficient than the others, which is as fast as the general modular exponentiation. The result indicates that the hardness of some cryptosystems based on modular Chebyshev polynomials is almost equivalent to that of solving general discrete logarithm.

In a hybrid key encapsulation construction, multiple independent key encapsulation mechanisms are combined in a way that ensures the resulting key is secure according to the strongest mechanism. Such constructions can combine mechanisms that are secure in different settings and achieve the combined security of all mechanisms. For example classical and post-quantum mechanisms can be combined in order to secure communication against current threats as well as future quantum adversaries. This paper contains proofs of security for two hybrid key encapsulation mechanisms along with the relevant security definitions. Practical interpretation of these results is also provided in order to guide the use of these mechanisms in applications and standards.

We use biometrics like fingerprints and facial images to identify ourselves to our mobile devices and log on to applications everyday. Such authentication is internal-facing: we provide measurement on the same device where the template is stored. If our personal devices could participate in external-facing authentication too, where biometric measurement is captured by a nearby external sensor, then we could also enjoy a frictionless authentication experience in a variety of physical spaces like grocery stores, convention centers, ATMs, etc. The open setting of a physical space brings forth important privacy concerns though.

We design a suite of secure protocols for external-facing authentication based on the cosine similarity metric which provide privacy for both user templates stored on their devices and the biometric measurement captured by external sensors in this open setting. The protocols provide different levels of security, ranging from passive security with some leakage to active security with no leakage at all. With the help of new packing techniques and zero-knowledge proofs for Paillier encryption - and careful protocol design, our protocols achieve very practical performance numbers. For templates of length 256 with elements of size 16 bits each, our fastest protocol takes merely 0.024 seconds to compute a match, but even the slowest one takes no more than 0.12 seconds. The communication overhead of our protocols is very small too. The passive and actively secure protocols (with some leakage) need to exchange just 16.5KB and 27.8KB of data, respectively. The first message is designed to be reusable and, if sent in advance, would cut the overhead down to just 0.5KB and 0.8KB, respectively.

Event date: 7 June to 11 June 2021
Submission deadline: 8 January 2021
Notification: 22 February 2021

Proof of Work (PoW) protocols, originally proposed to circumvent DoS and email spam attacks, are now at the heart of the majority of recent cryptocurrencies. Current popular PoW protocols are based on hash puzzles. These puzzles are solved via a brute force search for a hash output with particular properties, such as a certain number of leading zeros. By considering the hash as a random function, and fixing a priori a sufficiently large search space, Grover's search algorithm gives an asymptotic quadratic advantage to quantum machines over classical machines. In this paper, as a step towards a fuller understanding of post quantum blockchains, we propose a PoW protocol for which quantum machines have a smaller asymptotic advantage. Specifically, for a lattice of rank \(n\) sampled from a particular class, our protocol provides as the PoW an instance of the Hermite Shortest Vector Problem (Hermite-SVP) in the Euclidean norm, to a small approximation factor. Asymptotically, the best known classical and quantum algorithms that directly solve SVP type problems are heuristic lattice sieves, which run in time \(2^{0.292n + o(n)}\) and \(2^{0.265n + o(n)}\) respectively. We discuss recent advances in SVP type problem solvers and give examples of where the impetus provided by a lattice based PoW would help explore often complex optimization spaces.

The random oracle model (ROM) enjoys widespread popularity, mostly because it tends to allow for tight and conceptually simple proofs where provable security in the standard model is elusive or costly. While being the adequate replacement of the ROM in the post-quantum security setting, the quantum-accessible random oracle model (QROM) has thus far failed to provide these advantages in many settings. In this work, we focus on adaptive reprogrammability, a feature of the ROM enabling tight and simple proofs in many settings. We show that the straightforward quantum-accessible generalization of adaptive reprogramming is feasible by proving a bound on the adversarial advantage in distinguishing whether a random oracle has been reprogrammed or not. We show that our bound is tight by providing a matching attack. We go on to demonstrate that our technique recovers the mentioned advantages of the ROM in three QROM applications:

1) We give a tighter proof of security of the message compression routine as used by XMSS. 2) We show that the standard ROM proof of chosen-message security for Fiat-Shamir signatures can be lifted to the QROM, straightforwardly, achieving a tighter reduction than previously known. 3) We give the first QROM proof of security against fault injection and nonce attacks for the hedged Fiat-Shamir transform.

This paper gives the first definitions and constructions for incremental pseudo-random functions (IPRFs). The syntax is nonce based. (Algorithms are deterministic but may take as input a non-repeating quantity called a nonce.) The design approach is modular. First, given a scheme secure only in the single-document setting (there is just one document on which incremental updates are being performed) we show how to generically build a scheme that is secure in the more realistic multi-document setting (there are many documents, and they are simultaneously being incrementally updated). Then we give a general way to build an IPRF from (1) an incremental hash function with weak collision resistance properties and (2) a symmetric encryption scheme. (This adapts the classic Carter-Wegman paradigm used to build message authentication schemes in the non-incremental setting.) This leads to many particular IPRFs. Our work has both practical and theoretical motivation and value: Incremental PRFs bring the benefits of incrementality to new applications (such as incremental key derivation), and the movement from randomized or stateful schemes to nonce based ones, and from UF (unforgeability) to PRF security, bring incremental symmetric cryptography up to speed with the broader field of symmetric cryptography itself.

The six infinite families of power APN functions are among the oldest known instances of APN functions, and it has been conjectured in 2000 that they exhaust all possible power APN functions. Another long-standing open problem is that of the Walsh spectrum of the Dobbertin power family, which is the only one among the six families for which it remains unknown. In this paper, we derive alternative representations for functions from the infinite APN monomial families, with the hope that this will pave the way for further progress in this area. More concretely, we show how the Niho, Welch, and Dobbertin functions can be represented as the composition $x^i \circ x^{1/j}$ of two power functions, and prove that our representations are the simplest possible in the sense that no two power functions of lesser algebraic degree can produce the same composition. We also investigate compositions of the form $x^i \circ L \circ x^{1/j}$ for a linear polynomial $L$, and computationally determine all APN functions of this form for $n \le 9$ and for $L$ with coefficients in $\mathbb{F}_2$ in order to confirm that our theoretical constructions exhaust all possible cases. We present some observations and computational data on power functions with exponent of the form $\sum_{i = 1}^{k-1} 2^{2ni} - 1$, which can be seen as generalizations of both the inverse and the Dobbertin APN families. Finally, we present our computational data on the Walsh coefficients of the Dobbertin function over $\F$ for $n \le 35$, and conjecture the exact form of its Walsh spectrum.

The existence of a provable one-way function is a long-standing open problem. This short note presents an example towards the existence a provable one-way function, example in which both directions are polynomial. Namely, we prove that given a sorted array it takes O(n) operations to randomly permute the array values uniformly over the permutation space, while (comparison based) sorting of the permuted array (of big enough values) requires in the worst case (and in the average case) Omega(n log n) compare operations . We also present a candidate cryptosystem based on permutations of random polynomial values.

Recent research in Dynamic Searchable Symmetric Encryption (DSSE) focuses on efficient search over encrypted data while allowing updates. Unfortunately, as demonstrated by many attacks, updates can be a source of information leakage that can compromise DSSE privacy. To mitigate these attacks, forward and backward privacy of DSSE schemes have been introduced. A concerted effort of the research community has resulted in the publication of many DSSE schemes. To the best of our knowledge, however, there is no DSSE scheme supporting conjunctive queries, which achieves both forward and backward privacy.

We give two DSSE schemes with forward and backward privacy, which support conjunctive queries, and they are suitable for different applications. In particular, we first introduce a new data structure termed the extended bitmap index. Then we describe our forward and backward private DSSE schemes, which support conjunctive queries. Our security analysis proves the claimed privacy characteristics, and experiments show that our schemes are practical. Compared to the state-of-the-art DSSE VBTree supporting conjunctive queries (but not backward privacy), our schemes offer search time that is a few orders of magnitude faster. Besides, our schemes claim better security (called Type-C backward privacy).

In this paper we introduce new algorithms that, based only on the independent round keys assumption, allow to practically compute the exact expected differential probability of (truncated) differentials and the expected linear potential of (multidimensional) linear hulls. That is, we can compute the exact sum of the probability or the potential of all characteristics that follow a given activity pattern. We apply our algorithms to various recent SPN ciphers and discuss the results.

We introduce a novel variant of Lagrange interpolation called modular Lagrange interpolation that allows us to obtain and prove error bounds for explicit low-degree polynomial approximations of a function on a union of equally-spaced small intervals even if the function overall is not continuous. We apply our technique to the mod function and obtain explicit low-degree polynomial approximations with small error. In particular, for every $k$ and $N >>k$, we construct low-degree polynomials that approximate $f(x)\:=\: x$ mod $N$, for $|f(x)| \leq 1$ and $|x| \leq kN$, to within O($1/N$) additive approximation. For $k= O(\log N)$, the result is generalized to give O($d$)-degree polynomial approximations to within O($N^{-d}$) error for any $d \geq 1$. Literature in approximation theory allows for arbitrary precision polynomial approximation of only smooth functions, whereas the mod function is only piecewise linear. These polynomials can be used in bootstrapping for approximate homomorphic encryption, which requires computing the mod function near multiples of the modulus. Our work bypasses the fundamental error of approximation in prior works caused by first approximating the mod function by a scaled sine function. For typical settings of $N$, these polynomials have lower error than the fundamental error introduced by using the scaled sine function at degrees computable in multiplicative depth seven or eight.

We present two new related families of lattice trapdoors based on the inhomogeneous NTRU problem (iNTRU) defined in Genise et. al (ASIACRYPT 2019). Our constructions are ``gadget-based'' and offer compact secret keys and preimages and compatibility with existing, efficient preimage sampling algorithms. Our trapdoors can be used as a fundamental building block in lattice-based schemes relying lattice trapdoors. In addition, we implemented our trapdoors using the PALISADE library.

There are lots of applications of inner-product functional encryption (IPFE). In this paper, we consider two important extensions of it. One is to enhance IPFE with access control such that only users with a pre-defined identity are allowed to compute the inner product, referred as identity-based inner-product functional encryption (IBIPFE). We formalize the definition of IBIPFE, and propose the first adaptive-secure IBIPFE scheme from Decisional Bilinear Diffie-Hellman (DBDH) assumption. In an IBIPFE scheme, the ciphertext is related to a vector $\vec{x}$ and a new parameter, identity ID. Each secret key is also related to a vector $\vec{y}$ and an identity ID'. The decryption algorithm will output the inner-product value $⟨x, y⟩$ only if ID $=$ ID. The other extension is to make IBIPFE leakage resilient. We consider the bounded-retrieval model (BRM) in which an adversary can learn at most $l$ bits information from each secret key. Here, $l$ is the leakage bound determined by some external parameters, and it can be set arbitrarily large. After giving the security definition of leakage-resilient IBIPFE, we extend our IBIPFE scheme into a leakage-resilient IBIPFE scheme in the BRM by hash proof system (HPS).

Byzantine Broadcast is an important topic in distributed systems and improving its round complexity has long been a focused challenge. Under honest majority, the state of the art for Byzantine Broadcast is 10 rounds for a static adversary and 16 rounds for an adaptive adversary. In this paper, we present a Byzantine Broadcast protocol with expected 8 rounds under a static adversary and expected 10 rounds under an adaptive adversary. We also generalize our idea to the dishonest majority setting and achieve an improvement over existing protocols.

Most efficient zero-knowledge arguments lack a concrete security analysis, making parameter choices and efficiency comparisons challenging. This is even more true for non-interactive versions of these systems obtained via the Fiat-Shamir transform, for which the security guarantees generically derived from the interactive protocol are often too weak, even when assuming a random oracle.

This paper initiates the study of {\em state-restoration soundness} in the algebraic group model (AGM) of Fuchsbauer, Kiltz, and Loss (CRYPTO '18). This is a stronger notion of soundness for an interactive proof or argument which allows the prover to rewind the verifier, and which is tightly connected with the concrete soundness of the non-interactive argument obtained via the Fiat-Shamir transform.

We propose a general methodology to prove tight bounds on state-restoration soundness, and apply it to variants of Bulletproofs (Bootle et al, S\&P '18) and Sonic (Maller et al., CCS '19). To the best of our knowledge, our analysis of Bulletproofs gives the {\em first} non-trivial concrete security analysis for a non-constant round argument combined with the Fiat-Shamir transform.