Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote -1 down vote favorite

The wikipedia page on computational indistinguishability says that two ensembles are not distinguishable if "any non-uniform probabilistic polynomial time algorithm A" cannot tell them apart. To help me better understand the definition, I searched for an example of an algorithm that did not fit the above restriction---in particular a non polynomial time algorithm---that could differentiate between two computational indistinguishable ensembles. Rather to my surprise, I found none, so I ask, could anyone provide me with an example of one?

share|improve this question
1  
Brute force on the input of algorithm $A$? But otherwise I suspect the algorithm would be highly dependent on the underlying cryptographic primitive, the simplest example is RSA where integer factorization is subexponential (but not polynomial) but this isn't a great example, being public-key and all. – Thomas Feb 21 at 19:58
1  
Another example is this: distinguish between a stream of output from Blowfish-CTR and AES-CTR (or generally two block ciphers with different block sizes in CTR mode). An algorithm can distinguish them without even touching the keys, using the birthday paradox, with complexity $\approx 2^{32}$, which is not polynomial-time (is exponential) but far better than brute-force. – Thomas Feb 21 at 20:15

2 Answers

up vote 0 down vote

Here are two examples of attack algorithms that are not polynomial-time:

  • Exhaustive search. Consider an algorithm that iteratively enumerates all possible keys, and checks to see if it seems to be correct. The running time of this algorithm is non polynomial: for a $b$-bit key, it will take $2^b$ steps of computation, which is larger than any polynomial of $b$.

  • Factoring. The running time of the state-of-the-art factoring algorithms is larger than any polynomial of $b$, where $b$ represents the number of bits of the number you want to factor. For instance, the running time of some factoring algorithms is something like $2^{\sqrt{b}}$, which grows faster than any polynomial function of $b$. As far as we know right now, there's no way to factor integers in polynomial time.

The definition you are considering only concerns itself with attack algorithms whose running time is a polynomial, so the above two attacks are considered out of scope (they're not considered a "break" of the cryptosystem).

Edit 2/22: In the context of distinguishing two probability distributions, if you want a natural example, try exhaustive keysearch: to distinguish AES-CTR output from true random, one algorithm might try all possible $2^{128}$ keys to see if any of them match the observed value from the distribution, and output 1 if it matches, else 0. This algorithm does distinguish the two probability distributions, but it takes exponential time. (Strictly speaking, we should make this a $b$-bit key so that we can apply asymptotic running time, but whatever, hopefully you get the idea.)

P.S. If this gets to be a bit much and you need a study break, don't miss Eric Hughes' infamous advice on How to Give a Math Lecture at a Party (lyrics).

share|improve this answer
I understand the examples you give, but how would you apply them to a (sample from a) probability distribution? What would exhaustive search be like in this case? I mean, there is no "key" for which to check for correctness! – wmnorth Feb 22 at 12:46
@wmnorth, any algorithm that spends, say, exponential time doing some computation before producing an output. (I suspect I must not be understanding your question; why don't you try explaining what you real confusion is?) Have you studied running time analysis of algorithms? If not, any good algorithms textbook should have something on big-O notation and running time analysis -- I very much recommend you read it. – D.W. Feb 22 at 18:34
I'll try to clarify my question. I am familiar with run time analysis of algorithms, and big-O notation, my question is not about that; it's about algorithms (or statistical tests if you will) that are capable of distinguishing two different (but computationally indistinguishable) probability ensembles. From all I've read, being indistinguishable means that there is no non-uniform probabilistic polynomial time algorithm could tell one ensemble from the other. However, I could not find an example of an algorithm that could distinguish the two ensembles, and that's what I asked for. – wmnorth Feb 22 at 22:41
(cont.) You mentioned exhaustive search, which is indeed non polynomial. But what does it mean to do exhaustive search when trying to distinguish two probability ensembles? To give a concrete example, what would it mean to do an exhaustive search in order to try to distinguish the output of a PRNG from the uniform distribution? Does this clarify what I am trying to ask? – wmnorth Feb 22 at 22:46
@wmnorth, sorry, I can't make any sense of your question. I think you must have some hidden assumptions, or must be asking a different question than what you really want to know. What does it mean for an algorithm to take exponential time when trying to distinguish two probability ensembles/ It just means that the running time is exponential. I really don't understand what the confusion is. (If you are asking for a natural example of an exponential time algorithm for distinguishing two probability distributions, that's different; if so, edit your question!) – D.W. Feb 22 at 22:56
show 1 more comment
up vote 0 down vote

I am not a complexity theorist, but I believe this fits the requirements.

The best known algorithms for factoring are superpolynomial time algorithm so they are not polynomial time. An example of something th superpolynomial time algorithm could distinguish are outputs from the Blum-Blum-Shub PRNG.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.