AuthorsM. Øygarden, P. Felke and H. Raddum
EditorsJ. A. Garay
TitleAnalysis of Multivariate Encryption Schemes: Application to Dob
Project(s)Simula UiB
Publication TypeProceedings, refereed
Year of Publication2021
Conference NamePublic-Key Cryptography (PKC 2021)
VolumeLNCS, vol 12710
Pagination155 - 183
Date Published05/2021
PublisherSpringer International Publishing
Place PublishedCham
ISBN Number978-3-030-75244-6
ISSN Number0302-9743

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

Citation Key28252

Contact person