Title: Efficient Cryptanalysis of RSE(2)PKC and RSSE(2)PKC
Authors: Wolf, Christopher ×
Braeken, An
Preneel, Bart #
Issue Date: 2005
Publisher: Springer
Series Title: Lecture Notes in Computer Science vol:3352 pages:294-307
Conference: SCN 2004 date:September 08-10, 2004
Abstract: In this paper, we study the new class step-wise Triangular Schemes (STS) of public key cryptosystems (PKC) based on multivariate quadratic polynomials. In these schemes, we have m, the number of equations, n the number of variables, L the number of steps/layers, r the number of equations/variables per step, and q the size of the underlying field. We present two attacks on the STS class by exploiting the chain of the kernels of the private key polynomials. 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. Since the legitimate user has workload q(r) for decrypting/computing a signature, the attacks presented in this paper are very efficient. As an application, we show that two special instances of STS, namely RSE(2)PKC and RSSE(2)PKC, recently proposed by Kasahara and Sakai, are insecure.
ISSN: 0302-9743
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 Status SizeFormat
article-552.pdf Published 0KbAdobe 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