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
1
vote
2
answers
75
views
How to prove that an algorithm is the time optimal algorithm for implementing a problem?
Given an objective function, we can give many programming implementations based on existing computers. Can we prove that the algorithm given is time optimal?
For example, if we give a recursive solver ...
- 21.2k
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
2
answers
73
views
Asymptotic efficiency of modular multiplication
What is the best known asymptotic/concrete complexity of modular multiplication?
Using Montgomery multiplication, if $M(n)$ is the cost of one integer multiplication of $n$ bits, then the cost is $2M(...
- 12.4k
4
votes
4
answers
3k
views
Cryptography based on uncomputable problems?
A lot of cryptography is based on the assumption that ${\sf P} \neq {\sf NP}$.
Is it conceivable to construct a cryptography system based on a class of much harder problems than ${\sf NP}$-problems, ...
- 51
15
votes
2
answers
6k
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....
- 9,001
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
4
votes
4
answers
381
views
Average- and worst-case complexity
The terms "average-case", "worst-case" hardness are quite confusing.
What do they mean when they say certain problems (like lattices)
have an average-case to worst-case ...
- 363
1
vote
2
answers
159
views
State recovery algorithm for Xorshift128 given modular outputs
I am researching the Xorshift128 PRNG. I am particularly interested in recovering the state given a set of outputs that have the remainder taken with different values.
A common way to take a unsigned ...
CommunityBot
- 1
2
votes
1
answer
47
views
A problem related to two bitwise sums of rotations of two different bitstrings
Let $r(b, t)$ denote the bitstring $b$ rotated to the left by $t$ bits: for example, $r(00110101, 5) = 10100110.$
Consider the following game. Player A picks two (different) $n$-bit strings $(T_1, T_2)...
- 21.9k
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
1
answer
85
views
How does the security of AES change if we allow multiple uses in a row? How does it change if we limit the key space? And introduce a filter function?
$$f_0 = A$$
$$f_{n+1}=AES(f_n,k_n)$$
$$f_i = B$$
For given 128-bit values $A, B$ we want to find a chain of suitable 128-bit keys $k_1$ to $k_i$.
The total length $i$ is undetermined. Every valid key ...
CommunityBot
- 1
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, $...
- 138k
1
vote
2
answers
100
views
Circuits for general computing
In TCS, functions need to be converted into boolean circuits.
So is this Boolean circuit a combinational logic, i.e. a directed acyclic graph, satisfying the topological order?
I would appreciate your ...
- 112
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 ...
- 445
1
vote
2
answers
94
views
Can we find pairs $(c,m)$ with $f(c)=f(m)=true$ in $c = AES(m,K)$ with a fixed known Key $K$ significantly faster than brute force?
Different to the usual adversary use case we do not want to find the hidden key but instead pairs of $(m,c)$ which each fulfill a certain property $f(x)=true$
An example property could be e.g. 42 ...
- 554
0
votes
1
answer
120
views
How much Computer Science theory needs to be learnt for learning zkSnarks & what is a good book for it?
My background is that of a reasonably experienced programmer who hasn't learnt Comp Science formally. I am now learning Cryptography as a hobby in my spare time & I think I have learnt a ...
- 700
1
vote
2
answers
61
views
Linear complexity of real and complex sequences
In cryptography output sequences of stream ciphers are binary valued (or more generally finite field valued). However mathematically sequences over real and complex variables can also be generated by ...
- 21.9k
3
votes
1
answer
150
views
Quantifying the success probability of brute force attack against (search) LPN
I've been trying to learn about attacks on LPN ($n$-bit secret, noise rate $\eta$), and have found several allusions to a brute force algorithm that runs in time exponential in $n$ and requires a ...
- 21.9k
1
vote
1
answer
200
views
Why mining bitcoins is difficult?
As I understand to obtain a Golden Block is to finding a nonce that matches a hash lower than a given target, as shown in this research-gate article.
And here is a "py" kernel: Bitcoin ...
- 452
5
votes
1
answer
302
views
Which is the smallest, cyclic in 3 directions, consistent structure of random values which can be hidden at the adversaries machine? (some comparison)
Or more general each member can be part of up to three 2D locally euclidean planes of 2 different dimensions each.
(each of those planes is cyclic in two orthogonal directions, like a torus)
Given ...
- 573
1
vote
1
answer
312
views
If RSA uses $e$ with $\gcd(e,\phi(N))\ne1$ but $e$ is hard to factorize has an adversary still an advantage in finding $d$ for $m^{ed}\equiv m\mod N$?
Usually RSA uses an encryption exponent $e$ with $\gcd(e,\phi(N))=1$.
This question shows why that need to be the case: For $\ne1$ there might exist no decryption exponent $d$ because other $m'\ne m$ ...
- 573
1
vote
0
answers
32
views
big-O (time complexity) for AES (CBC - mode) [duplicate]
I have been searching for many days about the time complexity of O(n) for AES (preferably CBC mode). Moreover, I am searching for formal documents like papers/books/standards. I found this paper: ...
- 187
4
votes
2
answers
184
views
Cryptography based on #P-complete problems
Are there any examples of a cryptographic scheme based on (an average-case form of) a #P-complete problem?
- 5,133
1
vote
1
answer
81
views
What is the Work Factor of the one time pad?
Work Factor is defined as the minimum amount of work (can be the length of the key) to determine the secret key of an cryptosystem (HAC, Menezes, Alfred J. et al).
And One time pad have unconditional ...
- 138k
3
votes
1
answer
1k
views
RSA decryption using CRT: How does it affect the complexity?
There is an efficient variant of the RSA using the CRT:
\begin{align*}
d_p &= d \pmod{p-1}\\
d_q &= d \pmod{p-1} \\
q_{\operatorname{inv}} &= q^{-1} \pmod{p}
\end{align*}
where the ...
- 145k
1
vote
1
answer
114
views
Does generic group black box model prohibit MSB of discrete logarithm?
Black box generic models prohibit calculation of discrete logarithm in groups of order $q=2p+1$ where $p,q$ are random primes to $\Omega(\sqrt{p})$ steps (refer Discrete Logarithm in the generic group ...
- 145k
7
votes
1
answer
516
views
Notion of elementary operation when complexities in the form of $2^{128}$
In lots of cryptoanalytic papers I read, attack complexities are stated in the form of a constant. For example, this related key attack on of AES states:
[...] For AES-256 we show the first key ...
- 2,565
1
vote
1
answer
116
views
Complexity of Hash mining/signing
While reading about mining in crypto currency, I found that it requires some leading bits of a hash function output to be 0. This boils down to preimage resistance of the hash function, hence done ...
- 2,565
3
votes
2
answers
199
views
LWE with the matrix A repeated
Consider the following version of Learning With Errors.
You are either given $(A, As_1 + e_1, As_2 + e_2, \ldots, As_k + e_k)$ or $(A, u_1, u_2, \ldots, u_k)$, where
$A$ is an $m \times n$ matrix ...
- 11.6k
1
vote
1
answer
52
views
How secure is a projection to a subspace with much lower member size for $x\mapsto x^a$ mod $N = PQ$, $P=2p+1$, $Q=2qr+1$, to target space $r=2abc+1$?
A cyclic sequence can be produced with
$$s_{i+1} = s_i^a \mod N$$
with $N = P \cdot Q$ and $P = 2\cdot p+1$ and $Q = 2\cdot q\cdot r+1$ and $r = 2\cdot u \cdot v \cdot w +1$ with $P,Q,p,q,r,u,v,w$ ...
- 21.9k
2
votes
1
answer
42
views
How difficult is finding $i$ for sequence $s_{i} = g^{s_{i-1}} \mod P$ with $s_0 = g$ for given value $v\in [1,P-1]$
Assuming we found a constant $g$ and a prime $P$ which is able to produce all values from $1$ to $P-1$ with it's sequence
$$s_{i} = g^{s_{i-1}} \mod P$$
$$s_0 = g$$
How many steps are needed to ...
- 21.9k
2
votes
1
answer
80
views
How difficult is finding $i$ in tetration $^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\cdot^{g}}}}_i\equiv v \mod P$ for $v\in[1,P-1]$
EDIT: I messed up something (see comments at answer). This question contains some false statements EditEnd.
For tetration modulo prime $P$
$$^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\...
- 573
4
votes
2
answers
101
views
Is it possible to construct a 1-out-of-N OT with communication complexity smaller than the sender's whole input?
The constructions of 1-out-of-$n$ OT for $l$-bit strings I've seen had communication complexity proportional to $nl$. I wonder, is it possible to do OT with active security and transfer less than $O(...
- 19.1k
3
votes
1
answer
151
views
Questions regarding the pseudorandom function construction of Banerjee, Peikert, and Rosen
I am trying to understand the following pseudorandom function constructed by Banerjee, Peikert, and Rosen in this paper, assuming the hardness of LWE. Consider the following LWE/LWR based pseudorandom ...
- 11.6k
-1
votes
1
answer
185
views
What is the time and space complexity of the AES S-boxes? [closed]
What are the time and space complexity of the AES S-boxes? Could someone please explain how these are determined?
- 11.7k
0
votes
1
answer
196
views
Comparing different cipher text all saying the same thing
How can I compare different cipher text? When deciphered, say the same thing. I would like to find out the ciphering method. Any help would be appreciated. Thanks.
The primary code needs to be a 8 ...
- 3
2
votes
1
answer
177
views
LWE and extended trapdoor claw free functions
Let $q \geq 2$ be a prime integer. Consider two functions, given by:
$$f(b, x) = Ax + b \cdot u + e~~~(\text{mod}~q),$$
$$g(b, x) = Ax + b \cdot (As + e') + e~~~(\text{mod}~q),$$
where we have:
\begin{...
- 11.6k
4
votes
2
answers
311
views
Time Complexity Of Solving DLog When g and P are known
This (https://en.m.wikipedia.org/wiki/Discrete_logarithm) Wikipedia article confuses me. If you have the equation a = g^n (mod P), and g, P and a are all known, then how does a brute force solving for ...
- 47.5k
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
3
answers
608
views
Berlekamp–Massey input sequence length
For a given periodic sequence of length $N$ for which minimal polynomial is being constructed. Does the Berlekamp-Massey algorithm take the input of $2N$, i.e., the repeated input sequence or just the ...
- 47.5k
6
votes
1
answer
508
views
Why Zero-Knowledge protocols are used for NP problems if IP is the class of interactive proof systems where they come from?
As stated in the title, I'm studying ZKPs and I see they are just interactive proof systems that respect the zero-knowledge property. Now, if that's true, why aren't they used for IP problems, the ...
- 27.6k
0
votes
1
answer
231
views
Rabin-Miller primality test complexity
I was thinking about the complexity of the Rabin-Miller primality test.
On wikipedia I find O(k log3n), but there is no explanation.
My idea was too simple. To see if n is prime, we have k attempts ...
- 21.2k
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
9
votes
1
answer
3k
views
A discrete-log-like problem, with matrices: given $A^k x$, find $k$
Let $p$ be a large prime; we will work in $GF(p)$. Let $A$ be a $n\times n$ matrix. Also, let $x$ be a $n$-vector and $k$ a positive integer.
Suppose we are given $p$, $A$, $x$, and $y$. The goal ...
- 36.2k
2
votes
2
answers
394
views
Does SHA-256 have (128-time + 128-space = 256-overall)-bit collision resistance?
First, we consider those hash functions that can actually provide 256-bit pre-image security, and not something like SHAKE128<l=256bits> where the sponge ...
- 138k
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
1
vote
1
answer
259
views
Time complexity of a brute force attack on Shamir's Secret Sharing SSS
I have searched everywhere in academic papers about time complexity of a brute force attack on a Shamir's Secret Sharing key. I'm confused between if it is $O(p^k)$ or $O(p)$, such that $p$ is the ...
- 145k
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 ...
- 441
3
votes
1
answer
18k
views
How do I derive the time complexity of encryption and decryption based on modular arithmetic?
I want to calculate the time complexity of two encryption and decryption algorithms.
The first one (RSA-like) has the encryption
$$ C := M^e \bmod N $$
and decryption
$$ M_P := C^d \bmod N. $$
...
- 138k
5
votes
3
answers
1k
views
Why do Problems for Post-Quantum algorithms have to be NP-Hard?
The mathematical problems used for Post-Quantum Cryptography problems I came across, are NP-complete, e.g.
Solving quadratic equations over finite fields
short lattice vectors and close lattice ...
- 191