RR-4988 : Breaking Littlewood's cipher

Abstract : In 1953, the celebrated mathematician John Edensor Littlewood proposed a stream cipher based on logarithm tables. Fifty years later, we propose the first analysis of his scheme. Littlewood suggests the idea of using real functions as tools to build cryptographic primitives. Even when considering modern security parameters, the original scheme can be broken by a simple attack based on differentiation. We generalise the scheme such that it resists this attack, but describe another attack which is derived from both polynomial approximation and Coppersmith's technique to find the small roots of modular multivariate polynomials. In contrast with these negative results we describe a candidate for a very efficient one-way function and present an open problem based on this work.

Résumé : En 1953, le célèbre mathématicien John Edensor Littlewood a proposé un schéma de chiffrement reposant sur les tables de logarithmes. 50 ans plus tard, nous décrivons la première cryptanalyse de ce protocole. Littlewood suggère l'idée d'utiliser les fonctions de la variable réelle comme outils de base pour construire des primitives cryptographiques. Même si l'on considère des paramètres de sécurité actualisés, le schéma original peut être cassé par une simple attaque utilisant des dérivées successives. Nous généralisons le protocole de telle sorte qu'il résiste à cette attaque simple, mais une autre attaque peut être réalisée, en utilisant d'une part des approximations polynomiales et d'autre part la méthode de Coppersmith pour trouver les petites racines de polynômes modulaires multivariés. En opposition à ces cryptanalyses, nous décrivons un nouveau candidat de fonction à sens uniqe très efficace et présentons un problème ouvert lié à ce travail.

RR-4988 - Breaking Littlewood's cipher