Re: Secure key exchange with hashing and the birthday paradox

Will Dickson wrote:
Interesting. Does this mean that you couldn't, say, do a DH key exchange,
but use the black-box signature scheme to sign the exchanged messages
in order to prevent an MITM attack?

Sure, you can do that. However, for signed DH to be secure, you have
to assume that the Diffie-Hellman problem is hard. Thus, this is not
a generically secure scheme (i.e., one that is secure, with no added
assumptions, other than that the one-way function/permutation is indeed
one-way). The question here is: Can you build a key exchange that is
secure, where the only assumption used is the one-wayness of the one-way
permutation used in the scheme? For signature schemes, the answer is yes;
for key exchange, the answer is no.

Let me try putting it another way. As Paul Rubin wrote, there is a
scheme S[f] with the following properties:
(i) S is the template of a signature scheme. It is parametrized
by a function f. When you plug in some function f, you get a
signature scheme, denoted by S[f]. In other words, you can think
of S as a mapping from functions to signature schemes.
(ii) S[f] uses f only in a 'black-box' manner. The only thing that
S[f] does with f is evaluate f on some points; S[f] does not look
at the code or description of f, and S[f] does not depend on the
internals of f in any way. In other words, the only way that S[f]
uses f is that, at various points in the computation of a signature,
S[f] computes some value x and needs a way to get the value f(x).
Other than that, S[f] does not depend on f in any way. Another way
to put this is that f is used only as a subroutine that can be
called (but whose implementation cannot be inspected).
(iii) S[f] is generically secure. If f is any one-way permutation,
then S[f] is guaranteed to be secure. Put another way, there is
a security theorem of the following form:
Theorem. For all functions f, if f is a one-way permutation,
then S[f] is a secure signature scheme.
Note that the security of S[f] does not rely on any unproven
assumptions (e.g., that factoring is hard; that DDH is hard),
other than the assumption that f is one-way. Also S[f] can be
handed *any* one-way permutation f, and must work no matter what
kind of one-way permutation it is given.
At this point, you might wonder whether it is possible to do the same
sort of thing for key-exchange protocols. What Impagliazzo and Rudich
showed is that, in fact, you cannot. There is no corresponding scheme
KE such that: (i) KE[f] is a key-exchange protocol; (ii) KE[f] uses f
only in a 'black-box' manner; (iii) KE[f] is generically secure: one can
prove that if f is any one-way permutation, then KE[f] is a secure
key-exchange protocol (with no further assumptions needed).

Signed DH fails the third condition above: its security relies on an
extra unproven hardness assumption, e.g., that the Diffie-Hellman problem
is hard.