Stack Exchange Network

Stack Exchange network consists of 175 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

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.

6
votes
0answers
164 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. ...
5
votes
0answers
95 views

P-Complete hashes, hashing to a larger set

Historically hashes have been from a large set (say 256 characters) to a smaller set (256 bits). Also, hash functions that are P-complete have no known parallel algorithm; they must be computed ...
4
votes
0answers
144 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$ ...
4
votes
0answers
167 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}...
4
votes
0answers
76 views

Computing cost for a trillionaire to compute GNFS in RFC 3766

RFC 3766, Section 4.1 discusses picking $n$ to achieve some target cost for employing the GNFS, i.e., $T$ is known and $N$ is unknown in the below equation: $$T = \kappa \cdot \exp{\left(c \cdot (\ln{...
3
votes
0answers
70 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 ...
3
votes
0answers
161 views

Majority encryption algorithm?

Assume that I want to leave an encrypted message to a group of $n$ people in a way that they can only decrypt it if they work together in the following sense: For some fixed $k < n$ every sub-...
2
votes
0answers
45 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 ...
2
votes
0answers
50 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
0answers
47 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(nlogn) ...
1
vote
0answers
53 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}[\...
1
vote
0answers
107 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
0answers
33 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 ...
1
vote
0answers
51 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/...
1
vote
0answers
20 views

Use of elapsed execution time as a variable input

Given that, with a significant number of decimals, it may be difficult to predict elapsed execution time of a piece of code, despite having knowledge of exact hardware and software specifications; is ...
1
vote
0answers
26 views

Weakly Sublinear Compact FE from Succinct FE and XiO

I'm confused about a problem these days and I decided to seek an answer here. The question is about the section 4.1 of the paper LPST16. Let me recall the weakly sublinear compact FE scheme $\textrm{...
1
vote
0answers
139 views

Best/average/worst-case complexity for cryptography

I understand that the complexity of a problem can be measured by it's best-case, average-case, or worst-case complexity. Am I correct in thinking that, for cryptographic purposes, each of these is of ...
1
vote
0answers
497 views

Performance of Fully homomorphic encryption VS Paillier encryption in Practice

Consider two schemes both have computation complexity linear to the input size (i.e. number of inputs). One scheme is based on Paillier encryption and the other one is based on fully homomorphic ...
1
vote
0answers
300 views

Complexity of verifying OTP secret

What is the minimum number of unique pairs of digests and inputs to a one-time pass needed to verify that a secret is equal to a ...
0
votes
0answers
24 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 ...
0
votes
0answers
56 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 ...
0
votes
0answers
104 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 ...