Practical Statistically-Sound Proofs of Exponentiation in Any Group

The paper presents practical and statistically sound proofs of exponentiation in any group. It discusses the computation process, applications in verifiable delay functions and time-efficient arguments for NP, as well as interactive protocols and the overview of PoEs. The research contributes a statistically sound PoE that reduces proof size significantly.

• Proof of Exponentiation
• Statistically Sound
• Group Theory
• Verifiable Delay Functions

edupu Follow

Uploaded on Sep 12, 2024 | 0 Views

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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Practical Statistically-Sound Proofs of Exponentiation in any Group Charlotte Hoffmann1, Pavel Hub ek2, Chethan Kamath3, Karen Klein4, Krzysztof Pietrzak1 1Institute of Science and Technology Austria 2Charles University, Faculty of Mathematics and Physics 3Tel Aviv University 4ETH Zurich

2. Proofs of Exponentiation (?,?,?,?) ? ???= ? in ? PoE ? ? If ord(?) is known: ? and ? compute ? ?? mod ord ? and ??. Otherwise: ? performs ? sequential exponentiations ? ?? ??2 ??3 ??? and sends a Proof of Exponentiation (PoE) to ?. Cost of computing and verifying the proof ?. 2 Practical Statistically-Sound Proofs of Exponentiations in any Group

3. PoE Applications Verifiable Delay Functions (VDFs) [BBBF18, Pie19, Wes20]: Verifiable: given a proof, everyone can efficiently and soundly verify correctness of the result Delay: can t be computed faster than a given time parameter ? even with parallelization Function: unique output Time- and Space-Efficient Arguments for NP [BHR+21]: PoEs as building blocks in polynomial commitment scheme 3 Practical Statistically-Sound Proofs of Exponentiations in any Group

4. Plan 1. PoE Constructions and Properties 2. Technical Overview: Our PoE 4 Practical Statistically-Sound Proofs of Exponentiations in any Group

5. Plan 1. PoE Constructions and Properties 2. Technical Overview: Our PoE 5 Practical Statistically-Sound Proofs of Exponentiations in any Group

6. Interactive Protocols Completeness: If statement is true, ? accepts with probability 1 statement ? ? ? ? Soundness: If statement is false, ? rejects with high probability accept/ reject ? ? Statistical Soundness: Cheating? is computationally unbounded Computational Soundness: Cheating? is polynomially bounded 6 Practical Statistically-Sound Proofs of Exponentiations in any Group

7. Overview of PoEs ?,?,?,? s.t. ???= ? Wesolowski [Wes20] Pietrzak [Pie19] Block et al. [BHR+21] ?1 ?1,1,?2,1, ,??,1 $ Our Contribution: Statistically-sound PoE that reduces proof size of [BHR+21] by almost one order of magnitude for ? of a special form $ ? $,$, ,$ ?2 ?1,2,?2,2, ,??,2 1 grp element log? grp elements ?log? grp elements Adaptive Root Assumption Statistically sound in some grps/ Low Order Assumption Statistically sound in any group 7 Practical Statistically-Sound Proofs of Exponentiations in any Group

8. Why Statistical Soundness for PoEs? Polynomial Commitment [BHR+21]: Statistical knowledge soundness VDFs: Soundness holds even if group order known by prover Class groups: Low-order assumption not well studied/understood RSA groups: Need to sample safe primes and prove that a modulus is product of safe primes 8 Practical Statistically-Sound Proofs of Exponentiations in any Group

9. Technical Overview 9 Practical Statistically-Sound Proofs of Exponentiations in any Group

10. Plan 1. PoE Constructions and Properties 2. Technical Overview: 1. PoE construction of [BHR+21] 2. Our work: Reduce complexity 10 Practical Statistically-Sound Proofs of Exponentiations in any Group

11. One Round of [BHR+21] PoE ??= ?? ?? ??/2 ??,1= ?? ??/2= ?? ??,1 ?1,1,?2,1, ,??,1 $,$, ,$ ?1,2,?2,2, ,??,2 11 Practical Statistically-Sound Proofs of Exponentiations in any Group

12. [BHR+21] PoE Main Idea Want: Reduce the number of statements to ? ??/2= ?? ?1??/2= ?1 ?2??/2= ?2 ?2???/2= ?2? ?? ??= 1 w/ probability 1/2 ? 0,12? ??/2 ?? ?? ?? = ?? ? [2?] ? [2?] Goal: Reduce this number 1 2. If at least one of the initial statements is wrong, the new statement is wrong with probability = = = ? times At least one of the statements is wrong with probability at least 1 2 ?. 12 Practical Statistically-Sound Proofs of Exponentiations in any Group

13. Our Construction First Step ?? 0,1, ,? 12 ????= ????= ?? ?? ?? ?? ?? ?? ? ? ? ? ? ? ? ? ?? 0,1, ,? ?? 0,1 Pr new statement wrong Pr new statement wrong 1 2 1 2 Due to low order elements [BBF18, BP00]: ?? ??????= ?? ????= ??? ord(?) ?? Pr ord(?) ??= 1 ord(?) 13 Practical Statistically-Sound Proofs of Exponentiations in any Group

14. Our Construction First Step ?1,1,?2,1, ,??,1 $,$, ,$ ??? {0,1, ,?} ?1,2,?2,2, ,??,2 14 Practical Statistically-Sound Proofs of Exponentiations in any Group

15. Our Construction Second Step ? ? ?<? prime ? log?log? ?? ?= ? ?? ?1?? ?= ?1 ?? ?= ?? ?? ?= ?2 ?? ?? ?2 ??= ?? ? [?] compute ?? ord ? ?? ?? ?= ? ?? ?? = ???? ?? If ? has low order: ? ?? = ?? ?? = ?? Reduce proof size of [BHR+21] from ?log? to ?log?/log? 15 Practical Statistically-Sound Proofs of Exponentiations in any Group

16. Our Construction Basic Protocol ? ?? ??<? prime ???? ?= ?? ? ? ?/log? ?1,1,?2,1, ,??,1 ?1,1,?2,1, ,??,1 $,$, ,$ ??? {0,1, ,?} Statistical Soundness: ??= ?? ? [?] compute ?? ?1,1,?2,1, ,??,1 ?1,2,?2,2, ,??,2 If ord(?) ?? ? obtains correct result ?? Else ? has sufficiently high order ? rejects after interactive phase w.h.p. 16 Practical Statistically-Sound Proofs of Exponentiations in any Group

17. On Parameters ? and ? ? ? ?<? prime [BHR+21]: ? has to be large to ensure soundness of polynomial commitment: ? 2? ???? ? VDFs: Can adjust the cost of the initial exponentiation by adjusting time parameter ? Example Set ? = 80,T = 232,? = 521 ? 2703 Proof size drops from ?log? = 2560 to ?log?/log? =284 group elements 655 KB to 74 KB 17 Practical Statistically-Sound Proofs of Exponentiations in any Group

18. Comparison Verifier s complexity increases Cost of Verifying ? PoEs PoE Statistically Sound? Verifier s Complexity Proof Size log? + ?2 1 [Wes20] no ?log? + ?2+ log? log? [Pie19] in some groups ?2log? + ?log? ?log? [BHR+21] yes ?2log?/log? + ?log? log?/log? ?log?/log? Our work w/o recursion yes ?2log?/log? + ?log? loglog?/log? ?(log?/log? + 1) Our work w/ recursion yes Solve via recursion and batching Questions? 18 Practical Statistically-Sound Proofs of Exponentiations in any Group