# security amplification

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.

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?

• 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.
– 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.
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.
• @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). Jul 17 '13 at 19:13