Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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
63 views

'random' function $r_{n+1} = f(r_n)$, $|\{r_i,\forall i\}|=N$, $r_N = r_1$ where a function $g(r_k)=k$ is harder than in ECC?

Is there a deterministic pseudo random function $f$ with $r_{n+1} = f(r_n)$, $|\{r_i,\forall i\}|=N$, $r_N = r_0$, (for given random initial value $r_0$) where a function which derives the index of a ...
0
votes
1answer
32 views

Question on the Quadratic Residuosity Assumption

I am reading the Handbook of Applied Cryptography and on page 99 the authors write , after showing that $QRP \le_P FACTORING$: It is believed that the $QRP$ is as difficult as the problem of ...
1
vote
0answers
40 views

What if an AES Whitebox 1024-bit (or larger key) is created? Does it increase complexity consistently?

Following the Chow et al paper and Muir's tutorial, I was able to implement the AES algorithm using tables embedding keys of 128, 192 and 256-bit sizes, later extended to 1024, 2048 and 4096-bit sizes....
0
votes
1answer
29 views

Definition of support in the context of an encryption scheme and usage of P = NP assumption in lemma 9.2 (Arora, Barak)

EDIT: I've migrated the question by deleting the same question I asked on mathematics stackexchange. 2 questions: (1) I am confused about the definition of support used in the proof given in the ...
1
vote
1answer
80 views

(Whitebox Crypto) Using ChaCha20, is it safe to reduce the nonce length in a single block cipher?

I am willing to write a Whitebox Crypto unit using ChaCha20 algorithm (Bernstein, D. 2008) for an input consisting of a single block. The fact it is going to be a single block cipher is of special ...
4
votes
1answer
143 views

Are there post-quantum cryptosystems with a gap between classical and quantum security?

Is there a gap between classical attacks and quantum attacks against some post-quantum security assumptions? (I'm particularly interested in asymmetric cryptography.) I understand that there is no ...
1
vote
2answers
121 views

What is the difference between computational complexity and time complexity?

Computational complexity seems to be used quite a lot in cryptographic papers. The time complexity I am referring to is the one from Computational Complexity Theory. Are these two the same things?
1
vote
1answer
64 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 ...
3
votes
0answers
81 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 ...
3
votes
1answer
114 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
0answers
97 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 ...
2
votes
1answer
90 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
98 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
92 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
76 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
81 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
73 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
69 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
109 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
715 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
762 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
119 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
56 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
31 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 ...
-1
votes
2answers
128 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
53 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 ...
9
votes
5answers
521 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
98 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?
3
votes
0answers
65 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
288 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 ...
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....
0
votes
1answer
89 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
126 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
121 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. ...
0
votes
1answer
41 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
77 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
237 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
38 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
176 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
175 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 ...
6
votes
2answers
177 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 ...
7
votes
2answers
192 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. ...
1
vote
1answer
66 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 ...
5
votes
2answers
179 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$ ...
1
vote
2answers
619 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 ...
4
votes
1answer
360 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
73 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
155 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$ ...