1
$\begingroup$

I recently saw a sketch relating to provable security in a book, regarding the amount of time it takes to factor N where N = pq and p,q are primes.

It says that "There is a trivial algorithm which always factors a number in time $\sqrt N$ , so there is an adversary $A$ such that $Adv_b (A, 2^{b/2}) = 1$" b is the amount of bits of $N$.

Here there is a distinction drawn between the adversary and the algorithm. However, if the algorithm can always factor a number in $\sqrt N$ why does it matter, how strong the adversary is?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ An adversary is someone who wields an algorithm. Usually adversaries are limited in computational budget. But if the book draws a distinction other than that, it would be helpful for you to quote what distinction the book claims to draw if it's not clear; otherwise we're left guessing what the author of the book might have been thinking about while writing text we can't see. $\endgroup$
    – Squeamish Ossifrage
    Commented Jun 11, 2019 at 17:30
  • $\begingroup$ "An adversary is someone who wields an algorithm." I have seen places where the adversary is assumed to be bounded computationally. If the adversary has an algorithm that can solve the problem in constant time. Why does it matter that he is computationally bounded? $\endgroup$
    – WeCanBeFriends
    Commented Jun 11, 2019 at 17:36
  • 2
    $\begingroup$ Not all algorithms will run within the adversary's budget. There's an algorithm which finds a ChaCha key given a ChaCha ciphertext by trying all $2^{256}$ possible keys, but there's no adversary who can afford to run that algorithm to completion. $\endgroup$
    – Squeamish Ossifrage
    Commented Jun 11, 2019 at 17:49
  • $\begingroup$ @SqueamishOssifrage Makes sense. If an algorithm does run within the adversaries budget, can I assume that the running time of the algorithm and the running time of the adversary are equal? $\endgroup$
    – WeCanBeFriends
    Commented Jun 11, 2019 at 18:00
  • 2
    $\begingroup$ You can use the words that way if you like, using ‘adversary’ to mean ‘cost-limited algorithm’, but it's impossible to say what the source you're reading means by it if you don't quote it. This question is unanswerable without reference to your source. $\endgroup$
    – Squeamish Ossifrage
    Commented Jun 11, 2019 at 18:04

2 Answers 2

Reset to default
3
$\begingroup$

This statement is just stating that since there exists an algorithm that can factor a number in time sqrt(N), we can use what we know about this algorithm to calculate the probability that the adversary can win an indistinguishability game against a challenger using this encryption scheme.

In other words, the algorithm is used to calculate the advantage of the adversary. Since the algorithm can factor $N$ in time sqrt(N), we must pick big enough primes, so that no probabilistic polynomial time adversary can attack the system.

Improve this answer
$\endgroup$
20
  • 1
    $\begingroup$ Yes, but we usually assume the adversary is limited by the resources available from modern day computers. This is the difference between computational security and information-theoretic security. The former allows for a small possibility of failure and takes into consideration computational limits. The latter requires a secure encryption scheme against an adversary with unlimited computational power. Because informational-theoretic security is so hard to accomplish. computational security is usually used. $\endgroup$
    – hlz2103
    Commented Jun 11, 2019 at 17:41
  • 1
    $\begingroup$ Almost. An adversary's advantage in an indistinguishability game (which is often used to prove security) is the probability above 1/2 that the adversary will win the game. In indistinguishability games, the adversary gets to choose two messages, and then guess which message was encrypted, They will always have at least 50% chance of winning (just by guessing randomly). The probability that the Adversary wins the game is 1/2 + Advantage $\endgroup$
    – hlz2103
    Commented Jun 11, 2019 at 17:49
  • 1
    $\begingroup$ Introduction To Modern Cryptography by Yehuda Lindell and Jonathan Katz is a superb resource. Chapters 2 and 3 will explain the games. Here is a link to the free PDF: repo.zenk-security.com/… . You can also buy a used edition of version 2 for pretty cheap $\endgroup$
    – hlz2103
    Commented Jun 11, 2019 at 17:59
  • 3
    $\begingroup$ In order to prove that a scheme is secure, you have to prove that the Adversary has negligible advantage over 1/2. If you cannot prove this, and the adversary's advantage is always above 1/2, then the scheme is definitely insecure. $\endgroup$
    – hlz2103
    Commented Jun 11, 2019 at 18:01
  • 1
    $\begingroup$ :) Happy to help $\endgroup$
    – hlz2103
    Commented Jun 11, 2019 at 18:01
2
$\begingroup$

However, if the algorithm can always factor a number in $\sqrt N$ why does it matter, how strong the adversary is?

In this particular case the statements made are:

  • If we can deterministically factor, we can deterministically break RSA.
  • If we can factor in time $\sqrt N$ then our adversary also runs in time $2^{b/2}\approx \sqrt N$.

While these may be somewhat obvious in this case, for different algorithms the factoring may be probabilistic and then there would be a relation of the impact of this probability on the advantage. In general this notation was probably used for the purpose of consistency.

Improve this answer
$\endgroup$
0

Your Answer

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

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