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 |
| 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 |
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.