Paper 2021/929

A polynomial time key-recovery attack on the Sidon cryptosystem

Pierre Briaud, Jean-Pierre Tillich, and Javier Verbel

Abstract

The Sidon cryptosystem is a new multivariate encryption scheme based on the theory of Sidon spaces which was presented at PKC 2021. As is usual for this kind of schemes, its security relies on the hardness of solving particular instances of the MQ problem and of the MinRank problem. A nice feature of the scheme is that it enjoys a homomorphic property due the bilinearity of its public polynomials. Unfortunately, we will show that the Sidon cryptosystem can be broken by a polynomial time key-recovery attack. This attack relies on the existence of solutions to the underlying MinRank instance which lie in a subfield and which are inherent to the structure of the secret Sidon space. We prove that such solutions can be found in polynomial time. Our attack consists in recovering an equivalent key for the cryptosystem by exploiting these particular solutions, and this task can be performed very efficiently.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Multivariate cryptographyEncryption schemeAlgebraic attackMinRank Problem
Contact author(s)
javier verbel @ tii ae
History
2021-07-11: revised
2021-07-09: received
See all versions
Short URL
https://ia.cr/2021/929
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/929,
      author = {Pierre Briaud and Jean-Pierre Tillich and Javier Verbel},
      title = {A polynomial time key-recovery attack on the Sidon cryptosystem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/929},
      year = {2021},
      url = {https://eprint.iacr.org/2021/929}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.