The improved Levin’s algorithm for constrained probabilistic pseudo-Boolean functions
DOI:
https://doi.org/10.30837/rt.2025.2.221.03Keywords:
cryptographic protection of information, provably secure keystream generator, Goldreich–Levin theorem, improved Levin’s algorithm, probabilistic functionAbstract
The problem of finding “highly probable” approximations of Boolean functions consists in generating a list of all linear Boolean functions that agree with a given Boolean function in at least a specified number of binary sets. If a Boolean function is given by its truth table, the most well-known algorithm for solving this problem is the Fast Hadamard Transform. However, this method is not optimal in terms of complexity, even among deterministic algorithms. If the Boolean function is given by an oracle and depends on hundreds or thousands of variables, the application of deterministic algorithms for finding its linear approximations becomes practically infeasible. In this case, polynomial probabilistic algorithms are used, such as the Goldreich–Levin algorithm and its modifications. One of the fastest among them currently is the improved Levin’s algorithm. In the language of coding theory, this algorithm performs list decoding of the Hadamard code, which involves the value vectors of all n-variable linear Boolean functions.
This paper presents a generalization of the improved Levin’s algorithm to the case of constrained probabilistic pseudo-Boolean functions. The main result is a theorem establishing a lower bound on the probability that each sought approximation appears in a random list generated by the proposed algorithm. The consideration of such functions is necessary to extend the applicability of the improved Levin’s algorithm (in place of the original Goldreich–Levin algorithm) within the well-known framework for proving the security of stream ciphers. In particular, the results of this paper enable a more efficient reduction of problems in proofs of pseudo-randomness for certain well-known keystream generators, assuming high computational complexity of decoding random linear block codes or solving random systems of nonlinear Boolean equations. The obtained results can also be used for finding linear approximations of encryption transformations of block ciphers, which is important for constructing linear attacks against them.
References
Goldreich O., Levin L.A. A hard core predicate for all one-way functions // Proc. 21st ACM Symposium on Theory of Computing. 1989. P. 25–32.
Fischer J.-B., Stern J. An efficient pseudo-random generator provably as secure as syndrome decoding // EUROCRYPT’96: Proc. 15th International Conference on Theory and Application of Cryptographic Techniques. Springer, 1996. P. 245–255.
Gaborit Ph., Laudaroux C., Sendrier N. SYND: a very fast code-based cipher stream with a security reduction // IEEE International Symposium on Information Theory (ISIT’07). Nice, France, July 2007. P. 186–190.
Meziani M., Hoffmann G., Cayrel P.-L. Improving the performance of the SYND stream cipher // Progress in Cryptology – AFRICACRYPT 2012. Berlin : Springer, 2012. P. 99–116.
Berbain C., Gilbert H., Patarin J. QUAD: A multivariate stream cipher with provable security // Journal of Symbolic Computation. 2009. Vol. 44, № 12. P. 1703–1723.
Levin L.A. Randomness and non-determinism // Journal of Symbolic Logic. 1993. Vol. 58, № 3. P. 1102–1103.
Bshouty N., Jackson J., Tamon C. More efficient PAC-learning of DNF with membership queries under the uniform distribution // Proc. 12th Annual Conference on Computational Learning Theory. 1999. P. 286–295.
Goldreich O., Rubinfeld R., Sudan M. Learning polynomials with queries: the highly noisy case // SIAM Journal on Discrete Mathematics. 2000. Vol. 13, № 4. P. 535–570.
Kabatiansky G., Tavernier C. List decoding of Reed-Muller codes // Proc. 9th International Workshop on Algebraic and Combinatorial Coding Theory. 2008. P. 230–235.
Trevisan L. Some applications of coding theory in computational complexity : препринт № cs/0409044v1 / Luca Trevisan. Cornell University, 2004. 17 с. (arXiv:cs/0409044v1).
Fourquet R., Loidreau P., Tavernier C. Finding good linear approximations of block ciphers and its application to cryptanalysis of reduced round DES // Proc. WCC 2009. P. 501–515.
Abdouli A. S., Dumer I., Kabatiansky G., Tavernier C. The Goldreich-Levin algorithm with reduced complexity // Thirteenth International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2012). Po-morie, Bulgaria, June 15–21, 2012. P. 7–14.
Олексійчук А. М., Курінний О. В. Методи криптоаналізу потокових шифрів : навч. посіб. Київ : КПІ ім. Ігоря Сікорського, 2023. 172 с.
Dumer I.I., Kabatiansky G.A., Tavernier C. List decoding of binary first-order Reed-Muller codes // Prob-lems of Information Transmission. 2007. Vol. 43, № 3. P. 225–232.
Kopparty S., Saraf S. Local list decoding and testing of random linear codes from high-error // SIAM Journal on Computing. 2013. Vol. 42, № 3. P. 1302–1326.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
