---
_id: '13143'
abstract:
- lang: eng
  text: "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 prime
    N has been found, the only way for another party to independently verify the primality
    of N 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.\r\nIn 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 for N – generate
    an efficiently verifiable proof at a little extra cost certifying that N is not
    prime. The interactive protocol has statistical soundness and can be made non-interactive
    using the Fiat-Shamir heuristic.\r\nOur approach is based on a cryptographic primitive
    called Proof of Exponentiation (PoE) which, for a group G, certifies that a tuple
    (x,y,T)∈G2×N satisfies x2T=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."
acknowledgement: 'We are grateful to Pavel Atnashev for clarifying via e-mail several
  aspects of the primality tests implementated 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.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Charlotte
  full_name: Hoffmann, Charlotte
  id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
  last_name: Hoffmann
- first_name: Pavel
  full_name: Hubáček, Pavel
  last_name: Hubáček
- first_name: Chethan
  full_name: Kamath, Chethan
  last_name: Kamath
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  ama: 'Hoffmann C, Hubáček P, Kamath C, Pietrzak KZ. Certifying giant nonprimes.
    In: <i>Public-Key Cryptography - PKC 2023</i>. Vol 13940. Springer Nature; 2023:530-553.
    doi:<a href="https://doi.org/10.1007/978-3-031-31368-4_19">10.1007/978-3-031-31368-4_19</a>'
  apa: 'Hoffmann, C., Hubáček, P., Kamath, C., &#38; Pietrzak, K. Z. (2023). Certifying
    giant nonprimes. In <i>Public-Key Cryptography - PKC 2023</i> (Vol. 13940, pp.
    530–553). Atlanta, GA, United States: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-31368-4_19">https://doi.org/10.1007/978-3-031-31368-4_19</a>'
  chicago: Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, and Krzysztof Z Pietrzak.
    “Certifying Giant Nonprimes.” In <i>Public-Key Cryptography - PKC 2023</i>, 13940:530–53.
    Springer Nature, 2023. <a href="https://doi.org/10.1007/978-3-031-31368-4_19">https://doi.org/10.1007/978-3-031-31368-4_19</a>.
  ieee: C. Hoffmann, P. Hubáček, C. Kamath, and K. Z. Pietrzak, “Certifying giant
    nonprimes,” in <i>Public-Key Cryptography - PKC 2023</i>, Atlanta, GA, United
    States, 2023, vol. 13940, pp. 530–553.
  ista: 'Hoffmann C, Hubáček P, Kamath C, Pietrzak KZ. 2023. Certifying giant nonprimes.
    Public-Key Cryptography - PKC 2023. PKC: Public-Key Cryptography, LNCS, vol. 13940,
    530–553.'
  mla: Hoffmann, Charlotte, et al. “Certifying Giant Nonprimes.” <i>Public-Key Cryptography
    - PKC 2023</i>, vol. 13940, Springer Nature, 2023, pp. 530–53, doi:<a href="https://doi.org/10.1007/978-3-031-31368-4_19">10.1007/978-3-031-31368-4_19</a>.
  short: C. Hoffmann, P. Hubáček, C. Kamath, K.Z. Pietrzak, in:, Public-Key Cryptography
    - PKC 2023, Springer Nature, 2023, pp. 530–553.
conference:
  end_date: 2023-05-10
  location: Atlanta, GA, United States
  name: 'PKC: Public-Key Cryptography'
  start_date: 2023-05-07
date_created: 2023-06-18T22:00:47Z
date_published: 2023-05-02T00:00:00Z
date_updated: 2023-06-19T08:03:37Z
day: '02'
department:
- _id: KrPi
doi: 10.1007/978-3-031-31368-4_19
intvolume: '     13940'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2023/238
month: '05'
oa: 1
oa_version: Submitted Version
page: 530-553
publication: Public-Key Cryptography - PKC 2023
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783031313677'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Certifying giant nonprimes
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13940
year: '2023'
...