Paper 2020/367

Exploiting Decryption Failures in Mersenne Number Cryptosystems

Marcel Tiepelt and Jan-Pieter D'Anvers


Mersenne number schemes are a new strain of potentially quantum-safe cryptosystems that use sparse integer arithmetic modulo a Mersenne prime to encrypt messages. Two Mersenne number based schemes were submitted to the NIST post-quantum standardization process: Ramstake and Mersenne-756839. Typically, these schemes admit a low but non-zero probability that ciphertexts fail to decrypt correctly. In this work we show that the information leaked from failing ciphertexts can be used to gain information about the secret key. We present an attack exploiting this information to break the IND-CCA security of Ramstake. First, we introduce an estimator for the bits of the secret key using decryption failures. Then, our estimates can be used to apply the Slice-and-Dice attack due to Beunardeau et al. at significantly reduced complexity to recover the full secret. We implemented our attack on a simplified version of the code submitted to the NIST competition. Our attack is able to extract a good estimate of the secrets using $2^{12}$ decryption failures, corresponding to $2^{74}$~failing ciphertexts in the original scheme. Subsequently the exact secrets can be extracted in $O(2^{46})$ quantum computational steps.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Proceedings of the 7th ACM ASIA Public-Key Cryptography Workshop (APKC '20)
Mersenne number cryptosystemsdecryption failuresIND-CCAcryptanalysispost-quantum
Contact author(s)
marcel tiepelt @ kit edu
2020-04-02: received
Short URL
Creative Commons Attribution


      author = {Marcel Tiepelt and Jan-Pieter D'Anvers},
      title = {Exploiting Decryption Failures in Mersenne Number Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2020/367},
      year = {2020},
      doi = {10.1145/3384940.3388957},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.