Paper 2015/907

Cryptographic Assumptions: A Position Paper

Shafi Goldwasser and Yael Tauman Kalai


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 {\em measures} according to which we classify and compare assumptions, as to which are {\it 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). Our governing principle is relying on hardness assumptions that are independent of the cryptographic constructions.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
yaelism @ gmail com
2015-10-27: revised
2015-09-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shafi Goldwasser and Yael Tauman Kalai},
      title = {Cryptographic Assumptions: A Position Paper},
      howpublished = {Cryptology ePrint Archive, Paper 2015/907},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.