In
computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
and
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, two families of distributions are computationally indistinguishable if no efficient algorithm can tell the difference between them except with negligible probability.
Formal definition
Let
and
be two
distribution ensemble In cryptography, a distribution ensemble or probability ensemble is a family of distributions or random variables X = \_ where I is a (countable) index set, and each X_i is a random variable, or probability distribution. Often I=\N and it is requir ...
s indexed by a
security parameter
In cryptography, a security parameter is a way of measuring of how "hard" it is for an adversary to break a cryptographic scheme. There are two main types of security parameter: ''computational'' and ''statistical'', often denoted by \kappa and \ ...
''n'' (which usually refers to the length of the input); we say they are computationally indistinguishable if for any
non-uniform probabilistic
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
''A'', the following quantity is a
negligible function In mathematics, a negligible function is a function \mu:\mathbb\to\mathbb such that for every positive integer ''c'' there exists an integer ''N'c'' such that for all ''x'' > ''N'c'',
:, \mu(x), 0 such that for all ''x'' ...
in ''n'':
:
denoted
.
Lecture 4 - Computational Indistinguishability, Pseudorandom Generators
/ref> In other words, every efficient algorithm ''As behavior does not significantly change when given samples according to ''D''''n'' or ''E''''n'' in the limit as . Another interpretation of computational indistinguishability, is that polynomial-time algorithms actively trying to distinguish between the two ensembles cannot do so: that any such algorithm will only perform negligibly better than if one were to just guess.
Related notions
Implicit in the definition is the condition that the algorithm, , must decide based on a single sample from one of the distributions. One might conceive of a situation in which the algorithm trying to distinguish between two distributions, could access as many samples as it needed. Hence two ensembles that cannot be distinguished by polynomial-time algorithms looking at multiple samples are deemed indistinguishable by polynomial-time sampling.[ Goldreich, O. (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press.] If the polynomial-time algorithm can generate samples in polynomial time, or has access to a random oracle
In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time th ...
that generates samples for it, then indistinguishability by polynomial-time sampling is equivalent to computational indistinguishability.
References
External links
* Yehuda Lindell
Yehuda Lindell (born 24 February 1971) is a professor in the Department of Computer Science at Bar-Ilan University where he conducts research on cryptography with a focus on the theory of secure computation and its application in practice. Lindell ...
Introduction to Cryptography
* Donald Beaver and Silvio Micali
Silvio Micali (born October 13, 1954) is an Italian computer scientist, professor at the Massachusetts Institute of Technology and the founder of Algorand. Micali's research centers on cryptography and information security.
In 2012, he received ...
and Phillip Rogaway
Phillip Rogaway is a professor of computer science at the University of California, Davis. He graduated from Beverly Hills High School, and later earned a BA in computer science from UC Berkeley and completed his PhD in cryptography at MIT, in ...
, The Round Complexity of Secure Protocols (Extended Abstract), 1990, pp. 503–513
* Shafi Goldwasser
en, Shafrira Goldwasser
, name = Shafi Goldwasser
, image = Shafi Goldwasser.JPG
, caption = Shafi Goldwasser in 2010
, birth_place = New York City, New York, U.S.
, birth_date =
, death_date ...
and Silvio Micali
Silvio Micali (born October 13, 1954) is an Italian computer scientist, professor at the Massachusetts Institute of Technology and the founder of Algorand. Micali's research centers on cryptography and information security.
In 2012, he received ...
. Probabilistic Encryption. JCSS, 28(2):270–299, 1984
* Oded Goldreich
Oded Goldreich ( he, עודד גולדרייך; b. 1957) 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 ...
. Foundations of Cryptography: Volume 2 – Basic Applications. Cambridge University Press, 2004.
* Jonathan Katz
Jonathan Paul Katz (born December 1, 1946) is an American actor and comedian best known for his starring role in the animated sitcom ''Dr. Katz, Professional Therapist'' as Dr. Katz. He also is known for voicing Erik Robbins in the UPN/Adult Swi ...
, Yehuda Lindell
Yehuda Lindell (born 24 February 1971) is a professor in the Department of Computer Science at Bar-Ilan University where he conducts research on cryptography with a focus on the theory of secure computation and its application in practice. Lindell ...
, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007
{{PlanetMath attribution, id=3457, title=computationally indistinguishable
Algorithmic information theory