### Abstract

We consider the subset sum pseudorandom generator, introduced by Rueppel and Massey in 1985 and given by a linearly recurrent bit sequence u_{0}, u_{1}, ... of order n over ℤ_{2}, and weights w = (w _{0},..., w_{n-1}) ∈. R^{n} 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+j}w_{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 | |

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 | Canada |

City | Waterloo |

Period | 9/08/04 → 10/08/04 |

Internet address |

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

## Cite this

*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