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
1answer
59 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
1answer
61 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
0answers
61 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 ...
4
votes
1answer
101 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
35 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
41 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
53 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
68 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
185 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
50 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
66 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
1answer
120 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
199 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
256 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
76 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
82 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
32 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
163 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
52 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
164 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
294 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
601 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 ...
167
votes
4answers
112k 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 ...