Certifying Giant Nonprimes in Computational Number Theory
This article discusses certifying giant nonprimes in computational number theory, covering topics such as giant prime numbers, Proth numbers, proofs of exponentiation, and PoEs for non-primality certificates. It presents a statistically sound certificate of non-primality for Proth numbers and outlines technical overviews and interactive protocols. Additionally, it introduces contributions aimed at reducing complexity and improving current protocols.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Crypto for Crypto Computational Number Theory: Certifying Giant Nonprimes x Charlotte Hoffmann1, Pavel Hub ek2, Chethan Kamath3, Krzysztof Pietrzak1 1Institute of Science and Technology Austria 2Charles University, Faculty of Mathematics and Physics 3Tel Aviv University
Giant Prime Numbers GIMPS and PrimeGrid: large-scale projects dedicated to searching giant prime numbers Expensive primality tests for numbers of special form (e.g. Proth, Mersenne) Prevent cheating and computation errors: Double checking Cryptographic proofs? 2
Proth Numbers ? = ???+ ? ? ,? < 2? odd Proth s Theorem For all x quadratic non-residue mod ?: ? prime ??2? 1= 1 mod ? 3
Proofs of Exponentiation Hidden order ???= ? in ? PoE ? ? If ord(?) is known: ? and ? compute ? ?? mod ord ? and ?? ? performs ? sequential exponentiations ? ?? ??2 ??3 ??? Cost of computing and verifying the proof ? 4
PoEs for (Non-)Primality Certificates? Proth s Thm: ? = ?2?+ 1 ? prime ??2? 1= 1 mod ? GIMPS and PrimeGrid deployed Pietrzak s PoE to certify primality test BUT: Pietrzak s PoE constructed for hidden order groups Here: order of ? Attack! known for ? prime 5
Our contribution Statistically sound certificate of non-primality for Proth numbers that reduces the complexity of double checking from ? to ?(?log?) increases the complexity of the currently deployed (not cryptographically sound) protocol by multiplicative factor 2 6
Plan 1. Pietrzak s PoE 2. An attack in Proth number groups 3. Our protocol 8
Interactive Protocols statement ? ? ? ? accept/ reject ? ? Soundness: If statement is false, ? rejects w.h.p. for every malicious ? Completeness: If statement is correct and ? is honest, ?accepts w.h.p. 9
Pietrzaks PoE [Pie19] ?2?= ? ?1= ?2?/2 ? ( ) ?2?/2= ?1 2?/2= ? ?1 ? $ (???1)2?/2= ??1 ? ?2 ?2= ?? accept/reject Can be made non-interactive using Fiat-Shamir. 10
The Attack [BBF18] Element of order ? Let ? = ?2?+ 1 prime ??2? 1= 1 mod ? ??2? 1= ? ? ? $ ? ) ( ? Holds if ? ?= 1 mod ? ?2 Pr[? accepts that ? is composite ] 1/? 11
Our Work: Observations ? ? = ?2?+ 1 prime ??2? 1= 1 mod ? Observations: ? only needs to exclude that the correct result is 1 Success probability of attack depends on order of ? The order of ? divides ? 1 = ?2? if ? prime ? can check if the order of ?is too small 12
Our Work: Non-primality Certificate ? = ?2?+ 1 prime ??2? 1= 1 mod ? 1 ??2? 1= ? Statistical security parameter Case 1: ??= 1 Compute ? 2 ? mod ? and check if ??= ?2? accept/reject Case 2: ??2? log ? 1 Pietrzak s PoE accept/reject Case 3: ??2? log ?= 1 [HHK+22] ?, Pietrzak s PoE for claim ??2? 1 ? log ?= ? Check if ?2? log ?= ? accept/reject 13
Summary and Open Problems weeks Prover s Space Verifier s Complexity Approach Sound? Prover s Complexity Proof Size Double checking ? 0 yes 0 0 Pietrzak s PoE in ? 3?log? log? 2 ? ? no ???? + ?????? ???? + ? ????? + ????? + ? ? ? Our work yes hours We construct non-primality certificate for Proth number ?2?+ 1 Open: Construct cryptographically sound certificate of primality Open: Certificates of (non-)primality for other types of numbers such as Mersenne numbers 2? 1 Questions? 14
