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.
47
questions
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,001
7
votes
3
answers
2k
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,645
7
votes
3
answers
5k
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
5
votes
3
answers
3k
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 ...
3
votes
1
answer
18k
views
How do I derive the time complexity of encryption and decryption based on modular arithmetic?
I want to calculate the time complexity of two encryption and decryption algorithms.
The first one (RSA-like) has the encryption
$$ C := M^e \bmod N $$
and decryption
$$ M_P := C^d \bmod N. $$
...
- 151
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,659
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
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
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
2
votes
3
answers
999
views
Why do we focus on polynomial time, rather than other kinds of time?
Polynomial time seems to be mentioned quite frequently on this site. It often forms a threshold between two possible outcomes like being secure or an attack's validity. I know what $\mathcal{O}(n^c)$ ...
- 15.2k
1
vote
2
answers
4k
views
Computational complexity of RSA
What's the computational complexity or RSA? One can assume it's O(prime length^2) it you consider multiplication by column, but speed tests slightly differ on slow operations with private key and ...
- 1,691
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
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
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,922
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
4
votes
2
answers
475
views
iterated discrete log problem
Consider the following problem: given $g_1 \ldots g_i,h_1 \ldots h_i \in G$, $\forall i$ find $x_i$ such that $g_i^{x_i}=h_i$
For $i=1$ this is the discrete log problem and is assumed to to have ...
- 1,614
2
votes
1
answer
952
views
DES-X , computation load and storage
The passage said that the computational load to attack DES-X can be reduced to approximately $2^{(56+64)}=2^{120}$ steps,and the storage of data sets should be $2^{64}$.
But I can't figure why it is ...
- 23
1
vote
1
answer
2k
views
The computational complexity of discrete log
I am trying to find out what the asymptotic computational complexity, in terms of big $O()$ notation, is for discrete log. Specifically, consider an element of the field $x \in \mathbb{F}_{q}$, ...
- 289
1
vote
1
answer
579
views
Big-O Encryption Algorithm
I am currently doing a research paper on the Blowfish encryption algorithm and one of the components that I need to include is time and space complexity.
I have tried reading academic articles and ...
- 13
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,420
19
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 ...
- 475
12
votes
2
answers
793
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
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.2k
8
votes
3
answers
584
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 ...
7
votes
1
answer
636
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.2k
6
votes
1
answer
874
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
2
answers
21k
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
5
votes
1
answer
302
views
Which is the smallest, cyclic in 3 directions, consistent structure of random values which can be hidden at the adversaries machine? (some comparison)
Or more general each member can be part of up to three 2D locally euclidean planes of 2 different dimensions each.
(each of those planes is cyclic in two orthogonal directions, like a torus)
Given ...
- 573
4
votes
2
answers
1k
views
Is AES solvable by reducing to SAT?
Consider a known plaintext attack on AES — just so we have an actual system of equalities that we can feed to a SAT solver.
Is AES solvable in this way? In other words, will the algorithm eventually ...
user9070
4
votes
0
answers
174
views
How many reversible gates would DES require?
How many reversible gates (said counting Toffoli and Controlled NOT, with free NOT) would be required to reversibly implement $(K,P)\mapsto(G,C)$ for the block cipher DES?
$P$ is the plaintext, $C$ ...
- 138k
4
votes
1
answer
231
views
Offline Complexity of the garbling scheme
The offline complexity of the garbling scheme means the time complexity of the circuit encoding algorithm, that is, $\textrm{GC.Circ}(1^\lambda, C)$, where $C$ is the circuit to be garbled. It's ...
- 932
3
votes
2
answers
205
views
LWE with the matrix A repeated
Consider the following version of Learning With Errors.
You are either given $(A, As_1 + e_1, As_2 + e_2, \ldots, As_k + e_k)$ or $(A, u_1, u_2, \ldots, u_k)$, where
$A$ is an $m \times n$ matrix ...
- 357
3
votes
2
answers
1k
views
Running time of Shamir's secret sharing scheme
Let $p>n$ be a prime number. The key steps in the $(t,n)$ Shamir's secret sharing is as follows:
Steps of dealer:
Choosing $s \in \mathbb{Z}_p^*$
Selecting $b_i \in \mathbb{Z}_p^*$ for polynomial ...
- 499
3
votes
1
answer
1k
views
Brute force attack expected running time
I am a bit confused about the expected running times of brute force attacks on different cryptosystems.
So let's assume a key size of $2^n$ bits.
Symmetric key cryptography:
$E(brute)$ = $2^{n-1}\...
- 201
2
votes
1
answer
3k
views
computational complexity class of decryption of AES [closed]
I haven't really seen what computational complexity class of decryption of AES is. Can anyone provide reference papers or answers here?
- 21
2
votes
2
answers
225
views
More general - what is the hard problem of recovering r from r*p mod q?
I would like to know the cryptographic hard problem that is most closely tied to recovering integer $r$ from the modular product $r\times p\mod q$. (This is a simplification of an earlier post that ...
- 273
2
votes
3
answers
1k
views
What is the time complexity of the basic components of a symmetric cipher?
I have a very basic knowledge on time complexity and even less on programming, so please bear with me. I am interested to know the time complexity in big-O notation of some of the basic operations in ...
- 1,025
2
votes
3
answers
1k
views
What is the point of differential cryptanalysis when the amount of necessary plaintext is unrealistic?
As someone with a non-crypto background, I learned that differential cryptanalysis is mostly weak against ciphers like DES because, being a chosen plaintext attack, for a state of art complexity of $2^...
- 141
1
vote
1
answer
117
views
Complexity of Hash mining/signing
While reading about mining in crypto currency, I found that it requires some leading bits of a hash function output to be 0. This boils down to preimage resistance of the hash function, hence done ...
- 603
1
vote
2
answers
1k
views
Complexity of ECB and OFB
What is the complexity of ECB in terms of Time and Memory?
and also in OFB? I can't find it in the internet, so I decided to ask it in here.
- 1,727
1
vote
3
answers
615
views
Berlekamp–Massey input sequence length
For a given periodic sequence of length $N$ for which minimal polynomial is being constructed. Does the Berlekamp-Massey algorithm take the input of $2N$, i.e., the repeated input sequence or just the ...
1
vote
1
answer
10k
views
What is the time complexity of computing a cryptographic hash function/random oracle?
I'm wondering what's the computational complexity of computing a hash function/random oracle when doing complexity analysis. For example, what's the computational complexity of computing $H(b\|r)$? ...
- 932
1
vote
1
answer
118
views
What is the hard problem for this algebraic encryption construct?
I would like to know what cryptographic hard problem this reduces to.
Select two large prime numbers $p$ and $q$, and let $N=pq$. Select a random positive integer $r$. Compute the encryption of ...
- 273
1
vote
1
answer
84
views
Encryption scheme with high complexity encryption over decryption
I need an encryption operation be 1000-1000000 times more complex than decryption operation. Is it possible to achieve with EC ...
- 111
1
vote
1
answer
3k
views
Why is AES unbreakable?
Why is it said that AES is unbreakable? Brute force attacks would take years to crack it, so is it possible to crack it if the computational speed of machines increase in the following decade?
- 23
0
votes
4
answers
2k
views
Solution with high decryption cost and low encryption cost
I am looking for any cryptographic solution that will meet those requirements :
Only known method to get the encrypted string need to be brute force.
Decrypting on modern computer not more than ...
- 57
0
votes
1
answer
244
views
Number of operations for Elgamal cryptosystem
In page 408 of Hoffstein, Piper, and Silverman's Introduction to Mathematical Cryptography, it says
"Roughly speaking, in order to achieve $k$ bits of security,
encryption and decryption for ...
- 3