HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Breaking Littlewood's cipher

Damien Stehlé 1
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 6:05:27 PM
Last modification on : Friday, February 4, 2022 - 3:21:42 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:27:17 PM


  • HAL Id : inria-00071590, version 1



Damien Stehlé. Breaking Littlewood's cipher. [Research Report] RR-4988, INRIA. 2003. ⟨inria-00071590⟩



Record views


Files downloads