CWI Cryptology Group

Abstract: We review some recent results in explicit constructions of extractors from independent sources, in particular a recent 2-source construction of Bourgain. Unlike "normal" exractors, extractors for independent sources do not need uniform randomness, but only (independent) sources of sufficient min-entropy. Explicit contstructions of such extractors were made possible by recent results in additive combinatorics due to Bourgain, Katz and Tao.

Abstract: Typically, secure computation is based on Shamir's scheme, which can be viewed as a cryptographic twist on the Reed-Solomon error correcting code. In this work we further the connections between secure computation and error correcting codes. For instance, We demonstrate that threshold secure computation in the secure channels model can be based on arbitrary codes.
For a network of size n, we then show a reduction in communication for secure computation amounting to a multiplicative logarithmic factor (in n) compared to classical methods for small, e.g., constant size fields, while tolerating t < (1/2-e)n players to be corrupted, where $e>0$ can be arbitrarily small. For large networks this implies considerable savings in communication.
Our results hold in the broadcast/negligible error model of Rabin and Ben-Or, and complement results from CRYPTO 2006 for the zero-error model of Ben-Or, Goldwasser and Wigderson (BGW).
We also present a new method for constructing high information rate ramp schemes based on arbitrary codes.

Abstract: We consider the problem of secure identification: given that a user U and a server S share a password w, how can U convince S that he indeed knows w, in such a way that (1) a dishonest U who does not know w cannot convince S, and (2) a dishonest S does not learn any information on w (beyond what is unavoidable). Very concretely, how can you convince an ATM that you know your PIN without actually typing it into the ATM?
In this talk, I describe a solution to this problem in the bounded-quantum-storage model: the scheme involves the communication of qubits (e.g. polarized photons) and is secure under the sole assumption that a dishonest party can store only a limited number of qubits. No other restriction is posed upon the attacker, in particular it may have unbounded computing power. The honest users on the other hand only need to produce, transmit and measure qubits in order to faithfully execute the scheme, no quantum memory is needed. This makes the scheme implementable with today's technology.

Abstract: We present two universally composable and practical protocols by which a dealer can, verifiably and non-interactively, secret-share an integer among a set of players. Moreover, at small extra cost and using a distributed verifier proof, it can be shown in zero-knowledge that three shared integers $a,b,c$ satisfy $ab =c$. This implies by known reductions non-interactive zero-knowledge proofs that a shared integer is in a given interval, or that one secret integer is larger than another. Such primitives are useful, e.g., for supplying inputs to a multiparty computation protocol, such as an auction or an election. The protocols use various set-up assumptions, but do not require the random oracle model.