# 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
Filter by
Sorted by
Tagged with
1 vote
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 ...
1 vote
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, ...
1 vote
73 views

1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
1 vote
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$ ...
1 vote
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: ...
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?
1 vote
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 ...
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
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 ...
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 ...
1 vote
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 ...
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 ...
1 vote
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$ ...
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 ...