Hot answers tagged

9

Boaz Barak addressed this in a blog post My takeaway from his post (roughly speaking) is that we only know how to design cryptographic primitives using computational problems that have some amount of structure, which we exploit. With no structure, we don't know what to do. With too much structure, the problem becomes efficiently computable (thus useless ...


9

I'm not sure this is a statement about primes so much as it is a statement about secret key generation: if the method is deterministic (e.g. take the smallest prime larger than 10^20), then your adversary can simply reproduce the computation to find your secret key.


7

[Certainly not a complete answer, but too long for a comment] Testing whether a given DFA accepts the base-2 representation of at least one prime number is not known to be computable. If it were uncomputable, that's some kind of weak evidence that there's no "regular-ish" formula for primality. (I mean, we know the set of primes itself is not regular, but ...


6

All of what I am going to say is well-known (all the links are to Wikipedia), but here it goes: The approach used in RSA using pairs of primes can also be applied in a more general framework of cyclic groups, notably the Diffie-Helmann protocol that generalizes $\left(\mathbb{Z}/pq\mathbb{Z}\right)^{\times}$ to an arbitrary group, notably elliptic curves ...


2

Some heuristic evidence: to the best of our knowledge $\pi(n)$ looks like a simple function corrected by random fluctuations. Thus I’d expect a poly-time machine with a $\pi(n)$ oracle to be no stronger than such a machine with a random oracle, and w.r.t. a random oracle $X$ adding a separate random oracle $Y$ to $\mathsf{P}$ gives $\#\mathsf{P}^X \not\...


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