ANALYSIS OF THE EFFECTIVENESS OF THE “GUESS AND DETERMINE” ATTACK ON THE GOLDREICH PSEUDORANDO SEQUENCE GENERATOR WITH THE MODIFIED P5 PREDICT

Abstract

This article investigates the stability of a Goldreich pseudorandom sequence generator of complexity class NC⁰
with different locality 5 predicates to a “guess-and-determine” attack. The generator is a local one, in which each output
bit depends only on a fixed number of input bits, which ensures high performance and parallelism of calculations. Five
variants of the P_5 predicate are considered, differing in the position of the nonlinear element (AND): at the beginning,
inside, and at the end of the Boolean function, as well as, for comparison, a linear predicate. The aim of the work is to
determine the influence of the location of the AND element and other generator parameters on the effectiveness of the
attack, in particular, on the success rate, execution time, number of necessary guesses, and number of collisions.
Experimental studies have been conducted for the sizes of the initial values n = 16, 32, 48, 64 and different stretch
coefficients s = 1.15; 1.20; 1.25; 1.30; 1.35. It was found that the position of the AND operation and the parameters n and
s significantly affect the stability of the generator. The Gaussian method can restore the initial value with a probability of
more than 90%, which confirms the need to use nonlinear elements to ensure cryptographic stability. Predicates with
AND at the beginning or end provide the highest attack success for small values of n and s, but are characterized by a
longer execution time. In contrast, the proposed predicates with AND inside turned out to be more stable for small s, especially with increasing size n. It was found that increasing the stretch factor s simplifies the attack due to the increase
in the number of collisions, while increasing the seed size n, on the contrary, reduces its effectiveness due to the
exponential growth of the state space. The results obtained clarify the influence of the predicate structure and parameters
of the Goldreich generator on its stability and can serve as a theoretical basis for predicting their behavior with increasing
n and designing more secure cryptographic generators.
Keywords: pseudorandom sequence generator, Goldreich generator, cryptanalysis, “guess-and-determine” attack,
low locality, nonlinearity, collisions.

References
1. Röck A. Pseudorandom number generators for cryptographic applications [Electronic resource]: Master’s
thesis / A. Röck, Paris-Lodron-Universität Salzburg, 2005. 131 p. Mode of access: https://wwwroc.inria.fr/secret/Andrea.Roeck/pdfs/dipl.pdf.
2. Кіх М. Комплексне криптографічне оцінювання гібридного генератора псевдовипадкових
послідовностей на основі аудіоентропії та нелінійних булевих функцій / М. Кіх, О. Нємкова // Кібербезпека:
освіта, наука, техніка. 2025. Том 31, № 3. P. 270–282. https://doi.org/10.28925/2663-4023.2025.31.1020.
3. Мандрона М. Атаки на генератори псевдовипадкових чисел / М. Мандрона, О. Гарасимчук // Вісник
Національного університету “Львівська політехніка”. Серія: Автоматика, вимірювання та керування. 2012.
№ 741. P. 251–256. Mode of access: https://ena.lpnu.ua/items/f0830f09-b7b1-4750-b462-6d9c0006e9f1.
4. Цебак О. Методи оцінки якості та криптостійкості послідовностей, згенерованих генераторами
псевдовипадкових чисел / О. Цебак, С. Войтусік // Сучасний захист інформації. 2025. Том 64, № 4. P. 164–171.
https://doi.org/10.31673/2409-7292.2025.041218.
5. Горячий О. Дослідження множини початкових значень генераторів псевдовипадкових чисел на основі
арифметики з рухомою комою / О. Горячий, В. Максимович, М. Шабатура // Сучасний захист інформації. 2024.
Том 58, № 2. P. 91–102. https://doi.org/10.31673/2409-7292.2024.020011.
6. Kelsey J. Cryptanalytic attacks on pseudorandom number generators / J. Kelsey, B. Schneier, D. Wagner, С.
Hall // Fast Software Encryption Workshop (FSE 1998). Lecture Notes in Computer Science, Springer, Vol. 1372, 1998.
P. 168–188. https://doi.org/10.1007/3-540-69710-1_12.
7. Горячий О. Розроблення генераторів псевдовипадкових чисел на основі покращених методів обчислення
елементарних функцій для задач кібербезпеки [Електронний ресурс] : Дисертація доктора філософії / О. Горячий
Національний університет “Львівська політехніка”, Львів, 2025. 288 p. Режим доступу:
https://lpnu.ua/sites/default/files/2025/radaphd/32585/disertaciya-goryachogo-o-ya.pdf.
8. Almaraz Luengo E. Cryptographically secured pseudo-random number generators: analysis and testing with
NIST statistical test suite / E. Almaraz Luengo, J. Román Villaizán // Mathematics. 2023. Vol. 11, no. 23. 4812.
https://doi.org/10.3390/math11234812.
9. Ruhault S. Security analysis for pseudo-random number generators [Electronic resource] : Doctoral thesis / S.
Ruhault, Ecole normale supérieure, 2015. 156 p. Mode of access: https://theses.hal.science/tel-01236602v2.
10. Goldreich O. Candidate one-way functions based on expander graphs / O. Goldreich // IACR Cryptology ePrint
Archive. 2000. Report 2000/063. Mode of access: https://www.wisdom.weizmann.ac.il/~oded/COL/ow-cand.pdf.
11. Mossel E. On ε-biased generators in NC⁰ / E. Mossel, A. Shpilka, L. Trevisan // 44th Annual IEEE Symposium
on Foundations of Computer Science (FOCS 2003). IEEE, 2003. P. 136–145. Mode of access: https://faculty.
wharton.upenn.edu/wp-content/uploads/2014/07/On_Biased_Generators_in_NC0_1.pdf.
12. Applebaum B. Cryptography in NC⁰ / B. Applebaum, Y. Ishai, E. Kushilevitz // SIAM Journal on Computing.
2006. Vol. 36, no. 4. P. 845–888. Mode of access: https://www.wisdom.weizmann.ac.il/~bennyap/pubs/nc0.pdf.
13. Applebaum B. Pseudorandom generators with long stretch and low locality from random local one-way
functions / B. Applebaum // SIAM Journal on Computing. 2013. Vol. 42, no. 5. P. 2008–2037. Mode of access:
https://eccc.weizmann.ac.il/report/2011/007/download/.
14. O'Donnell R. Goldreich's PRG: Evidence for near-optimal polynomial stretch / R. O'Donnell, D. Witmer //
IEEE 29th Conference on Computational Complexity (CCC 2014). IEEE, 2014. P. 1–12. Mode of access:
https://www.cs.cmu.edu/~dwitmer/papers/csp-prg.pdf.
15. Applebaum B. Algebraic attacks against random local functions and their countermeasures / B. Applebaum, S.
Lovett // 48th Annual ACM Symposium on Theory of Computing (STOC 2016). ACM, 2016. P. 1087–1100. Mode of
access: https://dl.acm.org/doi/epdf/10.1145/2897518.2897554.
16. Couteau G. On the concrete security of Goldreich's pseudorandom generator / G. Couteau, A. Dupin, P. Méaux,
M. Rossi, Y. Rotella // International Conference on the Theory and Application of Cryptology and Information Security
(ASIACRYPT 2018). – Springer, 2018. P. 96–124. Mode of access: https://eprint.iacr.org/2018/1162.pdf.
17. Couteau G. On the concrete security of Goldreich's pseudorandom generator [Electronic resource] / G. Couteau,
A. Dupin, P. Méaux, M. Rossi, Y. Rotella // ASIACRYPT 2018. 2018. Mode of access: https://asiacrypt.
iacr.org/2018/files/SLIDES/TUESDAY/421/slides_PRG.pdf.
18. Yang J. Revisiting the concrete security of Goldreich's pseudorandom generator / J. Yang, Q. Guo, T.
Johansson, M. Lentmaier // IEEE Transactions on Information Theory. 2020. Mode of access: https://ieeexplore.
ieee.org/document/9615074.
19. Applebaum B. Structured-seed local pseudorandom generators and their applications / B. Applebaum, D. Bui,
G. Couteau, N. Melissaris // IACR Cryptology ePrint Archive. 2024. Report 2024/1027. Mode of access: https://eprint.
iacr.org/2024/1027.pdf.
20. Fu X. Attacks on Goldreich's pseudorandom generators by grouping and solving / X. Fu, M. Li, S. Lyu, C. Liu
// IACR Cryptology ePrint Archive. 2024. Report 2024/1594. Mode of access: https://eprint.iacr.org/2024/1594.pdf.