Cryptology ePrint Archive: Report 2015/907

Cryptographic Assumptions: A Position Paper

Shafi Goldwasser and Yael Tauman Kalai

Abstract: The mission of theoretical cryptography is to define and construct provably secure cryptographic protocols and schemes. Without proofs of security, cryptographic constructs offer no guarantees whatsoever and no basis for evaluation and comparison. As most security proofs necessarily come in the form of a reduction between the security claim and an intractability assumption, such proofs are ultimately only as good as the assumptions they are based on. Thus, the complexity implications of every assumption we utilize should be of significant substance, and serve as the yard stick for the value of our proposals.

Lately, the field of cryptography has seen a sharp increase in the number of new assumptions that are often complex to define and difficult to interpret. At times, these assumptions are hard to untangle from the constructions which utilize them.

We believe that the lack of standards of what is accepted as a reasonable cryptographic assumption can be harmful to the credibility of our field. Therefore, there is a great need for measures according to which we classify and compare assumptions, as to which are safe and which are not. In this paper, we propose such a classification and review recently suggested assumptions in this light. This follows the footsteps of Naor (Crypto 2003).

Category / Keywords: foundations / assumptions

Date: received 16 Sep 2015

Contact author: yaelism at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150917:144137 (All versions of this report)

Short URL: ia.cr/2015/907

Discussion forum: Show discussion | Start new discussion