33 votes
Accepted

What are standard cryptographic assumptions?

I am struggling to understand what is meant by "standard cryptographic assumption". ‘Standard assumption’ broadly means an assumption that has withstood the scrutiny of many smart cryptanalysts for a ...
user avatar
27 votes
Accepted

How reassuring is 64-bit (in)security?

TL;DR; Just give me the numbers; Machines in a second in an hour in a day in a year Summit on SHA-1 $\approx 2^{49.7} $ $ \approx 2^{61.5}$ $\approx 2^{66.1}$ $\approx 2^{74.6}$ Titan on SHA-1 $\...
user avatar
  • 43.4k
22 votes

Why are only lattice problems used in cryptography?

What makes a problem suitable for cryptography is slightly different than what makes a problem NP-hard. What is required for cryptography is average-case hardness --- i.e., a randomly selected ...
user avatar
  • 4,493
21 votes
Accepted

What's the difference between polylogarithmic and logarithmic?

Definitions: An algorithm is said to run in logarithmic time if $T(n) = O(log(n))$ polylogarithmic time if $T(n) = O(log(n)^k)$ (also written as $T(n) = O(log^k(n))$) That means they are the same ...
user avatar
  • 4,691
19 votes

How reassuring is 64-bit (in)security?

There is a huge difference between $2^{-64}$ probability of failure, which is indeed very small, and having to run $2^{64}$ in order to carry out the attack. The latter is much too small to be ...
user avatar
15 votes

What happens for factoring algorithms if P=NP?

Proving P=NP would not necessarily give you an algorithm, because there are many different methods to prove something (i.e. Direct proof, Proof by contradiction, etc.). But it is shown that if you ...
user avatar
  • 6,326
14 votes
Accepted

Why does applying 56-bit DES twice only give 57 bits of security?

Decrypt the ciphertext with every possible key and store the result: $2^{56}$ decryptions. Now encrypt the (known) plaintext of the ciphertext with every possible key: $2^{56}$ encryptions. Now you ...
user avatar
  • 3,820
14 votes
Accepted

Why do look up tables speed things up compared to brute force?

Suppose you have an $n$-bit key. Suppose further you have some reliable predicate $P(k,m)$ which decides whether a key $k$ is the key you are looking for given the reference $m$. Furthermore, suppose ...
user avatar
  • 44.6k
13 votes
Accepted

uniform vs. non-uniform PPT

Your observations are basically correct. Informally it is as follows: For a uniform PPT algorithm think of a fixed Turing machine that has access to some random tape and the output of the algorithm is ...
user avatar
  • 12.1k
13 votes

Why don't table lookups run in constant time?

It mostly has to do with the real world influence of memory caches. A cache is a small amount of fast memory; when you read from memory, the contents are placed in this fast memory (possibly along ...
user avatar
  • 132k
12 votes
Accepted

Is there a cryptography algorithm that will remain safe if P=NP?

Whether P = NP is a question about the asymptotic growth of computational costs of algorithms as functions of input sizes. It may provide hints about concrete computational cost estimates of ...
user avatar
11 votes
Accepted

Practical differences between circuits and turing machines for cryptography

Just looking for a Turing machine vs circuit is a bit misleading. The important distinction is uniform (complexity class BPP) vs non-uniform (complexity class P/poly) adversaries. You can characterize ...
user avatar
  • 10.6k
11 votes
Accepted

Is it possible to construct an encryption scheme for which breaking is NP complete but there nearly always exists an efficient breaking algorithm

The Merkle–Hellman knapsack cryptosystem (Wikipedia article) is the canonical example of this. It was designed to rely on the difficulty of the subset sum problem, which is NP-complete. However, ...
user avatar
11 votes

What happens for factoring algorithms if P=NP?

Bill Garsarch just posted about this the other day. The short answer is that there is an explicit algorithm, which is known today, such that if P = NP (or even just FACTORING ∈ P) then the ...
user avatar
11 votes
Accepted

Why Zero-Knowledge protocols are used for NP problems if IP is the class of interactive proof systems where they come from?

The reason is that essentially, the class of languages in $\mathcal IP$ that are not in $\mathcal NP$ cannot be proven with an efficient prover. Since we are typically interested in the cryptographic ...
user avatar
10 votes
Accepted

For security, need a 1-1 crypto-mapping be NP-complete?

NP is about worst case hardness. An NP-hard problem can in fact be very easy to solve for the majority of cases. This would obviously be a poor cryptographic system. Further, some NP-hard problems may ...
user avatar
  • 37.7k
10 votes
Accepted

What is meaning of the term "language"?

The concept of language has been systematized. For example here you can become familiar with this in an accessible way. In the article you are reading the language has such meaning: Wikipedia BQP: ...
user avatar
10 votes
Accepted

Notion of elementary operation when complexities in the form of $2^{128}$

For other algorithms, the big-O notation usually hides the constant factors, making the exact elementary operation an unimportant detail. But the cryptographic papers state the complexities exact, ...
user avatar
  • 8,637
9 votes
Accepted

Why is AES unbreakable?

First, it's not said that AES is unbreakable, merely that none of the currently known attacks reduce the computational cost to a point where it's feasible. The current best attack on AES-128 takes 2^...
user avatar
9 votes
Accepted

What does it mean for an adversary to run in PPT?

An algorithm being probabilistic means that it is allowed to "throw coins", and use the results of the coin throws in its computations. This is reasonable because a realistic adversary has access to ...
user avatar
  • 7,904
9 votes
Accepted

Why do Problems for Post-Quantum algorithms have to be NP-Hard?

I am unaware of cryptography that is hard solely assuming that $P\neq NP$, so I believe you are misunderstanding something. I know the story best when it comes to lattices, so I'll discuss why ...
user avatar
  • 8,637
8 votes

How fast would a polynomial time factoring algorithm compute?

I know an algorithm that runs in polynomial time would be able to break an RSA key pair "quickly". But how quickly is "quickly"? No way to say, it might be microseconds, and it might be large ...
user avatar
  • 132k
8 votes

Running time of Shamir's secret sharing scheme

Is the running times of corresponding steps true? No. Step 3 of the dealer has to be executed $n$ times (once for each party) with each execution taking $O(t)$ time. So it must be $O(t\cdot n)$. ...
user avatar
  • 2,015
8 votes
Accepted

Is AES solvable by reducing to SAT?

Is AES solvable in this way? In other words, will the algorithm eventually complete, producing the correct key? Almost yes. It will produce some correct key — there might be more than one. (It ...
user avatar
  • 11.1k
8 votes
Accepted

What is the difference between Argon2d and Argon2i?

As @sejpm already hinted in his comment: both scale the same when it comes to the parameters. You might still want to read the RFC to get the complete picture, but the general differences can be ...
user avatar
  • 17.4k
8 votes
Accepted

Space complexity and cryptography

Maybe there is an encryption scheme out there that can be 'broken' in polynomial time, but only with super-polynomial space. That possibility can be excluded; if an algorithm uses $F(x)$ time (for ...
user avatar
  • 132k
8 votes

Why do we focus on polynomial time, rather than other kinds of time?

The focus on polynomial time comes from cryptography's historical origin as a branch of computational complexity. It makes sense for a theoretical field to develop technology-independent ways of ...
user avatar
  • 10.6k
8 votes
Accepted

If OWF were to exist, do we know for sure that one of the candidate OWF would indeed be a OWF?

Yes, you are looking for the notion of a universal one-way function. Rafael Pass/abhi shelat's notes contain a construction on page 49. The construction is "unnatural" in the sense that it ...
user avatar
  • 8,637
8 votes
Accepted

Is Indistinguishability Obfuscation Real?

First, the wikipedia article stated that the assumption required a PRG with an exponential stretch. This is not correct, and I have edited the article. Rather, the requirement is for a PRG in $NC_0$ ...
user avatar
7 votes

How can complexity be increased or decreased in AES?

This begs the question, why would you in any real-world circumstance wish to reduce the difficulty for an attacker to break your cryptosystem? To answer your question practically, the only reasonable ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible