1
$\begingroup$

If I execute a proof by reduction using a given adversary A as a subroutine to A'. How do I know that using adversary A which can solve a given hard subproblem, is the most efficient subroutine to use to solve the larger problem that A' solves?

Thanks in advance.

| improve this question | |
$\endgroup$
  • $\begingroup$ Maybe study Katz and Lindell's book: Introduction to modern Cryptography. $\endgroup$ – user2768 Nov 10 '16 at 14:32
  • 1
    $\begingroup$ I don't think that (now edited) reference is any useful without saying the title (wrt. to the level of this question) - even if one of the authors is active in this community. The title is Introduction to Modern Cryptography and is one of the common books used in university courses. $\endgroup$ – tylo Nov 10 '16 at 16:00
2
$\begingroup$

in reduction you have two problems A and B, A$\leq$B means that if you can solve problem B then you can solve problem A , now in most reductions ,the level of efficiently for the solver for A that you construct is the same as B unless you add more steps. so this means you cant know if its the most efficient , it may be and it may not.

| improve this answer | |
$\endgroup$
1
$\begingroup$

You don't, unless you specify that $A$ is the most efficient one.

But for provable security, you don't want to construct anything real and don't care about the efficiency except on the highest level (often poly time algorithm or not). You want to show, that such a real solver can not exist - under the hardness assumption. And this is usually done in a proof by contradiction.

| improve this answer | |
$\endgroup$
  • $\begingroup$ "You don't, unless you specify that A is the most efficient one." That seems like a dangerous thing to do in general. Does a "most efficient" algorithm exist? $\endgroup$ – fkraiem Dec 10 '16 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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