Intractability Flashcards
What is naive exponentiation and why isnt it efficient for large exponents? What can we do instead?
“Naive exponentiation” refers to the basic method of calculating an exponent by multiplying the base number by itself the required number of times. While this method is straightforward and easy to understand, it is not efficient for large exponents. The number of multiplications required grows exponentially with the exponent, which can be computationally expensive for large numbers. We can instead apply square and multiply.
How can you compute square and multiply?
if x is even
a^(x/2)^2 (mod N)
if x is odd
a(a^(x-1)/2)^2 (mod N)
What makes a problem intractable/hard?
A problem is hard if there exists a game setup, such that all probabilistic and polynomial-time adversaries A only have negligible success probability.
Whats the efficiency of square and multiply?
Using the square-and-multiply algorithm makes modular exponentiation much more efficient than naive exponentiation for large numbers. Instead of being exponential in the number of bits of x , it is cubic in the number of bits of the numbers involved.
What is the best known algorithm to break factoring (DH/RSA)?
General Number Field Sieve
Briefly explain the RSA Assumption
For x^e = y (mod N) an adversary is successful if they can correctly identify x given N, e and y
How do we know that diffie helman is actually secure?
From the decisional diffie helman assumption (that is based on the discrete logarithm problem) that states that it is computationally hard to distinguish between the pair g ^xy and g^z given a group G, a generator g, and random exponents x and y. The assumption implies that, for an adversary, it is difficult to decide whether a given value K is the result of raising g to the power of a random exponent z or is the result of raising g to the power xy without additional information. This assumption is fundamental to the security of many cryptographic protocols, including the Diffie-Hellman key exchange.
