CWI Cryptology Group

Abstract: Most of the known results about the optimization of secret sharing schemes for general access structures have been obtained by applying two techniques:
1. Lower bounds on the complexity are obtained by linear constructions.
2. Upper bounds are found by using basic properties of the Shannon entropy. Since these properties are exactly the axioms defining polymatroids, this is actually a combinatorial technique.
Nevertheless, it can be proved that it is impossible to solve the problem by using only these techniques. In this talk, we discuss several old and new results and techniques that make it possible to go beyond the results attained by the previous methods.

Abstract: We consider how to build an efficient compression function from a small number of random, non-compressing primitives (fixed-key blockciphers were our original motivation). Our main goal is to achieve a level of collision resistance as close as possible to the optimal birthday bound. We present a 2n-to-n bit compression function based on three independent n-to-n bit random functions, each called only once. We show that if the three random functions are treated as black box (i.e., modelled as random oracles), the collision resistance of our scheme is \Theta(2^{n/2}/n^c) for c\approx 1. We also give a heuristic, backed by experimental results, suggesting that the security loss is at most four bits for block sizes up to 256 bits.
We believe this is the best result to date on the matter of building a collision resistant compression function from non-compressing functions. It also relates to an open question from Black et al. (Eurocrypt'05), who showed that compression functions that invoke a single non-compressing random function cannot suffice.
Joint work with Tom Shrimpton.

Abstract: We introduce a new primitive called Intrusion-Resilient Secret Sharing (IRSS), whose security proof exploits the fact that there exist functions which can be efficiently computed interactively using low communication complexity in $k$, but not in $k-1$ rounds.
IRSS is a means of sharing a secret $M$ amongst a set of players which comes with a very strong security guarantee. The shares in an IRSS are made artificially large so that it is hard to retrieve them completely, and the reconstruction procedure is interactive requiring the players to exchange $k$ short messages. The adversaries considered can attack the scheme in rounds, where in each round the adversary can choose some player to corrupt and some function, and he retrieves the output of that function applied to the share of the corrupted player. This model captures for example computers connected to a network which can occasionally by infected by malicious software like viruses, who can compute any function on the infected machine, but cannot send out (undetected) a huge amount of data.
Using methods from the bounded-retrieval model, we construct an IRSS scheme which is secure against any computationally unbounded adversary as long as the total amount of information retrieved by the adversary is somewhat less than the length of the shares and the adversary makes at most $k-1$ corruption rounds (as described above, where $k$ rounds are necessary for reconstruction).
Joint work with Stefan Dziembowski, FOCS'07 to appear

Abstract: We put forward a new paradigm for building hybrid encryption schemes from constrained chosen-ciphertext secure (CCCA) key-encapsulation mechanisms (KEMs) plus authenticated symmetric encryption. Constrained chosen-ciphertext security is a new security notion for KEMs that we propose. It has less demanding security requirements than standard CCCA security (since it requires the adversary to have a certain plaintext-knowledge when making a decapsulation query) yet we can prove that it is CCCA sufficient for secure hybrid encryption.
Our notion is not only useful to express the Kurosawa-Desmedt public-key encryption scheme and its generalizations to hash-proof systems in an abstract KEM/DEM security framework. It also has a very constructive appeal, which we demonstrate with a new encryption scheme whose security relies on a class of intractability assumptions that we show (in the generic group model) strictly weaker than the Decision Diffie-Hellman (DDH) assumption. This appears to be the first practical public-key encryption scheme in the literature from an algebraic assumption strictly weaker than DDH.
Joint work with Dennis Hofheinz (CRYPTO '07)