# Reductionist proofs of decisional problems to computational

Are they any reductionist proofs where an attacker $\mathcal{I}$ for a well established computationally "hard" problem $\mathsf{Π}$ is employing an attacker $\mathcal{A}$ who we assume is able to break a decisional problem $\mathsf{Γ}$ (i.e: semantic security->guess if $b=1$ or $b=0$) in order $\mathcal{I}$ to break $\mathsf{Π}$ and if so to conclude that $\mathsf{Γ}$ is as secure as $\mathsf{Π}$, meaning that if there exists $\mathcal{A}$, we can build $\mathcal{I}$?

Further explanation:

Typically when there is a reduction to a decisional hard problem then in your construction either you model your security with an adversary that breaking the system means that the attacker should compute something or it has to distinguish something (indistinguishability games in order $\mathcal{A}$ to guess $b$ from an encryption of $x_b$). And this attacker is used as a subroutine by the well established problem attacker in order to break his scheme.

Let’s say that the attacker in our model is able to distinguish encryption $x_0$ from encryption $x_1$. This doesn't mean that the attacker is revealing the underlying key, nor that it has to compute something. It means that it can only distinguish. I have hard understandings how such attackers can be used as subroutines for well-established computational problems where an attacker $\mathcal{B}$ has to compute something instead of distinguish (or decide). And I would like to know if such reductions exist or if – from theory – you can never reduct from decisional to computational. I.e: CDH cannot use a DDH attacker to compute $g^{ab}$ but it is the other way around.

-
Do you need more explanation or easier one, e.g., "SearchLWE vs DecisionalLWE"? –  xagawa Jun 1 '14 at 12:44
This is somewhat related to the concept of "Gap problems". As an example (mentioned by @Xagawa), LWE doesn't seem to admit a Gap-related problem, i.e., a computational problem which is still hard when using an oracle for the decisional version, since in the case of LWE, both SearchLWE and Decisional LWE are proven equivalent. But this is not always the case, so there are computational problems that are still hard even with a decisional oracle. –  cygnusv Feb 25 at 16:18

A classic example of this sort of thing would be the Goldreich-Levin hard-core bit for an arbitrary one-way function.

The proof of security for the Goldreich-Levin construction involves showing that if Mallory can predict this single-bit value (even with probability slightly better than $1/2$), then it is possible to invert the one-way function. Thus, this is a reduction where the subroutine has just the ability to distinguish (to predict a single-bit value). The reduction shows how to use this to solve a computational problem (to invert a one-way function). The core of the algorithm shows that if Mallory can distinguish $(r_i, x \cdot r_i)$ from $(r_i, b_i)$ (where $b_i$ is a random bit, $r_i$ is a random $n$-bit value, and $x_i$ is a secret $n$-bit value), then we can use Mallory as a subroutine to learn the secret value $x$.

For further details on the Goldreich-Levin construction, I recommend Luca Trevisan's lecture notes: https://lucatrevisan.wordpress.com/2009/03/09/cs-276-lecture-11-one-way-functions/ and https://lucatrevisan.wordpress.com/2009/03/09/cs276-lecture-12-goldreich-levin/. Notice especially Theorem 1 on the latter page, which is a reduction of the form you asked for. Or, you can read Mihir Bellare's presentation of the Goldreich-Levin construction and associated proof of correctness, to see a different exposition of the same result.

-
Thank you. Very educative and precise analysis –  curious Jun 2 '14 at 7:37
This is also another right-up towards this direction cseweb.ucsd.edu/~mihir/papers/gl.pdf –  curious Jun 2 '14 at 8:50

Such reductions I know are

1. the reductions in hardcore predicates/functions from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions,
2. the reductions in (provably-secure) PRGs/PRFs from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions, and
3. the reductions in LPN/LWE.

# Re:

Can you be more specific? I.e: with CDH ? How CDH can be broken using a decisional problem attacker? ? curious yesterday

Very recently, Fazio, Gennaro, Milinda Perera, and E. Skeith III (CRYPTO 2013) proved that

1. If the CDH problem over elliptic curves (EC) is hard, every bit of the secret DH value is unpredictable, and
2. If the partial CDH problem over the finite field $\mathbb{F}_{p^2}$ is hard, every bit of the secret DH value is unpredictable.

## Overview.

Let $P:\mathbb{G} \to \{0,1\}$ is a predicate that is a candidate of hard core of the CDH function, $f(xg,g^a,g^b) = g^{ab}$.

We want to construct $\mathcal{I}$ that, given $g,g^a,g^b$, computes $g^{ab}$ by using a predictor $\mathcal{A}$ that predicts $P$ with non-negligible advantage.

Fazio et al. adopted a general framework proposed by Akavia, Goldwasser, and Safra (FOCS 2003), which can be considered as an extension of the proof strategy for the Goldreich-Levin general hardcore predicate.

The framework of Akavia et al. is summarized as follows:

1. We define a multiplication code that $\mathcal{C} = \{C_x:\mathbb{Z}_N \to \{0,1\} \mid x \in \mathbb{Z}_N\}$, where $$C_x(k) = P(k \cdot x).$$ Imagine a very long codeword of length $N$ whose $k$-th value is $P(k \cdot x)$. (Since they will consider the Fourier transformation, $\{0,1\}$ will be replaced with $\{-1,+1\}$.)
2. We can treat the predictor as a received word whose values are corrupted at most half minus non-negligible portion.
3. The reduction algorithm now uses a list-decoding algorithm to find out candidates of $x$. If the candidates are few, the reduction algorithm outputs one of them. (In the CDH case, we cannot verify whether the guess is correct or not.)

Akavia et al. constructed the list-decoding algorithm for "good" multiplication codes and showed several candidates of one-way functions are "good." Fazio et al. defined multiplication codes for EC-CDH and PartCDH and showed their "good" properties.

-