International Association
for Cryptologic Research

We analyze the authenticated encryption algorithm of ORANGE, a submission to the NIST lightweight cryptography standardization process. We show that it is practically possible to craft forgeries out of two observed transmitted messages that encrypt the same plaintext. The authors of ORANGE have confirmed the attack, and they discuss a fix for this attack in their second-round submission of ORANGE to the NIST lightweight cryptography competition.

We define the notion of one-shot signatures, which are signatures where any secret key can be used to sign only a single message, and then self-destructs. While such signatures are of course impossible classically, we construct one-shot signatures using quantum no-cloning. In particular, we show that such signatures exist relative to a classical oracle, which we can then heuristically obfuscate using known indistinguishability obfuscation schemes.

We show that one-shot signatures have numerous applications for hybrid quantum/classical cryptographic tasks, where all communication is required to be classical, but local quantum operations are allowed. Applications include one-time signature tokens, quantum money with classical communication, decentralized blockchain-less cryptocurrency, signature schemes with unclonable secret keys, non-interactive certifiable min-entropy, and more. We thus position one-shot signatures as a powerful new building block for novel quantum cryptographic protocols.

We suggests a relaxed freshness paradigm for challenge-response authentication for each field of application where challenger and responder are tightly coupled and authentication takes place in a friendly environment. Replay attacks are not feasible under this premise, and freshness can be relaxed to relative freshness: no refresh is required as long as all previously tested responders were authentic. One field of application is anti-counterfeiting of electronic device components. The main contribution is a formal security proof of an authentication scheme with choked refresh. A practical implication is the lifetime increase of stored challenge-response-pairs. This is a considerable advantage for solutions based on hardware intrinsic security. For solutions based on symmetric keys, it opens the possibility to use challenge-response-pairs instead of secret keys by the challenger – a cheap way to reduce the risk of key disclosure.

We provide a solution for the authentication of a component, accessory, smart card or tag by a main device via challenge-response-tests of two MCU intrinsic features: Progression in the execution of test programs (measured in processor clocks) and peripheral feedback to internal stimulation. The main device will be called challenger and the other device responder. Our solution requires that the authentic responders are characterized by a dedicated MCU model and a common responder ID in read-only MCU registers. Its main application is the detection/lock-out of counterfeit batteries, cartridges, sensors, or control units. The solution also suits as a redundant authentication factor in high security applications, such as payment, or conditional access.

We discuss existing and new security notions for white-box cryptography and comment on their suitability for Digital Rights Management and Mobile Payment Applications, the two prevalent use-cases of white-box cryptography. In particular, we put forward indistinguishability for white-box cryptography with hardware-binding (IND-WHW) as a new security notion that we deem central. We also discuss the security property of application-binding and explain the issues faced when defining it as a formal security notion. Based on our proposed notion for hardware-binding, we describe a possible white-box competition setup which assesses white-box implementations w.r.t. hardware-binding. Our proposed competition setup allows us to capture hardware-binding in a practically meaningful way.

While some symmetric encryption schemes have been proven to admit plain white-box implementations, we show that not all secure symmetric encryption schemes are white-boxeable in the plain white-box attack scenario, i.e., without hardware-binding. Thus, even strong assumptions such as indistinguishability obfuscation cannot be used to provide secure white-box implementations for arbitrary ciphers. Perhaps surprisingly, our impossibility result does not carry over to the hardware-bound scenario. In particular, Alpirez Bock, Brzuska, Fischlin, Janson and Michiels (ePrint 2019/1014) proved a rather general feasibility result in the hardware-bound model. Equally important, the apparent theoretical distinction between the plain white-box model and the hardware-bound white-box model also translates into practically reduced attack capabilities as we explain in this paper.

Deoxys-BC is the core internal tweakable block cipher of the authenticated encryption schemes Deoxys-I and Deoxys-II. Deoxys-II is one of the six schemes in the final portfolio of the CAESAR competition, while Deoxys-I is a 3rd round candidate. By well studying the new method proposed by Cid et al. at ToSC 2017 and BDT technique proposed by Wang and Peyrin at ToSC 2019, we find a new 11-round related-tweakey boomerang distinguisher of Deoxys-BC-384 with probability of $2^{-118.4}$, and give a related-tweakey rectangle attack on 13-round Deoxys-BC-384 with a data complexity of $2^{125.2}$ and time complexity of $2^{186.7}$, and then apply it to analyze 13-round Deoxys-I-256-128 in this paper. This is the first time that an attack on 13-round Deoxys-I-256-128 is given, while the previous attack on this version only reaches 12 rounds.

In the CAESAR competition, Deoxys-I and Deoxys-II are two important authenticated encryption schemes submitted by Jean et al. Recently, Deoxys-II together with Ascon, ACORN, AEGIS-128, OCB and COLM have been selected as the final CAESAR portfolio. Notably, Deoxys-II is also the primary choice for the use case ``Defense in depth''. However, Deoxys-I remains to be one of the third-round candidates of the CAESAR competition. Both Deoxys-I and Deoxys-II adopt Deoxys-BC-256 and Deoxys-BC-384 as their internal tweakable block ciphers.

In this paper, we investigate the security of round-reduced Deoxys-BC-256/-384 and Deoxys-I against the related-tweakey boomerang and rectangle attacks with some new boomerang distinguishers. For Deoxys-BC-256, we present 10-round related-tweakey boomerang and rectangle attacks for the popular setting $(|tweak|,|key|)=(128,128)$, which reach one more round than the previous attacks in this setting. Moreover, an 11-round related-tweakey rectangle attack on Deoxys-BC-256 is given for the first time. We also put forward a 13-round related-tweakey boomerang attack in the popular setting $(|tweak|,|key|)=(128,256)$ for Deoxys-BC-384, while the previous attacks in this setting only work for 12 rounds at most. In addition, the first 14-round related-tweakey rectangle attack on Deoxys-BC-384 is given when $(|tweak|<98,|key|>286)$, that attacks one more round than before. Besides, we give the first 10-round rectangle attack on the authenticated encryption mode Deoxys-I-128-128 with one more round than before, and we also reduce the complexity of the related-tweakey rectangle attack on 12-round Deoxys-I-256-128 by a factor of $2^{28}$. Our attacks can not be applied to (round-reduced) Deoxys-II.

End-user privacy in mobile telephony systems is nowadays of great interest because of the envisaged hyper connectivity and the potential of the unprecedented services (virtual reality, machine-type communication, vehicle-to-everything, IoT, etc) being offered by the new 5G system. This paper reviews the state of subscription privacy in 5G systems. As the work on 5G Release 15 – the first full set of 5G standards – has just recently been completed, this seems to be an ideal occasion for such a review. The scope of the privacy study undertaken is limited to the wireless part of the 5G system which occurs between the service provider’s base station and the subscriber’s mobile phone. Although 5G offers better privacy guarantees than its predecessors, contrary to popular belief, this work highlights that there still remain significant issues which need rectifying. To shed light on this matter, we undertook an endeavour to (i) compile the privacy vulnerabilities that already existed in the previous mobile telephony generations. Thereafter, (ii) the privacy improvements offered by the recently finalised 5G standard were aggregated. Consequently, (iii) we were able to highlight privacy issues from previous generations that remain unresolved in 5G Release 15. For completeness, (iv) we also explore new privacy attacks which surfaced after the publication of the 5G standard. To address the identified privacy gaps, we present future research directions in form of proposed improvements.

Using recent results on solving the equation $X^{2^k+1}+X+a=0$ over a finite field $\GF{2^n}$, we address an open question raised by the first author in WAIFI 2014 concerning the APN-ness of the Kasami functions $x\mapsto x^{2^{2k}-2^k+1}$ with $gcd(k,n)=1$, $x\in\GF{2^n}$

Event date: 24 May to 26 May 2020

Event date: 2 September to 4 September 2020
Submission deadline: 23 March 2020
Notification: 22 May 2020

Hybrid Authenticated Key Exchange (AKE) protocols combine keying material from different sources (post-quantum, classical, and quantum key distribution (QKD)) to build protocols that are resilient to catastrophic failures of the different components. These failures may be due to advances in quantum computing, implementation vulnerabilities, or our evolving understanding of the quantum (and even classical) security of supposedly quantum-secure primitives. This hybrid approach is a prime candidate for initial deployment of post-quantum-secure cryptographic primitives because it hedges against undiscovered weaknesses. We propose a general framework HAKE for analysing the security of such hybrid AKE protocols. HAKE extends the classical Bellare-Rogaway model for AKE security to encompass forward security, post-compromise security, fine-grained compromise of different cryptographic components, and more. We use the framework to provide a security analysis of a new hybrid AKE protocol named Muckle. This protocol operates in one round trip and leverages the pre-established symmetric keys that are inherent to current QKD designs to provide message authentication, avoiding the need to use expensive post-quantum signature schemes. We provide an implementation of our Muckle protocol, instantiating our generic construction with classical and post-quantum Diffie-Hellman-based algorithmic choices. Finally, we report on benchmarking exercises against our implementation, examining its performance in terms of clock cycles, elapsed wall-time, and additional latency in both LAN and WAN settings.

We give an algorithm for key recovery of the Legendre pseudorandom function that supersedes the best known algorithms so far. The expected number of operations is $O(\sqrt{p\log{\log{p}}})$ on a $\Theta(\log{p})$-bit word machine, under reasonable heuristic assumptions, and requires only $\sqrt[4]{p~{\log^2{p}}\log{\log{p}}}$ oracle queries. If the number of queries $M$ is smaller, the expected number of operations is $\frac{{p}\log{p}\log\log{p}}{M^2}$. We further show that the algorithm works in many different generalisations -- using a different character instead of the Legendre symbol, using the Jacobi symbol, or using a degree $r$ polynomial in the Legendre symbol numerator. In the latter case we show how to use Möbius transforms to lower the complexity to $O(p^{\operatorname{max}\{r-3,r/2\}}r^2\log{p})$ Legendre symbol computations, and $O(p^{\operatorname{max}\{r-4,r/2\}}r^2\log{p})$ in the case of a reducible polynomial. We also give an $O(\sqrt[3]{p})$ quantum algorithm that does not require a quantum oracle, and comments on the action of the Möbius group in the linear PRF case. On the practical side we give implementational details of our algorithm. We give the solutions of the $64, 74$ and $84$-bit prime challenges for key recovery with $M=2^{20}$ queries posed by Ethereum, out of which only the $64$ and $74$-bit were solved earlier.

The survey deals with elliptic curves which are implemented in the OpenSSL 1.1.1d software library. The objective of this work is to highlight the elliptic curves which comply with the Russian national digital signature standard, namely the GOST R 34.10--2012. For this reason the paper focuses on the OpenSSL elliptic curves over a finite field of a prime order and provides the results of testing those curves for compliance with the GOST R 34.10--2012 requirements. Two cases are observed. The first case covers a complete set of restrictions imposed on elliptic curves parameters, whereas the second one differs in that a restriction on a bit length of a number of points on the curve is omitted. For both cases the paper presents tables which list the curves tested along with corresponding match marks. In order to conduct tests the Wolfram Mathematica computing system was employed, and the Wolfram language source code is given in the appendices. Note, that the paper does not address to a rationale of the requirements of the standard nor does it focus on the parameters generation issues.

We provide the first systematic analysis of (Non-Interactive) Fully Distributed Verifiable Random Functions (DVRFs), including their syntax, definition of integrity and privacy properties, and describe and analyse three concrete constructions, two of which are original. Building on recent work (Agrawal, Mohassel, Mukherjee, Rindal: CCS 2018), we strengthen the standard pseudorandomness property by allowing an adversary to make partial queries on the challenge value, and call the resulting property strong pseudorandomness. We show how a prominent DVRF construction in the blockchain space meets standard pseudorandomness, and provide two other instantiations that meet strong pseudorandomness, under widely accepted cryptographic assumptions. We review how to generically build a Decentralized Random Beacon (DRB) from any DVRF instance. DRBs have recently gained a lot traction as a key component for leader(s) election in decentralized ledger technologies. We provide implementations and experimental evaluations of three concrete DVRFs, using different cryptographic libraries. Our two new DRB instantiations are strongly pseudorandom and strongly unbiasable, while exhibiting high performance and linear communication complexity (as they are in essence non-interactive). We provide a C++ reference implementation that is available in open source form.

We propose a new family of public key encryption (PKE) and key encapsulation mechanism (KEM) schemes based on the plain learning with errors (LWE) problem. Two new design techniques are adopted in the proposed scheme named SCloud: the sampling method and the error-reconciliation mechanism. The new sampling method is obtained by studying the property of the convolution of central binomial distribution and bounded uniform distribution which can achieve higher efficiency and more flexibility w.r.t the parameter choice. Besides, it is shown to be more secure against the dual attack due to its advantage in distinguish property. The new error-reconciliation mechanism is constructed by combining the binary linear codes and Gray codes. It can reduce the size of parameters, and then improve the encryption/decryption efficiency as well as communication efficiency, by making full use of the encryption space. Based on these two techniques, SCloud can provide various sets of parameters for refined security level.

The selfish mining attack allows cryptocurrency miners to mine more than their "fair share" of blocks, stealing revenue from other miners while reducing the overall security of payments. This malicious strategy has been extensively studied in Bitcoin, but far less attention has been paid to how the strategy may impact other cryptocurrencies. Because selfish mining is an attack against the difficulty adjustment algorithm (DAA) of a cryptocurrency, it may have a different effect when used on coins with different DAAs. In this work, we study the degree to which selfish mining can increase the revenue of miners for a wider variety of cryptocurrencies than have been studied before, including Bitcoin, Litecoin, Bitcoin Cash, Dash, Monero, and Zcash. To do so, we generalize the selfish mining strategy to blockchains with variable difficulty, and use simulations to measure how profitable the strategy is. We find that the other cryptocurrencies under consideration are far more susceptible to selfish mining than Bitcoin is, and that the strategy is profitable for miners with a lower hash rate. We also show that by dishonestly reporting block timestamps, selfish miners can generate enormously disproportionate revenues up to 2.5 times larger than they would through honest mining for some DAAs. For each DAA, we consider what happens when parameters are changed, and suggest parameter sets that would improve the algorithm’s resilience against selfish mining.

We give the first public-key functional encryption that supports the generation of functional decryption keys for degree-2 polynomials, with succinct ciphertexts, whose semi-adaptive simulation-based security is proven under standard assumptions. At the heart of our new paradigm lies a so-called partially function-hiding functional encryption scheme for inner products, which admits public-key instances, and that is sufficient to build functional encryption for degree-2 polynomials. Doing so, we improve upon prior works, such as the constructions from Lin (CRYPTO 17) or Ananth Sahai (EUROCRYPT 17), both of which rely on function-hiding inner product FE, that can only exist in the private-key setting. The simplicity of our construction yields the most efficient FE for quadratic functions from standard assumptions (even those satisfying a weaker security notion). The interest of our methodology is that the FE for quadratic functions that builds upon any partially function-hiding FE for inner products inherits the security properties of the latter. In particular, we build a partially function-hiding FE for inner products that enjoys simulation security, in the semi-adaptive setting, where the challenge sent from the adversary can be chosen adaptively after seeing the public key (but before corrupting functional decryption keys). This is in contrast from prior public-key FE for quadratic functions from Baltico et al. (CRYPTO 17), which only achieved an indistinguishability-based, selective security. As a bonus, we show that we can obtain security against Chosen-Ciphertext Attacks straightforwardly. Even though this is the de facto security notion for encryption, this was not achieved by prior functional encryption schemes for quadratic functions, where the generic Fujisaki Otamoto transformation (CRYPTO 99) does not apply.

Composable security definitions, sometimes called simulation-based definitions, provide very strong security guarantees. In particular, they assure that the guarantees hold in any context. However, they are also met with some skepticism because of many impossibility results; goals such as commitments and zero-knowledge that are achievable in a stand-alone sense were shown to be unachievable composably (without a setup) since provably no efficient simulator exists. In particular, in the context of adaptive security, the so-called simulator commitment problem arises: once a party gets corrupted, an efficient simulator is unable to be consistent with its pre-corruption outputs. A natural question is whether such impossibility results are unavoidable or only artifacts of frameworks being too restrictive.

In this work, we propose a new type of composable security statement that evades the commitment problem by a specific instantiation of the concept of system specifications in the Constructive Cryptography (CC) framework, capturing the intersection of several interval-wise guarantees, each specifying the guarantees between two events. We develop the required theory within the CC framework and present the corresponding new composition theorem.

We present three applications of our notion. First, we show in the context of symmetric encryption with adaptive corruption how our notion naturally captures the expected confidentiality guarantee---the messages remain confidential until either party gets corrupted---and that it can be achieved by any standard semantically secure scheme (negating the need for non-committing encryption). Second, we present a composable formalization of commitments that is instantiable without a trusted setup like a CRS, and show its application to coin tossing over the telephone, one of the early intuitive applications of commitments. Third, we reexamine a result by Hofheinz, Matt, and Maurer [Asiacrypt'15] implying that IND-ID-CPA security is not the right notion for identity-based encryption, unmasking this claim as an unnecessary framework artifact.

Though Fully Homomorphic Encryption (FHE) has been realized, most practical implementations utilize leveled Somewhat Homomorphic Encryption (SHE) schemes, which have limits on the multiplicative depth of the circuits they can evaluate and avoid computationally intensive bootstrapping. Many SHE schemes exist, among which those based on Ring Learning With Error (RLWE) with operations on large polynomial rings are popular. Of these, variants allowing operations to occur fully in Residue Number Systems (RNS) have been constructed. This optimization allows homomorphic operations directly on RNS components without needing to reconstruct numbers from their RNS representation, making SHE implementations faster and highly parallel. In this paper, we present a set of optimizations to a popular RNS variant of the B/FV encryption scheme that allow for the use of significantly larger ciphertext moduli (e.g., thousands of bits) without increased overhead due to excessive numbers of RNS components or computational overhead, as well as computational optimizations. This allows for the use of larger ciphertext moduli, which leads to a higher multiplicative depth with the same computational overhead. Our experiments show that our optimizations yield runtime improvements of up to 4.48 for decryption and 14.68 for homomorphic multiplication for large ciphertext moduli.