# 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.

258 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
990 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 ...
10k 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}$
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....
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?
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?
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 ...
791 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, ...
3k 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 ...
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 ...
3k views

872 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?
292 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 ...
925 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. ...
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$ ...
1k views

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 0 answers 190 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. ... 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 ... 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 ...
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 ...