Computational indistinguishability
- Computational indistinguishability
-
In computational complexity, if 
and 
are two distribution ensembles indexed by a security parameter n (which usually refers to the length of the input), then we say they are computationally indistinguishable if for any non-uniform probabilistic polynomial time algorithm A, the following quantity is a negligible function in n:
![\delta(n) = \left| \Pr_{x \gets D_n}[ A(x) = 1] - \Pr_{x \gets E_n}[ A(x) = 1] \right|.](a/9ea8766080a6ffd516258bc806af3eaa.png)
In other words, for every efficient algorithm A, its behavior does not significantly change when given samples according to Dn or En.
This article incorporates material from computationally indistinguishable on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
References
- Donald Beaver and Silvio Micali and Phillip Rogaway, The Round Complexity of Secure Protocols (Extended Abstract), 1990, pp. 503—513
- S. Goldwasser and S. Micali. Probabilistic Encryption. JCSS, 28(2):270–299, 1984
- O. Goldreich. Foundations of Cryptography: Volume 2 – Basic Applications. Cambridge University Press, 2004.
- Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007
External links
Yehuda Lindell. Introduction to Cryptography (lecture notes) [1]
Wikimedia Foundation.
2010.
Look at other dictionaries:
Computational — may refer to: Computer Computational algebra Computational Aeroacoustics Computational and Information Systems Laboratory Computational and Systems Neuroscience Computational archaeology Computational auditory scene analysis Computational biology … Wikipedia
Ciphertext indistinguishability — is a property of many encryption schemes. Intuitively, if a cryptosystem possesses the property of indistinguishability, then an adversary will be unable to distinguish pairs of ciphertexts based on the message they encrypt. The property of… … Wikipedia
List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… … Wikipedia
Symbol grounding — The Symbol Grounding Problem is related to the problem of how words (symbols) get their meanings, and hence to the problem of what meaning itself really is. The problem of meaning is in turn related to the problem of consciousness, or how it is… … Wikipedia
Computing Machinery and Intelligence — Computing Machinery and Intelligence, written by Alan Turing and published in 1950 in Mind, is a seminal paper on the topic of artificial intelligence in which the concept of what is now known as the Turing test was introduced to a wide audience … Wikipedia
Zero-knowledge proof — In cryptography, a zero knowledge proof or zero knowledge protocol is an interactive method for one party to prove to another that a (usually mathematical) statement is true, without revealing anything other than the veracity of the statement.A… … Wikipedia
Cramer-Shoup cryptosystem — The Cramer Shoup system is an asymmetric key encryption algorithm, and was the first efficient scheme proven to be secure against adaptive chosen ciphertext attack using standard cryptographic assumptions. Its security is based on the… … Wikipedia
Cramer–Shoup cryptosystem — The Cramer–Shoup system is an asymmetric key encryption algorithm, and was the first efficient scheme proven to be secure against adaptive chosen ciphertext attack using standard cryptographic assumptions. Its security is based on the… … Wikipedia
Electron configuration — Electron atomic and molecular orbitals Simp … Wikipedia
