Paper 2016/010

Eliminating Decryption Failures from the Simple Matrix Encryption Scheme

Albrecht Petzoldt, Jintai Ding, and Lih-Chung Wang

Abstract

The SimpleMatrix encryption scheme as proposed by Tao et al. \cite{TD13} is one of the very few existing approaches to create a secure and efficient encryption scheme on the basis of multivariate polynomials. However, in its basic version, decryption failures occur with non-negligible probability. Although this problem has been addressed in several papers \cite{DP14,TX15}, a general solution to it is still missing.\\ In this paper we propose an improved version of the SimpleMatrix scheme, which eliminates decryption failures completely and therefore solves the biggest problem of the SimpleMatrix encryption scheme. Additionally, we propose a second version of the scheme, which reduces the blow-up factor between plain and ciphertext size to a value arbitrary close to 1.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Multivariate CryptographySimpleMatrix Encryption SchemeDecryption FailuresBlow-up Factor
Contact author(s)
petzoldt @ imi kyushu-u ac jp
History
2016-01-06: received
Short URL
https://ia.cr/2016/010
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/010,
      author = {Albrecht Petzoldt and Jintai Ding and Lih-Chung Wang},
      title = {Eliminating Decryption Failures from the Simple Matrix Encryption Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2016/010},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/010}},
      url = {https://eprint.iacr.org/2016/010}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.