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
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
133
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.7k
8
votes
1
answer
387
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 ...
- 183
1
vote
1
answer
142
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$ ...
- 155
0
votes
0
answers
57
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}\...
- 1,095
2
votes
2
answers
166
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 ...
- 706
3
votes
1
answer
126
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 ...
- 1,441
2
votes
1
answer
1k
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 ...
- 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:
𝑂(𝐷𝑆𝐴 𝑆𝑖...
- 11
6
votes
1
answer
160
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 ...
- 173
0
votes
1
answer
94
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 &...
- 617
2
votes
2
answers
311
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 ...
- 123
0
votes
1
answer
244
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 ...
- 3
3
votes
1
answer
315
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 ...
- 217
10
votes
0
answers
137
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, $...
- 5,133
5
votes
2
answers
549
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 ...
- 719
2
votes
0
answers
68
views
Balanced Feistel networks: Are there any lower bounds on the computational complexity of breaking a $k$-round Feistel cipher?
This paper by Patarin presents an attack (section 9) on balanced Feistel networks with $k$ rounds, where the input is a bit-string is of length $2n$. (Since it is balanced, this means each PRF takes ...
- 399
9
votes
0
answers
572
views
Can LWE be NP-hard?
Regev's reduction shows that LWE is quantumly at least as hard as CVP with an approximation factor of $n/\alpha$ for $0<\alpha<1$. But I just watched this talk which said that if $\sqrt{n/\log n}...
- 1,095
1
vote
0
answers
59
views
Can Trivium ciphertext be decrypted by an adversary if the key is known, but the IV is not?
Suppose that the adversary is able to recover the key of Trivium cipher. But the associated IV is unknown to him. Will he be able to decrypt the ciphertexts without any complexity?
- 73
1
vote
1
answer
116
views
Computationally expensive key derivation whose difficulty is asymmetric
I am looking for a primitive or a construction that meets the following requirements. Is such a construction (a) theoretically possible, and (b) in existence right now?
Given are:
a long secret $X$
...
- 729
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)...
- 187
0
votes
0
answers
44
views
How to Solve Discret Log Computation Problem
Given $g^a$ in $Z_p$, it is hard to get the solution $a$. Everyone says yes, I wonder why it is hard. Could anyone give a specific mathematical way to show it is indeed hard?
1
vote
1
answer
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 ...
- 119
0
votes
1
answer
107
views
Is it hard to find a big random easy to factor number?
Suppose that I give you the challenge of successfully factoring any very big random number. That is, you pick a big random number (say, 65536 bits) and try to factor it. If you manage to, you win. If ...
- 1,335
1
vote
3
answers
192
views
Calculate the complexity of HKDF with a 96bit salt and a 128bit key?
I have a 128 bit Pre-Shared Key. I don't want to use it directly. I'd much rather generated a session key with HKDF(PSK, SALT) = SESSIONKEY.
I'm however under ...
1
vote
1
answer
93
views
Are there any algorithms for which generating any zero-knowledge proofs is not practical?
It is related to my earlier question:
Can zkSNARK or other zero-knowledge proofs be used to proof message authenticity without revealing private key?
Are there any algorithms for which generating ...
user76634
1
vote
0
answers
31
views
Help with next step in the Quadratic Sieve
So I am at the same step as someone from math.stackexchange but he never recieved an answer so I will copy-paste his question here:
Say, for N = 90283, I compute bound 𝐵=𝑒(12+𝑜(1))(ln(𝑛)ln(ln𝑛√))...
- 111
1
vote
0
answers
58
views
Why is this attack complexity equal that exact number of bit operations?
in the this paper,section 3,autors attack hamsi-256. Im trying to make a parametrized version, so i need to understand how do they estimate the complexity of attack in bit operations,that reads as ...
- 55
1
vote
1
answer
259
views
Show that $\text{FACTORING} \le_P \text{SQROOT}$
I tried to prove that $\text{FACTORING} \le_P \text{SQROOT}$ in a general setting, so $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}$.
THEOREM:Let $n$ be a composite ...
- 617
31
votes
2
answers
5k
views
What are standard cryptographic assumptions?
I am struggling to understand what is meant by "standard cryptographic assumption".
The Wikipedia artice on the Goldwasser–Micali system (GM) reads "GM has the distinction of being the first ...
- 617
2
votes
1
answer
1k
views
Complexity of a brute-force search
I am currently thinking about the complexity of a brute-force attack on a cipher. Let the key length of the cipher be 64 bit. Then there are $2^{64}$ different keys in the keyspace. If you do a brute-...
- 509
3
votes
1
answer
475
views
Partial key recovery from linear equations
I have searched for my question but I didn't find any relevant answer to my situation. I guess maybe it is too easy but I am a newbie in crypto and I can't figure out the answer.
Here is the exercise:
...
- 45
1
vote
0
answers
78
views
'random' function $r_{n+1} = f(r_n)$, $|\{r_i,\forall i\}|=N$, $r_N = r_1$ where a function $g(r_k)=k$ is harder than in ECC?
Is there a deterministic pseudo random function $f$ with $r_{n+1} = f(r_n)$, $|\{r_i,\forall i\}|=N$, $r_N = r_0$, (for given random initial value $r_0$) where a function which derives the index of a ...
- 573
0
votes
1
answer
85
views
Question on the Quadratic Residuosity Assumption
I am reading the Handbook of Applied Cryptography and on page 99 the authors write
, after showing that $QRP \le_P FACTORING$:
It is believed that the $QRP$ is as difficult as the problem of ...
- 617
1
vote
0
answers
98
views
What if an AES Whitebox 1024-bit (or larger key) is created? Does it increase complexity consistently?
Following the Chow et al paper and Muir's tutorial, I was able to implement the AES algorithm using tables embedding keys of 128, 192 and 256-bit sizes, later extended to 1024, 2048 and 4096-bit sizes....
0
votes
1
answer
62
views
Definition of support in the context of an encryption scheme and usage of P = NP assumption in lemma 9.2 (Arora, Barak)
EDIT: I've migrated the question by deleting the same question I asked on mathematics stackexchange.
2 questions: (1) I am confused about the definition of support used in the proof given in the ...
- 97
1
vote
1
answer
293
views
(Whitebox Crypto) Using ChaCha20, is it safe to reduce the nonce length in a single block cipher?
I am willing to write a Whitebox Crypto unit using ChaCha20 algorithm (Bernstein, D. 2008) for an input consisting of a single block. The fact it is going to be a single block cipher is of special ...
4
votes
1
answer
245
views
Are there post-quantum cryptosystems with a gap between classical and quantum security?
Is there a gap between classical attacks and quantum attacks against some post-quantum security assumptions? (I'm particularly interested in asymmetric cryptography.)
I understand that there is no ...
- 2,565
1
vote
2
answers
3k
views
What is the difference between computational complexity and time complexity?
Computational complexity seems to be used quite a lot in cryptographic papers.
The time complexity I am referring to is the one from Computational Complexity Theory.
Are these two the same things?
- 1,303
2
votes
1
answer
865
views
Computational Complexity: ECC multiplication vs Modular multiplication
How does performing scalar multiplication on an elliptic curve compare to exponentiation in a multiplicative group modulo a prime?
I.e. on a given elliptic curve of size $|t|$, what's the complexity ...
- 31
3
votes
0
answers
305
views
Group Rings on Cryptography
Let $R[G]$ or $RG$ be the group ring where $R=F_q$ and $G$ is any group. Let $Dim(V)=\vert G \vert$. It's clear that $V$ has $\vert R \vert^{\vert G \vert}$ distinct $\vert G \vert$-tuples. This ...
- 898
4
votes
1
answer
236
views
Induction is problematic in computational cryptography - Why?
In Dr. Lindell's lecture The Yao Construction and its Proof Of Security, in briefly explaining the hybrid argument, he makes the statement that mathematical induction is a problem in computational ...
- 85
2
votes
1
answer
151
views
Multivariate Cryptography: Security of the affine transform T
In this question, I'd like to discuss the security of the last transformation $T$ employed in the construction of a MV-scheme. MVCrypto is based on solving a system of polynomial equations, but ...
- 898
2
votes
1
answer
708
views
Bit-strength of discrete logarithm for a group of integers modulo a safe prime
Preliminaries
Let $p$ be a safe prime number.
Let $\mathbb{Z}_p^*$ be the multiplicative group of integers modulo $p$.
We have $\mathbb{Z}_p = \{\,a \in \mathbb{Z} \mid 1 \le a \lt p\,\}$ .
Let $g \...
- 153
7
votes
1
answer
734
views
What makes the quadratic residuosity problem hard?
The quadratic residuosity problem is the problem of determining whether, for given $r$, $m$, $\exists a.a^2\equiv r\mod m$.
This problem's believed to be hard to solve in general (e.g. an efficient ...
- 191
1
vote
0
answers
233
views
Time complexity of Euler's totient function
I believe there are different time complexities for Euler's totient function depending on how you execute the algorithm. The two I know of are:
Iterate through 1 to k and calculate each $\gcd$: $O(n \...
- 125
2
votes
1
answer
151
views
Why does the following SIS-based decision language not make sense?
I'm currently reading about important lattices problems and noticed that while CVP, SVP, and LWE have decisional versions, SIS does not. I read in the question Relation between decisional SIS and ...
- 247
1
vote
2
answers
763
views
Speed of the General number field sieve
So according to the wikipedia page https://en.wikipedia.org/wiki/General_number_field_sieve the algorithm has complexity $$\exp \left( \left(\sqrt[\leftroot{1}\uproot{0}3]{\frac{64}{9}} + o(1) \right) ...
- 225
2
votes
1
answer
387
views
Attack on a Feistel Cipher given the key and half of the ciphertext
Consider a classical Feistel Cipher, with the round functions given and the keys used in the ciphering process.
Is it possible to reconstruct the original data if half of the ciphered text is given? ...
- 123
2
votes
1
answer
168
views
If DDH is hard then CCA-secure PKES exist?
My cryptography slides describe several relations between cryptographic problems. I don't still have a good justification on the following:
If decisional Diffie-Hellman problem is hard then there ...
- 1,243