Stateless Deterministic Multi-Party EdDSA Signatures Study
Explore the research on stateless, deterministic multi-party EdDSA signatures with low communication, diving into the details of the study conducted by Qi Feng, Kang Yang, Kaiyi Zhang, Xiao Wang, Yu Yu, and Xiang Xie from various renowned institutions. The study focuses on the derivation process, interactive zero-knowledge proofs, core challenges encountered, and the multi-verifier zero-knowledge techniques discussed. Delve into the intricacies of key generation, signing processes, ZK proofs, and the unique features of multi-verifier IT-MAC 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
PKC 2025 Stateless Deterministic Multi-Party EdDSA Signatures with Low Communication Qi Feng1, Kang Yang2, Kaiyi Zhang3, Xiao Wang4, Yu Yu3,6, Xiang Xie5,6 1Wuhan University, 2State Key Laboratory of Cryptology, 3Shanghai Jiao Tong University, 4Northwestern University, 5rimus Labs, 6Shanghai Qi Zhi Institute
This Paper ??? ?? ??? ?? ??= ? ??,? ??= ?? ? ??= ? ??,? ??= ?? ? Interactive ZKP ? ?? ?(??,?) ??is honestly and deterministically derived by ?? and ? ?? ? ?(??,?) ? = ??+ ?? ? = ?(??||?||?) ? = ??+ ?? ? = ?(??||?||?) ??= ?? ??? ? ??= ?? ??? ? ? = ??+ ?? ? = ??+ ??
Core Challenge Produce [?] during KeyGen When signing on ?, prove in ZK on circuit ? ? = ? ??? , where ?: 0,1? 0,1 ? ?1?2 ? = ? ? ? = ? ?,? ? = ? ? VOLE-based ZK for Boolean circuits IT-MAC over Group ? ? ?(?,?)
Multi-Verifier ZK Original BDOZ-style IT-MAC: A secret value ? ?2 is represented by ? = ?,?,? , where ?0 keeps ? and MAC tag ? ?2?, ?1 keeps random key ? ?2? and fixed global key ?2?, such that ? = ? ? holds. Multi-Verifier IT-MAC: [?] = ?, ??,?? ? [?] means ? keeps {?,?1, ,??} ?2?, each ?? keeps ??, ? ?2?, such that ??= ??+ ? ? ?2? holds over field ?2?.
Multi-Verifier ZK check ? ? = 1? witness ? Verifiers Prover 1, ,?? ? ?2? ?= ??,?? ? ??= ?,?? ?? ?2? If ? = ???, ?? = ??+ [??] If ? = ??? and ?-th mult gate: for each gate ?,?,?,? ? ??= ?? ?? ?? ?2 ???= ?? ?+ ?? ???= ?? ?+ ?? ?, ??? ? ?, ??? ?? ? ?,?,? ???? ?? ?, ???, ??? ?,?,? ???? BatchCheck In the MV setting accept iff all ??????,??,?? = 1
Multi-Verifier BatchCheck check ? ? = 1? witness ? Verifiers Prover ?1, ,?? ?2? Define ? = ? ??? ??,?, ??,? = ?? ??,?,??? ? [?] Check ? = ? [?]?? ??,? ??,? ??,?, ??,? ? ?, ? Our approach: polynomial batchcheck inspired by Mac n Cheeseof [BMRS 21]
Multi-Verifier BatchCheck check ? ? = 1? witness ? Verifiers Prover ??,1 ??,? ??,? ??,1 ??,? ??,? 2 2 ??,? ??,? 2+1 2+1 recursively perform log? times ?1 ?? ?1 ?? 2 2 = ? [?/2]?? ?? ?2[?] ? ?2? ??? ??? ? = 0 s.t., ? ? Shr( ) 2 CheckZero ? [2][ (?)] ? 1 + 2 = ? ?/2??1 ??1 + ??2 ??2 = ? ? ??,? ??,?= ?
How to deterministic? Random Challenges: generate ? using the Fiat-Shamir heuristic. Multi-Verifier Vector Oblivious Linear Evaluation Correlations: PCF [BCG+20] can deterministically incremental and on-demand local generation of mv-VOLE correlation with fixed ? and ? from the ????, generated in the setup phase.
Core Challenge Produce [?] during KeyGen When signing on ?, prove in ZK on circuit ? ? = ? ??? , where ?: 0,1? 0,1 ? ?1?2 ? = ? ? ? = ? ?,? ? = ? ? VOLE-based ZK for Boolean circuits IT-MAC over Group ? ? ?(?,?) Communication costs: ?(? + log? ?) in one round
Multi-Verifier IT-MAC over Group IT-MAC over Group: We extend the original BDOZ-style IT-MACs to group of authenticated values as well. Given the group parameters ?,G,? ,[?] = ?,?,? means ?0 keeps {?,?} ?2, ?1 keeps ?, ? ?, such that ? = ? + ? holds over group ?. Multi-Verifier IT-MAC over Group: [?] = ?, ??,?? ? [?] means ? keeps {?,?1, ,??} ?2, each ?? keeps ??, ? ? ?, such that ??= ??+ ? ? holds over group ?.
? = ? ?,? ? = ? ? Provable Nonce Derivation ? ? ?(?,?) ?,?? Prover Verifiers COT PCF ?? Setup Online ?? ?? ?? open and check ??= ?? ? ??= ?? ? accept iff IT-MAC of ? is verified
Provable Nonce Derivation Verifiers Prover ?= ?? ?, ,?? ? ?2? ??, ?? ? ?2? ??= ?,?? ?? ??= ?? ? ? ??= ?? ? ? ?2? conversion 1, ,?? ? ?? ?= ?? ?, ?? ? ?? ??= ?,??
Sacrifice-based consistency check [KelOrs16] Conversion Subprotocol extend on-demand mv-edabits{ ? , ?1, , ? }, s.t., ?? 0,1 ,? = ? ?? mod ? [EGKRS 20] Prover Verifiers ?1 ?, , ? ? ?1 ?, , ? ? Boolean circuits ? = ? + ? Open(?1, ,? ) ?1 ?, , ? ? ?1 ?, , ? ? ? = ? ? ?? ? = ? ? ?? ? ??= ??+ ? ?
Core Challenge Produce [?] during KeyGen When signing on ?, prove in ZK on circuit ? ? = ? ??? , where ?: 0,1? 0,1 ? ?1?2 ? = ? ? ? = ? ?,? ? = ? ? VOLE-based ZK for Boolean circuits IT-MAC over Group ? ? ?(?,?) Communication costs: ?( ? + log ? ? + ? ) in one round
Summary We propose a stateless and deterministic multi-party EdDSA, in the assumption of all-but-one malicious corruption. Support standard EdDSA PRF circuit (e.g., SHA512) Low communication costs: Comm.: improve communication costs compared to [GKMN 21]. Rounds: match regular threshold Schnorr (3 rounds). See the paper for concrete cost analysis and details.
OfficePLUS PKC 2025 Calibri 1.3 Thanks cn.bing.com OfficePLUS officeplus@microsoft.com fengqi.whu@whu.edu.cn https://eprint.iacr.org/2024/358
