International Association
for Cryptologic Research

In 2018, Aono et al. (ASIACRYPT 2018) proposed to use quantum backtracking algorithms (Montanaro, TOC 2018; Ambainis and Kokainis, STOC 2017) to speedup lattice point enumeration. Quantum lattice sieving algorithms had already been proposed (Laarhoven et al., PQCRYPTO 2013), being shown to provide an asymptotic speedup over classical counterparts, but also to lose competitiveness at dimensions relevant to cryptography if practical considerations on quantum computer architecture were taken into account (Albrecht et al., ASIACRYPT 2020). Aono et al.'s work argued that quantum walk speedups can be applied to lattice enumeration, achieving at least a quadratic asymptotic speedup à la Grover search while not requiring exponential amounts of quantum accessible classical memory, as it is the case for sieving. In this work, we explore how to lower bound the cost of using Aono et al.'s techniques on lattice enumeration with extreme cylinder pruning, assuming a limit to the maximum depth that a quantum computation can achieve without decohering, with the objective of better understanding the practical applicability of quantum backtracking in lattice cryptanalysis.

FIDO2 is currently the main initiative for passwordless authentication in web servers. It mandates the use of secure hardware authenticators to protect the authentication protocol's secrets from compromise. However, to ensure that only secure authenticators are being used, web servers need a method to attest their properties.The FIDO2 specifications allow for authenticators and web servers to choose between different attestation modes to prove the characteristics of an authenticator, however the properties of most these modes have not been analysed in the context of FIDO2. In this work, we analyse the security and privacy properties of FIDO2 when the different attestation modes included in the standard are used, and show that they lack good balance between security, privacy and revocation of corrupted devices. For example, the basic attestation mode prevents remote servers from tracing user's actions across different services while requiring reduced trust assumptions. However in case one device is compromised, all the devices from the same batch (e.g., of the same brand or model) need to be recalled, which can be quite complex (and arguably impractical) in consumer scenarios. As a consequence we suggest a new attestation mode based on the recently proposed TokenWeaver, which provide more convenient mechanisms for revoking a single token while maintaining user privacy.

V2V technology has the potential to prevent 615,000 collisions per year in the US, reduce congestion by up to 30%, and support efforts in slowing climate change by eliminating 5% of vehicle CO2 emissions. However, the security of V2V technology is often an afterthought, much less the threat of quantum computing on this security. With experts estimating that RSA-2048 will be broken by quantum computers with a probability of 50-99% by 2051, and cars manufactured today having an expected lifespan of 30 years, time is running out. This research is the first full-scale study into how post-quantum cryptography (PQC) will interact with current standards for vehicle-to-vehicle (V2V) communications. Connected vehicles use V2V technology to exchange safety messages that allow them to avoid colliding with each other, improving roadway safety and proximity awareness. These communications must be secured against malicious attacks to ensure an adversary cannot abuse V2V to cause a collision, traffic jam, or other unsafe and/or disruptive situation. The IEEE 1609.2 standard (2016) specifies authentication mechanisms for V2V communication. However, it relies on the Elliptic Curve Digital Signature Algorithm (ECDSA), which is not quantum-secure. It is therefore imperative that this standard be updated to support quantum-secure algorithms in line with current PQ standardisation efforts by NIST (2016). To the best of our knowledge, ours is among the first works to consider PQC in conjunction with the 1609.2 standard from the perspective of digital signatures, and the first to do so with consideration for the unique constraints imposed by the complex, wireless environment of V2V communications. In this talk, we consider how the three NIST digital signature finalists would integrate with the IEEE 1609.2 standard and, using these observations, we propose several practical designs for consideration during migration to PQC. Specifically, we conclude that Falcon-512 is the most suitable NIST PQC finalist for V2V and illustrate how Falcon can be incorporated into pure PQC, hybrid classical-PQC, backwards-compatible and ``partially quantum-secure'' designs to leverage PQ security while accounting for its large public key sizes. Through experimental evaluation of these designs using a software-defined radio testbed, we show that a partially quantum-secure hybrid scheme, using post-quantum certificates to support classical ECDSA signatures, achieves the best compromise between PQ security and little impact on V2V system performance during the transition phase.

This paper presents a set of efficient and parameterized hardware accelerators that target post-quantum lattice-based cryptographic schemes, including a versatile cSHAKE core, a binary-search CDT-based Gaussian sampler, and a pipelined NTT-based polynomial multiplier, among others. Unlike much of prior work, the accelerators are fully open-sourced, are designed to be constant-time, and can be parameterized at compile-time to support different parameters without the need for re-writing the hardware implementation. These flexible, publicly-available accelerators are leveraged to demonstrate the first hardware-software co-design using RISC-V of the post-quantum lattice-based signature scheme qTESLA with provably secure parameters. In particular, this work demonstrates that the NIST’s Round 2 level 1 and level 3 qTESLA variants achieve over a 40-100x speedup for key generation, about a 10x speedup for signing, and about a 16x speedup for verification, compared to the baseline RISC-V software-only implementation. For instance, this corresponds to execution in 7.7, 34.4, and 7.8 milliseconds for key generation, signing, and verification, respectively, for qTESLA’s level 1 parameter set on an Artix-7 FPGA, demonstrating the feasibility of the scheme for embedded applications.

We revisit the construction of IND-CCA secure key encapsulation mechanisms (KEM) from public-key encryption schemes (PKE). We give new, tighter security reductions for several constructions. Our main result is an improved reduction for the security of the $$U^{\not \bot }$$ -transform of Hofheinz, Hövelmanns, and Kiltz (TCC’17) which turns OW-CPA secure deterministic PKEs into IND-CCA secure KEMs. This result is enabled by a new one-way to hiding (O2H) lemma which gives a tighter bound than previous O2H lemmas in certain settings and might be of independent interest. We extend this result also to the case of PKEs with non-zero decryption failure probability and non-deterministic PKEs. However, we assume that the derandomized PKE is injective with overwhelming probability.In addition, we analyze the impact of different variations of the $$U^{\not \bot }$$ -transform discussed in the literature on the security of the final scheme. We consider the difference between explicit ( $$U^{\bot }$$ ) and implicit ( $$U^{\not \bot }$$ ) rejection, proving that security of the former implies security of the latter. We show that the opposite direction holds if the scheme with explicit rejection also uses key confirmation. Finally, we prove that (at least from a theoretic point of view) security is independent of whether the session keys are derived from message and ciphertext ( $$U^{\not \bot }$$ ) or just from the message ( $$U^{\not \bot }_m$$ ).