CWI Cryptology Group

Abstract: We construct efficient and natural encryption schemes that remain secure (in the standard model) even when used to encrypt messages that may depend upon their secret keys. Our schemes are based on well-studied ``noisy learning'' problems. In particular, we design
1) A symmetric-key cryptosystem based on the ``learning parity with noise'' (LPN) problem, and
2) A public-key cryptosystem based on the ``learning with errors'' (LWE) problem, a generalization of LPN that is at least as hard as certain worst-case lattice problems (Regev, STOC 2005; Peikert, STOC 2009).
Remarkably, our constructions are close (but non-trivial) relatives of prior schemes based on the same assumptions --- which were proved secure only in the usual key-independent sense --- and are nearly as efficient. For example, our most efficient public-key scheme encrypts and decrypts in amortized O-tilde(n) time per message bit, and has only a constant ciphertext expansion factor. This stands in contrast to the only other known standard-model schemes with provable security for key-dependent messages (Boneh et a.l, CRYPTO 2008), which incur a significant extra cost over other semantically secure schemes based on the same assumption. Our constructions and security proofs are simple and quite natural, and use new techniques that may be of independent interest.
This is joint work with Chris Peikert and Amit Sahai.

Abstract: We revisit the rate-1 blockcipher based hash functions as first studied by Preneel, Govaerts and Vandewalle (Crypto'93) and later extensively analysed by Black, Rogaway and Shrimpton (Crypto'02). We analyse a further generalization where any pre- and postprocessing is considered. This leads to a clearer understanding of the current classification of rate-1 blockcipher based schemes as introduced by Preneel et al. and refined by Black et al. In addition, we also gain insight in chopped, overloaded and supercharged compression functions. In the latter category we propose two compression functions based on a single call to a blockcipher whose collision resistance exceeds the birthday bound on the cipher's blocklength.

Abstract: The traditional security notion for digital signature schemes requires it to be hard for an adversary to forge a valid signature, even after having obtained signatures for messages of its choice. This security notion has often proved to be insufficient in practice where an adversary can use ``side-channel attacks'' to obtain additional information about the secret state that is accessed to compute the signatures.
We propose the security notion of "leakage-resilient signatures", where the adversary may obtain arbitrary information about the secret state, as long as the amount of this information is bounded in each signature query. This notion naturally captures security against all possible side-channel attacks where the adversary only obtains a bounded amount of information during each measurement. We also provide the first instantiation of a leakage-resilient signature scheme. Our construction is a generic tree-based transformation from any standard signature scheme and it is provably leakage-resilient given that the underlying standard signature scheme is secure in the traditional sense.
This is joint work with Eike Kiltz and Krzysztof Pietrzak