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
23
questions
4
votes
1answer
74 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
0answers
32 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 (...
0
votes
1answer
35 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 ...
2
votes
1answer
41 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 $\...
2
votes
0answers
55 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 $\...
5
votes
3answers
179 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
5answers
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
0answers
48 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 ...
2
votes
1answer
61 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 ...
3
votes
0answers
63 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 ...
8
votes
1answer
166 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 ...
4
votes
2answers
201 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 to ...
0
votes
1answer
70 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
1answer
76 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$ ...
0
votes
0answers
30 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 ...
2
votes
1answer
140 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 ...
2
votes
0answers
50 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 $...
2
votes
1answer
140 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
1answer
224 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 ...
8
votes
2answers
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 ...
11
votes
1answer
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 ...
7
votes
1answer
559 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 ...
164
votes
4answers
111k 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 ...
