Colloquium Speaker

Speaker:Rene Peralta
University of Wisconsin, Milwaukee
Topic:"Bit commitment, cryptographic proofs, and conjunction-limited circuits."
Date:Tuesday, May 4, 1999
Time:9:30 AM
Place:Gould-Simpson, Room 701

Refreshments will be served in the 7th-floor lobby of Gould-Simpson at 9:15 AM


We explain the cryptographic notion of "bit-commitment". We explain how this primitive can be used to prove knowledge of a secret bit-string S without actually disclosing S. The technique involves the construction of a Boolean circuit which is satisfiable only by S. The circuit is constructed over the base (AND, XOR, NOT). The proof that S is known turns out to be of length linear in the number of AND gates of the circuit. Hence the question of how many conjunctions are necessary for computing different classes of Boolean functions is of interest in cryptographic applications (e.g. electronic commerce, computer security). We discuss recent results on conjunction-limited circuits.

The talk will be accessible to a general audience.