International Association
for Cryptologic Research

We prove that the discrete logarithm problem can be solved in quasi-polynomial expected time in the multiplicative group of finite fields of fixed characteristic. More generally, we prove that it can be solved in the field of cardinality $p^n$ in expected time $(pn)^{2\log_2(n) + O(1)}$.

We report on a simple technique that supports some recent developments on AES by Grassi and Rechberger and Bao, Guo and List. We construct a weight transition probability matrix related to AES that characterises fixed configurations of active bytes in differences of ciphertexts when plaintext differences are fixed to some (possibly other) configuration of active bytes. The construction is very simple and one might even consider it to be a little naive. However, the derived probabilities match recent results on 5- and 6-rounds AES derived through more sophisticated means, indicating that it might be worth a further investigation.

TLS (Transport Layer Security) is a widely deployed protocol that plays a vital role in securing Internet trafic. Given the numerous known attacks for TLS 1.2, it was imperative to change and even redesign the protocol in order to address them. In August 2018, a new version of the protocol, TLS 1.3, was standardized by the IETF (Internet Engineering Task Force). TLS 1.3 not only benefits from stronger security guarantees, but aims to protect the identities of the server and client by encrypting messages as soon as possible during the authentication. In this paper, we model the privacy guarantees of TLS 1.3 when parties execute a full handshake or use a session resumption, covering all the handshake modes of TLS. We build our privacy models on top of the one defined by Hermans et al. for RFIDs (Radio Frequency Identification Devices) that mostly targets authentication protocols. The enhanced models share similarities to the Bellare-Rogaway AKE (Authenticated Key Exchange) security model and consider adversaries that can compromise both types of participants in the protocol. In particular, modeling session resumption is non-trivial, given that session resumption tickets are essentially a state transmitted from one session to another and such link reveals information on the parties. On the positive side, we prove that TLS 1.3 protects the privacy of its users at least against passive adversaries, contrary to TLS 1.2, and against more powerful ones.

Smart contracts allow for exchange of coins according to program rules. While it is well known that so called bribery contracts can influence the incentive mechanism of a Nakamotostyle consensus, we present a more fine-grained bribery attack incentivizing a temporary censorship against a specific account. To this end, we introduce three different bribery contracts on the blockchain where each uniquely manipulates the rewards that a rational miner would receive. Additionally, we formalize the established bribery mechanisms as a Markov game and show for each game the existence of equilibria leading to successful censorships. Finally, we compare the bribery mechanisms with respect to the scalability of the attack costs and the strategic dominance. Our work is motivated by off-chain protocols including payment and state channels which require to publish transactions within a certain amount of time. In such off-chain protocols a temporary censorship attack can result into significant financial damage.

We provide new zero-knowledge argument of knowledge systems that work directly for a wide class of language, namely, ones involving the satisfiability of matrix-vector relations and integer relations commonly found in constructions of lattice-based cryptography. Prior to this work, practical arguments for lattice-based relations either have a constant soundness error ( 2/3 ), or consider a weaker form of soundness, namely, extraction only guarantees that the prover is in possession of a witness that “approximates” the actual witness. Our systems do not suffer from these limitations.

The core of our new argument systems is an efficient zero-knowledge argument of knowledge of a solution to a system of linear equations, where variables of this solution satisfy a set of quadratic constraints. This argument enjoys standard soundness, a small soundness error ( 1/poly ), and a complexity linear in the size of the solution. Using our core argument system, we construct highly efficient argument systems for a variety of statements relevant to lattices, including linear equations with short solutions and matrix-vector relations with hidden matrices.

Based on our argument systems, we present several new constructions of common privacy-preserving primitives in the standard lattice setting, including a group signature, a ring signature, an electronic cash system, and a range proof protocol. Our new constructions are one to three orders of magnitude more efficient than the state of the art (in standard lattice). This illustrates the efficiency and expressiveness of our argument system.

We construct public-key function-private predicate encryption for the ``small superset functionality,'' recently introduced by Beullens and Wee (PKC 2019). This functionality captures several important classes of predicates:

- Point functions. For point function predicates, our construction is equivalent to public-key function-private anonymous identity-based encryption.

- Conjunctions. If the predicate computes a conjunction, our construction is a public-key function-private hidden vector encryption scheme. This addresses an open problem posed by Boneh, Raghunathan, and Segev (ASIACRYPT 2013).

- $d$-CNFs and read-once conjunctions of $d$-disjunctions for constant-size $d$.

Our construction extends the group-based obfuscation schemes of Bishop et al. (CRYPTO 2018), Beullens and Wee (PKC 2019), and Bartusek et al. (EUROCRYPT 2019) to the setting of public-key function-private predicate encryption. We achieve an average-case notion of function privacy, which guarantees that a decryption key $sk_f$ reveals nothing about $f$ as long as $f$ is drawn from a distribution with sufficient entropy. We formalize this security notion as a generalization of the (enhanced) real-or-random function privacy definition of Boneh, Raghunathan, and Segev (CRYPTO 2013). Our construction relies on bilinear groups, and we prove security in the generic bilinear group model.

In this paper we put forth new one-message proof systems for several practical applications, like proving that an El Gamal ciphertext decrypts to a given value and correctness of a shuffle. Our proof systems are not based on any setup/trust assumption like the RO or the common reference string model and are perfectly sound, that is they are written proofs in the sense of mathematics.

Our proof systems satisfy a generalization of zero-knowledge (ZK) that we call harmless zero-knowledge (HZK). The simulator of an $O$-HZK proof for a relation over a language $L$ is given the additional capability of invoking an oracle $O$ relative to which $L$ is hard to decide. That is, the proof does not leak any knowledge that an adversary might not compute by itself interacting with an oracle $O$ that does not help to decide the language.

Unlike ZK, non-interactivity or perfect soundness do not contradict HZK and HZK can replace ZK in any application in which, basically, the computational assumptions used in the application hold even against adversaries with access to $O$. An $O$-HZK proof is WH, assuming some computational problem to be hard for adversaries with access to $O$, and strong-WI when quantifying over distributions that are indistinguishable by adversaries with access to $O$.

We provide a specific oracle $O$ that is enough powerful to make our main proof systems $O$-HZK but not trivial: indeed, we show concrete and practical cryptographic protocols that can be proven secure employing an $O$-HZK proof in the reduction and that are instead not achievable using traditional ZK (unless assuming a CRS/RO).

Efficient one-message proof systems with perfect soundness were only known for relations over bilinear groups and were proven only witness indistinguishable.

As byproduct, we also obtain a perfectly sound non-interactive ZAP and HZK proof for NP from a number-theoretic assumption over multiplicative groups of hidden order.

Classification of personal text messages has many useful applications in surveillance, e-commerce, and mental health care, to name a few. Giving applications access to personal texts can easily lead to (un)intentional privacy violations. We propose the first privacy-preserving solution for text classification that is provably secure. Our method, which is based on Secure Multiparty Computation (SMC), encompasses both feature extraction from texts, and subsequent classification with logistic regression and tree ensembles. We prove that when using our secure text classification method, the application does not learn anything about the text, and the author of the text does not learn anything about the text classification model used by the application beyond what is given by the classification result itself. We perform end-to-end experiments with an application for detecting hate speech against women and immigrants, demonstrating excellent runtime results without loss of accuracy.

In this paper, we introduce a new construction of lattice-based reusable fuzzy signature for remote user authentication that is secure against quantum computers. We define formal security models for the proposed construction, and we prove that it can achieve user authenticity, biometrics reusability and user privacy. In particular, the proposed new construction ensures that: 1) biometrics reusability is achieved such that fuzzy signatures remain secure even when the same biometrics is reused multiple times; 2) a third party having access to the communication channel between an authorized user and the authentication server cannot identify the authorized user.

Embedded microprocessors are an important component of reconfigurable architectures. Fine-grain (e.g., cycle-accurate) power analysis of such processors has been used to improve power and energy efficiency, and detect implementation vulnerabilities, in embedded applications. However, such analysis is difficult to conduct; it requires either specialized and often expensive equipment, or construction of test architectures using disparate acquisition and analysis tools. In this research, we expand the Flexible Open-source workBench fOr Side-channel analysis (FOBOS) to facilitate exact time-domain correlation of clock cycle and device state to power measurements, and to perform power analysis on a soft core processor. We first validate the fine-grain power analysis capabilities of FOBOS through cycle-accurate analysis of power consumption of AES encryption running on a soft core processor in the Spartan-6 FPGA. We then analyze the results in the context of Simple Power Analysis side-channel attacks, and confirm power correlation of certain instructions with Hamming Weight or Hamming Distance of secret key bytes. Finally, we show that an assumption of a pure Hamming Distance power model for load-to-register instructions is not sufficient for this embedded processor architecture, and that power models using both Hamming Distance and Hamming Weight should be considered for Differential Power Analysis.

Event date: 1 December 2020
Submission deadline: 2 December 2019

Event date: 31 August 2020
Submission deadline: 31 October 2019
Notification: 30 April 2020

Videos from lectures at Eurocrypt 2019 are now on the web. This includes the IACR distinguished lecture by Cynthia Dwork, titled "Differential Privacy and the People's Data".

CRAFT is a lightweight involuntary block cipher, designed to provide efficient protection against differential fault attack. It is a tweakable cipher which encrypts a 64-bit plaintext using a 128-bit key and 64-bit public tweak. In this paper, compared to the designers' analysis, we provide a more detailed analysis of CRAFT against differential, linear hull, and zero correlation cryptanalysis. Our distinguishers for reduced round CRAFT cover more number of rounds compared to the designers' analysis. In our analysis, we observed a strange differential behavior of CRAFT, more precisely, for any number of rounds, the differential has an extremely higher probability compared to any differential characteristic. As an example, while the best characteristic for 11 rounds of the cipher has the probability of $2^{-80}$, we presented a differential with the probability of $2^{-60}$, contain $2^{20}$ characteristic, all with the same optimum probability of $2^{-80}$. Next, we are using a partitioning technique, based on an optimal expendable truncated characteristic, to provide a better estimation of the differential effect on CRAFT. Thanks to technique, we were able to find differential distinguishers for 9, 10, 11, 12 and 13 rounds of the cipher in single tweak model with the probabilities of $2^{-40.204463}$, $ 2^{-45.124812} $, $ 2^{-49.799815}$, $ 2^{-54.726466}$ and $ 2^{-59.399491}$ respectively. These probabilities should be compared with the best distinguishers provided by the designers in the same model for 9 and 10 rounds of the cipher with the probabilities of $ 2^{-54.67}$ and $ 2^{-62.61}$ respectively.

In addition, we considered the security of CRAFT against the new concept of related tweak zero correlation (ZC) linear cryptanalysis and present a new distinguisher which covers 14 rounds of the cipher, while the best previous ZC distinguisher covered 13 rounds.

We also provide many related key characteristics for a full round cipher that the probability of any full round distinguisher will not be less than $2^{-32}$. It is noteworthy to mention the designers has no claim against the related key attack and even provided a deterministic related key characteristic for full round cipher, and extended it to exhaustive key search with the complexity of $2^{124}$. However, given our distinguishers, it is possible to recover the key with the complexity of $2^{40}$.

Although the provided analysis does not compromise the cipher, we think it provides a better insight behind the designing of CRAFT.

The basic concept behind the emergence of Internet of Things (IoT) is to connect as many objects to the Internet as possible in an attempt to make our lives better in some way. However, connecting everyday objects like your car or house to the Internet can open up major security concerns. In this paper, we present a novel security framework for the Message Queue Transport Telemetry (MQTT) protocol based on publish/subscribe messages in order to enhance secure and privacy-friendly Internet of Things services. MQTT has burst onto the IoT scene in recent years due to its lightweight design and ease of use implementation necessary for IoT. Our proposed solution provides 3 security levels. The first security level suits for lightweight data exchanges of non-tampered messages. The second security level enhances the privacy protection of data sources and data receivers. The third security level offers robust long-term security with mutual authentication for all parties. The security framework is based on light cryptographic schemes in order to be suitable for constrained and small devices that are widely used in various IoT use cases. Moreover, our solution is tailored to MQTT without using additional security overhead.

Authenticated encryption (AE) has been a vital operation in cryptography due to its ability to provide confidentiality, integrity, and authenticity at the same time. Its use has soared in parallel with widespread use of the Internet and has led to several new schemes. There have been studies investigating software performance of various schemes. However, the same is yet to be done for hardware. We present a comprehensive survey of hardware (specifically ASIC) performance of the most commonly used AE schemes in the literature. These schemes include encrypt-then-MAC combination, block cipher based AE modes, and the recently-introduced permutation-based AE scheme. For completeness, we implemented each scheme with various standardized block ciphers and/or hash algorithms, and their lightweight versions. Our evaluation targets minimizing the time-area product while maximizing the throughput on an ASIC platform. We used 45nm NANGATE Open Cell Library for syntheses. We present area, speed, time-area product, throughput, and power figures for both standard and lightweight versions of each scheme. We also provide an unbiased discussion on the impact of the structure and complexity of each scheme on hardware implementation. Our results reveal 13-30% performance boost in permutation-based AE compared to conventional schemes and they can be used as a benchmark in the ongoing AE competition CAESAR.

The tower field implementation of the $\mathbb{F}_{2^8}$ inverter is not only the key technique for compact implementations of the S-boxes of several internationally standardized block ciphers such as AES, Camellia, and SM4, but also the underlying structure many side-channel attack resistant AES implementations rely on. In this work, we conduct an exhaustive study of the tower field representations of the $\mathbb{F}_{2^8}$ inverter with normal bases by applying several state-of-the-art combinatorial logic minimization techniques. As a result, we achieve improved implementations of the AES, Camellia and SM4 S-boxes in terms of area footprint. Surprisingly, we are still able to improve the currently known most compact implementation of the AES S-box from CHES 2018 by 5.5 GE, beating the record again (Excluding this work, the latest improvement was proposed at CHES 2018, which achieves 11.75 GE improvement over the optimal implementation at the time). For Camellia and SM4, the improvements are even more significant. The Verilog codes of our implementations of the AES, Camellia and SM4 S-boxes are openly available.

In this paper we give nearly-tight reductions for modern implicitly authenticated Diffie-Hellman protocols in the style of the Signal and Noise protocols which are extremely simple and efficient. Unlike previous approaches, the combination of nearly-tight proofs and efficient protocols enables the first real-world instantiations for which the parameters can be chosen in a theoretically sound manner.

Our reductions have only a linear loss in the number of users, implying that our protocols are more efficient than the state of the art when instantiated with theoretically sound parameters. We also prove that our security proofs are optimal: a linear loss in the number of users is unavoidable for our protocols for a large and natural class of reductions.

Oblivious RAM (ORAM) is a cryptographic primitive that allows a client to hide access pattern to its data encrypted and stored at a remote server. Traditionally, ORAM algorithms assume the server acts purely as a storage device. Under this assumption, ORAM has at least $log(N)$ bandwidth blowup for $N$ data entries. After three decades of improvements, ORAM algorithms have reached the optimal logarithmic bandwidth blowup. Nonetheless, in many practical use-cases a constant bandwidth overhead is desirable. To this purpose, Devadas et al. (TCC 2016) formalized the server computation model for ORAM and proposed Onion ORAM which relies on homomorphic computation to achieve constant worst-case bandwidth blowup. This line of work is generally believed to be purely theoretical, due to the large overheads of homomorphic computation. In this paper, we present Onion Ring ORAM, the first efficient constant bandwidth ORAM scheme in the single server model, based on the Onion ORAM construction and the leveled version of the TFHE scheme by Chillotti et al.. We propose a series of improvements, most notably including a more efficient homomorphic permutation protocol. We implement Onion Ring ORAM and show that it can outperform state-of-the-art logarithmic-bandwidth ORAM like Path ORAMs and Ring ORAM when the network throughput is limited. Under one setting, our construction improves the end-to-end latency by 1.5 times over Ring ORAM and 7.3 times over Path ORAM.

The underlying fundaments of blockchain are cryptography and cryptographic concepts that provide reliable and secure decentralized solutions. Although many recent papers study the use-cases of blockchain in different industrial areas, such as finance, health care, legal relations, IoT, information security, and consensus building systems, only few studies scrutinize the cryptographic concepts used in blockchain. To the best of our knowledge, there is no Systematization of Knowledge (SoK) that gives a complete picture of the existing cryptographic concepts which have been deployed or have the potential to be deployed in blockchain. In this paper, we thoroughly review and systematize all cryptographic concepts which are already used in blockchain. Additionally, we give a list of cryptographic concepts which have not yet been applied but have big potentials to improve the current blockchain solutions. We also include possible instantiations (references) of these cryptographic concepts in the blockchain domain. Last but not least, we explicitly postulate 18 challenging problems that cryptographers interested in blockchain can work on.