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.

Filter by
Sorted by
Tagged with
1
vote
0answers
274 views

Time complexity of birthday attack type problem

I have two sorted lists: $A=\{a_1, \ldots, a_n\}$ and $B=\{b_1, \ldots, b_m\}$. I know that the probability of $a_i=b_j$ is $c$ for $1 \leq i \leq n$ and $1\leq j \leq m$. The time complexity of ...
1
vote
1answer
52 views

Computational Complexity: ECC multiplication vs Modular multiplication

How does performing scalar multiplication on an elliptic curve compare to exponentiation in a multiplicative group modulo a prime? I.e. on a given elliptic curve of size $|t|$, what's the complexity ...
2
votes
0answers
89 views

Multivariate Cryptography: Security of the affine transform T

In this question, I'd like to discuss the security of the last transformation $T$ employed in the construction of a MV-scheme. MVCrypto is based on solving a system of polynomial equations, but ...
3
votes
0answers
63 views

Group Rings on Cryptography

Let $R[G]$ or $RG$ be the group ring where $R=F_q$ and $G$ is any group. Let $Dim(V)=\vert G \vert$. It's clear that $V$ has $\vert R \vert^{\vert G \vert}$ distinct $\vert G \vert$-tuples. This ...
6
votes
2answers
184 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. ...
3
votes
1answer
104 views

Induction is problematic in computational cryptography - Why?

In Dr. Lindell's lecture The Yao Construction and its Proof Of Security, in briefly explaining the hybrid argument, he makes the statement that mathematical induction is a problem in computational ...
2
votes
1answer
67 views

Bit-strength of discrete logarithm for a group of integers modulo a safe prime

Preliminaries Let $p$ be a safe prime number. Let $\mathbb{Z}_p^*$ be the multiplicative group of integers modulo $p$. We have $\mathbb{Z}_p = \{\,a \in \mathbb{Z} \mid 1 \le a \lt p\,\}$ . Let $g \...
4
votes
1answer
76 views

What makes the quadratic residuosity problem hard?

The quadratic residuosity problem is the problem of determining whether, for given $r$, $m$, $\exists a.a^2\equiv r\mod m$. This problem's believed to be hard to solve in general (e.g. an efficient ...
1
vote
0answers
76 views

Time complexity of Euler's totient function

I believe there are different time complexities for Euler's totient function depending on how you execute the algorithm. The two I know of are: Iterate through 1 to k and calculate each $\gcd$: $O(n \...
2
votes
1answer
72 views

Why does the following SIS-based decision language not make sense?

I'm currently reading about important lattices problems and noticed that while CVP, SVP, and LWE have decisional versions, SIS does not. I read in the question Relation between decisional SIS and ...
1
vote
2answers
520 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 ...
3
votes
2answers
6k 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 ...
1
vote
2answers
73 views

Speed of the General number field sieve

So according to the wikipedia page https://en.wikipedia.org/wiki/General_number_field_sieve the algorithm has complexity $$\exp \left( \left(\sqrt[\leftroot{1}\uproot{0}3]{\frac{64}{9}} + o(1) \right) ...
2
votes
1answer
52 views

Attack on a Feistel Cipher given the key and half of the ciphertext

Consider a classical Feistel Cipher, with the round functions given and the keys used in the ciphering process. Is it possible to reconstruct the original data if half of the ciphered text is given? ...
2
votes
1answer
67 views

If DDH is hard then CCA-secure PKES exist?

My cryptography slides describe several relations between cryptographic problems. I don't still have a good justification on the following: If decisional Diffie-Hellman problem is hard then there ...
0
votes
1answer
86 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 ...
0
votes
1answer
332 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)$? ...
8
votes
2answers
732 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 ...
3
votes
1answer
102 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
0answers
54 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}[\...
0
votes
0answers
27 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 ...
5
votes
2answers
3k 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 ...
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....
-1
votes
2answers
112 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(...
1
vote
1answer
51 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 ...
8
votes
4answers
399 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
1answer
96 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 ...
13
votes
3answers
3k 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?
0
votes
0answers
58 views

What is the computational complexity of Coppersmith's bivariate algorithm?

Coppersmith's original paper Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known says the algorithm to find bivariate roots under certain conditions runs in ...
2
votes
0answers
55 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 ...
1
vote
3answers
252 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 ...
6
votes
3answers
687 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?
0
votes
1answer
87 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 ...
1
vote
0answers
113 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 ...
1
vote
1answer
92 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. ...
8
votes
3answers
463 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 ...
0
votes
1answer
39 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 ...
3
votes
0answers
74 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 ...
2
votes
3answers
229 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)$ ...
1
vote
0answers
35 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 ...
5
votes
1answer
173 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 ...
0
votes
1answer
156 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 ...
3
votes
1answer
77 views

DSSP reduction to DSSI

In “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies" by DeFeo, Jao and Plut, a reduction from the Decisional Supersingular Product (DSSP) problem to Decisional ...
6
votes
2answers
169 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 ...
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 ...
19
votes
1answer
551 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 ...
5
votes
2answers
154 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$ ...
4
votes
1answer
267 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 ...
0
votes
1answer
69 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 ...
4
votes
0answers
147 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$ ...