Given you a protocol, if we can reduce breaking the protocol to a hard problem,

Question

Given you a protocol, if we can reduce breaking the protocol to a hard problem, such as DLP or CDH, then we can say that this protocol is secure.

Theoretically speaking, reduction is a good method to prove the security of a protocol. As to key-exchange protocols, if the reduction method uses the adversary as a subroutine, then the simulator will construct an algorithm. If the adversary can break the protocol under a certain model then the simulator can solve a hard problem, say CDH.

But in practice, can the algorithm constructed by the simulator can be realised with a computer program? And does it really work?

Explanation / Answer

The idea of proofs by reduction is that it should be possible to turn a real adversary into an algorithm doing some "useful" computation. So yes and yes.

However, sometimes, reductions are weak, in the sense that even if the real adversary is feasible (can be run in reasonable time on reasonable computers), the resulting algorithm doesn't have to be feasible. The algorithm can be constructed as a computer program, but it doesn't really work. So that's yes and no.

Sometimes, we also have even weaker proofs, so-called existence proofs. They only prove that if an adversary exists, then an algorithm doing some "useful" computation exists. Which means that even if we are given an adversary, we don't really know how to construct the algorithm doing that "useful" computation. So that's no and no.

Modern cryptography recognizes all of these differences. Reductions that work are best. Weak reductions are considered solid evidence of security, but leaves something to be desired. The even weaker reductions are sometimes considered evidence of security, and sometimes leave a lot to be desired.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.