FAEST: Post-Quantum Signatures and Zero-Knowledge Proofs

Delve into the world of FAEST, a post-quantum signature scheme, with a focus on publicly verifiable zero-knowledge proofs. The presentation covers VOLE-in-the-Head, families of ZK proofs, and the application of VOLE in creating VOLE-ZK proofs. Learn about the background of VOLE, its use in the designated verifier setting, and how it enables ZK proofs through linear commitment and commitment-prove methods.

• FAEST
• Post-Quantum
• Zero-Knowledge Proofs
• VOLE-in-the-Head
• ZK Proofs

borys Follow

Uploaded on Mar 23, 2024 | 3 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. FAEST Emmanuela Orsini Carsten Baum Christian Majenz Lennart Braun Lawrence Roy (Lance) Peter Scholl Sebastian Ramacher Cyprien Delpech de Saint Guilhem Shibam Mukherjee Christian Rechberger Michael Kloo 1

2. Banquet (post-quantum) Signature dishes Picnic BBQ 2

3. Bringing to you: The FAEST 3

4. Based on Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures From VOLE-in-the-Head Carsten Baum, Lennart Braun, Cyprien Delpech de Saint Guilhem, Michael Kloo , Emmanuela Orsini, Lawrence Roy, Peter Scholl CRYPTO 2023 No VOLEs were harmed while making this presentation 4

5. Families of ZK Proofs Linear MPC-in-the-head VOLE-ZK Proof size Ligero Size: 1 bit per AND gate designated verifier STARKs ... Prover runtime 5

6. VOLE-in-the-Head: a general tool for making VOLE-ZK proofs publicly verifiable Speed Security Linear size AES/SHA 11-16x witness Application: FAEST post-quantum signature scheme 6

7. VOLE VOLE- -ZK in the designated verifier setting ZK 7

8. Background: VOLE (vector oblivious linear evaluation) ?(?) = ?? + ? Prover Verifier ? ? ?? ? VOLE ? ?? ? = ? + ? Can be instantiated with OT, HE, LPN 8

9. ZK from VOLE (designated verifier) [BMRS 21, WYKW 21] Use VOLE as a linear commitment to ? To open Prover sends (?,?), Verifier checks if? = ? + ? Hiding: since ? is random Binding: opening to ? ? requires guessing prob. 1/|?| (as long as is kept secret from Prover D.V.) ?(?) = ?? + ? ? ? (?) Commitments are linearly homomorphic 9

10. ZK from VOLE via Commit-and-Prove [BMRS 21, WYKW 21] Commit to witness ? Evaluate ? gate-by-gate: Linear gates: easy Multiplication: ??? 10

11. Multiplication check (QuickSilver) [DIO 21, YSWW 21] ? ? ? Multiply two lines quadratic polynomial ???? = ?0+ ?1? + ???2 Commit to output ? ??? = ? + ?? ???? ???(?) should be degree-1 Open and check First, mask with random deg-1 commitment ??(?) ?1 ?3= ???( ) ???(?) ?2 ??(?) 11

12. Cost analysis for VOLE-ZK Per multiplication gate: Commit to ? o 1 VOLE element Open masked commitment o Can be amortized to constant size (check random combination of polynomials) For circuit: ? + ? field elements for ? inputs and ? mult. gates (assuming LPN-based VOLE) Improvements: o General deg-2 and higher degree gates; branching; field switching 12

13. VOLE VOLE- -in in- -the Adding public verifiability the- -Head Head 13

14. MPC-in-the-Head vs VOLE-in-the-head: high-level differences ?1 challenge MPC protocol for ?(?1+ + ??) ? 1 views from ? ?? ? = ?1+ + ?? 14

15. How to do VOLE? Warm-up: using OT Key observation: ?-out-of-? secret sharing + OT VOLE in ?? (from SoftSpokenOT [Roy 22]) ?1 Pick ?? (? 1)-out- of-? OT ? ?? for ? ?? 0 when ? = ? = ?? ( ?) ? = ?1+ + ?? ? = 1 ?1 ? ?? (in ??) ? = ? + ? 15

16. How to do VOLE-in-the-head? All-but-one vector commitment Commit to ? random strings Run VOLE-ZK proof Challenge Open ? 1 GGM tree (similarly to hypercube) Convert to VOLE ?, ? ? = ? + ? 16

17. VOLE-in-the-head: some details (? 1)-out-of-? vector commit VOLE in ?? Commitments have soundness error 1 What about ?? for large ?? ? For extension fields, ? = ??: Repeat ? times, with same ? ?? Cost over ?2, 11-16 bits per AND (for 128-bit security) Needs consistency check 17

18. More details: consistency checking When repeating ? times: Need to ensure prover uses consistent ? Consistency check from[Roy 22]: Universal hash function ? ? = ??, ? = ? ? Check ? ? = ? + ? Security: Needs new analysis for round-by-round soundness with Fiat-Shamir 18

19. FAEST FAEST Post-quantum signature 19

20. Paradigm for ZK-based signatures Signature: NIZK proof of knowledge of s?, such that ?? = Enc??? Challenge: finding a ZK-friendly Enc Custom ciphers: e.g. LowMC, MiMC Other assumptions: code-based, multivariate 20

21. AES: a ZK-friendly OWF? ShiftRows, MixColumns, AddRoundKey: All linear over ?2 S-Box: Inversion in ?28 Prove in ZK as 1 multiplication constraint 21

22. Proving AES-128 in FAEST Witness: key + internal state of each round (+ key schedule) 1600 bits (in ?2) 200 constraints over ?28: 1 per S-box: degree-2 polynomial: ?? = 1 0 ? 1 (in ?28) if ? = 0 o.w. ? = ? S-Box What if ? = 0? Sample ? such that this never happens 1-2 bits less security (for AES-128) 22

23. FAEST summary: proving ?? = AES??(?) chall1 chall2 Commit to ?? and ????? after each round ? = ? + ? VOLE consistency check chall3 S-Box Mult. check Open VOLE outputs 23

24. FAEST performance (AVX2 + AES-NI) Sign/Verify Size 8ms FAEST-128s 5 006 B 1ms FAEST-128f 6 336 B 27ms FAEST-256s 22 100 B 3ms FAEST-256f 28 400 B Timings are from my laptop: AMD Ryzen 7 5800H, 3.2 4.4 GHz Signature sizes: Smaller than SPHINCS+ and most code-based candidates Faster signing, slower verification Even-Mansour variant: Enc?? = AES?? ? 10-15% smaller because of fixed key schedule 24

25. Work in progress Better domain separation Tighter proofs Parameter tweaking: Smaller signatures Faster verification Other OWFs: Pure MQ: size 3 kB Rain cipher 25

26. Conclusion Thank you! VOLE-ZK proofs: Lightweight and fast with linear size VOLE-in-the-head: publicly verifiable FAEST signature: Conservative security Reasonable performance 26