Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Revisiting the Concrete Security of Goldreich's Pseudorandom Generator

Yang, Jing LU ; Guo, Qian LU ; Johansson, Thomas LU orcid and Lentmaier, Michael LU (2022) In IEEE Transactions on Information Theory 68(2). p.1329-1354
Abstract

Local pseudorandom generators are a class of fundamental cryptographic primitives having very broad applications in theoretical cryptography. Following Couteau et al.’s work at ASIACRYPT 2018, this paper further studies the concrete security of one important class of local pseudorandom generators, i.e., Goldreich’s pseudorandom generators. Our first attack is of the guess-and-determine type. Our result significantly improves the state-of-the-art algorithm proposed by Couteau et al., in terms of both asymptotic and concrete complexity, and breaks all the challenge parameters they proposed. For instance, for a parameter set suggested for 128 bits of security, we could solve the instance faster by a factor of about... (More)

Local pseudorandom generators are a class of fundamental cryptographic primitives having very broad applications in theoretical cryptography. Following Couteau et al.’s work at ASIACRYPT 2018, this paper further studies the concrete security of one important class of local pseudorandom generators, i.e., Goldreich’s pseudorandom generators. Our first attack is of the guess-and-determine type. Our result significantly improves the state-of-the-art algorithm proposed by Couteau et al., in terms of both asymptotic and concrete complexity, and breaks all the challenge parameters they proposed. For instance, for a parameter set suggested for 128 bits of security, we could solve the instance faster by a factor of about 277, thereby destroying the claimed security completely. Our second attack further exploits the extremely sparse structure of the predicate P5 and combines ideas from iterative decoding. This novel attack, named guess-and-decode, substantially improves the guess-and-determine approaches for cryptographic-relevant parameters. All the challenge parameter sets proposed in Couteau et al.’s work in ASIACRYPT 2018 aiming for 80-bit (128-bit) security levels can be solved in about 258 (278) operations. We suggest new parameters for achieving 80-bit (128-bit) security with respect to our attacks. We also extend the attacks to other promising predicates and investigate their resistance.

(Less)
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Backtracking, Complexity theory, Cryptography, Generators, Goldreich’s pseudorandom generators, guess-and-decode, guess-and-determine, Iterative decoding, iterative decoding, P5, Protocols, Resistance
in
IEEE Transactions on Information Theory
volume
68
issue
2
pages
1329 - 1354
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • scopus:85119433155
ISSN
0018-9448
DOI
10.1109/TIT.2021.3128315
language
English
LU publication?
yes
id
3fc6ae26-1196-4fe6-a5cd-5e82137ce2ad
date added to LUP
2021-12-13 13:31:11
date last changed
2023-09-13 07:34:53
@article{3fc6ae26-1196-4fe6-a5cd-5e82137ce2ad,
  abstract     = {{<p>Local pseudorandom generators are a class of fundamental cryptographic primitives having very broad applications in theoretical cryptography. Following Couteau et al.&amp;#x2019;s work at ASIACRYPT 2018, this paper further studies the concrete security of one important class of local pseudorandom generators, i.e., Goldreich&amp;#x2019;s pseudorandom generators. Our first attack is of the guess-and-determine type. Our result significantly improves the state-of-the-art algorithm proposed by Couteau et al., in terms of both asymptotic and concrete complexity, and breaks all the challenge parameters they proposed. For instance, for a parameter set suggested for 128 bits of security, we could solve the instance faster by a factor of about 277, thereby destroying the claimed security completely. Our second attack further exploits the extremely sparse structure of the predicate P5 and combines ideas from iterative decoding. This novel attack, named guess-and-decode, substantially improves the guess-and-determine approaches for cryptographic-relevant parameters. All the challenge parameter sets proposed in Couteau et al.&amp;#x2019;s work in ASIACRYPT 2018 aiming for 80-bit (128-bit) security levels can be solved in about 258 (278) operations. We suggest new parameters for achieving 80-bit (128-bit) security with respect to our attacks. We also extend the attacks to other promising predicates and investigate their resistance.</p>}},
  author       = {{Yang, Jing and Guo, Qian and Johansson, Thomas and Lentmaier, Michael}},
  issn         = {{0018-9448}},
  keywords     = {{Backtracking; Complexity theory; Cryptography; Generators; Goldreich&#x2019;s pseudorandom generators; guess-and-decode; guess-and-determine; Iterative decoding; iterative decoding; P5; Protocols; Resistance}},
  language     = {{eng}},
  number       = {{2}},
  pages        = {{1329--1354}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  series       = {{IEEE Transactions on Information Theory}},
  title        = {{Revisiting the Concrete Security of Goldreich's Pseudorandom Generator}},
  url          = {{http://dx.doi.org/10.1109/TIT.2021.3128315}},
  doi          = {{10.1109/TIT.2021.3128315}},
  volume       = {{68}},
  year         = {{2022}},
}