International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Andreas Hülsing

Affiliation: TU Eindhoven, Netherlands

Publications

Year
Venue
Title
2019
CRYPTO
Quantum Indistinguishability of Random Sponges 📺
In this work we show that the sponge construction can be used to construct quantum-secure pseudorandom functions. As our main result we prove that random sponges are quantum indistinguishable from random functions. In this setting the adversary is given superposition access to the input-output behavior of the construction but not to the internal function. Our proofs hold under the assumption that the internal function is a random function or permutation. We then use this result to obtain a quantum-security version of a result by Andreeva, Daemen, Mennink, and Van Assche (FSE’15) which shows that a sponge that uses a secure PRP or PRF as internal function is a secure PRF. This result also proves that the recent attacks against CBC-MAC in the quantum-access model by Kaplan, Leurent, Leverrier, and Naya-Plasencia (Crypto’16) and Santoli, and Schaffner (QIC’16) can be prevented by introducing a state with a non-trivial inner part.The proof of our main result is derived by analyzing the joint distribution of any q input-output pairs. Our method analyzes the statistical behavior of the considered construction in great detail. The used techniques might prove useful in future analysis of different cryptographic primitives considering quantum adversaries. Using Zhandry’s PRF/PRP switching lemma we then obtain that quantum indistinguishability also holds if the internal block function is a random permutation.
2019
TCC
Tighter Proofs of CCA Security in the Quantum Random Oracle Model
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$$ ).
2019
ASIACRYPT
Decisional Second-Preimage Resistance: When Does SPR Imply PRE?
Daniel J. Bernstein Andreas Hülsing
There is a well-known gap between second-preimage resistance and preimage resistance for length-preserving hash functions. This paper introduces a simple concept that fills this gap. One consequence of this concept is that tight reductions can remove interactivity for multi-target length-preserving preimage problems, such as the problems that appear in analyzing hash-based signature systems. Previous reduction techniques applied to only a negligible fraction of all length-preserving hash functions, presumably excluding all off-the-shelf hash functions.
2018
PKC
SOFIA: $\mathcal {MQ}$MQ-Based Signatures in the QROM
We propose SOFIA, the first $$\mathcal {MQ}$$MQ-based signature scheme provably secure in the quantum-accessible random oracle model (QROM). Our construction relies on an extended version of Unruh’s transform for 5-pass identification schemes that we describe and prove secure both in the ROM and QROM.Based on a detailed security analysis, we provide concrete parameters for SOFIA that achieve 128-bit post-quantum security. The result is SOFIA-4-128 with parameters carefully optimized to minimize signature size and maximize performance. SOFIA-4-128 comes with an implementation targeting recent Intel processors with the AVX2 vector-instruction set; the implementation is fully protected against timing attacks.
2018
PKC
Rounded Gaussians
Andreas Hülsing Tanja Lange Kit Smeets
This paper suggests to use rounded Gaussians in place of discrete Gaussians in rejection-sampling-based lattice signature schemes like BLISS or Lyubashevsky’s signature scheme. We show that this distribution can efficiently be sampled from while additionally making it easy to sample in constant time, systematically avoiding recent timing-based side-channel attacks on lattice-based signatures.We show the effectiveness of the new sampler by applying it to BLISS, prove analogues of the security proofs for BLISS, and present an implementation that runs in constant time. Our implementation needs no precomputed tables and is twice as fast as the variable-time CDT sampler posted by the BLISS authors with precomputed tables.
2017
CHES
High-Speed Key Encapsulation from NTRU
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 307 914 cycles for the generation of a keypair, 48 646 for encapsulation, and 67 338 for decapsulation. It is, to the best of our knowledge, the first NTRU software with full protection against timing attacks.
2016
CRYPTO
2016
PKC
2016
PKC
2016
CHES
2016
ASIACRYPT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EUROCRYPT
2014
EPRINT

Program Committees

Asiacrypt 2019