Predicting subset sum pseudorandom generators

Joachim Zur Von Gathen*, Igor E. Shparlinski

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter

4 Citations (Scopus)

Abstract

We consider the subset sum pseudorandom generator, introduced by Rueppel and Massey in 1985 and given by a linearly recurrent bit sequence u0, u1, ... of order n over ℤ2, and weights w = (w 0,..., wn-1) ∈. Rn for some ring R. The rings R = ℤm are of particular interest. The ith value produced by this generator is Σ0≤j<n ui+jwj. It is also recommended to discard about log n least significant bits of the result before using this sequence. We present several attacks on this generator (with and without the truncation), some of which are rigorously proven while others are heuristic. They work when one "half" of the secret is given, either the control sequence uj or the weights wj. Our attacks do not mean that the generator is insecure, but that one has to be careful in evaluating its security parameters.

Original languageEnglish
Title of host publicationSelected areas in cryptography
Subtitle of host publication11th InternationalWorkshop, SAC 2004 Waterloo, Canada, August 9-10, 2004, Revised Selected Papers
EditorsHelena Handschuh, M. Anwar Hasan
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages241-251
Number of pages11
ISBN (Electronic)9783540305644
ISBN (Print)9783540243274
DOIs
Publication statusPublished - 2004
Event11th Annual Workshop on Selected Areas in Cryptography - Waterloo, Canada
Duration: 9 Aug 200410 Aug 2004
http://sacconference.org/SAC04/SAC2004.htm

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume3357
ISSN (Print)0302-9743

Conference

Conference11th Annual Workshop on Selected Areas in Cryptography
Abbreviated titleSAC 2004
CountryCanada
CityWaterloo
Period9/08/0410/08/04
Internet address

Fingerprint Dive into the research topics of 'Predicting subset sum pseudorandom generators'. Together they form a unique fingerprint.

  • Cite this

    Von Gathen, J. Z., & Shparlinski, I. E. (2004). Predicting subset sum pseudorandom generators. In H. Handschuh, & M. A. Hasan (Eds.), Selected areas in cryptography: 11th InternationalWorkshop, SAC 2004 Waterloo, Canada, August 9-10, 2004, Revised Selected Papers (pp. 241-251). (Lecture notes in computer science; Vol. 3357). Berlin: Springer, Springer Nature. https://doi.org/10.1007/978-3-540-30564-4_17