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
1
vote
1
answer
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 ...
- 13
1
vote
1
answer
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)$? ...
- 932
9
votes
2
answers
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 ...
- 693
3
votes
1
answer
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 ...
- 31
1
vote
0
answers
75
views
Complexity of arithmetic in (the integer ring of) a number field?
What is the running time complexity (average or worst case) of common arithmetic operations in number fields?
In fact, I'm only interested in the integer ring of the quadratic extension $\mathbb{Q}[\...
- 143
0
votes
0
answers
72
views
If finding a private key from a public key is [co-]NP-complete, does NP=co-NP?
In a given public key cryptosystem, if the problem of determining the private key from the public key is NP-complete or co-NP-complete, does that imply that NP = co-NP?
Complexity theory is ...
- 2,513
4
votes
2
answers
4k
views
Why do look up tables speed things up compared to brute force?
I'm currently reading up on lookup tables and efficiency. In my uni script it says the following:
For Brute Force:
Preparation time: $O(1)$
Disk space requirement: $O(1)$
Time required to crack the ...
- 143
-1
votes
2
answers
662
views
Determining whether functions are one-way or not
I read a book about one-way function. In this book, I saw 2 exercises that I can't understand and don't know how to solve. Can anyone help me to solve these?
Is $f(x,y)=x+y$ a one way function?
Is $f(...
- 31
1
vote
1
answer
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 ...
- 31
11
votes
5
answers
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 ...
- 303
1
vote
1
answer
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 ...
- 91
13
votes
3
answers
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
3
votes
0
answers
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 ...
- 269
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 ...
- 1,025
15
votes
2
answers
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....
- 9,001
0
votes
1
answer
163
views
Newbie question: one-way functions in cryptography
I'm reading this article on the basics of cryptography and it says that the main principle is about taking such an algorithm that knowing the end result and the algorithm, an eavesdropper wouldn't be ...
- 103
1
vote
0
answers
219
views
Double encryption : what method is the best?
Given the block-ciphers defined as follows :
$1.$ $C=$ $E_{k1}($$E_{k2}$$(M))$
$2.$ $C=$ $E_{k1{\oplus}k2}$$(M)$
$3.$ $C=$ $(E_{k1}(r),E_{k2}(r$ ${\oplus}$ $M))$
where $C$ is the cipher ...
- 11
1
vote
1
answer
570
views
Negative time complexity?
Just finishing an investigation into Shor's algorithm, and the following equation,
$$
O\big(\big(\log N\big)^2 \big(\log \log N\big)\big(\log \log \log N\big)\big)
$$
is given for its time complexity. ...
- 175
0
votes
1
answer
51
views
Secure offline treasure hunt
Say I would like to create an app that would allow users to organize treasure hunts for their parties. The host of the party would create a list of GPS coordinates for each hiding spot and distribute ...
- 103
4
votes
0
answers
141
views
If trapdoor OWF exists then f is a trapdoor OWF, is there such a construction?
Is there a known construction of f, such that given that a trapdoor OWF exists then f is a trapdoor OWF, so we can construct inefficient cryptomania, ala Levin's construction for minicrypt in "The ...
- 223
2
votes
3
answers
998
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)$ ...
- 15.2k
1
vote
0
answers
59
views
Computation complexity of modified Euclidean algorithm
The computational complexity of the extended Euclidean algorithm is $O(log(b)^2)$ ($b$ being the second integer) as referenced by Wikipedia. How to compute the complexity of the modified extended ...
- 43
5
votes
1
answer
229
views
Are there lower bounds to how efficient one can make obfuscated code?
I am wondering if there are any theoretical reasons why obfuscated programs cannot be nearly as efficient as the plaintext programs and whether there is any necessary computational overhead from ...
- 1,235
1
vote
1
answer
329
views
Time complexity of Weil pairing
I ran and timed an implementation of the Weil pairing on three set of parameters. One with an order of 512 bits, one with 256 bits and the last with 161 bits.
I took the Miller's algorithm to compute ...
- 165
6
votes
2
answers
310
views
Why do memory-hard functions rely on a time-space trade-off?
I was reading about memory-hard functions recently. In those papers I read, they almost always introduce a time-space trade-off like this:
$$
S(n) \times T(n) \in \Omega(\mathrm{Poly}(n))
$$
I ...
- 719
7
votes
2
answers
428
views
Space complexity and cryptography
It appears that in cryptography a lot of definitions are based on the time complexity of various algorithms. For example, a "good" encryption scheme should be resilient against a polynomial adversary. ...
- 203
1
vote
1
answer
83
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 ...
- 111
6
votes
2
answers
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$ ...
- 447
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 ...
- 1,691
4
votes
1
answer
827
views
How was this Mersenne Twister seed for a 20-character string known a priori found?
Someone generated a seed for the Mersenne Twister, with the intent of that seed producing this string:
"9!dlroW ,olleH"ck,@
Which is 20 characters long. Why he ...
- 143
0
votes
1
answer
105
views
Analysing communication complexity of a protocol
My question is more about the practical side of designing crypto. protocols and it is related to complexity. So, if you think it's irrelevant to this forum please kindly let me know and I will remove ...
- 442
4
votes
0
answers
174
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$ ...
- 138k
5
votes
1
answer
222
views
Making attacks on password hashes less economical
Perhaps an abstract question on complexity given the trade offs between memory vs runtime, I was wondering if it's possible to constrain only either extremes approaches to be optimally efficient, thus ...
- 201
1
vote
1
answer
464
views
Hash function composition - security level
When using two hash functions, g(x)=SHA-512 and f(x)=MD5
g(x) has 512 bit output (using salt)
f(x) has 128 bit output.
Let's say that z(x)=f(g(x))
meaning the output is 128 bit long.
The Question:
...
- 13
1
vote
0
answers
73
views
Complexity lower bound in Uber-Assumption family
I try to wrap my head around calculating of complexity lower bound using Corollary 1 from The Uber-Assumption Family by X.Boyen
(http://www.academia.edu/download/30698012/...
3
votes
1
answer
212
views
Complexity leveraging in case of exponentially many hybrids
Complexity leveraging is a proof technique in cryptography where the reduction algorithm runs in super-poly time. (see this). Many papers use complexity leveraging when there are exponentially many ...
- 1,384
0
votes
0
answers
193
views
Random self-reducibility and NP
I was reading the Wikipedia page https://en.m.wikipedia.org/wiki/Random_self-reducibility and it states: "If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy ...
- 11.7k
6
votes
1
answer
874
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?
7
votes
3
answers
2k
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?
- 3,635
5
votes
1
answer
1k
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
12
votes
2
answers
793
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
6
votes
2
answers
21k
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 ...
- 740
0
votes
1
answer
149
views
Simple designs for provable security in cryptographic primitives
We can say that a cryptographic primitive has $n$ bits security against a type of attack if it cannot break it in less than $2^n$ time (time-area product in some cases). The cryptographic primitive ...
- 359
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 ...
-2
votes
1
answer
1k
views
Assuming that NP = RP, how would this impact cryptography?
In terms of complexity classes, we assume that NP = RP. In other words, we assume that there is a randomized algorithm that solves a NP complete problem (and through polynomial time reductions, ...
1
vote
1
answer
485
views
How can PUF hardware be proportional to the number of challenge/response bits?
Wikipedia article claims that physical unclonable functions are superior to ROM because they require less hardware:
Unlike a ROM containing a table of responses to all possible challenges, which ...
- 244
3
votes
1
answer
362
views
For security, need a 1-1 crypto-mapping be NP-complete?
The book Foundations of Cryptography states:
It was understood that problems related to breaking a 1-1 cryptographic mapping could not be NP-complete and, more important, that NP-hardness of the ...
- 435
1
vote
1
answer
71
views
What is the "successive-configuration relation"?
This term is used in the book Foundations of Cryptography on pg 20 with regard to defining deterministic oracles, but is not previously defined and I can't seem to find a definition online easily.
- 435
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}$, ...
- 289
16
votes
2
answers
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}$
- 1,595