1
$\begingroup$

In this paper Patarin says that: "for every $\epsilon > 0$, when $m \ll 2^{n(1 - \epsilon)}$ ... for 7 rounds or more it is secure against all adaptive chosen plaintext attacks" where m is the number of queries that the adversary can evaluate.

What concretely is meant by $m \ll 2^{n(1 - \epsilon)}$?

For instance, to have statistical security $2^{-\sigma}$ (e.g. $\sigma = 40$) concretely how many queries can be evaluated?

$\endgroup$
5
  • $\begingroup$ define statistical security $\endgroup$ – kodlu Apr 25 '20 at 4:15
  • $\begingroup$ How would you even define << concretely? It's sort an asymptotic idea. $\endgroup$ – Adrian Self Apr 26 '20 at 1:00
  • $\begingroup$ @kodlu Where statistical security is the advantage of an adversary has in the Chosen Plaintext Attack game, when they are able to make $m$ queries and have unlimited computational resources. $\endgroup$ – Daniel-耶稣活着 Apr 26 '20 at 2:24
  • 1
    $\begingroup$ ok so you want the advantage to be upper bounded by $2^{-40}.$ $\endgroup$ – kodlu Apr 26 '20 at 3:22
  • $\begingroup$ @kodlu Yes, exactly. $\endgroup$ – Daniel-耶稣活着 Apr 26 '20 at 3:32
0
$\begingroup$

The linked paper is missing a lot of proof details. In any case, it seems impossible to say anything concrete for finite $n$ due to the existence of terms in $O(\cdot)$ notation in the bounds. You simply do not know how large those implied constants are.

$\endgroup$
4
  • $\begingroup$ Yeah--the missing proof details is a lot of the problem... In principle if the details of the proof were there I should be able to go through and figure out what the constants are in the $\mathcal{O}()$ notation. But since they are omitted, I was hoping someone out there might know of a place that someone had gone through and calculated the constants. Or if not, a place where I can find the full proof so I can go through and try to figure out the constants myself. $\endgroup$ – Daniel-耶稣活着 Apr 26 '20 at 2:28
  • $\begingroup$ Did it not reference where the full version is, in the paper? These kinds of arguments are usually asymptotic. $\endgroup$ – kodlu Apr 26 '20 at 3:21
  • 1
    $\begingroup$ see also here crypto.stackexchange.com/questions/43870/… for a related question and the followup comment which has links to more but based on @fgrieu's comment I don't hold high hopes that you'll get what you want. $\endgroup$ – kodlu Apr 26 '20 at 3:24
  • $\begingroup$ Yes, citation 15. "Extended version of this paper. Available from the author." I was hoping to find a source online, but I can contact the author. $\endgroup$ – Daniel-耶稣活着 Apr 26 '20 at 3:24

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.