Provable security

Provable security

In cryptography, a system has provable security if its security requirements can be stated formally in an adversarial model, as opposed to heuristically, with clear assumptions that the adversary has access to the system as well as enough computational resources. The proof of security (called a "reduction") is that these security requirements are met provided the assumptions about the adversary's access to the system are satisfied and some clearly stated assumptions about the hardness of certain computational tasks hold. An early example of such requirements and proof was given by Goldwasser and Micali for semantic security and the construction based on the quadratic residuosity problem.

The terminology of "provable security" has been criticized for a number of reasons. Part of the problem stems from the fact that it can be misleading to non-practitioners, since security is not being proved; only a reduction from security to some other unproven assumptions. Moreover there have been numerous attempts to define security, only later to discover that they fail to cover all the desirable characteristics. Some of the failures have been referred to as side channel attacks because they use information that falls outside the definition of the channel being protected. Oded Goldreich has also [http://eprint.iacr.org/2006/461 criticized] the terminology of "provable security".

There are several lines of research in provable security. One is to establish the `correct' definition of security for a given, intuitively understood task. Another is to suggest constructions and proofs based on general assumptions as much as possible, for instance the existence of a one-way function. A major open problem is to establish such proofs based on P ≠ NP, since the existence of one-way functions is not known to follow from the P ≠ NP conjecture.

Some proofs of the security are in given theoretical models such as the random oracle model, where real cryptographic hash functions are represented by an idealization. 'Exact security' or 'concrete security' is the name given to provable security reductions where one quantifies security by computing precise bounds on computational effort, rather than an asymptotic bound which is guaranteed to hold for 'sufficiently large' values of the security parameter.

Recently Koblitz and Menezes have criticized aspects of provable security in their papers [http://eprint.iacr.org/2004/152 Another Look at "Provable Security"] and [http://eprint.iacr.org/2006/229 Another Look at "Provable Security". II] . These views have been controversial in the community. A rebuttal, titled [http://www.wisdom.weizmann.ac.il/~oded/on-pmc.html On Post-Modern Cryptography] was posted by Oded Goldreich, who argues that the rigorous analysis methodology of provable security is the only one compatible with science.

Very recently AMS published a controversial article by Koblitz titled "The Uneasy Relationship Between Mathematics and Cryptography". Several rebuttals have been written and are available [http://www.wisdom.weizmann.ac.il/~oded/on-pmc.html here] and [http://in-theory.blogspot.com/2007_08_26_archive.html here] .


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Security testing — Security Testing: (The) Process to determine that an IS (Information System) protects data and maintains functionality as intended.The six basic security concepts that need to be covered by security testing are: confidentiality, integrity,… …   Wikipedia

  • Concrete security — In cryptography, concrete security or exact security is a practice oriented approach that aims to give more precise estimates of the computational complexities of adversarial tasks than polynomial equivalence would allow. Traditionally, provable… …   Wikipedia

  • Council of Registered Ethical Security Testers Certified Consultant — The CREST Certified Consultant certification is a professional certification provided by the [http://www.crest approved.org Council of Registered Ethical Security Testers (CREST)] .OverviewCREST Certified Consultants are highly skilled… …   Wikipedia

  • Cryptography — Secret code redirects here. For the Aya Kamiki album, see Secret Code. Symmetric key cryptography, where the same key is used both for encryption and decryption …   Wikipedia

  • CRYPTREC — is the Cryptography Research and Evaluation Committee set up by the Japanese Government to evaluate and recommend cryptographic techniques for government and industrial use. It is comparable in many respects to the European Union s NESSIE project …   Wikipedia

  • Key Wrap — constructions are a class of symmetric encryption algorithms designed to encapsulate (encrypt) cryptographic key material. The Key Wrap algorithms are intended for applications such as (a) protecting keys while in untrusted storage, or (b)… …   Wikipedia

  • Mihir Bellare — is a cryptographer and professor at the University of California, San Diego. He has published several seminal papers in the field of cryptography (notably in the area of provable security), many coauthored with Phillip Rogaway. Bellare has… …   Wikipedia

  • Public key certificate — Diagram of an example usage of digital certificate In cryptography, a public key certificate (also known as a digital certificate or identity certificate) is an electronic document which uses a digital signature to bind a public key with an… …   Wikipedia

  • QUAD (cipher) — Infobox block cipher name = QUAD caption = designers = Côme Berbain, Henri Gilbert and Jacques Patarin publish date = May 28, 2006 (at Eurocrypt) derived from = derived to = related to = certification = key size = 80 bits structure = multivariate …   Wikipedia

  • Topics in cryptography — This article is intended to be an analytic glossary , or alternatively, an organized collection of annotated pointers.Classical ciphers*Autokey cipher *Permutation cipher*Polyalphabetic substitution **Vigenère cipher*Polygraphic substitution… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”