Revisiting the Concrete Security of Goldreich's Pseudorandom Generator
(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)
- author
- Yang, Jing
LU
; Guo, Qian
LU
; Johansson, Thomas
LU
and Lentmaier, Michael LU
- organization
- publishing date
- 2022
- 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.&#x2019;s work at ASIACRYPT 2018, this paper further studies the concrete security of one important class of local pseudorandom generators, i.e., Goldreich&#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.&#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’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}}, }