CWI Cryptology Group

Abstract: The "P not equal NP" conjecture bears bad news to algorithmic design, and its extension to average-case hardness bears bad news to the actual solveability of real life problems. But there is a bright side to these bad news -- computational hardness can be used as a basis of cryptography. Much of this relation comes about through the theory of pseudorandomness, which refers to objects that look similar (i.e., are computationally indistinguishable) although they are fundamentally different (i.e., are statistically (or information-theoretically) distinguishable).
The talk will also touch on notions such as one-way functions, pseudorandom functions, private-key cryptosystems, zero-knowledge proofs, and general secure multi-party computation.

Abstract: Public key cryptography relies on hard computational problems in mathematics. The discrete logarithm problem in a finite group (namely, given g,h in G to compute x, if it exists, such that h=g^x) is one such computational problem, and it has proved to be extremely versatile for the development of cryptographic systems. Elliptic curves over finite fields provide groups for which the discrete logarithm problem seems to be essentially as hard as possible. This talk will give a survey of elliptic curves in public key cryptography. We will also discuss cryptologic applications of bilinear pairings on elliptic curves, and briefly describe recent research on efficient implementation of pairings.

Abstract: Induction is the process of making predictions of unobserved events from knowledge of observed ones. Inductive reasoning is of fundamental importance in natural sciences and, remarkably, also in information theory and cryptography. Consider, for example, an entanglement-based quantum key distribution (QKD) scheme, where a secret key is distilled from (a sufficiently large set of) pairs of entangled particles. The security of the final key necessarily depends on the strength of this entanglement, which therefore has to be determined by measurements. However, because measuring a particle pair inevitably destroys its entanglement, any of the pairs can either be measured or be used to generate the final key --- but not both. And this is where inductive reasoning comes in. Namely, from the fact that the observed particle pairs are entangled one wants to infer that the unobserved pairs are entangled, too.
In this talk, I will discuss the mathematical foundations of inductive reasoning in a quantum information context and show its applications to cryptography.

Abstract: In this talk, I will survey known results on the Private Information Retrieval (PIR) problem. In this problem, a user wishes to retrieve a value x_i from an n-bit string x (modeling a database) in a way that keeps the index i in [n] (modeling the user's query) secret and while minimizing the communication complexity (between the user and the database). In its basic form described above, communication complexity of essentially n bits is necessary and trivially sufficient. The problem becomes more interesting if k identical (and non-communicating) copies of x are available. I will present several approaches to the problem that yield non-trivial solutions, emphasizing the combinatorial and algebraic techniques behind those solutions. The above problem is sometimes referred to as information-theoretic PIR. Time permitting, I will also discuss the computational version of the problem.