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
0 votes
1 answer
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
0 votes
1 answer
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
1 answer
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 ...
1 vote
0 answers
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
4 votes
2 answers
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
0 votes
0 answers
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
0 answers
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$ ...
3 votes
1 answer
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
1 answer
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 ...
1 vote
1 answer
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
7 votes
1 answer
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
0 answers
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 ...
0 votes
0 answers
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 ...
3 votes
2 answers
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
3 votes
0 answers
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 ...
2 votes
1 answer
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 ...
2 votes
0 answers
34 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 ~~...
2 votes
1 answer
113 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{...
0 votes
0 answers
36 views

What class of complexity theory does a trapdoor function belong to

Let's suppose we have a protocol X (symmetric or assymetric codec) and it encrypts a message M and the only way to get decode M is to use the hidden information and impossible otherwise to crack. To ...
2 votes
1 answer
102 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 ...
2 votes
1 answer
91 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?
1 vote
0 answers
57 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
293 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 ...
0 votes
1 answer
95 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 ...
3 votes
1 answer
104 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 ...
0 votes
0 answers
110 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
255 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 ...
0 votes
0 answers
36 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
51 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
68 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
100 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 $\...
  • 882
5 votes
3 answers
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} +...
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
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
2 votes
1 answer
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 ...
4 votes
1 answer
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
8 votes
1 answer
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 ...
6 votes
3 answers
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
0 votes
1 answer
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
1 answer
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
0 votes
0 answers
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
2 votes
1 answer
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
2 votes
0 answers
54 views

How to prove simultaneous security for the Rabin's function

Let $p,q$ be odd primes, $n:=pq$ and $a,x \in \mathbb{Z}/n\mathbb{Z}$ be quadratic residues such that $x^2 \equiv a \pmod n$. I have understood the proof that calculating the least significant bit of $...
  • 565
3 votes
1 answer
257 views

Has anyone implemented a public-key encryption scheme using a universal one-way function?

There exists a function $f$ such that if one-way functions exist then $f$ is a one-way function. Such a function is called a universal one-way function. Now the public-key encryption schemes that I’...
2 votes
1 answer
712 views

Complexity of Gaussian Elimination over a Finite Field

I read somewhere that the complexity of solving a Linear $n\times n$ system over a Finite Field $\Bbb F_q$ using Gaussian Elimination is $\mathcal{O}(n^3)$ operations in $\Bbb F_q$. What's the role of ...
  • 21
8 votes
2 answers
2k views

(updated) Utilizing a non-computable function to create a one-way function

Why can't uncomputable functions be adapted to serve as theoretically perfect one-way functions? This has been bugging me for years, and I've never been able to track down an explanation of why it ...
  • 201
11 votes
1 answer
2k views

Meaning of "Security can be reduced to a problem"

I'm studying reductions in cryptography and confused about the way people use the word "reduction". My question is almost the same as a past question, but what I want to ask is slightly different. A ...
  • 111
8 votes
1 answer
720 views

Are post-quantum cryptographic ciphers *also* secure if the P=NP conjecture holds true?

First of all, I only understand the P versus NP debate on a rather shallow level as I am not a computer scientist. So perhaps the answer to the question is straightforward but if not, I would be ...
  • 465
5 votes
4 answers
405 views

Reductionist proofs of computational problems to decisional

Are they any reductionist proofs where an attacker $\mathcal{I}$ for a well established computationally "hard" problem $\mathsf{Π}$ is employing an attacker $\mathcal{A}$ who we assume is able to ...
  • 5,942
173 votes
4 answers
119k views

Why is elliptic curve cryptography not widely used, compared to RSA?

I recently ran across elliptic curve crypto-systems: An Introduction to the Theory of Elliptic Curves (Brown University) Elliptic Curve Cryptography (Wikipedia) Performance analysis of identity ...
  • 1,915