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?

Improve this question
$\endgroup$
5
  • $\begingroup$ define statistical security $\endgroup$
    – kodlu
    Apr 25, 2020 at 4:15
  • $\begingroup$ How would you even define << concretely? It's sort an asymptotic idea. $\endgroup$
    – Adrian Self
    Apr 26, 2020 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, 2020 at 2:24
  • 1
    $\begingroup$ ok so you want the advantage to be upper bounded by $2^{-40}.$ $\endgroup$
    – kodlu
    Apr 26, 2020 at 3:22
  • $\begingroup$ @kodlu Yes, exactly. $\endgroup$
    – Daniel-耶稣活着
    Apr 26, 2020 at 3:32

1 Answer 1

Reset to default
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.

Improve this answer
$\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, 2020 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, 2020 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, 2020 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, 2020 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.