SAC

Alfred Menezes talk (one of two invited talks at SAC this year) focused on "tightness" in security proofs. Loosely speaking when one proves the security of a protocol one tries to show that breaking the security of the protocol e.g forging a signature, is as hard as breaking some related problem in number theory which is believed to be hard such as the Diffie-Hellman problem. In practice this reduction can potentially increase the advantage of an adversary trying to break the protocol.

More precisely suppose A is an attacker which in time T succeeds in breaking the desired security of the scheme with probability e. Then if R is an algorithm attacking the underlying hard problem a breaking it in time T' with probability e', but which has access to A as an oracle then the tightness gap is T * e' / T' * e. If T is approximately equal to T (and e is approx. e') the reduction is tight. A particularly striking example given by Menezes, was the reduction obtained in the proof of security (in the random oracle model) of full domain hash RSA signatures. Here, if an adversary can forge an RSA signature in time T with success probability e, then one can solve the RSA problem in time T with success probability e/q where q is the number of queries made by the adversary to the random oracle. Note the tightness gap is q here. For 80 bit security we require T/e <= 2^80 thus if an attacker made say 2^60 queries to the random oracle, because of the loss of tightness in the reduction we require T'/e' <= 2^140 which requires a modulus of 4000 bits, far larger than is ever used in practice.

Even this simple example illustrates extra terms appearing in reductions can make the proofs redundant in practice. See here for further details: http://anotherlook.ca/