Primality Testing Under Adversarial Conditions
eprint.iacr.org
Primality Testing Under Adversarial Conditions
1–9 of 9 posts
Re: Primality Testing Under Adversarial Conditions
#2If the attacker has access to your prime number generator, how does a recommendation to change anything (like the primality test) in your system help? While interesting this seems like a thin layer of protection. OTOH every small thing is a step in the right direction right?
Re: Primality Testing Under Adversarial Conditions
#3If the attacker has access to your prime number generator, how does a recommendation to change anything (like the primality test) in your system help? While interesting this seems like a thin layer of protection. OTOH every small thing is a step in the right direction right?
This is primarily for when the other party in a transaction provides you a number that is putatively prime. It was not generated by "your" generator.
Re: Primality Testing Under Adversarial Conditions
#4The underlying weakness of the Miller-Rabin test has been known for a long time, and yet "just do N rounds of Miller-Rabin" keeps being perpetuated as the folklore solution to probabilistic primality testing. The BPSW test is basically superior in every way: there are no known counterexamples (and there's currently no feasible strategy to construct counterexamples, if any exist), it's as fast as a single Miller-Rabin test for discarding composites, and if I'm not mistaken, it's about as fast as N = 3 Miller-Rabin tests for primes. In other words, doing N = 50 Miller-Rabin rounds instead of just doing a single BPSW test really makes no sense. I'm happy that the authors advocate the BPSW test as a replacement. BPSW is the default pseudoprime test used in Mathematica, Maple and Pari/GP so it's definitely battle-tested too. Perhaps this work will finally prompt widespread change.
Re: Primality Testing Under Adversarial Conditions
#5My favouritely titled paper comes to mind: https://www.cse.iitk.ac.in/users/manindra/algebra/primality_...
Re: Primality Testing Under Adversarial Conditions
#6Or you could just use ECC instead of RSA and not have to worry about generating primes at all.
Re: Primality Testing Under Adversarial Conditions
#7My favouritely titled paper comes to mind: https://www.cse.iitk.ac.in/users/manindra/algebra/primality_...
To save everyone a click: "PRIMES is in P"
Re: Primality Testing Under Adversarial Conditions
#8If the attacker has access to your prime number generator, how does a recommendation to change anything (like the primality test) in your system help? While interesting this seems like a thin layer of protection. OTOH every small thing is a step in the right direction right?
This is primarily for when the other party in a transaction provides you a number that is putatively prime. It was not generated by "your" generator.
The other party has access to our communications. Why would they want to use weak encryption?
Re: Primality Testing Under Adversarial Conditions
#9The underlying weakness of the Miller-Rabin test has been known for a long time, and yet "just do N rounds of Miller-Rabin" keeps being perpetuated as the folklore solution to probabilistic primality testing. The BPSW test is basically superior in every way: there are no known counterexamples (and there's currently no feasible strategy to construct counterexamples, if any exist), it's as fast as a single Miller-Rabin…
"Perhaps this work will finally prompt widespread change."
I sure hope so. I've argued this to various languages and libraries for a few years, and mostly they don't really care, other than they've heard of M-R and not of anything else.
One bottleneck I ran into are the "Prove that the probability is smaller" argument. The probability bound for BPSW is actually not very good, but empirically we see that bound is grotesquely conservative. One can always add more random-base M-R tests if desired.
There is also the problem that statistical thinking is hard for people. This comes up with using fixed bases and not grasping that this ruins the "2^-80 probability!" (for example) claim. That only applies to a random input.