1
$\begingroup$

If I have to argue that an assumption A is stronger than B, should I argue this way:-

An adversary breaking the security of A does not translate to breaking the security of B. But, if an adversary breaks the security of B, it can break A too.

Right? or, there are other ways to compare stonger vs. weaker assumptions.

$\endgroup$
  • $\begingroup$ Are you asking essentially how to use argumentum a fortiori in cryptography? $\endgroup$ – forest Jun 17 '18 at 2:53
1
$\begingroup$

Yes you are right. Essentially when we say $A$ is a stronger assumption than $B$, what we mean is that assumption $A$ implies assumption $B$. $A$ implies $B$ tells us that:

  • if $A$ is true, then $B$ must be true.

$A$ implies $B$ is also equivalent to $\neg B$ implies $\neg A$, thus

  • if $B$ is false, then $A$ must be false.

In cryptography, assumptions often are related to the hardness of some problems. In this context, stronger assumptions are "easier" problems that can be reduced to weaker assumptions that are "harder"problems (solving the harder problems means the easier ones are also solvable). For example, say we have the following two assumptions:

  • $A$: factoring an integer $n$ is difficult;
  • $B$: factoring an integer $n$ with only large prime factors is difficult.

Clearly, if $A$ is true, then $B$ is true; if $B$ is false, $A$ is false. If we can solve $B$ then we can use the algorithm that solves $B$ to solve $A$.

$\endgroup$

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.