Technical Report CS-2000-01

Title: Cryptanalysis of Patarin's 2-Round Public Key System with S Boxes (2R)
Authors: Eli Biham
Abstract: In a series of papers Patarin proposes new efficient public key systems. A very interesting proposal, called {\it 2-Round Public Key System with S Boxes}, or {\it 2R}, is based on the difficulty of decomposing the structure of several rounds of unknown linear transformations and S boxes. This difficulty is due to the difficulty of decomposing compositions of multivariate binary functions. In this paper we present a novel attack which breaks the 64-bit block variant with complexity about $2^{30}$ steps, and the more secure 128-bit blocks variant with complexity about $2^{60}$ steps. It is interesting to note that this cryptanalysis uses only the ciphertexts of selected plaintexts, and does not analyze the details of the supplied encryption code.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2000
To the main CS technical reports page

Computer science department, Technion