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
0 answers
51 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 ...
Stevie's user avatar
  • 121
3 votes
1 answer
172 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: &...
NB_1907's user avatar
  • 610
0 votes
1 answer
34 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 ...
vxek's user avatar
  • 447
0 votes
0 answers
140 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 ...
ysnky's user avatar
  • 1
1 vote
1 answer
91 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, ...
user1035648's user avatar
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 ...
BlackHat18's user avatar
1 vote
2 answers
85 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 ...
槿铃兔's user avatar
1 vote
0 answers
67 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, ...
Emison Lu's user avatar
  • 112
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, ...
Dominic van der Zypen's user avatar
1 vote
2 answers
81 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(...
Sam Jaques's user avatar
  • 1,135
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,...
lyrically wicked's user avatar
2 votes
1 answer
59 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)...
lyrically wicked's user avatar
1 vote
2 answers
202 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 ...
joemelsha's user avatar
1 vote
0 answers
33 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},...
stack_math's user avatar
4 votes
4 answers
443 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 ...
user1035648's user avatar
1 vote
2 answers
102 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 ...
Emison Lu's user avatar
  • 112
4 votes
0 answers
88 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 ...
CHTM's user avatar
  • 41
1 vote
2 answers
98 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 ...
J. Doe's user avatar
  • 573
1 vote
1 answer
88 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 ...
J. Doe's user avatar
  • 573
0 votes
1 answer
129 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 ...
user93353's user avatar
  • 2,199
1 vote
2 answers
62 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 ...
Viren Sule's user avatar
3 votes
1 answer
158 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 ...
Gordon's user avatar
  • 33
1 vote
1 answer
330 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$ ...
J. Doe's user avatar
  • 573
1 vote
0 answers
33 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: ...
just_learning's user avatar
1 vote
1 answer
87 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 ...
charles's user avatar
  • 143
4 votes
2 answers
188 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?
a196884's user avatar
  • 381
5 votes
1 answer
313 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 ...
J. Doe's user avatar
  • 573
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 ...
Pazu's user avatar
  • 133
1 vote
1 answer
121 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 ...
Turbo's user avatar
  • 908
7 votes
1 answer
522 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 ...
cryptobeginner's user avatar
3 votes
2 answers
234 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 ...
BlackHat18's user avatar
1 vote
1 answer
53 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$ ...
J. Doe's user avatar
  • 573
2 votes
1 answer
43 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 ...
J. Doe's user avatar
  • 573
2 votes
1 answer
82 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\...
J. Doe's user avatar
  • 573
-1 votes
1 answer
198 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?
Aktar1990's user avatar
3 votes
1 answer
153 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 ...
BlackHat18's user avatar
0 votes
1 answer
214 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 ...
Adi's user avatar
  • 1
2 votes
1 answer
192 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{...
BlackHat18's user avatar
4 votes
2 answers
111 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(...
Ivan's user avatar
  • 41
4 votes
2 answers
313 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 ...
Darcy Sutton's user avatar
1 vote
0 answers
80 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, ...
mrose's user avatar
  • 111
1 vote
3 answers
643 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 ...
Mathpdegeek497's user avatar
6 votes
1 answer
551 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 ...
Andrea Farneti's user avatar
0 votes
1 answer
367 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 ...
killertoge's user avatar
0 votes
0 answers
88 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 ...
Natwar's user avatar
  • 441
2 votes
2 answers
437 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 ...
DannyNiu's user avatar
  • 9,080
2 votes
0 answers
143 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 ...
Fateh's user avatar
  • 107
1 vote
1 answer
120 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 ...
hola's user avatar
  • 603
1 vote
1 answer
282 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 ...
hambam's user avatar
  • 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 ...
Marc's user avatar
  • 297

1
2 3 4 5 6