GIMPS and PrimeGrid are large-scale distributed projects dedicated to searching giant prime numbers, usually of special forms like Mersenne and Proth primes. The numbers in the current search-space are millions of digits large and the participating volunteers need to run resource-consuming primality tests. Once a candidate primeN has been found, the only way for another party to independently verify the primality ofN used to be by repeating the expensive primality test. To avoid the need for second recomputation of each primality test, these projects have recently adopted certifying mechanisms that enable efficient verification of performed tests. However, the mechanisms presently in place only detect benign errors and there is no guarantee against adversarial behavior: a malicious volunteer can mislead the project to reject a giant prime as being non-prime.

In this paper, we propose a practical, cryptographically-sound mechanism for certifying the non-primality of Proth numbers. That is, a volunteer can – parallel to running the primality test forN – generate an efficiently verifiable proof at a little extra cost certifying thatN is not prime. The interactive protocol has statistical soundness and can be made non-interactive using the Fiat-Shamir heuristic.

Our approach is based on a cryptographic primitive called Proof of Exponentiation (PoE) which, for a group\({\mathbb {G}}\), certifies that a tuple\((x,y,T)\in {\mathbb {G}}^2\times \mathbb {N}\) satisfies\(x^{2^T}=y\) (Pietrzak, ITCS 2019 and Wesolowski, J. Cryptol. 2020). In particular, we show how to adapt Pietrzak’s PoE at a moderate additional cost to make it a cryptographically-sound certificate of non-primality.

1. 1.

   GIMPS first tests by trial division whether a candidate number has any prime divisors of size up to a bound between\(2^{66}\) and\(2^{81}\). Only when this is not the case is that they run a more expensive specialized primality test: details can be found onthis page.

2. 2.

   Note that some primality tests, like, e.g., Miller-Rabin [27,34], can be modified to (sometimes) yield factors in case the number being tested is not a prime.

3. 3.

   More details can be found inthis thread ofmersenneforum.org. An implementation due to Atnashev is available onGitHub. The idea of using PoEs for certifying giant primes has been discussed also by Mihai Preda in anotherthread in the same forum already in August 2019.

4. 4.

   If the order of the group is known, then\(x^{2^T}\) can be computed efficiently using the shortcut:\(y=x^e\) (over\({\mathbb {G}}\)) for\(e=2^T\bmod {{{\,\textrm{ord}\,}}({\mathbb {G}})}\).

5. 5.

   Recall that the order of an element\(g\in {\mathbb {G}}\), denoted\({{\,\textrm{ord}\,}}(g)\), is the least integer such that\(g^{{{\,\textrm{ord}\,}}(g)}=1\). An example of a group without low-order elements issigned quadratic residues\(QR_N^+\), whereN is sampled as the product of safe primes [15,21]. This is also the algebraic setting used in Pietrzak’s VDF [28].

6. 6.

   For\(N\in \mathbb {N}\), let\(\pi (N)\) denote the number of primes less thanN. By prime number theorem, asymptotically\(\pi (N)\) approaches\(N/\log (N)\). For the case of Proth numbers, however, even the question of whether there are infinitely many of them is open [9].

7. 7.

   One could also use SNARGs [22,26] for this purpose but, being a general-purpose primitive, the resulting schemes would not be practically efficient.

8. 8.

   In the actual protocol, we explain how the verifier can check if the Jacobi symbol ofx is\(-1\) (Step 1 in Fig. 3).

9. 9.

   Note that if\(\mu \) has orderk, then\(-\mu \) has order 2k (which is not coprime to\(2^{n-1}\)), which is the reason we have to square the statement in Equation (4) before computing the inverse of the exponent.

10. 10.

    In fact, Miller’s test [27] runs in strict polynomial time assuming the Generalised Riemann Hypothesis.

11. 11.

    Since these numbers have a succinct representation, the complexity of these tests is, strictly-speaking, exponential in the size of the input (which isn for\(M_n\)).

12. 12.

    PrimeGrid has already implemented a check\(\mu ^{k\cdot 2^{64}}=1?\) [3]. Our analysis shows that an exponent of 64 is not sufficient for cryptographic soundness as this only gives\(64/\log (n)\) bits of security “per round”; once we apply the Fiat-Shamir methodology to make the proof non-interactive, each round can be attacked individually.

We are grateful toPavel Atnashev for clarifying via e-mail several aspects of the primality testsimplementated in the PrimeGrid project. Pavel Hubáček is supported by the Czech Academy of Sciences (RVO 67985840), the Grant Agency of the Czech Republic under the grant agreement no. 19-27871X, and by the Charles University project UNCE/SCI/004. Chethan Kamath is supported by Azrieli International Postdoctoral Fellowship, ISF grants 484/18 and 1789/19, and ERC StG project SPP: Secrecy Preserving Proofs.

Authors and Affiliations

1. Institute of Science and Technology Austria, Klosterneuburg, Austria

   Charlotte Hoffmann & Krzysztof Pietrzak

2. Institute of Mathematics, Czech Academy of Sciences, Prague, Czech Republic

   Pavel Hubáček

3. Tel Aviv University, Tel Aviv, Israel

   Chethan Kamath

Corresponding author

Correspondence toCharlotte Hoffmann.

Editors and Affiliations

1. Georgia Institute of Technology, Atlanta, GA, USA

   Alexandra Boldyreva

2. Georgia Institute of Technology, Atlanta, GA, USA

   Vladimir Kolesnikov

A Attacking Pietrzak’s Protocol in Proth Number Groups

An attack with success probability at least\(1-(1-1/{{\,\textrm{ord}\,}}(\alpha ))^{\log T}\).

Full size image

In this section we show how a malicious prover\(\mathcal{P}^*\) can falsely convince the verifier\(\mathcal{V}\) that a Prothprime is composite when using Pietrzak’s PoE. This attack was first described in [8]. Let\(N=k2^n+1\) be prime andx be any quadratic non-residue moduloN. SinceN is prime, it holds that\(x^{k2^{n-1}}=-1\mod N\). The easiest way for\(\mathcal{P}^*\) to cheat is claiming that the result of this exponentiation is 1 instead of\(-1\) and then multiplying the honest messages by\(-1\) until the recombination step (Step2d ofPPoE) yields a correct instance. The probability that\(\mathcal{V}\) accepts this false “proof” of non-primality is\(1-1/2^{\log (n-1)}=1-(n-1)^{-1}\). To see this, consider the first round of the protocol.\(\mathcal{P}^*\) multiplies the correct midpoint\(v=(x^{k})^{2^{(n-1)/2}}\) by\(-1\) and sends the message\(-v\) to\(\mathcal{V}\).\(\mathcal{V}\) samples a random coinr and they both compute\(x'=-x^{kr}v\) and\(y'=(-v)^r\) to create the new statement\(x'^{2^{(n-1)/2}}=y'\). Plugging in the values for\(x',y'\) andv, we see that the new statement is correct wheneverr is an odd integer:

Ifr is even, the statement remains false and\(\mathcal{P}^*\) does the same in the next round.\(\mathcal{V}\) only outputsreject if all of the random coins are even which happens with probability\(1/2^{\log (n-1)}=(n-1)^{-1}\) since\(\log (n-1)\) is the number of rounds. Otherwise\(\mathcal{V}\) outputsaccept on a false statement. A generalization of this attack is shown in Fig. 4. Instead of multiplying the correct statement by\(-1\),\(\mathcal{P}^*\) multiplies the correct statement by an arbitrary group element\(\alpha \) and adapts its messages accordingly. The success probability can be lower bounded by\(1-(1-1/{{\,\textrm{ord}\,}}(\alpha ))^{\log (n-1)}\) which is the probability that in at least one round the bad element is raised to a multiple of the order of\(\alpha \). If\({{\,\textrm{ord}\,}}(\alpha )\) is not a prime number, this bound is not tight since the order of the bad element can decrease during the execution of the rounds, making the success probability even higher. In the case whereN is prime, the prover knows the group order\(N-1=k2^n\) and its factorization and can therefore construct elements of sufficiently low order.

Reprints and permissions

© 2023 International Association for Cryptologic Research

Policies and ethics