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.
42
questions with no upvoted or accepted answers
10
votes
0
answers
137
views
Hardness of iterated squaring in Paillier group
The (computational) problem of iterated squaring (IS) in the RSA group is defined as follows, where $\leftarrow$ denotes sampling uniformly at random:
Input: $(N,x,T)$, where $N$ is the RSA modulus, $...
- 5,133
9
votes
0
answers
572
views
Can LWE be NP-hard?
Regev's reduction shows that LWE is quantumly at least as hard as CVP with an approximation factor of $n/\alpha$ for $0<\alpha<1$. But I just watched this talk which said that if $\sqrt{n/\log n}...
- 1,095
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
5
votes
0
answers
115
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 ...
- 151
4
votes
0
answers
77
views
Is $g(x_1||x_2) = f(x_1 \wedge x_2)$ a one way function assuming f is a one way function
Intuitively I think not because assuming the bit string $x_1,x_2 \sim \{0,1\}^{n/2}$, $x_1 \wedge x_2$ is not uniformly random so if $g$ were still a one-way function then the fact that the definition ...
- 41
4
votes
0
answers
314
views
Cryptomania and NP $\cap$ co-NP
Cryptomania is usually presented as the Impagliazzo's world, which gives us public-key cryptography under the assumption that trapdoor OWFs exist.
For purposes of constructing public-key cryptography ...
- 223
4
votes
0
answers
141
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 ...
- 223
4
votes
0
answers
174
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$ ...
- 138k
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
3
votes
0
answers
305
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 ...
- 898
3
votes
0
answers
211
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 ...
- 269
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
2
votes
0
answers
135
views
Detailed running time analysis for Shamir secret sharing scheme
I am successfully working on Shamir's secret sharing scheme for few months. But the only issue I am facing is the calculation of theoretical time complexity.
Since I am from algorithmic background, I ...
- 107
2
votes
0
answers
154
views
Depth of $\operatorname{SHA-256}$ implementation by fan-in $2$ and fan-out $1$ Boolean circuits?
A fan-in $2$ and fan-out $1$ Boolean circuit is a circuit consisting of $\operatorname{AND}$, $\operatorname{OR}$ and $\operatorname{NOT}$ gates where number of inputs to $\operatorname{AND}$ and $\...
- 908
2
votes
0
answers
68
views
Balanced Feistel networks: Are there any lower bounds on the computational complexity of breaking a $k$-round Feistel cipher?
This paper by Patarin presents an attack (section 9) on balanced Feistel networks with $k$ rounds, where the input is a bit-string is of length $2n$. (Since it is balanced, this means each PRF takes ...
- 399
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
1
vote
0
answers
56
views
What exactly is the RAM program runtime?
In my previous understanding, if a RAM program requires $T$ read/write operations to memory during its execution, then the runtime of this RAM program is $T$. However, as I have read some literature, ...
- 112
1
vote
0
answers
35
views
A problem related to three outputs of the majority function for nine rotations of three bitstrings
Let $r(b,t)$ denote the bitstring $b$ rotated to the left by $t$ bits: for example, $$r(00110101,5)=10100110.$$
Let $m(b_1,b_2,b_3)$ denote the majority function: for example, $$m(10010111,00101110,...
- 1,327
1
vote
0
answers
32
views
Find Linear Complexity of sequence beginnings
I know that in order to find the linear complexity of the two sequence beginnings
$$(1,-1,0,-1,0,0,0,0,1,0,\dots)\in\mathbb{Z}_3^\mathbb{N}\\
(2,0,-1,-2,0,0,-2,2,-1,-2,\dots)\in\mathbb{Z}_5^\mathbb{N},...
- 111
1
vote
0
answers
72
views
Comparing complexity of RSA decryption with/without CRT
(Cross-listed on math stackexchange, received no replies)
For context, this is a homework question from an assignment already turned in. I am looking for better understanding of the concepts involved, ...
- 111
1
vote
0
answers
62
views
How efficiently can an attacker forge parts of a fingerprint?
If two devices do not trust each other yet, you can't simply send the correct fingerprint across: you have to manually verify it. I am looking into the security of comparing only random parts of a ...
- 11
1
vote
0
answers
59
views
Can Trivium ciphertext be decrypted by an adversary if the key is known, but the IV is not?
Suppose that the adversary is able to recover the key of Trivium cipher. But the associated IV is unknown to him. Will he be able to decrypt the ciphertexts without any complexity?
- 73
1
vote
0
answers
31
views
Help with next step in the Quadratic Sieve
So I am at the same step as someone from math.stackexchange but he never recieved an answer so I will copy-paste his question here:
Say, for N = 90283, I compute bound 𝐵=𝑒(12+𝑜(1))(ln(𝑛)ln(ln𝑛√))...
- 111
1
vote
0
answers
58
views
Why is this attack complexity equal that exact number of bit operations?
in the this paper,section 3,autors attack hamsi-256. Im trying to make a parametrized version, so i need to understand how do they estimate the complexity of attack in bit operations,that reads as ...
- 55
1
vote
0
answers
78
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 ...
- 573
1
vote
0
answers
98
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....
1
vote
0
answers
233
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 \...
- 125
1
vote
0
answers
75
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}[\...
- 143
1
vote
0
answers
219
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 ...
- 11
1
vote
0
answers
59
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 ...
- 43
1
vote
0
answers
73
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
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
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
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
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
1
vote
0
answers
390
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 ...
- 289
0
votes
0
answers
84
views
Which contemporary programming language is apt for implementation of algorithms in cryptography?
I am a researcher in cryptography. Most of the time I generally do theoretical/Mathematical work only and not doing the implementation part.
I am not able to get the feel about the time complexity of ...
- 441
0
votes
0
answers
38
views
Number of bit operations required for encryption in a Block cipher
I want to find out how many bit operations are performed for encryption in AES-128 with messages size $128$ bits.
For public key encryptions such as RSA and ElGamal, I know that number of bit ...
- 149
0
votes
0
answers
57
views
Composing subexponential L-function
Suppose $y=f(x)$ and $z=g(y)$ such that $y\in L_x[a,b]$ and $z\in L_y[c,d]$, where $L$ is the usual sub-exponential asymptotic notation
$$L_x[a,b] = \exp\left((b+o(1))(\log x)^a(\log\log x)^{1-a}\...
- 1,095
0
votes
0
answers
44
views
How to Solve Discret Log Computation Problem
Given $g^a$ in $Z_p$, it is hard to get the solution $a$. Everyone says yes, I wonder why it is hard. Could anyone give a specific mathematical way to show it is indeed hard?
0
votes
0
answers
72
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 ...
- 2,513
0
votes
0
answers
192
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 ...
- 11.7k