Talk:Provable security

Other models of security

I think its worth linking to other methods of modeling security or simply definining them all on a single pageBah23 17:20, 12 March 2007 (UTC)

Naor's version

Moni Naor emailed me an edited version of this article. I will be updating it bit by bit. Arvindn 01:11, 2 May 2007 (UTC)

In cryptography, a system is said to have provable security if its security requirements are stated formally in an adversarial model, as opposed to heuristically, with clear assumptions on the access to the system the adversary has as well as its computational resources. In addition assumptions on the computational hardness of some problems are made. The proof of security (called a "reduction") is that these security requirements are met provided the assumptions of the adversary's access to the system is as assumed and the computational hardness assumptions hold. An early example of such requirements and proof was given by Goldwasser and [Silvio Micali|Micali] for semantic security and the construction based on the Quadratic Residuosity Problem.

There are several lines of research in provable security. One is to establish the `correct' definition of security. Another is to suggests constructions and proofs based on as general assumptions as possible, for instance the existence of a one-way function. A major open problem is to establish such proofs based on P ≠ NP.

Some proofs of the security are in given theoretical models such as the [[Random oracle model|Random Oracle], 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 Another Look at "Provable Security" and Another Look at "Provable Security". II. These views are not shared by the majority of cryptographers. A rebuttal, titled 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.

Feel free to incorporate any of the following Bah23 14:05, 2 May 2007 (UTC)

Two security models are defined, namely \emph{unconditional security}\footnote{Unconditional security may also be termed \emph{information theoretic security}.} and \emph{computational security}\footnote{Computational security may also be termed \emph{complexity theoretic security}.}. The distinction between these classifications is based upon the computational power available to the attacker. The unconditional security model assumes the attacker has unbound computational power, whereas the computational security model assumes some upper bound on the attacker's resources. A scheme is believed to be secure if the attacker is unable to violate security properties with the allocated resources.

The notion of unconditional security was introduced by Shannon~\cite{Shannon49} with regards to the secrecy of symmetric encryption. An encryption scheme is said to be \emph{perfect} (or unconditionally secure) if an attacker gains no information about the plaintext after observing the ciphertext, other than what was already known. However, Shannon showed that for unconditional security to be achieved the key must be as long as the plaintext. This requirement makes such a scheme impractical for general use.

Little progress was made in the field until the introduction of public key cryptography~\cite{DH76}. The new principle demonstrated that cryptographic techniques could be secure without achieving unconditional security. Although it is theoretically possible to break such cryptographic methods, in practice such attacks are intractable\footnote{Intractable is widely accepted to mean those problems which are solvable in exponential time. By comparison tractable problems have solutions in polynomial time. Attacks in the computational security model should be realisable on a deterministic Turing machine in polynomial time.}. For example breaking symmetric cryptography with a key of length 512 bits is theoretically feasible, however in practice it will require a time frame greater than the age of the universe. The observation of computational infeasibility resulted in the introduction of the weaker, computational security model.

%\footnotetext{The first public key cryptographic algorithm was subsequently introduced by Rivest, Shamir \& Adleman~\cite{RSA}.}

The computational security model can be further divided into two sub-classes: \emph{reductionist} and \emph{practical}. Reductionist security uses \emph{reduction} to show that the difficulty of defeating a cryptographic scheme is \emph{``as difficult as solving a well-known and supposedly difficult (typically number-theoretic) problem, such as integer factorization or the computation of discrete logarithms"}~\cite{HAC}. The reductionist security model is not used to `prove the security of a cryptographic method.' Instead it shows that breaking scheme is equivalent to a difficult problem. Since solving the underlying problem is believed to be hard, the scheme is thought to be secure. Unfortunately it is not know whether the underlying problem is indeed difficult, hence `prove' in this sense means subject to some assumption. Without resolving the P versus NP problem (making a huge advancement in complexity theory research), we can never make any definite mathematical statements about the security of the system. The best we can do is provide a reduction which shows the difficulty of breaking the cryptosystem is as difficult as solving a well-known mathematical problem. Despite this drawback its the most universally accepted method within the cryptographic community. Two formalisms for reductionist security are defined: \emph{complexity-theoretic} and \emph{concrete} security. The complexity-theoretic security model provides a reduction and concludes that the crypto-method is secure since the hard problem is believed to be secure. This definition fails to capture how tightly related the two schemes are and thus does not aid the selection of suitable security parameters required for real world security. Concrete security analysis\footnotemark addresses this issue by examining the reduction to establish suitable sizes for security parameters. The approach requires some knowledge about the parameter sizes which are required to ensure the security of the underlying difficult problem. The second sub-class of computational security is practical security. This technique models the computational resources required for the best known attack against the system. If the required computation is beyond that of the attacker, the scheme is assumed to be secure. Unlike reductionist security no proof of equivalence to a hard problem is known.

\footnotetext{Concrete security is also termed \emph{provable security}. This term will be avoided to prevent confusion with the field of provable security which incorporates all schemes which allow the proof of security.}

References Bah23 09:53, 8 May 2007 (UTC)

@article{DH76,

author = "Whitfield Diffie and Martin E Hellman",

title = "New directions in cryptography",

journal = "Information Theory, IEEE Transactions on",

year = "1976",

volume = "22",

issue = "6",

pages = "644--654",

publisher="IEEE"

}

@article{Shannon49,

author = "Claude E Shannon",

title = "Communication theory of secrecy systems",

journal = "Bell System Technical Journal",

year = "1949",

volume = "28",

pages = "656--715",

publisher="Bell"

}

@book{HAC,

author = {Alfred J Menezes and Paul C van Oorschot and Scott A Vanstone},

title = {Handbook of Applied Cryptography},

year = {2001},

publisher={CRC Press},

edition = {5},

url = {http://www.cacr.math.uwaterloo.ca/hac/}

}

Thanks.. where is this from? Arvindn 21:18, 6 May 2007 (UTC)

My personal notes on the subject which may or may not appear online in a more complete form other the next couple of months. I am happy for any of the above to be used directly without reference. Bah23 09:42, 8 May 2007 (UTC)