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
13
questions
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 ...
