More on Security of Public-Key Cryptosystems Based on Chebyshev Polynomials

Recently, a public-key cryptosystem based on Chebyshev polynomials has been proposed, but it has been later analyzed and shown insecure. This paper addresses some unanswered questions about the cryptosystem. We deal with the issue of computational precision. This is important for two reasons. Firstly, the cryptosystem is defined on real numbers, but any practical data communication channel can only transmit a limited number of digits. Any real number can only be specified to some precision level, and we study the effect of that. Secondly, we show that the precision issue is related to its security. In particular, the algorithm previously proposed to break the cryptosystem may not work in some situations. Moreover, we introduce another method to break the cryptosystem with general precision settings. We extend the method to show that a certain class of cryptosystems is insecure. Our method is based on the known techniques on the shortest vector problem in lattice and linear congruences.

I. Introduction

Currently, secure network communications are supported by many cryptographic techniques. The techniques are partitioned into public-key cryptography and secret-key cryptography. While both disciplines are indispensable, practical public-key cryptographic systems are relatively slower than practical secret-key ones. Though the Rivest–Shamir–Adleman (RSA) cryptosystem [1] and the Diffie–Hellman key-agreement protocol [2] play important roles in practical systems, the speed gap between such public-key cryptosystems and secret-key cryptosystems [e.g., Advanced Encryption Standard (AES)] has narrowed the possibilities to hybridize the two types of cryptography. Thus, public-key cryptographic systems of comparable speed with secret-key ones are desired. For instance, the NTRU [3], based on polynomial rings, is known as such a candidate and its security has been discussed in the literature. As a new candidate, a public-key cryptosystem based on Chebyshev polynomials has been proposed in [4] recently. The system uses a key-agreement protocol similar to the Diffie–Hellman protocol. Also, it can be seen as a chaos-based cryptosystem, a class of cryptosystems making use of chaotic mappings or signals. Due to the sensitivity to initial conditions, chaotic systems often have random-like behaviors, which make them popular candidates as building blocks of cryptosystems [5]. Other chaos-based cryptographic primitives, like random number generators [6] and hash functions [7], are also studied in the literature.