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.
256
questions
-1
votes
0
answers
78
views
Could we build PSPACE-based cryptography - more secure post-quantum? [closed]
It seems not safe to exclude possibility of e.g. some next generation quantum computers being able to attack NP problems (e.g. 2WQC) - so maybe it is worth to start thinking of shifting the ...
- 107
0
votes
1
answer
31
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(...
- 1,065
1
vote
0
answers
34
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,248
2
votes
1
answer
46
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)...
- 1,248
1
vote
2
answers
139
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 ...
- 11
1
vote
0
answers
27
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
4
votes
4
answers
343
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 ...
- 347
1
vote
2
answers
97
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 ...
- 102
4
votes
0
answers
69
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
1
vote
2
answers
86
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 ...
- 571
1
vote
1
answer
82
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 ...
- 571
0
votes
1
answer
113
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 ...
- 2,167
1
vote
2
answers
58
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 ...
- 141
3
votes
1
answer
146
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 ...
- 33
1
vote
1
answer
248
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$ ...
- 571
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
1
vote
1
answer
79
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 ...
- 143
4
votes
2
answers
177
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?
- 381
5
votes
1
answer
297
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 ...
- 571
3
votes
1
answer
950
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 ...
- 133
1
vote
1
answer
104
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 ...
- 908
7
votes
1
answer
514
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 ...
- 347
3
votes
2
answers
178
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 ...
- 347
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$ ...
- 571
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 ...
- 571
2
votes
1
answer
78
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\...
- 571
-1
votes
1
answer
171
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?
- 13
2
votes
1
answer
133
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 ...
- 347
0
votes
1
answer
169
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 ...
- 1
2
votes
1
answer
167
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{...
- 347
4
votes
2
answers
96
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(...
- 41
4
votes
2
answers
304
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 ...
- 300
1
vote
0
answers
71
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
567
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 ...
6
votes
1
answer
473
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 ...
- 131
0
votes
1
answer
155
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 ...
- 299
0
votes
0
answers
82
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
2
votes
2
answers
358
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 ...
- 8,648
2
votes
0
answers
130
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
115
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 ...
- 603
1
vote
1
answer
251
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 ...
- 21
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 ...
- 297
4
votes
0
answers
309
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
1
vote
0
answers
61
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
2
votes
1
answer
97
views
Why the differential cryptanalysis complexity is linear with inverse of the probability while linear cryptanalysis is quadratic with the bias inverse?
I am trying to understand the analysis of the complexity of Differential Cryptanalysis versus the complexity of linear cryptanalysis.
In differential cryptanalysis the number of required texts is $\...
- 23
2
votes
0
answers
145
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
0
votes
1
answer
913
views
How fast is hashing and is it always regarded as an O(1) operation? [closed]
I've wondered how hashing can be such a fast operation. It's so fast that nobody talks about it in terms of performance and complexity.
I know that in terms of big O notation, you can drop all the ...
- 101
0
votes
1
answer
171
views
How to compare the time of encryption, cracking and verification elliptic curve problem in the same framework？
everyone! As a beginner, I would like to ask you a question. The best algorithm known for cracking (done by anonymous snooper) this problem （Discrete logarithm problem of elliptic curve or ECDSA）is ...
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
2
votes
1
answer
128
views
What language classes beyond NP allow constant-round zero-knowledge proofs?
While discussing proving a language in $\Sigma_2$ from a client to a server with a friend we realized that while we know that such a language is provable in zero-knowledge, we didn't know whether it ...
- 45.6k