8

Yes, you are looking for the notion of a universal one-way function. Rafael Pass/abhi shelat's notes contain a construction on page 49. The construction is "unnatural" in the sense that it involves parsing the input to the OWF $y$ as a pair $\langle M\rangle || x$, where $\langle M\rangle$ is interpreted as the description of a Turing machine. Then ...


8

First, the wikipedia article stated that the assumption required a PRG with an exponential stretch. This is not correct, and I have edited the article. Rather, the requirement is for a PRG in $NC_0$ with super-linear stretch (i.e., stretching from $n$ to $n^{1+\tau}$ for any $\tau>0$). This is indeed not known, as far as I could ascertain from a brief ...


6

I am unaware of cryptography that is hard solely assuming that $P\neq NP$, so I believe you are misunderstanding something. I know the story best when it comes to lattices, so I'll discuss why lattices are solely "adjacent" to an $NP$-hard problem. The story is rather simple, but also technical. Let $\mathsf{LWE}[n, \sigma, q]$ be the average-case ...


5

and the elf model proves a secure block cipher exists It is worth mentioning that lower bounds in computationally limited settings do not "lift" [1] to lower bounds in computationally stronger settings. For example, there are lower bounds of $\Omega(\sqrt{|G|})$ on DL in the generic group model. This does not prove that DL is hard in "real ...


5

AES is not an ideal cipher, nor is it intended to be an ideal cipher. AES is meant to be a practical cipher that offers a strength close to the key size. That means it is computationally infeasible to find the key even if given the plaintext and the ciphertext. AES - when correctly used with a strong mode of operation - produces ciphertext is ...


4

They don't need to be: isogeny-based cryptography has no connection to any NP-complete problems, as far as I am aware. Generally you want the underlying mathematical problem to be hard, and you can't get "harder" than NP, since (to be very imprecise) the secret key of a public-key cryptosystem acts like a "witness" for any hard problem ...


4

What I don’t get is why the complexity became quadratic in linear case? Well, in linear cryptanalysis, for each input, we get a bit with a bias of $0.5 \pm \epsilon$, and we need to determine if that bias is $0.5 + \epsilon$ or whether it is $0.5 - \epsilon$ If we were to query a random bit (that is, one with no bias) $n$ times and sum the results, we're ...


4

You are right. A hash function applied to $n$ bits of input will typically take $O(n)$ work to evaluate. It is important for a hash function to use every single bit of input as part of the calculation or collisions become very, very easy. The "hashing takes time $O(1)$" is true for fixed/bounded length inputs, but as you say this is misleading.


3

As far as I am aware, all the recent progress on discrete log algorithms which derived pseudopolynomial efficiencies took place for the case of small characteristic fields $GF(p^n)$ with a structured exponent $n$. So the best complexity is still exponential in $\log N$ where $N$ is the size of the subgroup under consideration. So nothing better than generic ...


3

I'll be retracting my close vote, and submit my reasoning of cryptogrphic algorithms' efficiency. To answer the question: Is there some bound in complexity which splits both efficient and not efficient cryptosystems or algorithms of cryptosystems? there isn't a clear separation between efficient and inefficient algorithms and cryptosystems, but often, ...


3

From a theoretical perspective in cryptography, a cryptosystem is efficient when the execution time of the algorithm run by the legitimate user grows as a polynomial of a security parameter $k$, while the execution time for the best algorithm an adversary can run to break the system grows faster than any polynomial of $k$ (some change that to: exponentially ...


3

The classic Gaussian Elimination algorithm is $O(n^3)$ runtime regardless of specific field and the Matrix, so in this case a finite field $F_q$ of order $q$ doesn't play a role in the complexity. This runtime is due to the fact that you are zeroing out entries in columns column-by-column to get into row reduced echelon form. For matrices in $GL(n, q)$, the ...


3

maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it Even that limited goal is beyond what we can prove. People have done studies on tiny functions (functions small enough that exhaustive search is possible); the difference between evaluating the function forward and backwards was ...


2

The sumcheck protocol can be made non-interactive, both in the random oracle model and under strong cryptographic assumptions. Good starting points to read about that are this paper and this paper. The high level intuition that even if Fiat-Shamir fails in general for interactive protocols with many rounds, it holds whenever the protocol satisfies some ...


2

maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it. Even a problem with $\Omega(n^7)$ could suffice to build somewhat practical cryptography: $c⋅(2128)17≈c⋅319557$ bits (for some constant $c$) would be required to obtain the same security level as a 128 bit key. Some people have ...


1

Let $n$ be the number of points in the curve group and $p$ the size of the field. The quoted estimate for Pollard $\rho$ is $\sqrt {\pi n/2}$ which is the number of elliptic curve group operations required. To sign a ECDSA message (assuming that you already have your key pair) is an elliptic curve scalar point multiplication which takes (using windowed ...


1

Your idea is correct. Although the running times of the honest prover and verifier do increase by the running time of $R$, this (somewhat counterintuitively) does not affect the concrete bounds for soundness and ZK (at least how they are usually defined). Note that $T$-soundness does not really make sense for a proof system, since it is sound against even ...


1

Miller-Rabin has been known since at least 1980 (according to Wikipedia). Even though it's probabilistic, it's good enough. For example, openssl uses it$^\textrm{1}$. Chapter 4 of the handbook talks about various primality tests, which may gave you a better understanding of the authors' thoughts. $^\textrm{1}$See the source code for bn_prime.c


1

Roughly speaking, in order to achieve $k$ bits of security, encryption and decryption for Elgamal, RSA, and ECC, require $\mathcal{O}(k^3)$ operations, while encryption and decryption for lattice-based systems require only $\mathcal{O}(k^2)$ operations. That quote uses "$k$ bits of security" where there should be "a security parameters of $k$ ...


Only top voted, non community-wiki answers of a minimum length are eligible