Re: Prime example of a can of worms

[Daniel Kahn Gillmor <dkg () fifthhorseman net>]

On Wed 2016-01-20 12:25:42 -0500, Kurt Seifried wrote:
> Sorry yes, although this also applies equally to keys/etc.

sure, though i hope we're not in a "few keys" scenario, that would
definitely be bad :)

> [dkg wrote:]
> > For one, the writeup addresses probabilistic primality tests, but
> > doesn't describe proofs of primality, which are significantly more
> > expensive to generate (and still probably more expensive to verify than
> > a short Miller-Rabin test).  But these proofs provide certainty in a way
> > that probabilistic tests might not.  If we're talking about runtime
> > primality checking when communicating with a potential adversary, are
> > there proofs about the (im)possibility of generating a pseudoprime that
> > is more or less likely to pass a miller-rabin test?
>
> I looked at this a bit and quite honestly the computational time involved
> is just to much to be useful, unless we're talking about generating a small
> set of highly trusted primes. For normal people, this just isn't feasible
> (witness prime generation taking between less then a second, and more than
> 10 minutes, nobody wants to wait 10 minutes...).

right, i'm not suggesting that proof generation be done at runtime, just
that it is an example of a stronger guarantee than we have for runtime
checks, and that it *only* applies to the "generating a small set of
highly-trusted primes" case.

> Agreed, I listed the diversity more as a stop-gap for the cases where
> people have older hard/software (e.g. Java) that will never support larger
> primes/keys. At least then you don't get caught in dragnets for the
> default/commonly used primes.

I agree with this analysis, but the chart in the middle of your paper
makes it looks like the diversity is "best", while the "small set of
heavily-evaluated primes" (i'm assuming that's what's meant with the
"few keys" side of the X axis) is merely "good".

     --dkg