Compact Ring Signatures from LWE - CRYPTO 2021 Research

Research presented at CRYPTO 2021 introduces a compact ring signature scheme using components instantiated from LWE. The scheme allows each signer to sign on behalf of a ring of users, offering properties of unforgeability, anonymity, and compactness. The work explores the possibility of building compact ring signatures from LWE with applications in areas like whistleblowing and blockchain. Key questions regarding the scheme's construction and its reliance on assumptions like derandomization, bilinear maps, and iO are addressed, highlighting the efforts to develop post-quantum and quantum-breakable solutions.

• Compact Ring Signatures
• LWE
• CRYPTO 2021
• Post-Quantum
• Blockchain

rubymae Follow

Uploaded on Jul 18, 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. Compact Ring Signatures from LWE Rohit Chatterjee1, Sanjam Garg2,3, Mohammad Hajiabadi4, Dakshita Khurana5, Xiao Liang1, Giulio Malavolta6, Omkant Pandey1, Sina Shiehian1,2 CRYPTO 2021 4 University of Waterloo 1 Stony Brook University 5 U. of Illinois Urbana-Champaign 2 UC Berkeley 6 Max Planck Institute for Security & Privacy 3 NTT Research

2. Compact Ring Signatures Each signer can sign on behalf of a ring of users No interaction! Properties: Unforgeability Anonymity Compactness: = ????(log ? ) Sublinear: = ?( ??) Applications: whistleblowing, blockchain

3. Previous Sublinear/Compact Ring Signatures ROM CRS Plain Size Assumption [MS 17] Compact Non-falsifiable [DKNS 04], [GK 15], [LLNW 16], [LPQ 18], [EZS+19], [BKP20], [LNS 21], [BHKS 18] Sublinear Pairings [CGS 07], [Gha 13], [Gon 17], [LPNY 20], [BDHKS 19] Compact Pairings No plain model construction from LWE!

4. Key Question Q:Can we build compact ring signatures from (poly-hard) LWE? [This work]: YES! Compact ring signature scheme using components instantiable from (poly-hard) LWE.

5. Can be based on: derandomization assumption [BOV 03], bilinear maps [GOS 12], or iO [BO 15] [BDHKS 19] Strengthening of Merkle tree, can be based on FHE PKE SPB-Hash NIWI Sign Our Task: Standard (Generic) Getting rid of NIWI Post-Quantum Quantum-breakable

6. [BDHKS19]: Construction PKE SPB-Hash NIWI Sign Signing/Verification Keys: ????.??,????.?? ????.??? Random ???.?? ?? ?? ????.??,???.?? ????.??

7. [BDHKS19]: Construction PKE SPB-Hash NIWI Sign ?? ?? ????.?? ????.??,???.?? Sign ? on behalf of ring ? = (??1, ,?? ) using key-pair (SK,VK) : ? ??? ??? .???() Compress the ring ? into a short-digest using SPB-Hash ? ????.????(????.??,?) ?: NIWI proof that ?? encrypts a valid signature under some i. . SPB-Hash.Hash( ?, ) ?? and ii. an SPB opening showing ?? is consistent with ct ? ???.?????(?) ? ?? . ??1 ??2

8. [BDHKS19]: Compactness PKE SPB-Hash NIWI Sign ?? ?? Statement: is small because is compact Witness: is small because SPB opening is compact => is compact ????.?? ????.??,???.?? ?: NIWI proof that ?? encrypts a valid signature under some ?? and ii. an SPB opening showing ?? is consistent with i. ct ? ???.?????(?) ? . SPB-Hash.Hash( ?, ) Small Small ?? . ??1 ??2

9. [BDHKS19]: Unforgeability PKE SPB-Hash NIWI Sign ?? ?? ????.?? ????.??,???.?? ?: NIWI proof that ?? encrypts a valid signature under some ?? and ii. an SPB opening showing ?? is consistent with i. ct ? ???.?????(?) ? Forger has to either forge ? or violate soundness of ?

10. [BDHKS19]: Anonymity PKE SPB-Hash NIWI Sign ?? ?? ????.?? ????.??,???.?? ?: NIWI proof that ?? encrypts a valid signature under some ?? and ii. an SPB opening showing ?? is consistent with i. VK0 VK1 ct ? ???.?????(?) ? Anonymity follows from a [NY 90] style argument (uses a dummy block )

11. Getting Rid of NIWI Observation: can use ZAPs instead of NIWI [BKM 06]. ZAP: 2-round public-coin witness-indistinguishable arguments ?? ?? ????.??,???.??,? ????.?? ZAP first message ZAP response generated using the ? from the lexicographically smallest ?? in the ring. ct ? ???.?????(?) ?

12. ZAPs: Status Want: ZAPs from LWE Several previous works: [LVW 19], [GJJM 20], [BFJ+ 20] Drawback: All need subexponential hardness of LWE (Necessitated by complexity leveraging) No constructions (that can establish soundness) from (poly-hard) LWE

13. ZAPs for NP coNP Might not need soundness for all NP languages! Unforgeability game: only 2 ways of beating soundness Either provide an invalid encryption (assume can be detected) Or encrypt a signature that is a valid forgery Defines a `non-witness for such forgeries [This work]: ZAPs for NP coNP from (poly-hard) LWE.

14. ZAPs for NP coNP: Ingredients Template: (Plain Model) Fiat-Shamir Compression of Trapdoor ?-Protocols Compress the -Protocol using Correlation Intractable hash functions Used in recent ZAP & NIZK constructions: [LVW 19], [CCH+ 19], [PS 19], [GJJM 20],[BFJ+ 20] Only establish soundness for NP coNP Key Ingredient: Commitment that is extractable given a non-witness ? P P V V Fiat-Shamir Challenge ? ? ? , ? = ? , ? Witness: w Witness: w

15. Background: Trapdoor -Protocols [CCH+19] General sigma protocol satisfying honest-verifier zero-knowledge and special soundness Also satisfies a trapdoor property: The bad challenge is efficiently computable given first message c ???is extractable Bad challenge function uses extraction trapdoor for ??? to recover ? P V ? ???(?) ? ? Witness: w

16. Background: Correlation-intractable hashing for circuits For any ? ?, given a hash key ? ?, an efficient adversary cannot find an ? such that ?? = ? ? . ? ? ? ? wins if ?? = ? ? ? 16

17. Background: Compressing Trapdoor -Protocols Prover uses a CI-Hash to compute ? P V ? ??? ? , ? = (?) ,? Witness: w

18. Background: ZAPs for NP from subexponentially hard LWE [LVW 19] Use a PKE scheme as the commitment Extraction trapdoor depends on the choice of ?? => The bad-challenge function depends on the choice of ?? => Need complexity leveraging to guess it => Need subexponential hardness assumption ??,?? chosen uniformly by V and P respectively P V pk, c PKE.Enc(?? ?? ,?), ? = ? ,? Statement: ? Witness: w h: CI hash function

19. ZAPs for NP coNP: Template Prover and verifier use a two-round commitment scheme Com = ???1,???2 ???2 takes instance ? and committed value as input ???1 takes an arbitrary string ? as input Want: extractability when ? ?, i.e., extractable when ? ? ? ?? ? ??: complement language P V Com1(?), c Com2(?,?), ? = ? ,? Statement: ? Witness: w h: CI hash function

20. Witness Extractable Commitments Two-round commitment scheme Com = ???1,???2for an NP language ? If ? is a witness for ? ?, ? can be extracted. If ? ?, ? is statistically hidden. C Com1( ?) R Com2(?,?) Statement: ? Statement: ? Witness: ?

21. Witness Extractable Commitments We build compact witness-extractable commitments from LWE. Uses malicious circuit-private FHE [OPP 14] provides `compactness Non-compact from OT+Garbling. C R Com1( ?) Com2(?,?) Statement: ? Statement: ? Witness: ?

22. Witness Extractable Commitments: Construction C wants to commit to b. Gx,b( ?): If ? is a witness for ? ?: output b Otherwise: output 0 C R ct FHE.Enc(FHE.pk, ?) cteval FHE.Eval(Gx,b,ct) Statement: ?

23. Witness Extractable Commitments: Construction Gx,b( ?): If ? is a witness for ? ?: output b Otherwise: output 0 Compactness: FHE is compact Extractable: ? ? FHE.Dec cteval,FHE.sk = b Hiding: follows from malicious circuit-privacy of FHE: ct (even malicious), ?: nothing is revealed beyond Gx,b(?). => If ? ?, nothing is revealed! C ct FHE.Enc(FHE.pk, ?) R cteval FHE.Eval(Gx,b,ct) Statement: ?

24. ZAPs for NP coNP Prover and verifier use a two-round commitment scheme Com = ???1,???2 ???2 takes instance ? and committed value as input ???1 takes an arbitrary string ? as input Want: extractability when ? ?, i.e., extractable when ? ? P P V V Com1(?), Com1( ?), c Com2(?,?), ? = ? ,? c Com2(?,?), ? = ? ,? Statement: ? Witness: w h: CI hash function

25. Thank You! eprint: https://eprint.iacr.org/2021/942.pdf