Predicting subset sum pseudorandom generators

Joachim Zur Von Gathen; Igor E. Shparlinski

doi:10.1007/978-3-540-30564-4_17

Predicting subset sum pseudorandom generators

Joachim Zur Von Gathen^*, Igor E. Shparlinski

^*Corresponding author for this work

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

6 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 u₀, u₁, ... of order n over ℤ₂, and weights w = (w ₀,..., w_n-1) ∈. Rⁿ for some ring R. The rings R = ℤ_m are of particular interest. The ith value produced by this generator is Σ_0≤j<n u_i+jw_j. 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 u_j or the weights w_j. Our attacks do not mean that the generator is insecure, but that one has to be careful in evaluating its security parameters.

Original language	English
Title of host publication	Selected areas in cryptography
Subtitle of host publication	11th InternationalWorkshop, SAC 2004 Waterloo, Canada, August 9-10, 2004, Revised Selected Papers
Editors	Helena Handschuh, M. Anwar Hasan
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	241-251
Number of pages	11
ISBN (Electronic)	9783540305644
ISBN (Print)	9783540243274
DOIs	https://doi.org/10.1007/978-3-540-30564-4_17
Publication status	Published - 2004
Event	11th Annual Workshop on Selected Areas in Cryptography - Waterloo, Canada Duration: 9 Aug 2004 → 10 Aug 2004 http://sacconference.org/SAC04/SAC2004.htm

Publication series

Name	Lecture notes in computer science
Publisher	Springer
Volume	3357
ISSN (Print)	0302-9743

Conference

Conference	11th Annual Workshop on Selected Areas in Cryptography
Abbreviated title	SAC 2004
Country/Territory	Canada
City	Waterloo
Period	9/08/04 → 10/08/04
Internet address	http://sacconference.org/SAC04/SAC2004.htm

Access to Document

10.1007/978-3-540-30564-4_17

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). Springer, Springer Nature. https://doi.org/10.1007/978-3-540-30564-4_17

@inbook{cdd0471a99aa44a4b6d5723cae812e64,

title = "Predicting subset sum pseudorandom generators",

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 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.",

author = "{Von Gathen}, {Joachim Zur} and Shparlinski, {Igor E.}",

year = "2004",

doi = "10.1007/978-3-540-30564-4_17",

language = "English",

isbn = "9783540243274",

series = "Lecture notes in computer science",

publisher = "Springer, Springer Nature",

pages = "241--251",

editor = "Helena Handschuh and Hasan, {M. Anwar}",

booktitle = "Selected areas in cryptography",

address = "United States",

note = "11th Annual Workshop on Selected Areas in Cryptography, SAC 2004 ; Conference date: 09-08-2004 Through 10-08-2004",

url = "http://sacconference.org/SAC04/SAC2004.htm",

}

Von Gathen, JZ & Shparlinski, IE 2004, Predicting subset sum pseudorandom generators. in H Handschuh & MA Hasan (eds), Selected areas in cryptography: 11th InternationalWorkshop, SAC 2004 Waterloo, Canada, August 9-10, 2004, Revised Selected Papers. Lecture notes in computer science, vol. 3357, Springer, Springer Nature, Berlin, pp. 241-251, 11th Annual Workshop on Selected Areas in Cryptography, Waterloo, Canada, 9/08/04. https://doi.org/10.1007/978-3-540-30564-4_17

Predicting subset sum pseudorandom generators. / Von Gathen, Joachim Zur; Shparlinski, Igor E.
Selected areas in cryptography: 11th InternationalWorkshop, SAC 2004 Waterloo, Canada, August 9-10, 2004, Revised Selected Papers. ed. / Helena Handschuh; M. Anwar Hasan. Berlin: Springer, Springer Nature, 2004. p. 241-251 (Lecture notes in computer science; Vol. 3357).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - Predicting subset sum pseudorandom generators

AU - Von Gathen, Joachim Zur

AU - Shparlinski, Igor E.

PY - 2004

Y1 - 2004

N2 - 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 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.

AB - 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 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.

UR - http://www.scopus.com/inward/record.url?scp=35048885560&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-30564-4_17

DO - 10.1007/978-3-540-30564-4_17

M3 - Chapter

AN - SCOPUS:24144463944

SN - 9783540243274

T3 - Lecture notes in computer science

SP - 241

EP - 251

BT - Selected areas in cryptography

A2 - Handschuh, Helena

A2 - Hasan, M. Anwar

PB - Springer, Springer Nature

CY - Berlin

T2 - 11th Annual Workshop on Selected Areas in Cryptography

Y2 - 9 August 2004 through 10 August 2004

ER -

Predicting subset sum pseudorandom generators

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this