International Association
for Cryptologic Research

In this work we study the leakage resilience of authenticated encryption schemes. We show that, if one settles for non-adaptive leakage, leakage-resilient authenticated encryption schemes can be built solely from leakage-resilient pseudorandom functions. Degabriele et al. (ASIACRYPT 2019) introduce the FGHF' construction which allows to build leakage-resilient authenticated encryption schemes from functions which, under leakage, retain both pseudorandomness and unpredictability. We revisit their construction and show the following. First, pseudorandomness and unpredictability do not imply one another in the leakage setting. Unfortunately, this entails that any instantiation of the FGHF' construction indeed seems to require a function that is proven both pseudorandom and unpredictable under leakage. Second, however, we show that the unpredictability requirement is an artefact that stems from the underlying composition theorem of the N2 construction given by Barwell et al. (ASIACRYPT 2017). By recasting this composition theorem, we show that the unpredictability requirement is unnecessary for the FGHF' construction. Thus, leakage-resilient AEAD schemes can be obtained by instantiating the FGHF' construction with functions that are solely pseudorandom under leakage.

Authenticated Encryption has emerged as a high-performance and resource-efficient solution to achieve message authentication in addition to encryption. This has motivated extensive study of algorithms for Authenticated Encryption with Associated Data (AEAD). While there have been significant efforts to benchmark these algorithms on hardware and software platforms, very little work has focused on the integration of these ciphers onto a System-on-Chip (SoC). This work looks at design alternatives for the SoC integration of few of the finalists of the Competition for Authenticated Encryption: Security, Applicability, and Robustness (CAESAR). We highlight the penalty on area and performance that is incurred during SoC integration, and analyze the impact of design choices on the same. Our observations indicate that integration onto a system significantly affects the lightweight and high-performance properties of these ciphers, and achieving a trade-off requires careful design decisions.

The last few years have witnessed increasing interest in the deployment of zero-knowledge proof systems, in particular ones with succinct proofs and efficient verification (zk-SNARKs). One of the main challenges facing the wide deployment of zk-SNARKs is the requirement of a trusted key generation phase per different computation to achieve practical proving performance. Existing zero-knowledge proof systems that do not require trusted setup or have a single trusted preprocessing phase suffer from increased proof size and/or additional verification overhead. On the other other hand, although universal circuit generators for zk-SNARKs (that can eliminate the need for per-computation preprocessing) have been introduced in the literature, the performance of the prover remains far from practical for real-world applications.

In this paper, we first present a new zk-SNARK system that is well-suited for randomized algorithms---in particular it does not encode randomness generation within the arithmetic circuit allowing for more practical prover times. Then, we design a universal circuit that takes as input any arithmetic circuit of a bounded number of operations as well as a possible value assignment, and performs randomized checks to verify consistency. Our universal circuit is linear in the number of operations instead of quasi-linear like other universal circuits. By applying our new zk-SNARK system to our universal circuit, we build MIRAGE, a universal zk-SNARK with very succinct proofs---the proof contains just one additional element compared to the per-circuit preprocessing state-of-the-art zk-SNARK by Groth (Eurocrypt 2016). Finally, we implement MIRAGE and experimentally evaluate its performance for different circuits and in the context of privacy-preserving smart contracts.

Nakamoto consensus, arguably the most exciting development in distributed computing in the last few years, is in a sense a recasting of the traditional state-machine-replication problem in an unauthenticated setting, where furthermore parties come and go without warning. The protocol relies on a cryptographic primitive known as proof of work (PoW) which is used to throttle message passing with the PoW difficulty level being adjusted appropriately throughout the course of the protocol execution.

While the original formulation was only accompanied by rudimentary analysis, significant and steady progress has been made in abstracting out the protocol’s properties and providing a formal analysis under various restrictions, starting with the work by Garay, Kiayias and Leonardos [Eurocrypt ’15], for a simplified version of the protocol which excluded PoW difficulty adjustment and assumed a fixed number of parties as well as synchronous communication rounds. These assumptions have since been somewhat relaxed, first by Pass, Seeman and Shelat [Eurocrypt ’17] who also focused on the simplified version of the protocol but on the bounded-delay model of communication, and by Garay, Kiayias and Leonardos [Crypto ’17] who looked into the full protocol including the PoW difficulty adjustment mechanism with a variable number of parties but assuming synchronous communication and a predetermined schedule of participation. Despite the above progress, the full analysis of the protocol in the more realistic setting of bounded delays and dynamic participation has remained elusive.

This paper’s main result is the proof that Nakamoto’s protocol achieves, under suitable conditions, consistency and liveness in bounded-delay networks with adaptive (as opposed to predetermined) dynamic participation assuming, as before, that the majority of the computational power favors the honest parties. While our techniques draw from previous analyses, our objective is significantly more challenging, demanding the introduction of new techniques and insights in order to realize it.

Quantum computers promise to solve hard mathematical problems such as integer factorization and discrete logarithms in polynomial time, making standardized public-key cryptography (such as digital signature and key agreement) insecure. Lattice-Based Cryptography (LBC) is a promising post-quantum public-key cryptographic protocol that could replace standardized public-key cryptography, thanks to the inherent post-quantum resistant properties, efficiency, and versatility. A key mathematical tool in LBC is the Number Theoretic Transform (NTT), a common method to compute polynomial multiplication that is the most compute-intensive routine, and which requires acceleration for practical deployment of LBC protocols. In this paper, we propose, a high-throughput Processing In-Memory (PIM) accelerator for NTT-based polynomial multiplier with the support of polynomials with degrees up to 32k. Compared to the fastest FPGA implementation of an NTT-based multiplier, achieves on average 31x throughput improvement with the same energy and only 28% performance reduction, thereby showing promise for practical deployment of LBC.

With the dawn of quantum computers, higher security than $128$ bits has become desirable for primitives and modes. During the past decade, highly secure hash functions, MACs, and encryption schemes have been built primarily on top of keyless permutations, which simplified their analyses and implementation due to the absence of a key schedule. However, the security of these modes is most often limited to the birthday bound of the state size, and their analysis may require a different security model than the easier-to-handle secret-permutation setting. Yet, larger state and key sizes are desirable not only for permutations but also for other primitives such as block ciphers. Using the additional public input of tweakable block ciphers for domain separation allows for exceptionally high security or performance as recently proposed modes have shown. Therefore, it appears natural to ask for such designs.

While security is fundamental for cryptographic primitives, performance is of similar relevance. Since 2009, processor-integrated instructions have allowed high throughput for the AES round function, which already motivated various constructions based on it. Moreover, the four-fold vectorization of the AES instruction sets in Intel's Ice Lake architecture is yet another leap in terms of performance and gives rise to exploit the AES round function for even more efficient designs.

This work tries to combine all aspects above into a primitive and to build upon years of existing analysis on its components. We propose Pholkos, a family of (1) highly efficient, (2) highly secure, and (3) tweakable block ciphers. Pholkos is no novel round-function design, but utilizes the AES round function, following design ideas of Haraka and AESQ to profit from earlier analysis results. It extends them to build a family of primitives with state and key sizes of $256$ and $512$ bits for flexible applications, providing high security at high performance. Moreover, we propose its usage with a $128$-bit tweak to instantiate high-security encryption and authentication schemes such as SCT, ThetaCB3, or ZAE. We study its resistance against the common attack vectors, including differential, linear, and integral distinguishers using a MILP-based approach and show an isomorphism from the AES to Pholkos-$512$ for bounding impossible-differential, or exchange distinguishers from the AES. Our proposals encrypt at around $1$--$2$ cycles per byte on Skylake processors, while supporting a much more general application range and considerably higher security guarantees than comparable primitives and modes such as PAEQ/AESQ, AEGIS, Tiaoxin346, or Simpira.

Recently, Kamara and Moataz described the first encrypted relational database solution with support for a non-trivial fraction of SQL that does not make use of property-preserving encryption (Asiacrypt, 2018). More precisely, their construction, called SPX, handles the set of conjunctive SQL queries. While SPX was shown to be optimal for the subset of uncorrelated conjunctive SQL queries, it did not handle correlated queries optimally. Furthermore, it only handles queries in heuristic normal form. In this work, we address these limitations by proposing an extension of SPX that handles all conjunctive SQL queries optimally no matter what form they are in.

Motivated by the impact of fast algebraic attacks on stream ciphers, and recent constructions using a threshold function as part of the filtering function, we study the fast algebraic immunity of threshold functions. As a first result, we determine exactly the fast algebraic immunity of all majority functions in more than $8$ variables. Then, For all $n\geq 8$ and all threshold value between $1$ and $n$ we exhibit the fast algebraic immunity for most of the thresholds, and we determine a small range for the value related to the few remaining cases. Finally, provided $m\geq 2$, we determine exactly the fast algebraic immunity of all threshold functions in $3\cdot 2^m$ or $3\cdot 2^m +1$ variables.

Privacy and machine learning are difficult to coexist due to their nature: parivacy should be kept from others while machine learning requires large amount of data. Among several possible solutions to this problem, Fully Homomorphic Encryption has been a center of intensive researches in this field. FHE enables linear operations of ciphertext. To take advantage of this property, many protocols to achieve statistical operaions have been proposed. On the other hand, many of them are impractical. Some of the approaches introduce cryptosystems that are not familiar. Moreover, most of their protocols are approximation which might sensitively depend on our choice of parameters. In this paper, we propose fast, simple, and exact privacy-preserving linear equation solver using FHE. Our two-party protocol is secure against at least semi-honest model, and we can exactly calculate the model even without the bootstrapping.

OR-proofs enable a prover to show that it knows the witness for one of many statements, or that one out of many statements is true. OR-proofs are a remarkably versatile tool, used to strengthen security properties, design group and ring signature schemes, and achieve tight security. The common technique to build OR-proofs is based on an approach introduced by Cramer, Damgård, and Schoenmakers (CRYPTO’94), where the prover splits the verifier’s challenge into random shares and computes proofs for each statement in parallel. In this work we study a different, less investigated OR-proof technique, put forward by Abe, Ohkubo, and Suzuki (ASIACRYPT’02). The difference is that the prover now computes the individual proofs sequentially. We show that such sequential OR-proofs yield signature schemes which can be proved secure in the non-programmable random oracle model. We complement this positive result with a black-box impossibility proof, showing that the same is unlikely to be the case for signatures derived from traditional OR-proofs. We finally argue that sequential-OR signature schemes can be proved secure in the quantum random oracle model, albeit with very loose bounds and by programming the random oracle.

Inner product encryption is a powerful cryptographic primitive, where a private key and a ciphertext are both associated with a predicate vector and an attribute vector, respectively. A successful decryption requires the inner product of the predicate vector and the attribute vector to be zero. Most of the existing inner product encryption schemes suffer either long private key or heavy decryption cost. In this manuscript, an efficient inner product encryption is proposed. The length for a private key is only an element in $\mathbb{G}$ and an element in $\mathbb{Z}_p$. Besides, only a pairing is needed for decryption. Moreover, both formal security proof and implementation result are demonstrated in this manuscript. To the best of our knowledge, our scheme is the most efficient one in terms of the private key length and the number of pairings for decryption.

Decades of research in both cryptography and distributed systems has extensively studied the problem of state machine replication, also known as Byzantine consensus. A consensus protocol must satisfy two properties: consistency and liveness. These properties ensure that honest participating nodes agree on the same log and dictate when fresh transactions get added. They fail, however, to ensure against adversarial manipulation of the actual ordering of transactions in the log. Indeed, in leader-based protocols (almost all protocols used today), malicious leaders can directly choose the final transaction ordering.

To rectify this problem, we propose a third consensus property: transaction order-fairness. We initiate the first formal investigation of order-fairness and explain its fundamental importance. We provide several natural definitions for order-fairness and analyze the assumptions necessary to realize them.

We also propose a new class of consensus protocols called Aequitas. Aequitas protocols are the first to achieve order-fairness in addition to consistency and liveness. They can be realized in a black-box way using existing broadcast and agreement primitives (or indeed using any consensus protocol), and work in both synchronous and asynchronous network models.

Since the introduction of the ring-learning with errors problem, the number theoretic transform (NTT) based polynomial multiplication algorithm has been studied extensively. Due to its faster quasilinear time complexity, it has been the preferred choice of cryptographers to realize ring-learning with errors cryptographic schemes. Compared to NTT, Toom-Cook or Karatsuba based polynomial multiplication algorithms, though being known for a long time, still have a fledgling presence in the context of post-quantum cryptography. In this work, we observe that the pre- and post-processing steps in Toom-Cook based multiplications can be expressed as linear transformations. Based on this observation we propose two novel techniques that can increase the efficiency of Toom-Cook based polynomial multiplications. Evaluation is reduced by a factor of 2, and we call this method precomputation, and interpolation is reduced from quadratic to linear, and we call this method lazy interpolation. As a practical application, we applied our algorithms to the Saber post-quantum key-encapsulation mechanism. We discuss in detail the various implementation aspects of applying our algorithms to Saber. We show that our algorithm can improve the efficiency of the computationally costly matrix-vector multiplication by12−37%compared to previous methods on their respective platforms. Secondly, we propose different methods to reduce the memory footprint of Saber for Cortex-M4microcontrollers. Our implementation shows between2.6 and 5.7KB reduction in memory usage with respect to the smallest implementation in the literature.

Post-quantum cryptography introduces cryptographic algorithms that are secure against adversaries who can employ a quantum computer and it is the inevitable next-step in the evolution of the cryptographic algorithms. In order to create a conventional foundation the National Institute of Standards and Technology (NIST) started a competition for Post-Quantum Cryptography in 2017.

This paper introduces the first differential side channel analysis of a candidate in the competition; the Picnic Signature Scheme. We present a successful side channel analysis of the underlying Multiparty LowMc implementation and show how leakages can be exploited to recover the entire secret key using two different parts of the algorithm. LowMc key recovery then allows to forge signatures for the calling Picnic post-quantum signature scheme. We target the NIST reference implementation executed on a FRDM-K66F development board. Key recovery succeeds with less than 1000 traces, which can be obtained from less than 30 observed Picnic signatures.

In this work we study the (superposition-based, or QS2) quantum security of public key encryption schemes. Boneh and Zhandry (CRYPTO 2013) initiated this research area for symmetric and public key encryption, albeit restricted to a classical indistinguishability phase. Gagliardoni et al. (CRYPTO 2016) advanced the study of quantum security, for symmetric key encryption schemes, by giving the first definition where the indistinguishability phase is quantum. For public key encryption schemes, on the other hand, no notion of quantum security with a quantum indistinguishability phase exists. In this work we close this gap by defining strong QS2 security notions for the public key case. Our core idea follows the approach of Gagliardoni et al. by using so-called type-2 operators for encrypting the challenge message. Extending this idea to the public key case brings non-trivial obstacles: On the one hand, public key encryption schemes typically cannot recover the randomness when decrypting ciphertexts. On the other hand, many real-world schemes (including most quantum-resistant NIST candidates) suffer from a small probability of decryption failures. These two problems make it difficult to enforce the reversibility of the encryption operation needed by type-2 operators. Nevertheless, we identify a class of encryption schemes, which we call recoverable, that allow to avoid decryption failures given knowledge of the original encryption randomness, and we show that many real-world quantum-resistant schemes, including many NIST candidates, are of this type. Then we show how to define and construct type-2 encryption operators for schemes that are fully correct or recoverable. Moreover, we show that for recoverable schemes, the type-2 operator can be efficiently implemented even without knowledge of the secret key. This means that, for the public key case, type-2 operators are actually very natural, and already included in the traditional "post-quantum" (QS1) definition of security. Equipped with these results, we (1) give the first quantum security notion (qINDqCPA) for public key encryption with a quantum indistinguishability phase, (2) prove that the canonical LWE-based encryption scheme achieves our security notion, (3) show that our notion is strictly stronger than existing security notions, and (4) study the general classification of quantum-resistant public key encryption schemes.

Non-interactive zero-knowledge proofs (NIZKs) are important primitives in cryptography. A major challenge since the early works on NIZKs has been to construct NIZKs with a statistical zero-knowledge guarantee against unbounded verifiers. In the common reference string (CRS) model, such "statistical NIZK arguments" are currently known from k-Lin in a pairing-group and from LWE. In the (reusable) designated-verifier model (DV-NIZK), where a trusted setup algorithm generates a reusable verification key for checking proofs, we also have a construction from DCR. If we relax our requirements to computational zero-knowledge, we additionally have NIZKs from factoring and CDH in a pairing group in the CRS model, and from nearly all assumptions that imply public-key encryption (e.g., CDH, LPN, LWE) in the designated-verifier model. Thus, there still remains a gap in our understanding of statistical NIZKs in both the CRS and the designated-verifier models.

In this work, we develop new techniques for constructing statistical NIZK arguments. First, we construct statistical DV-NIZK arguments from the k-Lin assumption in pairing-free groups, the QR assumption, and the DCR assumption. These are the first constructions in pairing-free groups and from QR that satisfy statistical zero-knowledge. All of our constructions are secure even if the verification key is chosen maliciously (i.e., they are "malicious-designated-verifier" NIZKs), and moreover, they satisfy a "dual-mode" property where the CRS can be sampled from two computationally indistinguishable distributions: one distribution yields statistical DV-NIZK arguments while the other yields computational DV-NIZK proofs. We then show how to adapt our k-Lin construction in a pairing group to obtain new publicly-verifiable statistical NIZK arguments from pairings with a qualitatively weaker assumption than existing constructions of pairing-based statistical NIZKs.

Our constructions follow the classic paradigm of Feige, Lapidot, and Shamir (FLS). While the FLS framework has traditionally been used to construct computational (DV)-NIZK proofs, we newly show that the same framework can be leveraged to construct dual-mode (DV)-NIZKs.

Homomorphic encryption primitives have the potential to be the main enabler of privacy preserving computation delegation to cloud environments. One of the avenues which has been explored to reduce their significant computational overhead with respect to cleartext computation is the one of the so-called noise-free homomorphic encryption schemes. In this work, we present an attack against fully homomorphic encryption primitives where a distinguisher for a single plaintext value exists. We employ two noise-free homomorphic encryption schemes where such a property holds as our case studies, providing detailed attack procedure against them. We validate the effectiveness and performance of our attacks on prototype implementations of the said schemes, and suggest two countermeasures to our attack tailored to the schemes at hand.

Event date: 22 June to 25 June 2020
Submission deadline: 25 March 2020
Notification: 25 April 2020

Simula UiB (http://simula-uib.com) in Bergen, Norway, has one three-year Ph.D positions available in the field of cryptography. Ph.D students at Simula UiB enjoy a startup-like international working environment with good salaries and work-life balance, with very few obligations on top of doing research. Project/Job description: The Ph.D candidate will be supervised by Helger Lipmaa (https://sites.google.com/view/helgerlipmaa) on topics related to zk-SNARKs and zero-knowledge and their various applications (cryptocurrencies, verifiable computation, e-voting, to name a few). Zk-SNARKs have been become excessively popular during the last few years due to the application in privacy-preserving cryptocurrencies, leading the MIT technology review to name them one of the “10 Breakthrough Technologies of 2018” (https://www.technologyreview.com/lists/technologies/2018/). Candidate Profile: a completed MSc degree in cryptography, or related areas (in particular, theoretical computer science, including algorithms and/or complexity theory, and mathematics). We will also consider applicants who are in the final phase of their Master studies. We expect an excellent academic track record, including top grades. The student is expected to be at home both in theory and in practice. Simula UiB is an equal opportunity employer, and women are particularly encouraged to apply. Simula UiB Offers: Modern office facilities located in downtown Bergen ("the gateway to the fjords"). A competitive salary starting from NOK 479.600 (approx 48000 euros). Special emphasis on wellness and work-life balance. Numerous additional benefits. About Simula UiB: Simula UiB AS is a research centre owned by Simula Research Laboratory AS and the University of Bergen (UiB). The goal of Simula UiB is to increase the security expertise in Norway through research and education in cryptography and information theory. The student will officially defend at UiB.

Closing date for applications:

Contact: Helger Lipmaa

More information: https://www.simula.no/about/job/call-phd-student-cryptography

Dear IACR member,

The IACR board is currently monitoring the outbreak of the novel coronavirus (COVID-19) and assessing its potential impact on forthcoming IACR conferences. Although the current conference schedule has not changed, we are in close contact with the conference organizers and constantly reevaluating the situation. In case a conference needs to be postponed, relocated, cancelled, or switched to a web-only format, we will be informing the membership and attendees as soon as possible via the IACR news system and other appropriate communication channels. Publication schedules will not be altered significantly even if conferences are affected.

In the meantime, we are in the process of implementing several measures to ease the burden on attendees who cannot physically attend the conference due to travel restrictions or concerns related to the novel coronavirus outbreak. These include:

• having a more flexible cancellation and refund policy; and
• allowing alternative methods of presentation, such as pre-recorded videos.

In order to guarantee the safety of conference attendees, we are also asking our conference organizers to follow the safety guidelines of the World Health Organization (WHO) and national health protection agencies such as the U.S. Centers for Disease Control and Prevention (CDC) and to ensure attendees are aware of these guidelines. In addition, we also plan to have a point of contact for each conference to address concerns by attendees.

Links:
WHO: https://www.who.int/emergencies/diseases/novel-coronavirus-2019
CDC: https://www.cdc.gov/coronavirus/2019-ncov/index.html
IACR News: https://www.iacr.org/news/