CWI Cryptology Group

Abstract: Computational security proofs in cryptography, without unproven intractability assumptions, exist today only if one restricts the computational model. For example, one can prove a lower bound on the complexity of computing discrete logarithms in a cyclic group if one considers only generic algorithms which can not exploit the properties of the representation of the group elements. A simple abstract model of computation is proposed which allows to capture such reasonable restrictions on the power of algorithms. Several instantiations of the model and the corresponding lower bounds are discussed, including different flavors of generic algorithms in groups.

Abstract: We give an exponential separation between one-way quantum and classical communication protocols for a partial Boolean function, which is a variant of the Boolean Hidden Matching Problem of Bar-Yossef et al. Earlier such an exponential separation was known only for a relational version of the Hidden Matching Problem. Our proof uses the Fourier coefficients inequality of Kahn, Kalai, and Linial. We also give a number of applications of this separation. In particular, in the setting of privacy amplification, we show that there exist strong extractors that yield a classically secure key, but that are insecure against a quantum adversary; and in the bounded-storage model of cryptography we give an example of a scheme that is secure against adversaries with a certain amount of classical storage, but that is completely insecure against adversaries with a similar (or even much smaller) amount of *quantum* storage. This is joint work with Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, in STOC 2007.

Abstract: Randomness extraction is of fundamental importance for information-theoretic cryptography. It allows to transform a raw key about which an attacker has some limited knowledge into a fully secure random key, on which the attacker has essentially no information. We show a new randomness-extraction technique which works also in case where the attacker has quantum information on the raw key. Randomness extraction is done by xor'ing a so-called δ-biased mask to the raw key. Up to date, only very few techniques are known to work against a quantum attacker, much in contrast to the classical (non-quantum) setting, which is much better understood and for which a vast amount of different techniques for randomness extraction are known. We show an application of the new technique to private error-correction.
This is joint work with Christian Schaffner.