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 ...
- 49.5k
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
$\...
- 49.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 ...
- 5,488
22
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 ...
- 4,933
21
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 ...
- 28.2k
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 ...
- 6,511
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 ...
- 46.4k
13
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 ...
- 49.5k
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 ...
- 151k
12
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, ...
- 49.5k
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 ...
- 121
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 ...
- 211
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 ...
- 14.6k
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 ...
- 28.2k
11
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, ...
- 14.6k
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 ...
- 14.5k
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 ...
- 38.9k
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:
...
- 224
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 ...
- 14.5k
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 ...
- 18.1k
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 ...
- 151k
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 ...
- 14.6k
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$ ...
- 28.2k
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.
- 9,795
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 ...
- 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 ...
- 1,175
7
votes
Why don't table lookups run in constant time?
I just wanted to extend poncho's answer as aspects of this question keep coming up. Generally speaking, you can write constant-time portions of software if you have privileged OS access, but it's not ...
- 4,948
7
votes
Can you explain what an NP statement is when they refer to it in Zero knowledge proofs?
Intuitively, an NP problem is one
that if you have a solution it is computationally easy to verify it, but it is not known if it is also computationally easy to find. Of course there exist formal ...
7
votes
Accepted
Induction is problematic in computational cryptography - Why?
The problem with induction is what it typically hides. I'll give an example. Assume that I want to prove that $n$ samples of $X$ is indistinguishable to $n$ samples of $Y$, assuming that a single ...
- 28.2k
7
votes
Accepted
Are there post-quantum cryptosystems with a gap between classical and quantum security?
Here's an example where the best known quantum attack is, in a sense, just "halfway" between the best known classical attack on one side, and a complete break on the other:
Inverting a cryptographic ...
- 12.2k
Only top scored, non community-wiki answers of a minimum length are eligible