# 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

50 questions
Filter by
Sorted by
Tagged with
63 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 ...
• 1,823
81 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
65 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 ...
• 480
1 vote
43 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 ...
• 503
164 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
21 views

### Using Coppersmith for a second trivariate polynomial

I have a trivariate polynomial whose roots I am interested. The polynomial has monomials in $\{X^4,X^2,X^2Y,X^2Z,1\}$. What is the best way to generate the lattice and apply $LLL$ so that I can get a ...
• 882
1 vote
23 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$ ...
491 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
98 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
72 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 ...
• 882
498 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
66 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 ...
• 129
56 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 ...
• 129
140 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 ...
• 1,823
34 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 ...
• 129
110 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 ...
• 337
34 views

• 121
68 views

• 882
212 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} +...
• 337
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 ...
60 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
80 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 ...
• 337
795 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 ...
• 65
275 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 ...
481 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
95 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
89 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$ ...
• 882
34 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 ...
• 529
219 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 ...
• 529
54 views

• 5,942