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
3
votes
0answers
43 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 ...
6
votes
1answer
118 views

Is indistingishuable obfuscation real?

I've recently stumbled upon an interesting Quantamagazine article. It states that the theoretical feasability of indistingishuable obfuscation (iO) has been proven, referencing a rather recent paper ...
2
votes
2answers
165 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
69 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
71 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 ...
1
vote
1answer
119 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
132 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
155 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 ...
163
votes
4answers
110k 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 ...