Reading some papers on security amplification of weak-PRP written by Stefano Tessaro, I noticed the use of notion "epsilon-PRP" and the notion of "security amplification". These notions, in conjunction with the statement

We consequently call a primitive satisfying this assumption an epsilon-PRP: Clearly, AES is much more likely to be a 0.99-PRP, rather than a fully-secure PRP.

from Tesaro-Security Amplification for the Cascade of Arbitrarily Weak PRPs: Tight Bounds via the Interactive Hardcore Lemma confused me.

Can anybody explain when security of PRP is higher, for epsilon very close to 1? Security amplification of cascade of PRP's occur when resulting epsilon is greater than every epsilon of basic PRP?

  • 2
    $\begingroup$ I can't quite tell what you are asking. Can you revise the question to clarify/elaborate what the question is? I see two incomplete sentences that end in with question mark, but I'm having trouble understanding what either one is intended to ask. $\endgroup$
    – D.W.
    Jul 15 '13 at 18:22

As D.W. said, your questions are not very clear. I interpret your first question as asking how the security of an $\epsilon$-PRP varies with $\epsilon$. The answer to this is quite clear from Tessaro's introduction: $\epsilon=0$ corresponds to the standard definition of PRP (also called fully-secure PRP in the paper). As $\epsilon$ grows, the security weakens. If you push to $\epsilon=1$ (which is not permited by the definition), there is no security left.

So the highlighted sentence in your question means that the assumption that AES is very weakly secure (0.99-PRP) is much weaker (and thus more likely) than the assumption that AES is fully secure.

Concerning your second question: The problem solved in the paper is to show that a cascade of $\epsilon$-PRPs with independent keys becomes more and more secure as the number of ciphers in the cascade grows. For $\epsilon\geq 1/2$, this was unknown from previous papers.

  • $\begingroup$ Thank you minar and DW, you two were so nice to spend time and read my questions. I'm sorry for the weak elaboration of my questions. Now it's clear, things were pushed to the limits for AES and that confused me. However I still cannot understand how "that the assumption that [...] is much weaker (and thus more likely) than the assumption that [...]". I'm not a native EnglishIdeed, you supposed right what the meaning of my questions was. $\endgroup$
    – Martin M
    Jul 16 '13 at 13:05
  • 1
    $\begingroup$ @MartinM The idea is that all $0.3$-PRPs are also $0.4$-PRPs, all $0.6$-PRPs are also $0.9$-PRPs and so on. So the bigger $\varepsilon$ gets, the more functions (or function families) are covered by the definition. And we have no idea how secure a PRP is actually, just can do guesses. We hope that AES actually is something like a $0.00...001$-PRP (the number of zeroes depending on the time bound for the adversary). $\endgroup$ Jul 17 '13 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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