Paper 2024/595
Analysis of Multivariate Encryption Schemes: Application to Dob and C*
Abstract
A common strategy for constructing multivariate encryption schemes is to use a central map that is easy to invert over an extension field, along with a small number of modifications to thwart potential attacks. In this work we study the effectiveness of these modifications, by deriving estimates for the number of degree fall polynomials. After developing the necessary tools, we focus on encryption schemes using the $C^*$ and Dobbertin central maps, with the internal perturbation (ip), and $Q_+$ modifications. For these constructions we are able to accurately predict the number of degree fall polynomials produced in a Gröbner basis attack, up to and including degree five for the Dob encryption scheme and four for $C^*$. The predictions remain accurate even when fixing variables. Based on this new theory we design a novel attack on Dob, which completely recovers the secret key for the parameters suggested by its designers. Due to the generality of the presented techniques, we also believe that they are of interest to the analysis of other big field schemes.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published by the IACR in JOC 2024
- DOI
- 10.1007/s00145-024-09501-w
- Contact author(s)
-
morten oygarden @ simula no
patrick felke @ hs-emden-leer de
haavardr @ simula no - History
- 2024-04-18: approved
- 2024-04-16: received
- See all versions
- Short URL
- https://ia.cr/2024/595
- License
-
CC0
BibTeX
@misc{cryptoeprint:2024/595,
author = {Morten Øygarden and Patrick Felke and Håvard Raddum},
title = {Analysis of Multivariate Encryption Schemes: Application to Dob and C*},
howpublished = {Cryptology ePrint Archive, Paper 2024/595},
year = {2024},
doi = {10.1007/s00145-024-09501-w},
note = {\url{https://eprint.iacr.org/2024/595}},
url = {https://eprint.iacr.org/2024/595}
}
