Provable security
Encyclopedia
In cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, a system has provable security if its security requirements can be stated formally in an adversarial
Adversary (cryptography)
In cryptography, an adversary is a malicious entity whose aim is to prevent the users of the cryptosystem from achieving their goal...

 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
Shafi Goldwasser
Shafrira Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel.-Biography:...

 and Micali
Silvio Micali
Silvio Micali is an Italian-born computer scientist at MIT Computer Science and Artificial Intelligence Laboratory and a professor of computer science in MIT's Department of Electrical Engineering and Computer Science since 1983. His research centers on the theory of cryptography and information...

 for semantic security
Semantic security
Semantic security is a widely used definition for security in an asymmetric key encryption algorithm. For a cryptosystem to be semantically secure, it must be infeasible for a computationally bounded adversary to derive significant information about a message when given only its ciphertext and...

 and the construction based on the quadratic residuosity problem
Quadratic residuosity problem
The quadratic residuosity problem in computational number theory is the question of distinguishing by calculating the quadratic residues modulo N, where N is a composite number...

.

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
One-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...

. 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
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....

' 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
Security parameter
In cryptography, the security parameter is a variable that measures the input size of the problem. Both the resource requirements of the cryptographic algorithm or protocol as well as the adversary's probability of breaking security are expressed in terms of the security parameter.The security...

.

Koblitz
Neal Koblitz
Neal I. Koblitz is a Professor of Mathematics at the University of Washington in the Department of Mathematics. He is also an adjunct professor with the Centre for Applied Cryptographic Research at the University of Waterloo. He is the creator of hyperelliptic curve cryptography and the...

 and Menezes
Alfred Menezes
Alfred Menezes is co-author of several books on cryptography, most notably the Handbook of Applied Cryptography.Menezes is a professor in the Department of Combinatorics & Optimization at the University of Waterloo. He is also the Managing Director of the Centre for Applied Cryptographic...

 have criticized aspects of provable security research in their papers Another Look at "Provable Security" and Another Look at "Provable Security". II. These views have been controversial in the community. A rebuttal, titled On Post-Modern Cryptography was posted by Oded Goldreich
Oded Goldreich
Oded Goldreich is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. His research interests lie within the theory of computation...

, who argues that the rigorous analysis methodology of provable security is the only one compatible with science.

In 2007 Koblitz
Neal Koblitz
Neal I. Koblitz is a Professor of Mathematics at the University of Washington in the Department of Mathematics. He is also an adjunct professor with the Centre for Applied Cryptographic Research at the University of Waterloo. He is the creator of hyperelliptic curve cryptography and the...

 published "The Uneasy Relationship Between Mathematics and Cryptography" in the Notices of the American Mathematical Society
Notices of the American Mathematical Society
Notices of the American Mathematical Society is a membership magazine of the American Mathematical Society, published monthly except for the combined June/July issue. It is the world's most widely read mathematics magazine, sent to the approximately 30,000 AMS members worldwide...

. Several rebuttals have been written by Oded Goldreich
Oded Goldreich
Oded Goldreich is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. His research interests lie within the theory of computation...

, Avi Wigderson
Avi Wigderson
Avi Wigderson is an Israeli mathematician and computer scientist, a professor of mathematics at the Institute for Advanced Study in Princeton. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural...

 and other researchers in the field.http://in-theory.blogspot.com/2007_08_26_archive.html. Ivan Damgård
Ivan Damgård
Ivan Bjerre Damgård is a Danish cryptographer and currently a professor at the Department of Computer Science , Aarhus University, Denmark....

 later wrote position paper
Position paper
A position paper is an essay that presents an opinion about an issue, typically that of the author or another specified entity; such as a political party. Position papers are published in academia, in politics, in law and other domains....

 at ICALP 2007 on the technical issues, and it was recommended by Scott Aaronson
Scott Aaronson
Scott Joel Aaronson is a theoretical computer scientist and faculty member in the Electrical Engineering and Computer Science department at the Massachusetts Institute of Technology.-Education:...

as a good in-depth analysis.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK