34 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 ...
Squeamish Ossifrage's user avatar
29 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 $\...
kelalaka's user avatar
  • 48.5k
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 ...
ckamath's user avatar
  • 5,198
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 ...
Elias's user avatar
  • 4,913
20 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 ...
Yehuda Lindell's 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 ...
AleksanderCH's user avatar
  • 6,445
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 ...
SEJPM's user avatar
  • 46k
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 ...
poncho's user avatar
  • 147k
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 ...
Squeamish Ossifrage's user avatar
12 votes

Cryptography based on uncomputable problems?

It is impossible to build a cryptographic algorithm using uncomputable problems because you cannot compute them. It would be impossible to execute the encryption. In order to use a problem for ...
tsen's user avatar
  • 121
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 ...
Mikero's user avatar
  • 13.3k
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 ...
Aaron Rotenberg's user avatar
11 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 ...
Mark Schultz-Wu's 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 ...
Yehuda Lindell's user avatar
11 votes
Accepted

Cryptography based on uncomputable problems?

Encryption, signatures, etc., can always be broken in NP. You can break any encryption scheme if you can solve the following decision problem: "does there exist a secret key and encryption ...
Mikero's user avatar
  • 13.3k
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 ...
mikeazo's user avatar
  • 38.6k
10 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, ...
Squeamish Ossifrage's user avatar
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: ...
simhumileco's 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, ...
Mark Schultz-Wu's user avatar
9 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 ...
Mikero's user avatar
  • 13.3k
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 ...
yyyyyyy's user avatar
  • 12.1k
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)$. ...
Artjom B.'s user avatar
  • 2,055
8 votes
Accepted

Importance of round complexity in determining the efficiency of an MPC protocol

First note that all polynomial-time functions can be securely computed with a constant number of rounds (Yao and BMR families) and all can be securely computed with protocols that have rounds ...
Yehuda Lindell's user avatar
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 ...
e-sushi's user avatar
  • 17.9k
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 ...
poncho's user avatar
  • 147k
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 ...
Mark Schultz-Wu's user avatar
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$ ...
Yehuda Lindell's user avatar
8 votes

Time Complexity Of Solving DLog When g and P are known

It's linear to the number of possible values of $n$, which is exponential in size to the number of bits used to represent $n$ in binary.
DannyNiu's user avatar
  • 9,216
7 votes

What's the difference between polylogarithmic and logarithmic?

An algorithm is said to take logarithmic time if T(n) = O(log n). An algorithm is said to run in polylogarithmic time if ...
Yaron's user avatar
  • 428
7 votes
Accepted

Computational requirements for breaking SHA-256?

First of all, are my assumptions above correct? What would the complexity of the three attacks be? I am also curious what "unit" a number like $2^{256}$ implies - is it something like ...
dusk's user avatar
  • 1,175

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