Reductionist proofs of decisional problems to computational
Such reductions I know are 


the reductions in hardcore predicates/functions from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions,
the reductions in (provably-secure) PRGs/PRFs from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions, and
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


If the CDH problem over elliptic curves (EC) is hard, every bit of the secret DH value is unpredictable, and
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:


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\}$.)
We can treat the predictor as a received word whose values are corrupted at most half minus non-negligible portion. 
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.