On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator

DOI10.1007/s10623-023-01220-wzbMath1526.94061OpenAlexW3173200580MaRDI QIDQ6095188

Aurélien Dupin, Pierrick Méaux, Mélissa Rossi

Publication date: 7 September 2023

Published in: Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10623-023-01220-w

zbMATH Keywords

Boolean functionsalgebraic immunityresiliencylocal pseudorandom generator

Mathematics Subject Classification ID

General topics of discrete mathematics in relation to computer science (68R01) Cryptography (94A60) Boolean functions (94D10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy for local small-bias generators
• Boolean functions optimizing most of the cryptographic criteria
• Two constructions of balanced Boolean functions with optimal algebraic immunity, high nonlinearity and good behavior against fast algebraic attacks
• A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity
• Further properties of several classes of Boolean functions with optimum algebraic immunity
• Results on highly nonlinear Boolean functions with provably good immunity to fast algebraic attacks
• Basic theory in construction of Boolean functions with maximum possible annihilator immunity
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\)
• Exploring crypto dark matter: new simple PRF candidates and their applications
• Boolean functions with maximum algebraic immunity: further extensions of the Carlet-Feng construction
• Limits on the locality of pseudorandom generators and applications to indistinguishability obfuscation
• On the concrete security of Goldreich's pseudorandom generator
• Fast evaluation, weights and nonlinearity of rotation-symmetric functions
• New constructions of even-variable rotation symmetric Boolean functions with maximum algebraic immunity
• Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification
• Efficient pseudorandom correlation generators from ring-LPN
• Improved filter permutators for efficient FHE: better instances and implementations
• A construction method of balanced rotation symmetric Boolean functions on arbitrary even number of variables with optimal algebraic immunity
• How to leverage hardness of constant-degree expanding polynomials over \(\mathbb{R}\) to build \(i\mathcal{O}\)
• Indistinguishability obfuscation without multilinear maps: new paradigms via low degree weak pseudorandomness and security amplification
• Secondary constructions of Boolean functions with maximum algebraic immunity
• Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression
• Constructing odd-variable RSBFs with optimal algebraic immunity, good nonlinearity and good behavior against fast algebraic attacks
• A new construction of rotation symmetric Boolean functions with optimal algebraic immunity and higher nonlinearity
• Construction of 1-resilient Boolean functions with optimal algebraic immunity and good non\-linearity
• Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity
• Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts
• On the One-Way Function Candidate Proposed by Goldreich
• A Dichotomy for Local Small-Bias Generators
• CONSTRUCTING 2m-VARIABLE BOOLEAN FUNCTIONSWITH OPTIMAL ALGEBRAIC IMMUNITY BASED ON POLAR DECOMPOSITION OF $\mathbb{F}^\ast_{2^{2m}}$
• A CLASS OF 1-RESILIENT BOOLEAN FUNCTIONS WITH OPTIMAL ALGEBRAIC IMMUNITY AND GOOD BEHAVIOR AGAINST FAST ALGEBRAIC ATTACKS
• Candidate weak pseudorandom functions in AC ⁰ ○ MOD ₂
• Highly Nonlinear Boolean Functions With Optimal Algebraic Immunity and Good Behavior Against Fast Algebraic Attacks
• Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
• Boolean Functions for Homomorphic-Friendly Stream Ciphers
• Algebraic immunity for cryptographically significant Boolean functions: analysis and construction
• Efficient Computation of Algebraic Immunity for Algebraic and Fast Algebraic Attacks
• An Infinite Class of Balanced Functions with Optimal Algebraic Immunity, Good Immunity to Fast Algebraic Attacks and Good Nonlinearity
• On the Construction of Boolean Functions With Optimal Algebraic Immunity
• A Method of Construction of Balanced Functions with Optimum Algebraic Immunity
• Computing the Algebraic Immunity Efficiently
• On the Security of Goldreich’s One-Way Function
• Construction of Rotation Symmetric Boolean Functions with Maximum Algebraic Immunity
• Rotation-symmetric functions and fast hashing
• Construction of Highly Nonlinear 1-Resilient Boolean Functions with Optimal Algebraic Immunity and Provably High Fast Algebraic Immunity
• Algebraic Attacks against Random Local Functions and Their Countermeasures
• Cryptographic Hardness of Random Local Functions–Survey
• Construction of Resilient and Nonlinear Boolean Functions with Almost Perfect Immunity to Algebraic and Fast Algebraic Attacks
• Revisiting the Concrete Security of Goldreich’s Pseudorandom Generator
• A Novel Application of Boolean Functions With High Algebraic Immunity in Minimal Codes
• A Complete Study of Two Classes of Boolean Functions: Direct Sums of Monomials and Threshold Functions
• Boolean Functions for Cryptography and Coding Theory
• More Balanced Boolean Functions With Optimal Algebraic Immunity and Good Nonlinearity and Resistance to Fast Algebraic Attacks
• On the Resistance of Boolean Functions Against Algebraic Attacks Using Univariate Polynomial Representation
• Advances in Cryptology - EUROCRYPT 2004
• Algebraic attacks against random local functions and their countermeasures
• Construction of Rotation Symmetric Boolean Functions on Odd Number of Variables with Maximum Algebraic Immunity
• Pseudorandom generators with long stretch and low locality from random local one-way functions
• On the Algebraic Immunity of Symmetric Boolean Functions
• Enumeration of 9-Variable Rotation Symmetric Boolean Functions Having Nonlinearity > 240
• Construction and Analysis of Boolean Functions of 2t+1 Variables with Maximum Algebraic Immunity
• Fast Software Encryption
• Progress in Cryptology - INDOCRYPT 2004
• Fast Software Encryption

This page was built for publication: On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator