1
$\begingroup$

I have seen a few security proofs where they show that solving one problem is equivalent to solving the other, via use of an oracle.

For example, when proving that problem A is equivalent to problem B. We assume an oracle which can solve problem A in polynomial time. Are there any other ways to prove that two problems are equivalent without an oracle?

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ What is your definition of ‘equivalent’? Note: It may be helpful to read ‘oracle’ as ‘subroutine’. For example, a Rabin signature forger can be used as a subroutine in an otherwise efficient factoring algorithm, and vice versa, a factoring algorithm can be used as a subroutine in an otherwise efficient Rabin signature forger; consequently effort spent on one finding a way to solve one problem applies immediately to the other. $\endgroup$
    – Squeamish Ossifrage
    Jun 17, 2019 at 16:59
  • $\begingroup$ @SqueamishOssifrage Yep should have been clearer. So one example was that the RSA problem has polynomial equivalence to the factoring problem in terms of hardness. So if we assume the existence of an oracle/sub-routine that the adversary can use to solve the factoring problem, then we can also solve the RSA problem. I think equivalence is in terms of the problem class that each one sits in, but not 100% sure $\endgroup$
    – WeCanBeFriends
    Jun 17, 2019 at 18:49
  • 1
    $\begingroup$ RSA and factoring are known to be equivalent (and maybe with some tightness loss, I don't know) in the generic ring model. It is known that factoring can't be much easier than RSA, obviously, but RSA might be a lot easier than factoring. $\endgroup$
    – Squeamish Ossifrage
    Jun 17, 2019 at 18:54
  • 1
    $\begingroup$ What is your definition of equivalence? $\endgroup$
    – Squeamish Ossifrage
    Jun 17, 2019 at 19:14
  • 2
    $\begingroup$ What is your definition of ‘easier’ or ‘harder’? The complexity-theoretic definition of these terms—not theorem, not proof technique, but definition—is written in terms of oracles/subroutines: problem A is not much easier than problem B if there is an algorithm that solves problem B efficiently using an oracle/subroutine for problem A. $\endgroup$
    – Squeamish Ossifrage
    Jun 17, 2019 at 19:25

1 Answer 1

Reset to default
3
$\begingroup$

As Squeamish Ossifrage pointed out in the comments, if you define "B is at least as hard as A" by "there is an algorithm that solves A given an oracle that solves B", which is a relatively standard way of defining "as hard as", then the oracles show up naturally in the reduction.

Yet, it should be pointed out that this is not always the definition. What Squeamish Ossifrage discussed corresponds to black-box reductions between primitives A and B. Put otherwise, saying "A and B are black-box equivalent" is exactly the same as saying that one can solve A with an oracle for solving B, and the other way around. Intuitively, a black-box reduction is a reduction that looks only at the input/output behavior of the primitive/attack, and does not use any specific details of its concrete implementation. In this case, it makes perfect sense to represent it by an oracle, since we do not care about how it's concretely implemented.

There are, however, many non-black-box reductions in cryptography. Black-box reductions are still by far the most common; they are much easier to find (non black-box techniques are often very advanced), often more efficient, and allow for proving separations (for example, we know that one-way functions and public-key encryption are provably not black-box equivalent: we can demonstrate that there is no black-box construction of PKE from OWF). A non-black-box reduction would not involve any oracle. It would be of the following form:

If there exists an algorithm $\mathsf{Alg}_A$ that breaks the primitive $A$, then there exists an algorithm $\mathsf{Alg}_B$ which, given the code of $\mathsf{Alg}_A$ as input, can break the primitive $B$.

(or, equivalently, you can also talk about a provably secure construction of a primitive using the code of a secure construction of another primitive)

Example of non-black-box reductions in cryptography include the construction of PKE from iO and OWF; the construction of maliciously secure computation from semi-honest secure computation and zero-knowledge proofs; a bunch of specific zero-knowledge proofs by Barak; the construction of IBE from CDH; the construction of iO from functional encryption; the construction of IND-CCA-secure encryption via IND-CPA secure encryption and NIZKs (the Naor-Yung paradigm); and many others. Some of these actually achieve constructions which are provably impossible to obtain via black-box reduction (see e.g. the paper of Barak).

Improve this answer
$\endgroup$
4
  • $\begingroup$ When we say "A is as hard as B" don't we also have to show "B is as hard as A" for equivalence? $\endgroup$
    – WeCanBeFriends
    Jun 20, 2019 at 20:17
  • $\begingroup$ "If there exists an algorithm 𝖠𝗅𝗀𝐴 that breaks the primitive 𝐴, then there exists an algorithm 𝖠𝗅𝗀𝐵 which, given the code of 𝖠𝗅𝗀𝐴 as input, can break the primitive 𝐵." Related to my previous question; this would only show that the primitiveB is as hard the primitive A, but not that they are equivalent, so B<=A ? $\endgroup$
    – WeCanBeFriends
    Jun 20, 2019 at 20:21
  • $\begingroup$ Last related question: If I want to show that breaking systemA is equivalent to breaking systemB, I would need to show that a reduction both ways? $\endgroup$
    – WeCanBeFriends
    Jun 20, 2019 at 20:23
  • 1
    $\begingroup$ Yes, exactly. I only discussed reductions in one direction, i.e., showing that a primitive is at least as secure as an other. To show equivalence, you need a reduction in both directions. $\endgroup$
    – Geoffroy Couteau
    Jun 20, 2019 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.