Questions tagged [complexity]
Complexity describes - in simple words - how hard (complex) it is to reach a specific goal; and under which conditions. In cryptography, this mostly ends up in using the complexity theory to analyze things. One of the main goals of complexity theory is to prove lower bounds on the resources (e.g. time and/or space) needed to solve a certain computational problem. Cryptography can therefore be seen as the complexity theory's main field of use.
267
questions
31
votes
2
answers
5k
views
What are standard cryptographic assumptions?
I am struggling to understand what is meant by "standard cryptographic assumption".
The Wikipedia artice on the Goldwasser–Micali system (GM) reads "GM has the distinction of being the first ...
- 617
20
votes
1
answer
10k
views
uniform vs. non-uniform PPT
I'm trying to understand PPT and in particular what the differences are in uniform and non-uniform PPT's. First, this is how I see it:
A probabilistic polynomial-time (PPT) algorithm $A$ is an ...
- 485
19
votes
2
answers
2k
views
Practical differences between circuits and turing machines for cryptography
In formal cryptography, we model algorithms (mostly our adversaries) as (Probabilistic) Turing Machines or as boolean circuits. In our lecture on formal cryptography, we learned that circuits are more ...
- 1,430
19
votes
1
answer
1k
views
Quantum complexity of LWE
As per my understanding, LWE is quantum secure because there is no known quantum algorithm to solve LWE in polynomial time. Due to the reductions given by Regev et al., if there is any algorithm that ...
- 1,265
17
votes
2
answers
11k
views
What's the difference between polylogarithmic and logarithmic? [closed]
I can't imagine one that is not polylogarithmic
but logarithmic.
$O(\log N)$ satisfies both.
What about $O(\log^{3}N)$, $O(\log^{100}N)$, and $O(\log^{10000}N)$ ?
Let's say $N=10^{10}$
- 1,605
15
votes
2
answers
6k
views
How reassuring is 64-bit (in)security?
In Feb 2017, CWI and Google announced SHAttered hash collision attack on SHA1, which took $2^{63.1}$ work estimated 6500 CPU years, to achieve. Therefore, 64-bit should be considered now an insecurity....
- 9,207
14
votes
3
answers
1k
views
Why are only lattice problems used in cryptography?
There are thousands of NP-hard problems out there. Why have only lattice problems been applied to cryptography?
- 239
13
votes
3
answers
4k
views
What happens for factoring algorithms if P=NP?
If someone ever demonstrates that P=NP, will it give us a polynomial factoring algorithm, or will it only tell us that such an algorithm exists, but we still have to find it?
- 217
13
votes
1
answer
4k
views
What does "running in polynomial time" really mean?
I'm currently learning private-key cryptography. I've been able to see that perfect secrecy is achievable if no assumption is made about the computational power of the attacker.
However, perfect ...
- 231
12
votes
2
answers
844
views
Is it possible to construct an encryption scheme for which breaking is NP complete but there nearly always exists an efficient breaking algorithm
The question stems from the fact that foundations of crypto states:
suppose breaking an encryption scheme is NP-complete, then P != NP implies that this encryption is hard to break in the worst case, ...
- 435
11
votes
5
answers
4k
views
Can you explain what an NP statement is when they refer to it in Zero knowledge proofs?
When I read about zero knowledge proof, I keep encountering the term NP-statement. I am aware of complexity classes but I am a little unclear on how it ties up to NP-statement.
I came across the ...
- 313
11
votes
4
answers
6k
views
What is the largest performed/possible bruteforce attack to date?
I've read that cracking 128-bit key is currently out of reach of all humanity. However, I can't seem to find any information on what scope of brute force attacks have been performed or are possible at ...
- 1,679
10
votes
2
answers
3k
views
Why is the complexity of RSA-1024 80 bit and not 86 bit?
Why is the complexity of RSA-1024 80 bit and not 86.76611925028119 bit?
Here is the complexity for the GNFS (pulled from the linked Wikipedia
article):
$$\exp\left( \left(\sqrt[3]{\frac{64}{...
- 425
10
votes
0
answers
151
views
Hardness of iterated squaring in Paillier group
The (computational) problem of iterated squaring (IS) in the RSA group is defined as follows, where $\leftarrow$ denotes sampling uniformly at random:
Input: $(N,x,T)$, where $N$ is the RSA modulus, $...
- 5,188
9
votes
2
answers
1k
views
What is meaning of the term "language"?
I don't have much formal background, and I could not find a suitable explanation for this after searching on Google/Wikipedia.
What is the meaning of the term "language" as used in cryptographic ...
- 737
9
votes
1
answer
7k
views
What does it mean for an adversary to run in PPT?
I've been reading this question where a detailed description of mine is given, I've understood that a polynomial-time adversary is an adversary for which the only feasible strategy are those that take ...
- 3,952
9
votes
1
answer
3k
views
A discrete-log-like problem, with matrices: given $A^k x$, find $k$
Let $p$ be a large prime; we will work in $GF(p)$. Let $A$ be a $n\times n$ matrix. Also, let $x$ be a $n$-vector and $k$ a positive integer.
Suppose we are given $p$, $A$, $x$, and $y$. The goal ...
- 36.4k
9
votes
0
answers
726
views
Can LWE be NP-hard?
Regev's reduction shows that LWE is quantumly at least as hard as CVP with an approximation factor of $n/\alpha$ for $0<\alpha<1$. But I just watched this talk which said that if $\sqrt{n/\log n}...
- 1,137
9
votes
0
answers
456
views
how to understand the universal hash and the leftover hash lemma [closed]
I always meet the leftover hash lemma when I read some papers.But I only know the defination of universal hash and the leftover hash lemma.How to understand them and how to use them?
- 239
8
votes
3
answers
4k
views
Complexity of arithmetic in a finite field?
I am wondering what the complexities are of adding/subtracting and muliplying/dividing numbers in a finite field $\mathbb{F}_q$. I need it to understand an article I am reading.
- 181
8
votes
3
answers
590
views
Pen-and-paper one-way function for externally-anonymous survey
When conducting surveys, an Administrator might send an Enumerator to survey a Respondent. For "sensitive" questions (e.g. about embarrassing behavior), the Respondent may be fine with the truth being ...
8
votes
3
answers
2k
views
Discrete log problem, when we have many examples
Suppose I have many instances of the discrete log problem, all using the same unknown exponent. Is this problem easier than the standard discrete log problem?
Oh, heck, I should be more precise. ...
- 36.4k
8
votes
1
answer
435
views
Is Indistinguishability Obfuscation Real?
I've recently stumbled upon an interesting Quanta Magazine article. It states that indistinguishability obfuscation (iO) 's theoretical feasibility has been proven, referencing a relatively recent ...
- 183
7
votes
3
answers
3k
views
Why don't table lookups run in constant time?
The Wikipedia article on big O notation says that performing a lookup is a constant time operation. So why are lookup tables susceptible to timing attacks?
- 3,655
7
votes
3
answers
6k
views
P = NP and current cryptographic systems
I've recently heard some people claiming that if the fact that P = NP is proven, most (all?) the current cryptographic algorithm considered secure like RSA will be unusable in secure systems.
My ...
- 205
7
votes
1
answer
18k
views
Big-O Notation: Encryption Algorithms
I am currently completing a dissertation concerning the encryption of data through a variety of cryptographic algorithms.
I have spent much time reading journals and papers but as yet have been ...
7
votes
2
answers
437
views
Space complexity and cryptography
It appears that in cryptography a lot of definitions are based on the time complexity of various algorithms. For example, a "good" encryption scheme should be resilient against a polynomial adversary. ...
- 203
7
votes
2
answers
3k
views
Meet-in-the-middle with checking complexity
In regards to meet in the middle type attacks, I have been considering the amount of operations in order to successfully find a key given two sets of plaintext / ciphertext pairs. All of the sources I ...
- 95
7
votes
1
answer
524
views
Notion of elementary operation when complexities in the form of $2^{128}$
In lots of cryptoanalytic papers I read, attack complexities are stated in the form of a constant. For example, this related key attack on of AES states:
[...] For AES-256 we show the first key ...
- 347
7
votes
1
answer
726
views
Formal definition of "explicit" algorithm?
A long time ago, I read that the definition of "cryptographic hash function" is "collision-resistant one-way function". (A similar definition shows up in the FIPS standards for SHA-1 etc.)
But this ...
- 1,377
7
votes
1
answer
1k
views
Fully Homomorphic Encryption over the Integers - Runtime Question
I have a question regarding the paper "Fully Homomorphic Encryption over the Integers"
(http://eprint.iacr.org/2009/616.pdf): On page 6 after they set their parameters, it says
"This setting results ...
- 73
7
votes
1
answer
1k
views
Relation between "P is not equal to NP" and "Existence of One-Way Function"
We know that If there exists a one-way function, then P ≠ NP. Why can we not conclude that if P ≠ NP, then there exists a one-way function? Is there a polynomial time computable function that is hard ...
- 73
7
votes
1
answer
860
views
What makes the quadratic residuosity problem hard?
The quadratic residuosity problem is the problem of determining whether, for given $r$, $m$, $\exists a.a^2\equiv r\mod m$.
This problem's believed to be hard to solve in general (e.g. an efficient ...
- 191
7
votes
1
answer
658
views
Finding where I am in a linear recurrence relation
Suppose I have a linear recurrence relation
$$a(n) = c_1 a(n-1) + \dots + c_k a(n-k) + d,$$
where the constants $c_1,\dots,c_k,d$ are given and the initial values $a(0),\dots,a(k-1)$ are given as well....
- 36.4k
6
votes
1
answer
3k
views
Why does applying 56-bit DES twice only give 57 bits of security? [duplicate]
Given two 56-bit keys, $k_1$ and $k_2$, why does $E_{k_1}(E_{k_2}(M))$ only give 57 bits of security?
So basically I'm unsure why it only gives 57 bits of security; I understand that one key will ...
- 171
6
votes
2
answers
22k
views
Computational requirements for breaking SHA-256?
Let's define "breaking" a hash function $H$ as being threefold (corresponding to the main properties of a cryptographic hash function):
preimage attacks to get $m$ knowing $H(m)$
second-preimage ...
- 740
6
votes
1
answer
569
views
Why Zero-Knowledge protocols are used for NP problems if IP is the class of interactive proof systems where they come from?
As stated in the title, I'm studying ZKPs and I see they are just interactive proof systems that respect the zero-knowledge property. Now, if that's true, why aren't they used for IP problems, the ...
- 131
6
votes
1
answer
168
views
If OWF were to exist, do we know for sure that one of the candidate OWF would indeed be a OWF?
We have several candidates for OWF, like multiplication/factoring and discrete exponencial/logarithm. What I am asking is:
Does the existence of one way functions imply that our candidate functions ...
- 173
6
votes
2
answers
318
views
Why do memory-hard functions rely on a time-space trade-off?
I was reading about memory-hard functions recently. In those papers I read, they almost always introduce a time-space trade-off like this:
$$
S(n) \times T(n) \in \Omega(\mathrm{Poly}(n))
$$
I ...
- 729
6
votes
1
answer
894
views
What is the difference between Argon2d and Argon2i?
I know that Argon2d accesses the memory array in a password dependent order and Argon2i accesses the memory array in a password independent order. What is the difference in computational complexity?
6
votes
3
answers
295
views
Polynomials and efficient computability
In public key crypto, the popular definitions of security (CPA, CCA1,2) depend on PPT adversaries. I'm trying to understand why adversaries should be PPT.
It's clear that adversaries should be at ...
- 161
6
votes
2
answers
945
views
Is there any research about cryptography on nondeterministic Turing machines?
I know it's a highly theoretical topic, but I was wondering if there was any research out there about what cryptography would be like assuming that we had access to nondeterministic Turing machines.
...
- 81
6
votes
2
answers
1k
views
Finding k collisions on hash function
Let $n$ be the size of the image-space of a hash function $H$.
It is known that you can find a collision on $H$ in $O(\sqrt{n})$ time (by birthday paradox).
How can I show that, in order to find $k$ ...
- 457
6
votes
3
answers
1k
views
Parallel-resistant proof-of-work scheme?
I am looking for a proof-of-work scheme which cannot be effectively parallelized.
For example, in hashcash (and by extension bitcoin) you have some collision-resistant hash function $f()$, a target $...
- 2,548
6
votes
0
answers
191
views
What are the theoretical memory requirements for these factoring algotihms?
Given an $n$ bit integer quadratic sieve takes $L(\frac12,1+o(1))$ time and number field sieve takes $L(\frac13,1.922)$ time where $L$ notation is given in https://en.wikipedia.org/wiki/L-notation.
...
- 908
5
votes
3
answers
4k
views
Is there a cryptography algorithm that will remain safe if P=NP?
From what I heard, many encryption algorithms are based on the assumption that some problems are computationally hard, i.e, NP-complete. In the unlikely event that someone proves that P=NP, these ...
5
votes
2
answers
1k
views
Can we say that if $P=NP$ there is no CPA secure public key encryption?
I've learned that public key encryption is based on the problem of Discrete Log (as regard to group theory) which believed to be hard.
But, can we say that it doesn't matter on which problem our ...
- 2,130
5
votes
3
answers
1k
views
Why do Problems for Post-Quantum algorithms have to be NP-Hard?
The mathematical problems used for Post-Quantum Cryptography problems I came across, are NP-complete, e.g.
Solving quadratic equations over finite fields
short lattice vectors and close lattice ...
- 307
5
votes
1
answer
232
views
Are there lower bounds to how efficient one can make obfuscated code?
I am wondering if there are any theoretical reasons why obfuscated programs cannot be nearly as efficient as the plaintext programs and whether there is any necessary computational overhead from ...
- 1,235
5
votes
1
answer
1k
views
Indistinguishability versus semantic security?
I found some foundations of crypto course notes that mention that these two are equivalent statements of their own degrees of security and was given the following definitions:
I was always under the ...
- 435