Provable Security Proofs and their Interpretation in the Real World

This paper analyses provable security proofs, using the EDL signa-ture scheme as its case study, and interprets their benefits and draw-backs when applied to the real world. Provable security has been an area of contention. Some, such as Koblitz and Menezes, give little credit to the potential extra security provided and argue that it is a distracting goal. However, others be-lieve that an algorithm with a security proof is superior to one without it, and are prepared to accept the impact to performance that their use might involve. Goldreich has been notable for his defence of the secu-rity proof, and for his opposition to the view of Koblitz and Menezes. This paper is designed to help the reader make their own decisions on security proofs. We achieve this by giving an introduction to the typ-ical security model used, then give a description of the EDL signature scheme and its tight reduction to the CDH problem in the Rando