On the security of stepwise triangular systems |
| |
Authors: | Christopher Wolf An Braeken Bart Preneel |
| |
Institution: | (1) Department Electrical Engineering, ESAT/COSIC, Katholieke Universiteit Leuven, Kasteelpark Arenberg 10, B-3001 Heverlee-Leuven, Belgium |
| |
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
ultivariate
uadratic equations. In this article, we first introduce Step-wise Triangular Schemes (STS) as a new class of
ultivariate
uadratic 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
. 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
ultivariate
uadratic public key scheme by discussing all possible variations and pointing out their vulnerabilities. |
| |
Keywords: | Multivariate cryptography Rank attacks Efficient cryptanalysis Triangular systems |
本文献已被 SpringerLink 等数据库收录! |
|