Reductionist proofs of computational problems to decisional

Question

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.

Answer 1

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.

Answer 2

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.

Their slides are avilable at Milinda Perera's website.

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.

Answer 3

This comes up frequently in security proofs in the random oracle model. Consider a simple example of hashed Diffie-Hellman:

• Alice chooses random exponent $a$ and sends $A = g^a$
• Bob chooses random exponent $b$ and sends $B = g^b$
• Both parties can compute the shared key $K = H(g^{ab})$

The security of this key agreement scheme is that $(A,B,K)$ is indistinguishable from $(A,B,K')$, where $K'$ is a uniform key chosen independently from $A,B$. This is a decisional property.

But the key agreement scheme is secure assuming the CDH assumption -- a computational assumption -- when $H$ is a random oracle.

In the random oracle model, the value $H(y)$ is uniformly distributed, to any distinguisher who has never queried $H$ at the point $y$. This is almost the definition of a random oracle. In this key agreement protocol, $K = H(g^{ab})$ is uniform to any eavesdropper who is unable to query $H$ at the point $g^{ab}$. But the CDH assumption says that it is hard to compute the value $g^{ab}$ (and hence hard to send that value to the $H$ oracle) given what the eavesdropper sees. In other words, an eavesdropper can query $H$ at $g^{ab}$ with only negligible probability.

More generally, a reduction algorithm can run the adversary and "see" what queries it makes to the random oracle. The reduction algorithm can then use these queries to break a computational assumption.

Answer 4

Here are some search-to-decisions reductions I'm aware of.

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence shows a reduction from some decision problem (I don't know the name for this decision problem) to average-case search HHP (Hidden Hyperplane Problem), and a reduction from search HHP to worst-case uSVP (unique Short Vector Problem).

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography shows a quantum reduction from approximate SVP (particularly discrete Gaussian sampling), GapSVP, and SIVP, to search-LWE; and a classical reduction from search-LWE to decision-LWE.

Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem shows a classical reduction from decision LWE to GapSVP (but requires exponential modulus).

On Ideal Lattices and Learning with Errors Over Rings has a search-to-decision for Ring-LWE.

Pseudorandomness of Ring-LWE for Any Ring and Modulus extends search-to-decision to more choices of rings and moduli.

On the hardness of the NTRU problem has a number of reductions between variants of the NTRU problem, including search-to-decision.

All the decisional problems above have an associated IND-CPA public-key cryptosystem.