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
1 vote
1 answer
43 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 ...
user avatar
  • 111
4 votes
2 answers
151 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?
user avatar
  • 349
0 votes
0 answers
42 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 of those planes is cyclic in two orthogonal directions, like a torus) Given just ...
user avatar
  • 869
3 votes
1 answer
422 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 ...
user avatar
  • 133
1 vote
1 answer
65 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 ...
user avatar
  • 872
7 votes
1 answer
488 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 ...
user avatar
3 votes
2 answers
67 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 ...
user avatar
1 vote
1 answer
37 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$ ...
user avatar
  • 869
2 votes
1 answer
40 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 ...
user avatar
  • 869
2 votes
1 answer
66 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\...
user avatar
  • 869
-1 votes
1 answer
98 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?
user avatar
2 votes
1 answer
101 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 ...
user avatar
0 votes
1 answer
51 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 ...
user avatar
  • 1
2 votes
1 answer
81 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{...
user avatar
4 votes
2 answers
60 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(...
user avatar
  • 41
3 votes
2 answers
262 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 ...
user avatar
1 vote
0 answers
57 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, ...
user avatar
  • 111
1 vote
3 answers
208 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 ...
user avatar
5 votes
1 answer
251 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 ...
user avatar
0 votes
0 answers
29 views

Besides block-cipher which other methods can only be computed step-by-step even with known secret (but fast per step) and can be inverted?

Depending at the cryptographic function used applying it $i$-times to a given input can be computed in different complexity classes (based at their input size). $$f^i(m_0) = c_i$$ For example for most ...
user avatar
  • 869
0 votes
1 answer
56 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 ...
user avatar
0 votes
0 answers
71 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 ...
user avatar
  • 421
2 votes
2 answers
158 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 ...
user avatar
  • 6,541
2 votes
0 answers
86 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 ...
user avatar
  • 107
1 vote
1 answer
100 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 ...
user avatar
  • 593
1 vote
1 answer
125 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 ...
user avatar
  • 21
0 votes
0 answers
30 views

Working of Algorithm on SP network by Kam and L. Davida

I am reading the paper titled "Structured Design of Substitution-Permutation Encryption Networks". by John B. Kam and Georges I. Davida (1979) They have presented and algorithm for ...
user avatar
4 votes
3 answers
841 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 ...
user avatar
  • 276
4 votes
0 answers
264 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 ...
user avatar
  • 182
1 vote
0 answers
58 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 ...
user avatar
  • 11
2 votes
1 answer
63 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 $\...
user avatar
  • 23
2 votes
0 answers
87 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 $\...
user avatar
  • 872
0 votes
1 answer
201 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 ...
user avatar
  • 101
0 votes
1 answer
157 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 ...
user avatar
0 votes
0 answers
32 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 ...
user avatar
  • 149
2 votes
1 answer
68 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 ...
user avatar
  • 44.5k
8 votes
1 answer
242 views

Is Indistinguishability Obfuscation Real?

I've recently stumbled upon an interesting Quanta Magazine article. It states that indistinguishability obfuscation (iO) 's theoretical feasibility has been proven, referencing a relatively recent ...
user avatar
1 vote
1 answer
92 views

Show that there is an efficient zero knowledge proof for any language $L \in NP$

Let $(P,V)$ be an efficient zero-knowledge interactive proof for some language $A \in NP$ that is $(T,\epsilon)-\text{sound}$ and $(T,\epsilon)-\text{ZK}$. I want to show that for every language $L$ ...
user avatar
  • 155
0 votes
0 answers
46 views

Composing subexponential L-function

Suppose $y=f(x)$ and $z=g(y)$ such that $y\in L_x[a,b]$ and $z\in L_y[c,d]$, where $L$ is the usual sub-exponential asymptotic notation $$L_x[a,b] = \exp\left((b+o(1))(\log x)^a(\log\log x)^{1-a}\...
user avatar
2 votes
2 answers
140 views

Provable Lower Bounds for some Algorithmic Problems?

Are there any problems for which we have known lower bounds? For example, for comparison based sorting, we know you need $\Omega(n \log n)$ comparisons. Edit: I'm aware that this requires restricting ...
user avatar
  • 652
3 votes
1 answer
118 views

$P \ne NP$: a proof relating complexity theory to block ciphers

I started thinking about P vs NP after reading another question on this stack exchange. Here I propose a proof that relates P vs NP to the existence of a secure block cipher in the elf model. Let's ...
user avatar
  • 1,381
2 votes
1 answer
612 views

Complexity of Gaussian Elimination over a Finite Field

I read somewhere that the complexity of solving a Linear $n\times n$ system over a Finite Field $\Bbb F_q$ using Gaussian Elimination is $\mathcal{O}(n^3)$ operations in $\Bbb F_q$. What's the role of ...
user avatar
  • 21
1 vote
0 answers
81 views

Digital Signature Complexity [duplicate]

I'm not familiar with algorithm complexity so I'm asking here. I need help determining degital signature complexity, I did some research and all I found is complexity for the D.S.A only: 𝑂(𝐷𝑆𝐴 𝑆𝑖...
user avatar
6 votes
1 answer
145 views

If OWF were to exist, do we know for sure that one of the candidate OWF would indeed be a OWF?

We have several candidates for OWF, like multiplication/factoring and discrete exponencial/logarithm. What I am asking is: Does the existence of one way functions imply that our candidate functions ...
user avatar
0 votes
1 answer
82 views

On splitting vs factoring

On page 89 Remark 3.5 in the Handbook of Applied Cryptography the following is written: A non-trivial factorization of $n$ is a factorization of the form $n = ab$ where $1 < a < n$ and $1 &...
user avatar
  • 565
2 votes
2 answers
190 views

When is a cryptosystem or its algorithm (like RSA) considered efficient?

When is a cryptosystem (like RSA) or its algorithm for keygeneration, encryption and decryption of messages considered efficient? Is there some bound in complexity which splits both efficient and not ...
user avatar
0 votes
1 answer
187 views

Number of operations for Elgamal cryptosystem

In page 408 of Hoffstein, Piper, and Silverman's Introduction to Mathematical Cryptography, it says "Roughly speaking, in order to achieve $k$ bits of security, encryption and decryption for ...
user avatar
  • 3
3 votes
1 answer
228 views

Is there a multiplicative group of integers modulo p in which the discrete logarithm is easy?

The complexity of computing discrete logarithms in a multiplicative group modulo a prime $p$ is assumed to be sub-exponential time. The complexity is determined by $q$, the biggest factor of the group ...
user avatar
  • 217
9 votes
0 answers
112 views

Hardness of iterated squaring in Pailler 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, $...
user avatar
  • 4,463
4 votes
2 answers
348 views

What makes AES look like an ideal cipher?

There are 2128! permutations on 128-bit inputs. AES supports a maximum key length of 256 bits, therefore offers at most 2256 permutations. The total number of 128-bit permutations is much larger than ...
user avatar
  • 657

1
2 3 4 5