Title: On the security of stepwise triangular systems
Authors: Wolf, Christopher ×
Braeken, An
Preneel, Bart #
Issue Date: 2006
Publisher: Springer Netherlands
Series Title: Designs, Codes and Cryptography vol:40 issue:3 pages:285-302
Abstract: In 2003 and 2004, Kasahara and Sakai suggested the two schemes RSE(2)PKC and RSSE(2)PKC, respectively. Both are examples of public key schemes based on Multivariate Quadratic equations. In this article, we first introduce Step-wise Triangular Schemes (STS) as a new class of Multivariate Quadratic public key schemes. These schemes have m equations, n variables, L steps or layers, r the number of equations and new variables per step and q the size of the underlying finite field F. Then, we derive two very efficient cryptanalytic attacks. The first attack is an inversion attack which computes the message/signature for given ciphertext/message in O(mn(3)Lq(r)+n(2)Lrq(r)), the second is a structural attack which recovers an equivalent version of the secret key in O(mn(3)Lq(r)+mn(4)) operations. As the legitimate user also has a workload growing with q(r) to recover a message/compute a signature, q(r) has to be small for efficient schemes and the attacks presented in this article are therefore efficient. After developing our theory, we demonstrate that both RSE(2)PKC and RSSE(2)PKC are special instances of STS and hence, fall to the attacks developed in our article. In particular, we give the solution for the crypto challenge proposed by Kasahara and Sakai. Finally, we demonstrate that STS cannot be the basis for a secure Multivariate Quadratic public key scheme by discussing all possible variations and pointing out their vulnerabilities.
ISSN: 0925-1022
Publication status: published
KU Leuven publication type: IT
Appears in Collections:ESAT - STADIUS, Stadius Centre for Dynamical Systems, Signal Processing and Data Analytics
Electrical Engineering - miscellaneous
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
article-813.pdf Published 226KbAdobe PDFView/Open Request a copy

These files are only available to some KU Leuven Association staff members


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science