Certifying giant nonprimes

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F23%3A00573360" target="_blank" >RIV/67985840:_____/23:00573360 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/978-3-031-31368-4_19" target="_blank" >http://dx.doi.org/10.1007/978-3-031-31368-4_19</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-31368-4_19" target="_blank" >10.1007/978-3-031-31368-4_19</a>

Result language

angličtina

Original language name

Certifying giant nonprimes

Original language description

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.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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Public-Key Cryptography – PKC 2023

ISBN

978-3-031-31367-7

ISSN

0302-9743

e-ISSN

—

Number of pages

24

Pages from-to

530-553

Publisher name

Springer

Place of publication

Cham

Event location

Atlanta

Event date

May 7, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—