Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

1
vote
1answer
48 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
30 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 ...
2
votes
0answers
55 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 ...
1
vote
4answers
187 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
27 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
2answers
146 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
76 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
118 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 ...
5
votes
2answers
114 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
62 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
93 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$ ...
0
votes
0answers
26 views

How can I compare the complexity of an ECC based authentication scheme with a Homomorphic one?

I have to compare a scheme complexity which uses a homomorphism Encryption Algorithm [ref] with to other schemes. I count the number of each operation in schemes, but I can not compare the result ...
2
votes
2answers
235 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
123 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
0answers
39 views

Theoretical cost of Paillier cryptosystem

How can we estimate the theoretical cost of Paillier cryptosystem? Examples can be found here https://en.wikipedia.org/wiki/Paillier_cryptosystem ? Can any please discuss the cost in terms of big O ...
0
votes
1answer
58 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
110 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$ ...
5
votes
1answer
138 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 ...
1
vote
1answer
143 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: ...
1
vote
0answers
37 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
1answer
62 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 ...
0
votes
0answers
80 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 ...
4
votes
1answer
333 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?
2
votes
2answers
312 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
votes
1answer
246 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 ...
11
votes
2answers
303 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, ...
3
votes
2answers
2k 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 ...
0
votes
1answer
79 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 ...
-1
votes
3answers
271 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 ...
-3
votes
1answer
134 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
1answer
111 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 ...
3
votes
1answer
352 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 ...
1
vote
1answer
26 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.
0
votes
1answer
294 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}$, ...
8
votes
2answers
2k 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}$
2
votes
2answers
181 views

More general - what is the hard problem of recovering r from r*p mod q?

I would like to know the cryptographic hard problem that is most closely tied to recovering integer $r$ from the modular product $r\times p\mod q$. (This is a simplification of an earlier post that ...
1
vote
1answer
61 views

What is the hard problem for this algebraic encryption construct?

I would like to know what cryptographic hard problem this reduces to. Select two large prime numbers $p$ and $q$, and let $N=pq$. Select a random positive integer $r$. Compute the encryption of ...
0
votes
1answer
101 views

Average number of multiplications in left-to-right k-ary exponentiation

On page 617 in chapter 14 of The Handbook of Applied Cryptography, the average number of multiplications in left-to-right k-ary exponentiation is $ l\times (2^k-1)/2^k$, where $l=\lfloor t/k\rfloor $,...
0
votes
0answers
102 views

How to prove that Asymmetric cryptography is more resource-hungry than Symmetric cryptography?

I had asked this question: Why are asymmetric cryptography keys more vulnerable to brute force attack than symmetric ones? some time back. One of the answers said that asymmetric cryptography is ...
2
votes
1answer
198 views

Computing the powers of hash (ripemd-160) function

Is there a way I can compute $2^{100}$th power of ripemd-160 of my string, just like I can do with square matrix powers? I.e. can I easily compute ripemd-160 large amount of times?
1
vote
1answer
214 views

What is the cost of encrypting of long message with public-key cryptography?

Let m be a message of arbitrary size, potentially very large. Is it necessary to use larger parameters in the public-key encryption scheme in order for the receiver to decrypt that message? My guess ...
4
votes
0answers
150 views

Complexity: Taylor series and security proofs

Taylor Series For some functions entered into Wolfram, a Taylor series expansion is represented in Big-O notation. E.g. $\sin x, x = \frac \pi4$ produces: $\frac {1} {\sqrt[]{2}} +\frac{x-\frac{\pi}...
2
votes
1answer
84 views

Difficulty of a congruence problem

The problem is described as follows. Let $c_1=p_1q_1+r$, $c_2=p_2q_2+r$, $\cdots$, $c_n=p_nq_n+r$, where $p_i$'s, $q_i$'s, $r$ are all large positive integers, and $p_i$'s and $q_i$'s are randomly ...
4
votes
1answer
293 views

Relation between “P is not equal to NP” and “Existence of One-Way Function”

We know that If there exists a one-way function, then P ≠ NP. Why can we not conclude that if P ≠ NP, then there exists a one-way function? Is there a polynomial time computable function that is hard ...
13
votes
3answers
493 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?
6
votes
0answers
230 views

how to understand the universal hash and the leftover hash lemma

I always meet the leftover hash lemma when I read some papers.But I only know the defination of universal hash and the leftover hash lemma.How to understand them and how to use them?
-1
votes
3answers
197 views

Can following discrete logarithm problem be considered as difficult?

For $m, m'$, is it possible to find $r, s, t$ such that $r^s = m$ and $r^t = m'$ in modulo $G$, where $G$ is a large prime. Do you think is it relatively easy to find such $r$ from $m$ and $m'$? ...
5
votes
0answers
155 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. ...
0
votes
0answers
149 views

Ciphertext attribute-based encryption complexities and performance

I am trying to analyze the performance of the Bethencourt CP-ABE (Ciphertext-Policy based, Attribute Based Encryption) scheme. Assume $e: G_0 \times G_0 \rightarrow G_T$ is a bilinear map where $G_0$...
0
votes
2answers
101 views

complexity of iterative squaring in relation to factorization

I've run into a question dealing with the number of modular multiplications of O(n) bit numbers in the following situation: Given two n bit primes p,q define m=pq. ​ ​ ​ Choose some 'a' so that ​ $2&...