Paper 2020/1442

Analysis of Multivariate Encryption Schemes: Application to Dob

Morten Øygarden, Patrick Felke, and Håvard Raddum

Abstract

In this paper, we study the effect of two modifications to multivariate public key encryption schemes: internal perturbation (ip), and Q_+. Focusing on the Dob encryption scheme, a construction utilising these modifications, we accurately predict the number of degree fall polynomials produced in a Gröbner basis attack, up to and including degree five. The predictions remain accurate even when fixing variables. Based on this new theory we design a novel attack on the Dob encryption scheme, which breaks Dob using the parameters suggested by its designers. While our work primarily focuses on the Dob encryption scheme, we also believe that the presented techniques will be of particular interest to the analysis of other big-field schemes.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2021
Contact author(s)
morten oygarden @ simula no
haavardr @ simula no
patrick felke @ hs-emden-leer de
History
2021-05-14: last of 2 revisions
2020-11-19: received
See all versions
Short URL
https://ia.cr/2020/1442
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1442,
      author = {Morten Øygarden and Patrick Felke and Håvard Raddum},
      title = {Analysis of Multivariate Encryption Schemes: Application to Dob},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1442},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1442}},
      url = {https://eprint.iacr.org/2020/1442}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.