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
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 ...
- 480
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$ ...
- 111
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 ...
- 13
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 ...
- 347
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 ...
- 129
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 ...
- 129
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 ...
- 129
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 ...
- 337
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 ~~...
- 337
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{...
- 337
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 ...
- 269
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?
- 337
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 ...
- 121
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 ...
- 103
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 ...
- 161
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} +...
- 337
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 ...
- 337
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 ...
- 83
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