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

274 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 ...
• 617
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,451
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
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,295
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,675
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....
• 9,632
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
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
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
868 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
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 ...
• 323
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
3k views

• 739
298 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
970 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
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
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 $... • 2,578 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. ... • 972 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,150
2k 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