Skip to main content

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.

Filter by
Sorted by
Tagged with
15 votes
2 answers
7k 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....
DannyNiu's user avatar
  • 9,421
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?
Melab's user avatar
  • 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 ...
Jaay's user avatar
  • 205
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 ...
Erel Segal-Halevi's user avatar
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. $$ ...
almodawan's user avatar
  • 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 ...
ThePiachu's user avatar
  • 1,679
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.
Nadori's user avatar
  • 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 ...
tbs's user avatar
  • 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 $...
rath's user avatar
  • 2,558
2 votes
3 answers
1k 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)$ ...
Paul Uszak's user avatar
  • 15.5k
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 ...
Smit Johnth's user avatar
  • 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 ...
Backslash36's user avatar
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}{...
user129789's user avatar
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 ...
Daniel's user avatar
  • 3,972
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 ...
user3411002's user avatar
4 votes
2 answers
492 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 ...
imichaelmiers's user avatar
2 votes
1 answer
980 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 ...
C learner's user avatar
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}$, ...
Simd's user avatar
  • 299
1 vote
1 answer
630 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 ...
Tamera Brown's user avatar
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 ...
hsalin's user avatar
  • 485
20 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 ...
malexmave's user avatar
  • 1,441
12 votes
2 answers
856 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, ...
z.karl's user avatar
  • 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 ...
D.W.'s user avatar
  • 36.5k
8 votes
3 answers
601 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 ...
BeingQuisitive's user avatar
7 votes
1 answer
662 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....
D.W.'s user avatar
  • 36.5k
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 ...
indiscreteLog's user avatar
6 votes
1 answer
907 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?
Denis Ismailovski's user avatar
5 votes
1 answer
320 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 ...
J. Doe's user avatar
  • 453
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 ...
user avatar
4 votes
0 answers
175 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$ ...
fgrieu's user avatar
  • 142k
4 votes
1 answer
240 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 ...
CryptoLover's user avatar
3 votes
2 answers
291 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 ...
BlackHat18's user avatar
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 ...
hanugm's user avatar
  • 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}\...
Pio's user avatar
  • 201
2 votes
2 answers
226 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 ...
Russ's user avatar
  • 273
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^...
AdHominem's user avatar
  • 141
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?
Dotdats's user avatar
  • 21
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 ...
Red Book 1's user avatar
  • 1,025
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.
goldroger's user avatar
  • 1,737
1 vote
3 answers
696 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 ...
Mathpdegeek497's user avatar
1 vote
1 answer
122 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 ...
hola's user avatar
  • 603
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?
eatq's user avatar
  • 23
1 vote
1 answer
122 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 ...
Russ's user avatar
  • 273
1 vote
1 answer
11k 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)$? ...
CryptoLover's user avatar
1 vote
1 answer
85 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 ...
k06a's user avatar
  • 111
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 ...
devd's user avatar
  • 57
0 votes
1 answer
256 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 ...
Paul's user avatar
  • 3