Efficient Cryptanalysis of RSE(2)PKC and RSSE(2)PKC

Christopher Wolf; An Braeken; Bart Preneel

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2004/237

Efficient Cryptanalysis of RSE(2)PKC and RSSE(2)PKC

Christopher Wolf, An Braeken, and Bart Preneel

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^3Lq^r + n^2Lrq^r)$, the second is a structural attack which recovers an equivalent version of the secret key in $O(mn^3Lq^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.

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. This is the extended version of an article published in Conference on Security in Communication Networks --- SCN 2004, volume 3352 of Lecture Notes in Computer Science, pages 294--309. Springer, September 8--10 2004.
Keywords: multivariate cryptography cryptanalysis rank attack Tame
Contact author(s): Christopher Wolf @ esat kuleuven ac be
History: 2005-08-06: last of 2 revisions; 2004-09-16: received; See all versions
Short URL: https://ia.cr/2004/237
License: CC BY

BibTeX

@misc{cryptoeprint:2004/237,
      author = {Christopher Wolf and An Braeken and Bart Preneel},
      title = {Efficient Cryptanalysis of RSE(2)PKC and RSSE(2)PKC},
      howpublished = {Cryptology ePrint Archive, Paper 2004/237},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/237}},
      url = {https://eprint.iacr.org/2004/237}
}