Re: bit commitement ???

From: Nick Hopper (hopper_at_cs.cmu.edu)
Date: 07/08/03 

Date: Tue, 08 Jul 2003 10:55:33 -0400

Mark Wooding wrote:
> Which leaves me wondering: can you construct a one-way permutation from
> an arbitrary one-way function? I've doodled (and very briefly Googled)
> for a little while and not come up with a construction.

The two references you want are:

[1] Rudich, "Limits on the provable consequences of one-way functions."
PhD Thesis, UC Berkeley, 1988(?).
(http://www-2.cs.cmu.edu/~rudich/papers/thesis.ps)

and

[2] Kahn, Saks, and Smyth. "A dual version of Reimer's inequality and a
proof of Rudich's conjecture." Proc. 15th Annual IEEE Conference on
Computational Complexity, 2000.

Rudich proves that, given a certain "reasonable combinatorial conjecture,"
there is no strongly black-box construction of a one-way permutation from
a one-way function, and KSS prove Rudich's "reasonable combinatorial"
conjecture.

-Nick

Relevant Pages