Compact Ring Signatures from LWE - CRYPTO 2021 Research

 
Compact Ring Signatures
Compact Ring Signatures
from LWE
from LWE
 
Rohit Chatterjee
Rohit Chatterjee
1
1
, Sanjam Garg
, Sanjam Garg
2,3
2,3
, Mohammad Hajiabadi
, Mohammad Hajiabadi
4
4
, Dakshita Khurana
, Dakshita Khurana
5
5
,
,
Xiao Liang
Xiao Liang
1
1
, Giulio Malavolta
, Giulio Malavolta
6
6
, Omkant Pandey
, Omkant Pandey
1
1
, Sina Shiehian
, Sina Shiehian
1,2
1,2
 
CRYPTO 2021
CRYPTO 2021
 
1
 Stony Brook University
2 
UC Berkeley
3 
NTT Research
 
 
4 
University of Waterloo
5 
U. of Illinois Urbana-Champaign
6 
Max Planck Institute for Security & Privacy
 
Compact Ring Signatures
 
Previous Sublinear/Compact Ring Signatures
ROM
CRS
Plain
[DKNS’04], [GK’15],
[LLNW’16], [LPQ’18],
[EZS+19], [BKP20],
[LNS’21], …
[CGS’07], [Gha’13],
[Gon’17], [LPNY’20],
No plain model construction from LWE!
 
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.
 
[BDHKS’19]
PKE
SPB-Hash
NIWI
Sign
 
Standard (Generic)
 
Post-Quantum
 
Quantum-breakable
Strengthening of
Merkle tree, can be
based on FHE
Can be based on:
derandomization assumption
[BOV’03],
bilinear maps [GOS’12], 
or iO [BO’15]
Our Task:
Getting rid of NIWI
 
[BDHKS’19]: Construction
 
[BDHKS’19]: Construction
 
[BDHKS’19]: Compactness
 
 
Small
Small
 
[BDHKS’19]: Unforgeability
 
 
[BDHKS’19]: Anonymity
 
Anonymity follows from a
[NY’90] style argument (uses a
‘dummy block’)
 
VK
0
 
VK
1
 
Getting Rid of NIWI
 
Observation: can use ZAPs instead of NIWI [BKM’06].
ZAP: 2-round public-coin witness-indistinguishable arguments
 
ZAP first
message
 
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
 
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
 
Fiat-Shamir
 
Background: Correlation-intractable hashing
for circuits
16
Use 
a PKE scheme as the commitment
h
: CI hash function
h
: CI hash function
 
Witness Extractable Commitments
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.
Witness Extractable Commitments:
Construction
C
 wants to commit
to b.
Witness Extractable Commitments:
Construction
h
: CI hash function
 
                          
Thank You!
 
            eprint: https://eprint.iacr.org/2021/942.pdf
Slide Note

Hello, I am RC, and I will present our work in CRYPTO, titled ...

Introduce coauthors by name

Embed
Share

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.


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.

E N D

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

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#