Questions tagged [computational-complexity-theory]
A subfield of theoretical computer science one of whose primary goals is to classify and compare the practical difficulty of solving problems about finite combinatorial objects
58
questions
1
vote
1
answer
240
views
Solving vs. verifying decision problems
I'm trying to understand the hardness of problems (e.g. in cryptography) from the point of view of complexity theory. For the complexity class NP, Wikipedia (11/2023) says
NP is the set of decision ...
- 139
1
vote
1
answer
92
views
Worst-case one-way permutations under P different from NP
This is probably obvious, but I cannot find it anywhere, since all textbooks define OWFs for average-case hardness.
Do we known if worst-case one-way permutations exist assuming $\mathbf{P} \neq \...
- 113
1
vote
2
answers
40
views
Let $X$ be the set of 256-bit strings and $x \rightarrow H(x)$ a map on this set, where $H$ is SHA-256. How often is $H^-1(y)$ empty?
It cannot be "frequent" because that implies $H$ is not really 256-bit. Are there statistical or mathematical bounds on this? Finding the inverse is computationally difficult, but what ...
- 111
1
vote
1
answer
92
views
Matrix multiplication circuit
I am trying to understand which operations are computable by an $\texttt{NC}^1$ circuit. However, I am struggling to understand whether there is such a circuit for multiplying a matrix with a vector ...
- 21
0
votes
1
answer
52
views
Complexity class of Decision Problem for Cracking Private Key in Elliptic curves
The integer factorization decision problem (does integer N have a prime factor = k?) is known to be an NP problem. Analogous to this, can we say that the decision problem for finding the private key ...
- 3
3
votes
1
answer
314
views
Assumptions on zero-knowledge proofs without trusted setup
Let's start with what got me wondering about this issue:
It's a curious construction, that while most digital signature schemes come from public-key encryption (Impagliazzo's cryptomania), there are ...
- 223
4
votes
4
answers
381
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 ...
- 363
1
vote
1
answer
68
views
Hash Flooding a Randomized Modular Hash Table
Assume we have a hash table using the function h(x) = x mod 32. h(x) = x mod 33. Also assume it dynamically resizes by doubling the amount of buckets and rehashing. If I was able to provide inputs for ...
- 113
2
votes
0
answers
186
views
Check if $F_1(k,x) = F(k,x) \oplus x$ is pseudorandom
Let F be a pseudorandom function. Check if if $F_1(k,x) = F(k,x) \oplus x$ is pseudorandom( $\oplus$ is bitwise XOR).
I found this question in a book. I am not sure how to proceed :
$F_1(k,x) = F(k,x) ...
- 173
5
votes
1
answer
165
views
Succinct verification of computation without ZKP
What the state of the art for producing quickly verifiable proofs of correct computation when your proof is allowed to leak knowledge?
For context, I am inspired by Miden VM's promises:
For any ...
- 53
0
votes
1
answer
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 ...
- 2,169
3
votes
2
answers
221
views
Is there a notion of information theoretic one-way function?
This is not a formal but intuitive concept of one-wayness. The intuition is that if you have a combinatorial object that requires $n$ bits to describe. A one way operation introduces noise in random ...
1
vote
1
answer
97
views
Private key encryption based on NP-complete problem
Over a decade ago, a question was asked on Stack Overflow, which basically asked if there were any encryption schemes that are reducible to an NP-complete problem, in the sense that breaking the ...
- 526
1
vote
0
answers
44
views
Proving stategies for computational properties
As far as I understand, a property is computational if it holds in a computationally-bounded context, so for ANY computationally-bounded involved entity (even if an unbounded one could discover the ...
- 700
4
votes
2
answers
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?
- 381
1
vote
0
answers
34
views
Computability of the messages of the Adversary for Semantic Security
Semantic Security may be defined using the distinguishability experiment/game, which we recall as follows:
Let $(E,D)$ be an encryption scheme. After the challenger chooses a security parameter $n$ ...
- 111
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 ...
- 133
1
vote
1
answer
112
views
What does it mean for public keys to be in coNP
I was reading this paper.
And on Page 2 the following claim was made:
Consider a public-key encryption scheme with a deterministic encryption
algorithm, and suppose that the set of valid public-keys ...
- 13
1
vote
1
answer
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 ...
- 908
7
votes
1
answer
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 ...
- 347
1
vote
0
answers
113
views
Working the multivariate Coppersmith algorithm
I recently studied the multivariate Coppersmith algorithm.
Let $f(x)$ be $n$-variate polynomial over $\mathbb{Z}_p$ for some prime $p$.
Informally, the multivariate Coppersmith's theorem stated that ...
- 149
0
votes
0
answers
112
views
Security of a variant of DDH
The standard DDH assumption states that given $(g,g^a,g^b,g^c)$, it is hard to determine whether $c$ is $ab$ or not.
A variant of DDH assumption is:
given $(g,g^a,g^b,g^c, g^{ab} ,g^{bc},g^{ac})$, it ...
- 149
3
votes
2
answers
304
views
What exactly does "Extension of a polynomial" mean?
This from the manuscript of a book on Zero Knowledge Proofs - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf
3.5 Low Degree and Multilinear Extensions Let $\mathbb F$ be any finite ...
- 2,169
3
votes
0
answers
41
views
Is block-wise locality pseudorandom generator standard assumption?
To my best knowledge, the Goldreich's pseudorandom generator (PRG) with locality 5 has been considered as one of standard assumptions.
On the other hand, Lin and Tessaro (Crypto'17) provides a new ...
- 149
3
votes
1
answer
151
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 ...
- 357
2
votes
0
answers
53
views
Centrality of Gaussian distribution for LWE error
Consider the LWE problem.
Let $A$ be an $m \times n$ matrix, $x$ is an $n \times 1$ vector, $u$ is a $m \times 1$ vector, and $e$ is sampled from a Gaussian distribution.
We are given either $Ax + e ~~...
- 357
2
votes
1
answer
177
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{...
- 357
2
votes
1
answer
119
views
Why do we always assume that the functions that the protocols can replicate are of the form $f:\{0,1\}^*\to\{0,1\}^*$?
Taking into account the vast literature of secure multiparty computation and secret sharing, there is a specific assumption that is made for the calculation of a rule function. The latter function ...
- 279
3
votes
2
answers
254
views
LWE and pseudorandom functions
Consider the learning with errors problem. Assuming LWE (or a variant of LWE, like ring LWE) is hard for polynomial time algorithms, can we construct a family of pseudorandom functions from there?
- 357
1
vote
0
answers
72
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, ...
- 111
6
votes
1
answer
509
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 ...
- 131
0
votes
1
answer
135
views
Consequences of P=NP for Authentication
Let's suppose that P=NP. That is, every problem whose solution can be quickly verified can also be solved quickly, regardless of what that means at a formal level. So, not only does P=NP, but there ...
- 103
3
votes
1
answer
210
views
Uniform and Non-Uniform PPTs
While reading the paper
2020 - Non-Malleable Codes for Bounded Polynomial Depth Tampering by Dana Dachman-Soled and Ilan Komargodski and Rafael Pass
I stumbled upon the case in which it was ...
- 125
0
votes
0
answers
171
views
Proof of theoritical security of Shamir's secret sharing
community !
I'm looking for the proof of theoritical security of Shamir's secret sharing. I found some articles saying that it's assimilable to the halting problem, which implies that there is no ...
- 21
4
votes
1
answer
418
views
How expensive would running a practical application on full homomorphic encryption be?
This is a multidisciplinary question, hopefully I can stay on topic.
It has been published that we can now use (try?) fully homomorphic encryption computation on cipher text inputs. But I'd like to ...
- 161
0
votes
0
answers
39
views
show that key recovery is not possible in a computationally secure system
(G, E, D) is a computationally secure encryption scheme over the message space $\{0,1\}^n$. Show that the probability that a PPT adversary can recover the key after seeing the encryption of a random (...
- 121
0
votes
1
answer
59
views
what's the reason of the notational difference between statistical and computational indistinguishabilities?
Statistical: $|\Pr[E_K(m_0)\in T]-\Pr[E_K(m_1)\in T]|\leq\epsilon$
Computational: $|\Pr[A(E_K(m_0))=1]-\Pr[A(E_K(m_1))=1]|\leq\epsilon(n)$
What is the $1$ doing there? Why isn't it $Pr[A(E_K(m_0))\in ...
- 121
2
votes
1
answer
98
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 $\...
- 23
2
votes
0
answers
154
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 $\...
- 908
5
votes
3
answers
272
views
A question regarding next-bit predictors
Consider a probability distribution $D$ over $n$ bit strings. Consider a next bit predictor $A$ as follows.
\begin{equation}
\underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})=X_k] \geq \frac{1}{2} +...
- 357
8
votes
5
answers
2k
views
Computational Complexity Of Breaking Information Theoretic Security
Wikipedia mentions that Shamir's secret sharing(SSS) for example, has information theoretic security. While I understand the concept that the adversary would just not have enough information to break ...
0
votes
0
answers
62
views
Is it possible to verify a python code produced an answer without re-doing the computation?
Context
Suppose Alice asks Bob to write a (python) code/function named get_sqrt(input) that computes and returns the square root of an input number named ...
- 101
2
votes
1
answer
89
views
Yao's theorem for the uniform case
Yao's theorem says that for a distribution, next bit unpredictability is equivalent to pseudo-randomness. This link proves Yao's theorem, but the proof relies on non-uniform probabilistic polynomial ...
- 357
6
votes
2
answers
2k
views
How to construct a circuit in zkSNARK
I have a few questions about how to use zk-snark. Since the basic logic of using zk-snark is:
using a circuit to represent a problem,
generate an R1CS from the circuit,
transform R1CS to QAP and then ...
- 85
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
6
votes
3
answers
535
views
How to ethically publish the result in case we prove that $P = NP$?
Suppose a researcher discovers that $P=NP$, and has an efficient algorithm for some common $NP$-Complete problem. Given the implications for cryptography, what would be the most ethical way for them ...
- 69
0
votes
1
answer
187
views
Complexity of multiplication of two numbers
If I am multiplying two numbers $m$ and $n$, where $n$ has $k$ digits and $m$ has at most $n/2$ digits, will it be considered polynomial time or exponential time in terms of $k$?
Addition (by proxy of ...
1
vote
1
answer
100
views
How long to reestablish PKI if Diffie Hellman and Factoring are in classical $P$?
Supposing there is a classical (no need quantum) $O(\log N)$ algorithm to factor integers $N$ and supposing there is a classical (no need quantum) $O(\log p)$ algorithm to find $g^{xy}$ given $g^x$ ...
- 908
0
votes
0
answers
39
views
What's the tightest time-space trade-off law for unbounded time and space?
Let's say that my CPU can be made arbitrarily faster (or I can become arbitrarily patient waiting for the CPU to complete its task), and let's say that my memory (e.g. RAM) can be made arbitrarily ...
- 563
2
votes
1
answer
310
views
How to estimate the maximum computational cost bound for Key Derivation Functions (KDFs) before it becomes useless security-wise?
From my understanding of Key Derivation Functions (KDFs), e.g. scrypt, Argon2, etc, we can tune their parameters such that it eventually becomes harder for an attacker to brute force a password-to-key ...
- 563