Annotated publication list

title
Estimating quantum speedups for lattice sieves
authors
Martin R. Albrecht, Vlad Gheorghiu, Eamonn W. Postlethwaite, John M. Schanck
abstract
Quantum variants of lattice sieve algorithms are routinely used to assess the security of lattice based cryptographic constructions. In this work we provide a heuristic, non-asymptotic, analysis of the cost of several algorithms for near neighbour search on high dimensional spheres. These algorithms are key components of lattice sieves. We design quantum circuits for near neighbour search algorithms and provide software that numerically optimises algorithm parameters according to various cost metrics. Using this software we estimate the cost of classical and quantum near neighbour search on spheres. For the most performant near neighbour search algorithm that we analyse we find a small quantum speedup in dimensions of cryptanalytic interest. Achieving this speedup requires several optimistic physical and algorithmic assumptions.
published in / presented at
Advances in Cryptology – ASIACRYPT 2020
presentations
2020-12-02 : Eamonn Postlethwaite @ ASIACRYPT 2020 [video]
2019-10-17 : Dagstuhl 19421 [slides | workshop]
publication dates
2020-12-05 : Posted to SpringerLink.
2020-09-14 : Updated IACR ePrint.
2020-05-20 : Updated IACR ePrint.
2019-10-07 : Posted to IACR ePrint.

title
Decryption failure is more likely after success
authors
Nina Bindel, John M. Schanck
abstract
The 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'Anvers--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's post-quantum standardization effort.
published in / presented at
Post-Quantum Cryptography – PQCrypto 2020
presentations
2020-09-16 : Nina Bindel @ PQCrypto 2020 [video]
publication dates
2020-04-10 : Posted to SpringerLink.
2020-02-07 : Updated IACR ePrint.
2019-12-02 : Posted to IACR ePrint.

files
paper: 20200207-decfail.pdf
scripts: github

title
Quantum Cryptanalysis in the RAM model: Claw-finding attacks on SIKE
authors
Samuel Jaques, John M. Schanck
abstract
We 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.
published in / presented at
Advances in Cryptology – CRYPTO 2019
presentations
2019-08-20 : Samuel Jaques @ CRYPTO 2019 [slides]
publication dates
2019-08-01 : Posted to SpringerLink.
2019-06-19 : Updated IACR ePrint.
2019-02-02 : Posted to IACR ePrint.

files
paper: 20190619-quantum-cryptanalysis-sike.pdf
scripts: 20190202-sike-scripts.tar.gz

notes
This paper was awarded a Best Young Researcher Paper award at CRYPTO.

title
CRYSTALS-Kyber: a CCA-secure module-lattice based KEM
authors
Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, Damien Stehlé
abstract
Rapid advances in quantum computing, together with the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digital-signature, encryption, and key-establishment protocols, have created significant interest in post-quantum cryptographic schemes.

This paper introduces Kyber (part of CRYSTALS -- Cryptographic Suite for Algebraic Lattices -- a package submitted to NIST post-quantum standardization effort in November 2017), a portfolio of post-quantum cryptographic primitives built around a key-encapsulation mechanism (KEM),based on hardness assumptions over module lattices. Our KEM is most naturally seen as a successor to the NewHope KEM (Usenix 2016). In particular, the key and ciphertext sizes of our new construction are about half the size, the KEM offers CCA instead of only passive security, the security is based on a more general (and flexible) lattice problem, and our optimized implementation results in essentially the same running time as the aforementioned scheme.

We first introduce a CPA-secure public-key encryption scheme, apply a variant of the Fujisaki--Okamoto transform to create a CCA-secure KEM, and eventually construct, in a black-box manner, CCA-secure encryption, key exchange, and authenticated-key-exchange schemes. The security of our primitives is based on the hardness of Module-LWE in the classical and quantum random oracle models, and our concrete parameters conservatively target more than 128 bits of post-quantum security.
published in / presented at
2018 IEEE European Symposium on Security and Privacy (EuroS&P)
presentations
2018-04-26 : EuroS&P [ slides | conference ]
publication dates
2018-07-16 : Updated IACR ePrint.
2018-07-09 : Posted to IEEE Xplore.
2017-06-27 : Posted to IACR ePrint.

files
paper: 20180709-kyber.pdf

notes
The NIST PQC submission package has its own entry on this page.
There is an implementation of Kyber on github.
The CRYSTALS package has its own site: pq-crystals.org.

title
High-speed key encapsulation from NTRU
authors
Andreas Hülsing, Joost Rijneveld, John M. Schanck, Peter Schwabe
abstract
This paper presents software demonstrating that the 20-year-old NTRU cryptosystem is competitive with more recent lattice-based cryptosystems in terms of speed, key size, and ciphertext size. We present a slightly simplified version of textbook NTRU, select parameters for this encryption scheme that target the 128-bit post-quantum security level, construct a KEM that is CCA2-secure in the quantum random oracle model, and present highly optimized software targeting Intel CPUs with the AVX2 vector instruction set. This software takes only 307914 cycles for the generation of a keypair, 48646 for encapsulation, and 67338 for decapsulation. It is, to the best of our knowledge, the first NTRU software with full protection against timing attacks.
published in / presented at
Cryptographic Hardware and Embedded Systems – CHES 2017
presentations
2017-09-26 : Joost Rijneveld @ CHES 2017 [slides | video].
publication dates
2017-08-29 : Updated IACR ePrint.
2017-08-25 : Posted to SpringerLink.
2017-07-11 : Updated IACR ePrint.
2017-07-05 : Posted to IACR ePrint.

files
paper : 20170828-ntruhrss.pdf

notes
The NIST PQC submission package has its own entry on this page.
There is an implementation of NTRU-HRSS on github.

title
Choosing parameters for NTRUEncrypt
authors
Jeff Hoffstein, Jill Pipher, John M. Schanck, Joseph H. Silverman, William Whyte, Zhenfei Zhang
abstract
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.
published in / presented at
Topics in Cryptology – CT-RSA 2017.
publication dates
2017-01-10 : Posted short conference version to SpringerLink.
2015-07-18 : Posted to IACR ePrint.

files
paper (full): 20150718-ntruparams.pdf
paper (short): 20170110-ntruparams.pdf

notes

title
Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3
authors
Matthew Amy, Olivia Di Matteo, Vlad Gheorghiu, Michele Mosca, Alex Parent, John M. Schanck
abstract
We investigate the cost of Grover's quantum search algorithm when used in the context of pre-image attacks on the SHA-2 and SHA-3 families of hash functions. Our cost model assumes that the attack is run on a surface code based fault-tolerant quantum computer. Our estimates rely on a time-area metric that costs the number of logical qubits times the depth of the circuit in units of surface code cycles. As a surface code cycle involves a significant classical processing stage, our cost estimates allow for crude, but direct, comparisons of classical and quantum algorithms.
We exhibit a circuit for a pre-image attack on SHA-256 that is approximately 2^{153.8} surface code cycles deep and requires approximately 2^{12.6} logical qubits. This yields an overall cost of 2^{166.4} logical-qubit-cycles. Likewise we exhibit a SHA3-256 circuit that is approximately 2^{146.5} surface code cycles deep and requires approximately 220 logical qubits for a total cost of, again, 2^{166.5} logical-qubit-cycles. Both attacks require on the order of 2^{128} queries in a quantum black-box model, hence our results suggest that executing these attacks may be as much as 275 billion times more expensive than one would expect from the simple query analysis.
published in / presented at
Selected Areas in Cryptography – SAC 2016.
presentations
2016-08-12 : Matt Amy @ SAC 2016 [slides].
publication dates
2016-11-30 : Updated IACR ePrint.
2016-11-30 : Updated arXiv.
2016-10-20 : Posted to SpringerLink.
2016-10-17 : Posted to IACR ePrint.
2016-10-13 : Updated arXiv.
2016-03-30 : Posted to arXiv.

files
paper: 20161130-preimage.pdf

title
Circuit-extension handshakes for Tor achieving forward secrecy in a quantum world
authors
John M. Schanck, William Whyte, Zhenfei Zhang
abstract
We 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 postquantum 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.
published in / presented at
Proceedings on Privacy Enhancing Technologies – PoPETS 2016.
presentations
2016-07-20: PETS [slides | video]
publication dates
2016-07-14: PoPETS 2016 online.
2016-06-13: Updated IACR ePrint.
2015-04-01: Posted to IACR ePrint. (title "A quantum-safe circuit-extension handshake for Tor").
files
paper: 20160602-tor.pdf

notes
There's a partial implementation using libntruencrypt.

title
NTRU modular lattice signature scheme on CUDA GPUs
authors
Wei Dai, Berk Sunar, John M. Schanck, William Whyte, Zhenfei Zhang
abstract
In this work we show how to use Graphics Processing Units (GPUs) with Compute Unified Device Architecture (CUDA) to accelerate a lattice based signature scheme, namely, the NTRU modular lattice signature (NTRU-MLS) scheme. Lattice based schemes require operations on large vectors that are perfect candidates for GPU implementations. In addition, similar to most lattice based signature schemes, NTRU-MLS provides transcript security with a rejection sampling technique. With a GPU implementation, we are able to generate many candidates simultaneously, and hence mitigate the performance slowdown from rejection sampling. Our implementation results show that for the original NTRU-MLS parameter sets, we obtain a 2x improvement in the signing speed; for the revised parameter sets, where acceptance rate of rejection sampling is down to around 1%, our implementation can be as much as 47x faster than a CPU implementation.
published in / presented at
High Performance Computing & Simulation – HPCS-2016
publication dates
2016-09-15 : Posted to IEEE Xplore.
2016-07-14 : Updated IACR ePrint.
2016-05-17 : Posted to IACR ePrint.
files
paper : 20160714-cuda.pdf

title
Transcript secure signatures based on modular lattices
authors
Jeff Hoffstein, Jill Pipher, John M. Schanck, Joseph H. Silverman, William Whyte
abstract
We introduce a class of lattice-based digital signature schemes based on modular properties of the coordinates 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 supported by a formal security reduction, we present arguments for its security and derive concrete parameters (first version) based on the performance of state-of-the-art lattice reduction and enumeration techniques. In the revision, we re-evaluate the security of first version of the parameter sets, under the hybrid approach of lattice reduction attack the meet-in-the-middle attack. We present new sets of parameters that are robust against this attack, as well as all previous known attacks.
published in / presented at
Post-Quantum Cryptography – PQCrypto 2014.
presentations
2014-10-01 : PQCrypto [slides | video]
publication dates
2016-04-29 : Updated IACR ePrint. Revised parameter sets.
2014-10-01 : Proceedings online.
2014-06-15 : Posted to IACR ePrint.
files
paper : 20160429-pqntrusign.pdf
notes
The system is called NTRU-MLS in the paper, but it is called pqNTRUSign elsewhere. There is a reference implementation available. The system is patented, but licenses are automatically granted to free software projects; see NTRUOpenSourceProject for usage restrictions. There is a pqNTRUSign NIST submission.

title
Practical signatures from the partial Fourier recovery problem
authors
Jeff Hoffstein, Jill Pipher, John M. Schanck, Joseph H. Silverman, William Whyte
abstract
We present PASSSign, a variant of the prior PASS and PASS-2 proposals, as a candidate for a practical post-quantum signature scheme. Its hardness is based on the problem of recovering a ring element with small norm from an incomplete description of its Chinese remainder representation. For our particular instantiation, this corresponds to the recovery of a signal with small infinity norm from a limited set of its Fourier coefficients. The key improvement over previous versions of PASS is the introduction of a rejection sampling technique from Lyubashevsky (2009) which assures that transcript distributions are completely decoupled from the keys that generate them. Although the scheme is not supported by a formal security reduction, we present extensive arguments for its security and derive concrete parameters based on the performance of state of the art lattice reduction and enumeration techniques.
published in / presented at
Applied Cryptography and Network Security – ACNS-2014.
presentations
2014-06-13 : ACNS [slides]
publication dates
2014-06-10 : Proceedings online.
2013-11-17 : Posted to IACR ePrint.
files
paper : 20131117-pass.pdf
notes
There is a reference implementation available. The system is patented, but licenses are automatically granted to free software projects; see NTRUOpenSourceProject for usage restrictions. The parameters for this system have not been reviewed since 2014. I suspect they need to be revised, but I've not done a new analysis.