Breaking Littlewood's Cipher
Damien Stehlé
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 generalize 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.
Download: pdf (Slightly outdated version).
Homepage