International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 28 July 2015

PhD Database PhD Database
Name: Saqib A. Kakvi
Topic: On the Improvement of Security Proofs: Bridging the Gap between Theory and Practice
Category: foundations

Description:

This Thesis makes a humble attempt to bridge the well-known gap between the use of cryptography in practice and the theory, or lack thereof, behind it. With a concentration on digital signature scheme, we endeavour forth to fill in the gaps and, as far as possible, join the two edges of our chasm. To this end, we start from primitives that lie close to, if not at the very edge, of one side and try to push ourselves closer and closer to the other end of the spectrum. \r\n

\r\n

\r\nFor our first leap, we start from the side of practice. Our starting point is one of the most widely used and implemented signature schemes, RSA-FDH. Despite it\'s wide acceptance, RSA-FDH has a loose security proof and is not as theoretically secure as it is assumed to be in practice. Hence, we have found our first gap to bridge. We present a tight security proof for RSA-FDH which meets the security expectations that have until now, been assumed by practitioners.\r\n

\r\n

\r\nThe next step sees us starting from the side of theory looking towards practice. Despite our satisfactory results vis à vis RSA-FDH, they are in the Random Oracle Model, which is shaky grounds at best. With this in mind, we look towards building tightly secure signatures in the standard model. Such signatures were known previously, but from a limited number of assumptions. We examined these schemes closer and were able to show a generic framework that was implicitly used to construct all of them. Utilising this framework we are able to construct tightly secure signatures from a multitude of assumptions. Sadly, our signatures fall a few hand spans short and are just gripping the edge of practicality.\r\n

\r\n

\r\nThe final hop we make does not take us all the way from theory to practice, but some headway is gained. The last step could be seen not only as a bridge between theory and practice, but also between our first two results. Recent results have shown that using obfuscation, one can prove RSA-FD[...]

Expand

Additional news items may be found on the IACR news page.