Improved Search-to-Decision Reduction for Random Local Functions

1. Problem Statement

The paper addresses the fundamental problem of Search-to-Decision Reductions for Random Local Functions.

• Random Local Functions: These are functions $f_{G,P}: \mathbb{F}_2^n \to \mathbb{F}_2^m$ where each output bit is computed by applying a fixed $d$-ary predicate $P$ to $d$ randomly chosen input bits. The structure is defined by a hypergraph $G$ (the connectivity) and the predicate $P$.
• The Core Question: If an adversary can efficiently distinguish the output of such a function from a random string (the Decision Problem), can they also efficiently invert the function to find the secret input (the Search Problem)?
• Context: Random local functions are candidates for One-Way Functions (OWF) and Pseudo-Random Generators (PRGs). Proving that "Decision $\implies$ Search" is crucial for establishing their security as PRGs.
• Limitations of Prior Work: Previous reductions (e.g., Applebaum [App12]) required the predicate $P$ to be sensitive (flipping one input bit always flips the output). This restriction excluded many potentially secure predicates. Furthermore, existing reductions often incurred significant overhead in the number of output samples required.

2. Methodology and Techniques

The authors present a new reduction that works for any constant-arity predicate, removing the sensitivity requirement. The core of their approach relies on hybrid arguments and graph transformations rather than constructing intermediate "next-bit predictors."

Key Technical Components:

1. Randomized Hypergraph Transformations ($T_{a,b}$):

   • The authors define a transformation $T_{a,b}$ on the hypergraph $G$. For a chosen pair of indices $(a, b)$, if a hyperedge contains $a$ or $b$, that vertex is randomly replaced by either $a$ or $b$ with probability $1/2$. Vertices not in $\{a, b\}$ remain unchanged.
   • Mixing Property: Repeated application of these random transformations acts as a Markov process that "mixes" the hypergraph. After $t = O(n \log(n/\epsilon))$ steps, the transformed hypergraph becomes statistically indistinguishable from a uniformly random hypergraph, regardless of the initial structure.

2. Hybrid Argument:

   • The proof constructs a sequence of hybrid distributions $H_0, H_1, \dots, H_t$.
   • $H_0$ corresponds to the "planted" distribution (real function output).
   • $H_t$ corresponds to the "null" distribution (random string).
   • The transition from $H_i$ to $H_{i+1}$ involves applying one random transformation.
   • If a distinguisher $\mathcal{D}$ has advantage $\epsilon$ in distinguishing $H_0$ from $H_t$, there must exist a step $i$ where $\mathcal{D}$ distinguishes $H_i$ from $H_{i+1}$ with advantage $\approx \epsilon/t$.

3. Predictor Construction without Sensitivity:

   • Unlike prior works that relied on the sensitivity of $P$ to predict specific bits, this method constructs predictors $S_i$ to determine the relationship between two secret bits, specifically $s_1 \oplus s_i$.
   • The Logic:
     • If $s_1 = s_i$, the transformation $T_{\pi(1), \pi(i)}$ (applied to a permuted hypergraph) does not change the function output distribution significantly because the inputs to the predicate are identical. The distribution remains close to the planted hybrid.
     • If $s_1 \neq s_i$, the transformation introduces randomness that decouples the output from the specific secret, pushing the distribution closer to the null (random) distribution.
   • By running the distinguisher on these transformed instances, the algorithm can detect the correlation between $s_1$ and $s_i$ with a small advantage.

4. Amplification:

   • Since the advantage per bit relationship is small ($\approx \epsilon/t$), the algorithm uses Hoeffding's inequality to amplify this advantage. By repeating the predictor $O((t/\epsilon)^2 \log n)$ times, it recovers the relationship $s_1 \oplus s_i$ with high confidence.
   • By guessing $s_1$ (2 possibilities) and recovering all $s_i$ relative to it, the full secret $s$ is recovered.

3. Key Contributions

1. Removal of Sensitivity Requirement: The primary contribution is a search-to-decision reduction that works for any $d$-ary predicate $P$, not just sensitive ones. This significantly broadens the class of local functions that can be proven secure based on the hardness of the decision problem.
2. Improved Sample Complexity: The reduction requires $O(m(n/\epsilon)^2 \log^3(n/\epsilon))$ outputs to invert a function with $m$ outputs and distinguishing advantage $\epsilon$. While this has a polynomial loss factor in $n$ compared to sensitive predicates, it is a generic solution for non-sensitive cases.
3. Generalizations:
   • Non-Constant Arity: The technique extends to super-constant arity $d = \text{polylog}(n)$ under specific conditions on $m$ and $\epsilon$.
   • Distinct Vertices: The reduction works even if the hypergraph requires distinct vertices in each hyperedge (a stricter model than allowing repeated vertices).
   • Noisy Predicates: The method adapts to predicates with added Bernoulli noise (relevant to the Learning Parity with Noise - LPN - problem).

4. Main Results

• Theorem 1.3 (Informal): Given a polynomial-time distinguisher with advantage $\epsilon$ for the decision problem of a random local function defined by any $d$-ary predicate $P$, there exists a polynomial-time algorithm that inverts the function with success probability $\Omega(\epsilon)$, using $O(m(n/\epsilon)^2 \log^3(n/\epsilon))$ outputs.
• Implication for PRGs: If a family of local functions is one-way (hard to invert), then a related family with shorter output length constitutes a Pseudo-Random Generator (PRG). Combined with the "weak-to-strong" compiler (Applebaum & Kachlon), this implies that one-way local functions can be transformed into strong local PRGs with negligible distinguishing advantage.

5. Significance and Impact

• Cryptographic Foundations: This work strengthens the theoretical foundation for using random local functions as cryptographic primitives. By removing the "sensitivity" constraint, it validates a wider range of predicates for use in One-Way Functions and PRGs.
• Connection to CSPs and LPN: The results deepen the understanding of the relationship between random Constraint Satisfaction Problems (CSPs) and cryptographic hardness. The generalization to noisy predicates directly impacts the security analysis of the Learning Parity with Noise (LPN) problem, a cornerstone of post-quantum cryptography.
• Technique Novelty: The approach of using random graph transformations to "mix" the hypergraph and create a hybrid argument is a novel technique in the field of local cryptography. It avoids the structural dependencies on the predicate that plagued previous reductions, suggesting potential applications in other areas of average-case complexity and learning theory.
• Optimality Gap: The authors acknowledge that their reduction is currently $\tilde{O}(n^{1.5})$ away from the optimal sample complexity known for sensitive predicates. However, they provide a framework that future work can potentially refine to close this gap.

In summary, this paper provides a robust, general-purpose reduction that decouples the security of random local functions from the specific algebraic properties of the predicate, significantly advancing the state of the art in local cryptography.