First, I would like to second that nearly all of cryptography is based on "computational" decision problems.
It sounds like you want cryptography based on (computational still) search problems.
Cryptography not based on computational problems exists as well (for example the one-time pad), but generally has severely limited applicability for efficiency reasons.
As for cryptography based on search problems, there are some natural candidates.
Namely, if one pairs
- cryptography based on some decision problem $D$, and
- a "search to decision" reduction involving that problem $D$
then you can get cryptography based on a search problem.
If such a reduction existed between CDH and DDH, it would answer your question.
Such reductions do exist in lattice-based cryptography, at least in parts.
So one can in principle take some lattice-based cryptosystem (defined relative to the decision variant of LWE) and then apply a search-to-decision reduction to obtain a cryptosystem based on the search variant of LWE.
This seems morally similar to me to the setting of starting with a cryptosystem defined relative to DDH and then getting a cryptosystem defined relative to CDH, which is what you alluded to wanting.
Anyway, for plain LWE these exist, see for example this paper.
For RLWE they exist as well, but are somewhat more complex/limited iirc. I won't bother looking for details, because one can concretely simply combine the above paper with an LWE-based PKE scheme, for example FrodoKEM, to answer your question.
