# 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
Filter by
Sorted by
Tagged with
1 vote
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 ...
1 vote
92 views

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 ...
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 ...
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
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 ...
1 vote
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 ...
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?
1 vote
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$ ...
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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
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 ...
53 views

98 views

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} +...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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
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$ ...