Questions tagged [computational-complexity-theory]
The computational-complexity-theory tag has no usage guidance.
7
questions
0
votes
0answers
29 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
49 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
117 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
93 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 ...
161
votes
4answers
108k 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 ...
