Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

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
71 views

Why doesn't the existence of the Quadratic Sieve algorithm imply that integer factorization is in the class SUBEXP?

SUBEXP is defined as the intersection of DTIME(2^n^c) over all c>0. The order of the Quadratic Sieve algorithm is O(exp((k+o(1))(logN)^1/2(loglogN)^1/2)). Doesn't this imply that the decision ...
Omeglac's user avatar
  • 13
0 votes
3 answers
87 views

Is it possible to construct a (pseudo-)continuous PRF or MAC?

Is it possible to construct an efficient-to-compute function $F: X \rightarrow Y$ such that Given samples $(x_1, F(x_1))...(x_n, F(x_n))$, any efficient adversary ($F$ itself is kept secret) can't ...
Marc_12's user avatar
  • 41
0 votes
0 answers
66 views

Key-dependent cipher generation

Is there any cryptanalysis possible if the cipher itself is deterministically derived from key material? For example, suppose you have n building blocks (ARX primitives, AES ops, other primitives) and ...
user avatar
1 vote
3 answers
657 views

(Complexity Theory) Given a large non-semiprime, is there a hard to compute but easy to verify problem?

Let's say I had an arbitrary number that was large, say 512 bits or bigger, but wasn't necessarily a semiprime. What is a computation that I could do on this number that would give me a unique ...
Starscream512'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
1 answer
322 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
114 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
43 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
125 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
58 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
342 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
  • 233
4 votes
4 answers
509 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
84 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
249 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
6 votes
1 answer
251 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
135 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,235
3 votes
2 answers
245 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
127 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
  • 730
4 votes
2 answers
193 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
36 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
114 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
123 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
  • 910
7 votes
1 answer
525 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
131 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
120 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
424 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,235
3 votes
0 answers
45 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
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
2 votes
0 answers
62 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
215 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
120 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
292 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
83 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
7 votes
1 answer
590 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
150 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
272 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
183 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
506 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
42 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
62 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
104 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
171 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
  • 910
5 votes
3 answers
306 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
64 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
92 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
7 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
  • 95
8 votes
1 answer
449 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