On Squaring Modulo Mersenne Numbers

David Naccache; Ofer Yifrach-Stav

Paper 2022/1197

On Squaring Modulo Mersenne Numbers

David Naccache, École Normale Supérieure - PSL

Ofer Yifrach-Stav, École Normale Supérieure - PSL

Abstract

During the design of a new primitive inspired by Squash we accidentally stumbled on the observation described in this note. Let $n$ be a $k$-bit Mersenne number whose factors are unknown. Consider an $\ell$-bit secret number $x=2^{k/2}a+b$. We observe that there are parameter configurations where a chunk of the value $b^2$ is leaked even if $k<2\ell$. This observation does not endanger any known scheme and in particular not Squash.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: Squash Mersenne Squaring
Contact author(s): david naccache @ ens fr
ofer friedman @ ens fr
History: 2022-09-12: approved; 2022-09-11: received; See all versions
Short URL: https://ia.cr/2022/1197
License: CC0

BibTeX

@misc{cryptoeprint:2022/1197,
      author = {David Naccache and Ofer Yifrach-Stav},
      title = {On Squaring Modulo Mersenne Numbers},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1197},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1197}},
      url = {https://eprint.iacr.org/2022/1197}
}