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

Filter by
Sorted by
Tagged with
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 ...
maya's user avatar
  • 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 \...
Noel Arteche's user avatar
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 ...
Warren MacEvoy's user avatar
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 ...
Mjf T's user avatar
  • 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 ...
UserX's user avatar
  • 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 ...
Ilk's user avatar
  • 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 ...
user1035648's user avatar
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 ...
DivideByZero's user avatar
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) ...
tonythestark's user avatar
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 ...
Matthias's user avatar
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 ...
user93353's user avatar
  • 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 ...
Mohammad Al-Turkistany's user avatar
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 ...
user918212's user avatar
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 ...
baro77's user avatar
  • 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?
a196884's user avatar
  • 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$ ...
Mathemagician's user avatar
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
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 ...
bagheera's user avatar
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 ...
Turbo's user avatar
  • 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 ...
cryptobeginner's user avatar
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 ...
filter hash's user avatar
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 ...
filter hash's user avatar
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 ...
user93353's user avatar
  • 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 ...
filter hash's user avatar
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 ...
BlackHat18's user avatar
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 ~~...
BlackHat18's user avatar
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{...
BlackHat18's user avatar
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 ...
Hunger Learn's user avatar
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?
BlackHat18's user avatar
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, ...
mrose's user avatar
  • 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 ...
Andrea Farneti's user avatar
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 ...
Thomas Anton's user avatar
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 ...
jacobi_matrix's user avatar
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 ...
hambam's user avatar
  • 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 ...
William Entriken's user avatar
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 (...
ihadanny's user avatar
  • 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 ...
ihadanny's user avatar
  • 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 $\...
sbox's user avatar
  • 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 $\...
Turbo's user avatar
  • 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} +...
BlackHat18's user avatar
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 ...
QuestionEverything's user avatar
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 ...
a.t.'s user avatar
  • 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 ...
BlackHat18's user avatar
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 ...
Mkotori's user avatar
  • 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 ...
programonkey's user avatar
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 ...
CS.N00b's user avatar
  • 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 ...
Muhammad Usman Qureshi's user avatar
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$ ...
Turbo's user avatar
  • 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 ...
caveman's user avatar
  • 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 ...
caveman's user avatar
  • 563