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
2
votes
2
answers
225
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 ...
- 273
1
vote
1
answer
118
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 ...
- 273
0
votes
1
answer
435
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 $,...
- 211
2
votes
1
answer
612
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?
- 23
1
vote
1
answer
1k
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 ...
- 258
4
votes
0
answers
282
views
Complexity: Taylor series and security proofs [closed]
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}...
- 214
2
votes
1
answer
126
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 ...
- 65
7
votes
1
answer
1k
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 ...
- 73
13
votes
3
answers
1k
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?
- 229
9
votes
0
answers
443
views
how to understand the universal hash and the leftover hash lemma [closed]
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?
- 229
-1
votes
3
answers
321
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'$? ...
- 101
6
votes
0
answers
190
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.
...
- 908
1
vote
0
answers
396
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 ...
- 219
0
votes
2
answers
161
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&...
- 225
3
votes
1
answer
207
views
Combining Hellman Pohlig with Sieve
Suppose integer $m$ has $\phi(m)=2pq^5r^2$ where $p,q,r$ are primes.
Hellman-Pohlig says that finding discrete log $z\bmod p$, $z\bmod q^5$, $z\bmod r^2$ and $z\bmod 2$ suffices to find $z\bmod\phi(m)...
- 908
0
votes
1
answer
251
views
Better than diceware? And sha512 related question [closed]
I am working on a secure password generator based on the following setup:
choose a publicly know (text) file
make some deliberate memorable changes to it
use collected entropy for a secure password ??...
- 13
2
votes
1
answer
422
views
How to measure the complexity of the discrete logarithm problem?
I looked here. The answer basically says that to calculate the complexity of the logarithm problem we have to take the length of the number representing the size of the group into accounts. It seems ...
1
vote
1
answer
206
views
Difference between computational complexities in General Number Field Sieve
I'm told that General Number Field Sieve works with computational complexity $e^{\sqrt[3]{\frac{64}{9}+o(1)}\;(\ln n)^{\frac{1}{3}}\;(\ln\ln n)^{\frac{2}{3}}}$. However, without some computation work ...
- 1,243
4
votes
2
answers
1k
views
o(1) in time complexity of number field sieve
It is well known that the time complexity of the number field sieve can be calculated by the formula
$$\exp\big((C+o(1)) (\log n)^{1/3}(\log \log n)^{2/3}\big)$$
The constant C is known for the ...
user27950
2
votes
1
answer
591
views
Computational Cost of bilinear maps
What is the exact computational complexity in absolute operation numbers (multiplications, exponentiations, etc) of a bilinear map evaluation both for symmetric and asymetric groups. And how this is ...
- 6,140
1
vote
0
answers
26
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 ...
- 11
3
votes
1
answer
3k
views
Probabilistic polynomial time algorithms in MAC's
According to the Wiki article, a MAC is a triple of probabilistic polynomial time algorithms $(G, S, V)$ such that:
G gives the key k on input 1^n, where n is the security parameter
S outputs a tag ...
2
votes
1
answer
2k
views
2DES Meet in the middle attack complexity
In the meet-in-the-middle attack, if we built the tables first and then looked for matches, we would have another high complexity problem. For each of the table 1 entries, compare with all the table 2 ...
- 91
2
votes
1
answer
223
views
Does this proof sketch show that finding a SHA-1 preimage is NP-hard?
Jutla & Patthak wrote "Is SHA-1 conceptually sound?" back in 2005, in which they provide a proof sketch (Appendix A) to show that finding a preimage for SHA-1 is NP-hard. Now, there are some ...
- 348
4
votes
1
answer
231
views
Offline Complexity of the garbling scheme
The offline complexity of the garbling scheme means the time complexity of the circuit encoding algorithm, that is, $\textrm{GC.Circ}(1^\lambda, C)$, where $C$ is the circuit to be garbled. It's ...
- 932
4
votes
1
answer
81
views
How to compute the output length of randomized encoding (or garbling)?
We consider randomized encoding for circuits as a equivalent primitive as the circuit garbling scheme. However, I have a question arised from their syntax, that is, how to compute the output length of ...
- 932
5
votes
2
answers
1k
views
What's the definition of the width of a circuit
We consider the size and depth of a circuit under most situations, but recently I read some papers which consider the “width” of a circuit, so I wonder what's the definition of the width of a circuit? ...
- 932
1
vote
0
answers
32
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{...
- 932
3
votes
1
answer
119
views
PRNG output with truly random noise
I am considering a situation where an adversary does not have access to the $n$-bit output string of a PRNG, but instead receives a noisy version of it, where each bit of the string is flipped with ...
2
votes
3
answers
1k
views
What is the point of differential cryptanalysis when the amount of necessary plaintext is unrealistic?
As someone with a non-crypto background, I learned that differential cryptanalysis is mostly weak against ciphers like DES because, being a chosen plaintext attack, for a state of art complexity of $2^...
- 141
4
votes
0
answers
91
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{...
- 141
4
votes
2
answers
1k
views
Importance of round complexity in determining the efficiency of an MPC protocol
Literature has different ways of specifying complexity of an MPC protocol:
computation complexity that measures the number of (assumed primitive) operations performed by all the parties;
...
- 540
19
votes
1
answer
990
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 ...
- 1,265
-2
votes
1
answer
122
views
Carmichael's function in Cryptography
The Carmichael's function says that for $a\in \mathbb{Z}_n^*$, if $gcd(a,n)=1$, then
\begin{equation}
a^{\lambda(n)} \equiv 1 \;(mod\; n).
\end{equation}
My aim is to find $a$ if factorization of $n$ ...
1
vote
2
answers
790
views
Time complexity of looking up in a rainbow table
It is mentioned in the famous paper Making a Faster Cryptanalytic Time-Memory Trade-Off (pdf) by Philippe Oechslin that:
The total number of calculations we have to make is thus
$\frac{t(t−1)}{2}$...
- 51
19
votes
2
answers
2k
views
Practical differences between circuits and turing machines for cryptography
In formal cryptography, we model algorithms (mostly our adversaries) as (Probabilistic) Turing Machines or as boolean circuits. In our lecture on formal cryptography, we learned that circuits are more ...
- 1,420
3
votes
0
answers
270
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-...
- 131
4
votes
2
answers
1k
views
Is AES solvable by reducing to SAT?
Consider a known plaintext attack on AES — just so we have an actual system of equalities that we can feed to a SAT solver.
Is AES solvable in this way? In other words, will the algorithm eventually ...
user9070
1
vote
0
answers
247
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 ...
- 153
3
votes
2
answers
1k
views
Running time of Shamir's secret sharing scheme
Let $p>n$ be a prime number. The key steps in the $(t,n)$ Shamir's secret sharing is as follows:
Steps of dealer:
Choosing $s \in \mathbb{Z}_p^*$
Selecting $b_i \in \mathbb{Z}_p^*$ for polynomial ...
- 499
0
votes
1
answer
155
views
Can a low density subset sum problem be intractable?
Hardness of a subset sum problem depends on it's density.
Is it possible for a subset sum problem to be intractable even if it's density is less than 0.9408?
0
votes
1
answer
91
views
Function with no fast path and with fast proof
When a function is iterated and each time a previous result is used as input to the next iteration (feedback), so that there is a limited benefit from parallel computing, is there such function that:
...
1
vote
1
answer
553
views
Finding a secret cipher given the key and known plaintext?
Let $x,y,k$ be plain text, cipher text and key respectively. Also suppose $\operatorname{Enc}$ is the algorithm of encryption for block cipher with size $n$. So we have
$$\operatorname{Enc}_k(x)=y$$
...
- 2,323
1
vote
1
answer
3k
views
Time complexity of trial division
Suppose $n=pq$, where $p,q$ are prime numbers.
Let $p ( \le q)$ be the smallest prime, then we know that $p \le \sqrt{n}$.
In trail division, we check $n \mod i$ for the values of $i$ from 2 to $\...
- 499
-2
votes
1
answer
92
views
Find a constant $C$ in $O(Cn^2)$?
I am writing a paper on RSA, and I am calculating some encryption running times.
I have been told that the encryption running time is $O(n^2)$ where $n$ is the modulus. I have also been told that ...
- 13
2
votes
0
answers
674
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 ...
- 442
5
votes
1
answer
827
views
Usage of Zero-knowledge proofs for NP-complete languages
It is well known that if OWFs/PRGs exist, then there is a zero knowledge proof for any NP-complete language, say G3C (graph coloring in 3 colors). The zero-knowledge notion maintains that any ...
- 51
3
votes
1
answer
152
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 ...
- 502
0
votes
3
answers
515
views
How can complexity be increased or decreased in AES?
I have been studying data compression for a while. For educational purposes, after a lot of reading, I managed to create a software that performs encryption and authentication using AES256-GCM. ...
- 23
2
votes
1
answer
3k
views
computational complexity class of decryption of AES [closed]
I haven't really seen what computational complexity class of decryption of AES is. Can anyone provide reference papers or answers here?
- 21