Score:5

Average false-positive rate for a round of Miller–Rabin

vn flag

I'm aware that the Miller–Rabin primality test will claim primality for a composite number with at most a $\frac{1}{4}$ probability for some arbitrary, odd composite $n$ and a random witness $a$ chosen uniformly in the range $[2,n-1)$. What is the actual average chance that that the test falsely claims that the number is prime? How does the chance change as the size of $n$ goes up? How does the chance change if $n$ is not divisible by any small primes up to, say, 2000?

I ask because this paper describes the probability that a composite will survive a number of test rounds. The probability is $p_{k,t}$ with $k$ being the size of the number to be tested in bits and $t$ being the number of rounds to be run. The paper proves that $\forall k \ge 2:p_{k,1} \le k^2 4^{2-\sqrt{k}}$, but this inequality is just an upper bound and a separate proof exists to show the much stronger bound $p_{600,1} \le 2^{-75}$. I'd like to find a function with a strong upper bound for $p_{k,t,n}$ with $n$ being trial division against all primes smaller than $n$, but I don't understand the math behind this paper well enough to come up with that.

Table 2 in the paper provides some example lower bounds for $-\lg{p_{k,t}}$:

\begin{array}{c|ccccccccc} k/t&1&2&3&4&5&6&7&8&9&10\\ \hline 100&5&14&20&25&29&33&36&39&41&44\\ 150&8&20&28&34&39&43&47&51&54&57\\ 200&11&25&34&41&47&52&57&61&65&69\\ 250&14&29&39&47&54&60&65&70&75&79\\ 300&19&33&44&53&60&67&73&78&83&88\\ 350&28&38&48&58&66&73&80&86&91&97\\ 400&37&46&55&63&72&80&87&93&99&105\\ 450&46&54&62&70&78&85&93&100&106&112\\ 500&56&63&70&78&85&92&99&106&113&119\\ 550&65&72&79&86&93&100&107&113&119&126\\ 600&75&82&88&95&102&108&115&121&127&133 \end{array}


OpenSSL's key generation appears to assume that this isn't the case, as it increases the number of rounds for larger primes under the illusion that false positive rate somehow impacts the security of the generated prime. Note that this code is used in the prime generation routine, so candidate primes are guaranteed to be uniformly distributed and not subject to worst-case false-positive rate.

From crypto/bn/bn_prime.c:87:

/*
 * Use a minimum of 64 rounds of Miller-Rabin, which should give a false
 * positive rate of 2^-128. If the size of the prime is larger than 2048
 * the user probably wants a higher security level than 128, so switch
 * to 128 rounds giving a false positive rate of 2^-256.
 * Returns the number of rounds.
 */
static int bn_mr_min_checks(int bits)
{
    if (bits > 2048)
        return 128;
    return 64;
}
Mark avatar
ng flag
You might be interested in [this](https://crypto.stackexchange.com/questions/17707/trial-divisions-before-miller-rabin-checks).
forest avatar
vn flag
@Mark That's interesting (and is partially the inspiration for this question), but it doesn't answer whether there is a stronger upper bound than $\forall k \ge 2:p_{k,1} \le k^2 4^{2-\sqrt{k}}$, _also_ taking into account trial divisions.
Mark avatar
ng flag
[Thomas Pornin's answer](https://crypto.stackexchange.com/a/17711) doesn't give a closed formula or anything, but it makes it sounds like the particular formula you get doesn't matter much, as most of the MR round you will run will be on composites that will be rejected after the first round.
Meir Maor avatar
in flag
I believe the bound you stated doesn't require the composite number be chosen at random the composite can be chosen by an adversary so long as the witness ia random(and check we didn't reach 1 prematurely when calculating exponent)
forest avatar
vn flag
@MeirMaor If the witness is random but the input number is chosen by an adversary, then the bound is $\frac{1}{4}$. If both the witness _and_ the input are chosen by the adversary, the probability for false-positives is of course $1$. The bound from the paper relies on the input being chosen uniformly at random.
Sam Jaques avatar
us flag
In defense of OpenSSL, if you check the commit that created that function: https://github.com/openssl/openssl/commit/42619397eb5db1a77d077250b0841b9c9f2b8984, it mentions Jake Massimo and Kenneth Paterson, who are half of the authors of this paper: https://eprint.iacr.org/2018/749. Even though there are contexts where you know the primes are uniformly generated and can use average-case soundness, that was sometimes used in cases where need adversarial soundness, so I think they decided to avoid a "foot gun" and have a single secure prime generator for all uses.
forest avatar
vn flag
@SamJaques Although the routine is used both for trusted and untrusted sources of candidate primes, the way the function itself behaves is odd. It would make more sense to hardcode the number of iterations at 128 (for both trusted and untrusted sources) instead of choosing between 128 and 64.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.