Efficient Lattice-Based Blind Signature Framework
This work presents a new framework for efficient round-optimal lattice-based blind signatures, offering enhanced security properties. It outperforms prior works in signature size and security assumptions, making it a promising advancement in the field of cryptographic 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
A New Framework For More Efficient Round-Optimal Lattice-based (Partially) Blind Signature via Trapdoor Sampling CRYPTO 2022 Shuichi Katsumata Rafael del Pino PQShield SAS AIST and PQShield Ltd
Blind Signatures Server: sk User: User: msg,vk c ' ?????? ? Correctness: If the protocol is run honestly then verification succeeds Unforgeability: An adversary cannot produce ? + 1 signatures after running the protocol ? times. Blindness: The server cannot link any signature to a specific execution
Our Result A more efficient lattice-based round-optimal (partially) blind signature (in the QROM). Generic Blind Signature Recipe [C:Fis05]: (Signer) Signature ? for ??? (User) Commit Message ??? (User) ZKProve (?,???) Standard BDLOP commitment New approach
Prior Lattice-based Works Schnorr-type Blind Signature [Ruc10,AEB20, HKLN20] Provable secure parameters require signature of several MBs. OTS + OR-profs [LNP22a] New round-optimal approach but requires an upper bound on the number of signature at setup. Fischlin s Generic Construction-based [AKSY22] Two instantiation of Fischlin s generic construction. One requires to evaluate a RO by an FHE and the other requires a new one-more SIS assumption. (*) [AKSY22] recently updated their paper: using the recent NIZK by [LNP22b], they achieve shorter signature than our scheme based on the one-more SIS assumption. 4
Prior Lattice-based Works Size Time Assumption HKLN20 7.7MB O(1) MSIS LNP22a 150KB O(Q) MLWE/MSIS 44KB* AKSY22 O(1) One-more-SIS Ours 100KB* O(1) MLWE/MSIS *Using a different NIZKPoK
Our Work In More Detail Round-Optimal and Unbounded Signature One message from user and another from server and no upper bound on the signature. Standard Assumption Based on MLWE and Decisional Small Matrix Ratio (i.e., NTRU) assumption. Quantum ROM Security The first work to have a concrete proof in the QROM. More Efficient than Prior Works Around 100KBs for the signature. Since it s a generic construction, we may be able to plugin recent NIZKs to further lower the signature size
The Fischlin Construction c c COM(pkc,m) SIGN(sk,c) ct Enc(pkE,c||?) Output (??,m, ) Proves in ZK that it has: - Public Public(m, ct) - Private Private(c, ) s.t. ct opens to a message (c,?) where c opens to m and ? is a signature of ? by the server.
The Fischlin Construction c c COM(pkc,m) SIGN(sk,H(c)) ct Enc(pkE,c||?) Output (??,m, ) Problems with lattices: Signatures (either FS-based or preimage-based) require a hash of the message Proving relations on multiple layers of encryption is very costly
The Fischlin Construction c c COM(pkc,m) SIGN(sk,H(c)) ct Enc(pkE,c||?) Output (??,m, ) A New Commit-then-Sign-and-ZKProve Protocol
Core Idea: Trapdoor-Compatible Commitments The [BDLOP18] Commitment: ?1 ?2 User private information Server private information ?? 0 =? ?? + ??= ?? + ?? Binding : ??? ?1;?1 = ??? ?2;?2 ? ?1 ?2 = 0 SIS Hiding : ? ?? ~ uniform LWE
Core Idea: Trapdoor-Compatible Commitments [ABB10] Style signature: User private information Server private information Sample small e such that: A0A1+ m G e = u If m is invertible and A1= A0R0then one can use G as a trapdoor to sample e.
Core Idea: Trapdoor-Compatible Commitments A0A1+ c2e = u Sign on commitment The trapdoor is now unusable. The server knows a trapdoor for A0!
Core Idea: Trapdoor-Compatible Commitments c2= BR + m G A0A1+ c2e = u commitment for msg Sign on commitment e1 e2 Re2 A0A1+ (BR + m G) e = u A0A1+ m G B = u Public matrix Private vector Simple SIS relation with efficient NIZK!
Our Scheme ?1,c2 ?1 ?2 0 =? ?? + Small e s.t ?? A0A1+ c2e = u e Check: e1 e2 Re2 A0A1+ msg G B = u Output (msg, ) is a NIZKPoK of a small secret e such that A0A1+ msg G B e = u
Dont we need to Hash c ? Lattice-based signatures require the message to be hashed for unforgeability. E.g if ?2= 0, and A0= [?/?,1], then an adversary can reconstruct a (slightly worse) basis for A0using a single signature!
Dont we need to Hash c ? Lattice-based signatures require the message to be hashed for unforgeability. Proving that the commitment c is well formed is enough to prove security ! We need a Straight-Line exact NIZKPoK (we us [Kat21] to adapt [LNS20])
Straight-Line Exact NIZK y c z All commonly used NIZKPoK have special soundness: Given (y,c,z) and (y,c ,z ) one can extract a witness w. We require Straight Line extractability: Given (y,c,z) and using trapdoor in the CRS one can extract a witness w. We use techniques from [Kat21].
Straight-Line Exact NIZK y c z The original proof of [Lyu09] only proves ?? = ?? instead of ?? = ? [LNS20,LNP22] Construct exact proofs for this relation
The Full Scheme ?1,c2 ?1 ?2 1= MNIZK(?1,?2,?) 0 =? ?? + Check 1 ?? Small e s.t A0A1+ c2e = u e Check: e1 e2 Re2 A0A1+ m G B = u Output (m, )
More Details in the Paper A more efficient lattice-based round-optimal (partially) blind signature (in the QROM). What is left to be done? Use more efficient straight-line exact NIZKPoK Increase efficiency even more through stronger assumptions
