[Cfrg] A problem with the security proof of AugPAKE?

["Stanislav V. Smyshlyaev" <[e-mail]>]

Dear SeongHan and colleagues!

It seems to me and my colleagues that there may be a major problem with a
security proof of AugPAKE, and I'll be thankful if you comment on this
issue.

If we look on the most significant part of the upper bound of adversary
advantage (Theorem 1 in https://eprint.iacr.org/2010/334.pdf), we'll have
the following:
\Adv^{ake}_{P}(\Enemy) \approx \frac{6(q_{sendC}+q_{sendS})}{N} + 2N^2\cdot
q_{hashH} \cdot Succ^{1sdh}_{g,\mathbb{G}}(t + \tau_e).

The problem we see is that the estimation depends on N (the volume of
dictionary) quadratically, and in the first part N occurs in the divisor
only linearly - so when the dictionary grows, the bound becomes weaker.

It wouldn't be a problem, if the effect were not present for ordinary
values of N (and would occur only for extremely large values of N) - but it
is.

[The rest part of the message contains rough estimations that illustrate
what I'm saying.]

If we estimate Succ^{1sdh}_{g,\mathbb{G}}(t)  as \frac{t^2}{|\mathbb{G}|}
(Pollard's rho-algorithm) and t \approx q_{hashH} the estimation will be
the following:
\Adv^{ake}_{P}(\Enemy) \approx \frac{6(q_{sendC}+q_{sendS})}{N} +
\frac{2N^2\cdot q^3_{hashH}}{|\mathbb{G}|} .
Let |\mathbb{G}| = 2^{256}$, $q_{hashH} = 2^{50}.
Then for N \geqslant
\sqrt[3]{\frac{6(q_{sendC}+q_{sendS})|\mathbb{G}|}{q^3_{hashH}}} \approx
2^{30} the estimation will be weaker for greater $N$.

And N=2^{30} is the dictionary for 6 symbols of (0-9, a-z, A-Z) -
absolutely reasonable value, that is definitely not extremely large.

Thank you in advance for your comments!


Best regards,

Stanislav V. Smyshlyaev, Ph.D.,

Head of Information Security Department,
CryptoPro LLC