# 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
1 vote
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 ...
1 vote
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)$? ...
1k views

### What is meaning of the term "language"?

I don't have much formal background, and I could not find a suitable explanation for this after searching on Google/Wikipedia. What is the meaning of the term "language" as used in cryptographic ...
1k views

### AES-128 (CBC) brute force given 90+ rightmost bits of key, known IV and Ciphertext?

Given: Known ciphertext (in hex) (ciphertext is the exact length of the message (i.e. non-padded). It is known that the cipher was developed using CBC. There is one and only one ciphertext message ...
1 vote
75 views

1 vote
98 views

### What does universal look like? What is the complexity(size/depth) of universal circuit

I was reading a paper about attribute based encryption. The authors showed that ciphertext-policy ABE can be constructed from key-policy ABE using universal circuit. But the universal circuit should ...
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 ...
1 vote
116 views

### Algorithm complexity: $\mathcal O(n\cdot m)$ vs. $\mathcal O(max(n,m)^2)$

Suppose $A(n,m,k)$ computes for 1 < i < n do { for 1 < j < m do { /* some efficient cryptographic operation */ } } where $k$ is a ...
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?
211 views

### Reduction from integer factoring to computational Diffie Hellman

The computational Diffie Hellman (CDH) problem for ${\mathbb{Z}}^*_p$ is given a prime $p$, a generator $g$ of ${\mathbb{Z}}^*_p$, and a pair $(g^i, g^j)$ to compute $g^{ij}$. The value $g$ is called ...
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 ...
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....