[Resource Topic] 2024/595: Analysis of Multivariate Encryption Schemes: Application to Dob and C*

Welcome to the resource topic for 2024/595

Analysis of Multivariate Encryption Schemes: Application to Dob and C*

Authors: Morten Øygarden, Patrick Felke, Håvard Raddum


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.

ePrint: https://eprint.iacr.org/2024/595

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .