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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In public key crypto, the popular definitions of security (CPA, CCA1,2) depend on PPT adversaries. I'm trying to understand why adversaries should be PPT.

It's clear that adversaries should be at most probabilistic sub-exponential, because otherwise they could exhaust the message space. It's also clear that adversaries should be at least PPT, because any computer can run low-order polynomial algorithms (barring unusual cases) and there's no good way to distinguish low-order polynomials from very high-order (and practically inefficient) polynomials.

So why not allow the adversaries to be probabilistic quasi-polynomials? Where quasi-polynomial means its time complexity is larger than all polynomials and smaller than all exponentials, like $n^{log(n)}$. Is there some example showing why it would not make sense for an adversary to be probabilitic quasi-polynomial?

share|improve this question

The reason I was taught why poly-time is the conventional way to define "efficient" algorithms is that it's the smallest notion closed under various forms of composition.

If we have an algorithm for deciding whether some input is in some language and we let $N$ be the length of the input, then we'd like to call all the following operations efficient:

  • Returning "yes" or "no" all the time costs one (or constant) time.
  • Reading the input costs $N$ time.
  • Calling one efficient algorithm taking time $A(N)$, then passing the result through an efficient algorithm taking time $B(N)$ gives a total time of $A(N) + B(N)$, so our class of "efficient running times" should be closed under addition.
  • If an algorithm taking $A(N)$ time on its own is efficient, and you have an algorithm with $A(N)$ steps where each step is a call to another efficient algorithm taking $B(N)$ time, then you end up with $A(N)B(N)$ time, so "efficiency" should be closed under multiplication.

Plug all that together and you get "polynomial in $N$" as the smallest possible "efficiency notion" - which does not of course exclude other, larger notions such as the ones mentioned above.

This is not so much a cryptography as a general complexity theory/theoretical CS point, which cryptographers have borrowed for their notions of security.

share|improve this answer
    
Even better, polynomial time is preserved by pretty much any modification of the computation model you can think of. For Turing machines you can have a RAM machine, or an alphabet as large as you want, or as many tapes as you want, and also make them as many-dimensional as you want. Then there's boolean circuits, lambda calculus, or just (suitably defined) good old pseudocode... – fkraiem yesterday

There is nothing stopping you from doing this. I don't know of any cryptosystem that is in use today that would be considered unsecure against a quasi-polynomial time adversary. RSA is probably the closest. It is super-polynomial (thanks to GNFS), so it would still be secure in a quasi-poly time adversarial model.

The only argument I see against quasi-polynomial time adversary models is that it obviously does not reflect reality as well as the PT adversary (otherwise we would see much larger RSA keys in use).

share|improve this answer
1  
"otherwise we would see much larger RSA keys in use" I wouldn't conclude that. Those definitions are asymptotic and don't say anything about concrete key sizes. – CodesInChaos Dec 13 '12 at 8:04
    
Thank you, but it's not obvious to me why quasi-poly doesn't reflect reality as well as PT? If there's nothing stopping us from taking this definition, then someone would have taken it as it's more general, so I'd like to know why quasi-poly doesn't work in our security definitions. – StuartHa Dec 13 '12 at 9:35

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.