Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

10
votes
2answers
2k 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....
6
votes
2answers
2k 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 ...
2
votes
1answer
12k 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. $$ ...
10
votes
4answers
5k 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 ...
6
votes
3answers
679 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 $...
6
votes
3answers
1k 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 ...
1
vote
3answers
431 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 ...
8
votes
3answers
2k 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.
7
votes
1answer
2k 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 ...
12
votes
1answer
2k 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 ...
2
votes
1answer
570 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 ...
-1
votes
4answers
864 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 ...
8
votes
2answers
2k 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}{...
3
votes
2answers
286 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 ...
15
votes
2answers
553 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 ...
13
votes
1answer
4k 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 ...
8
votes
3answers
457 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 ...
3
votes
3answers
224 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)$ ...
3
votes
2answers
5k 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 ...
5
votes
1answer
2k 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 ...
1
vote
1answer
2k 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?
7
votes
1answer
405 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....
6
votes
3answers
634 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?
6
votes
1answer
649 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 ...
4
votes
0answers
145 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$ ...
2
votes
2answers
189 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 ...
2
votes
1answer
741 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}\...
1
vote
2answers
839 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.
3
votes
1answer
146 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 ...
3
votes
2answers
967 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 ...
1
vote
1answer
65 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 ...
1
vote
1answer
65 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 ...