Common modulus and chosen-message attacks on public-key schemes with linear recurrence relations

Abstract

We consider the linear recurrence relation V-t(x) = Sigma(i=1)(m) (a(i)x + b(i))Vt-i(x) + cx + f where m greater than or equal to 1, a(i) and b(i), 1 less than or equal to i less than or equal to m, are integers. The RSA and LUC schemes can be defined by this relation. In this paper we show that if the linear recurrence relation has some properties, the public-key scheme based on it cannot withstand the common modulus and chosen-message attacks, no matter what the order in is and what the parameters for a(i) and b(i), 1 less than or equal to i less than or equal to m, are. This implies that the LUC cryptosystem cannot withstand the common modulus attack and the LUC digital signature scheme cannot withstand the chosen-message attack. (C) 1999 Elsevier Science B.V. All rights reserved.