28 research outputs found
Quantum Cryptanalysis in the RAM Model: Claw-Finding Attacks on SIKE
No full textWe introduce models of computation that enable direct comparisons between classical and quantum algorithms. Incorporating previous work on quantum computation and error correction, we justify the use of the gate-count and depth-times-width cost metrics for quantum circuits. We demonstrate the relevance of these models to cryptanalysis by revisiting, and increasing, the security estimates for the Supersingular Isogeny Diffie--Hellman (SIDH) and Supersingular Isogeny Key Encapsulation (SIKE) schemes. Our models, analyses, and physical justifications have applications to a number of memory intensive quantum algorithms
Clubcards for the WebPKI: smaller certificate revocation tests in theory and practice
No full textCRLite is a low-bandwidth, low-latency, privacy-preserving mechanism for distributing certificate revocation data. A CRLite aggregator periodically encodes revocation data into a compact static hash set, or membership test, which can can be downloaded by clients and queried privately. We present a novel data-structure for membership tests, which we call a clubcard, and we evaluate the encoding efficiency of clubcards using data from Mozilla\u27s CRLite infrastructure.
As of November 2024, the WebPKI contains over 900 million valid certificates and over 8 million revoked certificates. We describe an instantiation of CRLite that encodes the revocation status of these certificates in a 6.7 MB package. This is smaller than the original instantiation of CRLite presented at the 2017 IEEE Symposium on Security and Privacy, and it is smaller than the lower bound claimed in that work.
A sequence of clubcards can encode a dynamic dataset like the WebPKI revocation set. Using data from late 2024 again, we find that clubcards encoding 6 hour delta updates to the WebPKI can be compressed to 26.8 kB on average---a size that makes CRLite truly practical.
We have extended Mozilla\u27s CRLite infrastructure so that it can generate clubcards, and we have added client-side support for this system to Firefox. We report on some performance aspects of our implementation, which is currently the default revocation checking mechanism in Firefox Nightly, and we propose strategies for further reducing the bandwidth requirements of CRLite
A Comparison of NTRU Variants
No full textWe analyze the size vs. security trade-offs that are available when selecting parameters for perfectly correct key encapsulation mechanisms based on NTRU
An upper bound on the decryption failure rate of static-key NewHope
No full textWe give a new proof that the decryption failure rate of NewHope512 is at most . As in previous work, this failure rate is with respect to random, honestly generated, secret key and ciphertext pairs. However, our technique can also be applied to a fixed secret key. We demonstrate our technique on some subsets of the NewHope1024 key space, and we identify a large subset of NewHope1024 keys with failure rates of no more than
Multi-power Post-quantum RSA
No full textSpecial purpose factoring algorithms have discouraged the adoption of multi-power RSA, even in a post-quantum setting. We revisit the known attacks and find that a general recommendation against repeated factors is unwarranted. We find that one-terabyte RSA keys of the form are competitive with one-terabyte RSA keys of the form . Prime generation can be made to be a factor of 100000 times faster at a loss of at least but not more than bits of security against known attacks. The range depends on the relative cost of bit and qubit operations under the assumption that qubit operations cost bit operations for some constant
Decryption failure is more likely after success
No full textThe user of an imperfectly correct lattice-based public-key encryption scheme leaks information about their secret key with each decryption query that they answer---even if they answer all queries successfully. Through a refinement of the D\u27Anvers--Guo--Johansson--Nilsson--Vercauteren--Verbauwhede failure boosting attack, we show that an adversary can use this information to improve his odds of finding a decryption failure. We also propose a new definition of -correctness, and we re-assess the correctness of several submissions to NIST\u27s post-quantum standardization effort
Circuit-extension handshakes for Tor achieving forward secrecy in a quantum world
No full textWe propose a circuit extension handshake for Tor that is forward secure against adversaries who gain quantum computing capabilities after session negotiation. In doing so, we refine the notion of an authenticated and confidential channel establishment (ACCE) protocol and define pre-quantum, transitional, and post-quantum ACCE security. These new definitions reflect the types of adversaries that a protocol might be designed to resist. We prove that, with some small modifications, the currently deployed Tor circuit extension handshake, ntor, provides pre-quantum ACCE security. We then prove that our new protocol, when instantiated with a post-quantum key encapsulation mechanism, achieves the stronger notion of transitional ACCE security. Finally, we instantiate our protocol with NTRUEncrypt and provide a performance comparison between ntor, our proposal, and the recent design of Ghosh and Kate
Choosing Parameters for NTRUEncrypt
No full textAbstract. We describe a methods for generating parameter sets and calculating security estimates for NTRUEncrypt. Analyses are provided for the standardized product-form parameter sets from IEEE 1363.1-2008 and for the NTRU Challenge parameter sets.
TRANSCRIPT SECURE SIGNATURES BASED ON MODULAR LATTICES
No full textAbstract. We introduce the notion of a class of lattice-based digital signature schemes based on modular properties of the co-ordinates of lattice vectors. We also suggest a method of making such schemes transcript secure via a rejection sampling technique of Lyubashevsky (2009). A particular instantiation of this approach is given, using NTRU lattices. Although the scheme is not sup-ported by a formal security reduction, we present arguments for its security and derive concrete parameters based on the performance of state-of-the-art lattice reduction and enumeration techniques. 1
