Skip to main content

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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
167 views

Question about P and NP problem

There is a definition for NP shown below. Could anyone please explain why "By restricting the definition of NP to witness strings of length zero, we capture the same problems as those in P."?...
1 vote
1 answer
74 views

Why doesn't the existence of the Quadratic Sieve algorithm imply that integer factorization is in the class SUBEXP?

SUBEXP is defined as the intersection of DTIME(2^n^c) over all c>0. The order of the Quadratic Sieve algorithm is O(exp((k+o(1))(logN)^1/2(loglogN)^1/2)). Doesn't this imply that the decision ...
0 votes
0 answers
66 views

Difficulty of factoring large semiprime N if given a second value y = (p-1)*r, where r is a random large prime?

Lets say we have 2 public values: N and y $$ N = pq $$ $$ y = r(p-1) $$ Where p, q, and r are large primes, are different, have a large distance between them and are kept secret. I have three ...
3 votes
1 answer
2k views

Merkle Tree space complexity

When searching by using the Merkle tree, the time complexity is $\mathcal O(\log n)$ but I don't understand how space complexity is $\mathcal O(n)$. In my opinion, it should be also $\mathcal O(\log n)...
1 vote
1 answer
102 views

Discrete log problem - does luck exist?

Assume the discrete log problem: $g^x mod (p) = h$ For sure, $p$ is a prime number and $g$ is its primitive root or generator and assume that Alice sent $h$ to Bob and middle man caught it. So ...
0 votes
0 answers
55 views

What do we mean when we say we need more than polynomial time many cipher texts

What does it mean when we say something like „we need more than polynomial time many cipher texts“? I understand it as „an adversarial can run for polynomial time and try as many messages as possible ...
2 votes
0 answers
55 views

Inefficient double-lengthening PRG

I'm trying to prove that an inefficient double-lengthening PRG exists, i.e. construct a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{2n}$ My current approach is to bound the number of poly-time non-uniform ...
3 votes
1 answer
194 views

Testing whether the Euler Totient of a number equals to certain value

I have solved a problem in Project Euler. My solution was based on the finding the all numbers whose Euler Totient value equals to $13!$ However, while I was working on the problem, I thought that: &...
1 vote
1 answer
126 views

Decision LWE vs Search LWE: Which one is harder?

Sometimes if we have an attacker who's able to solve decision-LWE problem then we can use them (as a sub-routine) to solve (search) LWE problem, i.e., $\mathsf{sLWE} \leq \mathsf{dLWE}$. Conversely, ...
0 votes
1 answer
35 views

Can the runtime of a reduction help an adversary distinguish the reduction from the adversary's challenger?

Generally, in cryptography, the security of a scheme/protocol $\Pi$ relying on a hard problem $P$ is demonstrated by constructing a reduction $\mathcal{B}$ that takes as input an instance of the ...
0 votes
0 answers
188 views

Speed comparison of encryption algorithms

I am trying to compare various encryption algorithms in terms of encryption duration, decryption duration, information entropy, NPCR, UACI, and correlation coefficients. I used a Lena 256x256 ...
2 votes
1 answer
53 views

Learning the LWE secret with advice

I am trying to argue about the hardness of LWE, but in a setting that is different from the standard one. Consider the task of learning the LWE secret $s$ from noisy samples. The specifications of the ...
1 vote
2 answers
86 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 ...
1 vote
0 answers
70 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, ...
1 vote
2 answers
85 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(...
4 votes
4 answers
4k 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, ...
15 votes
2 answers
7k 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....
1 vote
0 answers
36 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,...
4 votes
4 answers
552 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 ...
1 vote
2 answers
304 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 ...
2 votes
1 answer
141 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 vote
0 answers
39 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},...
1 vote
1 answer
93 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 ...
10 votes
0 answers
160 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, $...
1 vote
2 answers
106 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 ...
4 votes
0 answers
96 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 ...
1 vote
2 answers
101 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 ...
0 votes
1 answer
139 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 ...
1 vote
2 answers
67 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 ...
3 votes
1 answer
162 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 ...
1 vote
1 answer
213 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 ...
5 votes
1 answer
320 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 ...
1 vote
1 answer
356 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$ ...
1 vote
0 answers
35 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: ...
4 votes
2 answers
194 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?
1 vote
1 answer
90 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 ...
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 ...
1 vote
1 answer
125 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 ...
7 votes
1 answer
525 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 ...
1 vote
1 answer
122 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 ...
3 votes
2 answers
291 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 ...
1 vote
1 answer
55 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$ ...
2 votes
1 answer
44 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 ...
2 votes
1 answer
87 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\...
4 votes
2 answers
131 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(...
3 votes
1 answer
155 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 ...
-1 votes
1 answer
208 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?
0 votes
1 answer
232 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 ...
2 votes
1 answer
227 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{...
4 votes
2 answers
318 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 ...

1
2 3 4 5 6