GUC-Secure Commitments via Random Oracles: New Findings
Exploring the feasibility of GUC-secure commitments using global random oracles, this research delves into the differences between local and global random oracles, outlining motivations and future work. It discusses UC frameworks, zero-knowledge proofs, oblivious transfers, and the GUC framework for analyzing protocol security in the presence of global random oracles.
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
GUC-Secure Commitments via Random Oracles: New Impossibility and Feasibility Zhelei Zhou, Zhejiang University Bingsheng Zhang, Zhejiang University Hong-Sheng Zhou, Virginia Commonwealth University Kui Ren, Zhejiang University
Outline Motivations: Why global random oracle? Why GUC? What is the difference between the local RO and the global RO? Our Focus: GUC-secure commitments in the global random oracle models. Lower bound on round complexity Round-optimal construction under minimal assumptions Our Results Future Work
Random Oracles Random oracles enable highly efficient protocols Examples: Fiat-Shamir heuristic based ZKP [ZXZS20,DIO21, YSWW21,DILO22], RO based OT [CO15,MR19,CSW20,ZZZR22], etc. People use hash functions (e.g., SHA256, MD5) to instantiate the random oracles global : different protocols use the same setup Zero Knowledge Proof Oblivious Transfer UC framework treats RO as a local setup
UC Framework Canetti s UC framework [Can01] can be used to: (i) analyze the security of protocols under concurrent executions; (ii) enable modular design of protocols. RO is local to the protocol instance! Ideal World Execution ???? ,?,? Real World Execution ???? ,?,? ?
Inconsistency shared states No shared states Oblivious Transfer Zero Knowledge Proof Zero Knowledge Proof Oblivious Transfer How to remove the inconsistency?
Generalized UC (GUC) Framework Canetti, Dodis, Pass and Walfish proposed the GUC framework [CDPW07] which can be used to analyze the security of the protocols in the presence of the global random oracles. Global Ideal World Execution ????? ,?,? Real World Execution ????? ,?,? ? ?
Local RO VS Global RO The power of the simulator: Observability: Simulator can see the queries sent by anyone (including the corrupted parties); Programmability: Simulator can determine the answer of the queries sent by anyone (including the corrupted parties). Ideal World Execution in UC Framework
Local RO VS Global RO The power of the simulator: Observability: Simulator can see the queries sent by anyone (including the corrupted parties); Programmability: Simulator can determine the answer of the queries sent by anyone (including the corrupted parties). Ideal World Execution in GUC Framework
Different Global ROs GrpoRO GsRO [CDPW07]: No extra power for simulator at all! GUC-secure COM is impossible! GroRO [CJS14]: Restricted observability: Simulator can see the adversary s queries 5-round GUC-secure COM under DLog assumption GrpRO GroRO GrpRO [CDGLN18]: Restricted programmability: Simulator can program the unqueried points without being detected 3-round GUC-secure COM under CDH assumption GsRO GrpoRO [CDGLN18]: Restricted programmability/observability 2-round GUC-secure COM unconditionally
Our Focus Why Commitment? Fundamental crypto primitive Why GroRO model? GsRO is too weak; GrpoRO is too strong GrpRO and GrpoRO do not capture deniability A reasonable global setup to study Deniability is impossible in the programmable RO model![Pas03][CJS14] Ref. [CJS14] [MRS17] [BGM19] [Bra21] Ours #Round 5 3 5 6 3 Assumptions DLog DLog Lattice-based Code-based OWF Comparison of GUC-secure commitments in the GroRO model
Our Research Question It is natural to ask: Q1: Lower bound on the round complexity of the GUC-secure commitment in the GroRO model? Q2: Round-optimal GUC-secure commitment in the GroRO model under minimal assumption?
Our Results The lower bound on round complexity for GUC-secure commitment is 2! We construct a 3-round (round-optimal) GUC-secure commitment protocols under minimal assumptions in the GroRO model.
Lower Bound Proof approach [CF01][CDPW07][DSW08] Assume such a protocol exists. Then leads to a contradiction. Can be run by anyone! Violate binding! (?,??) ??() ? ??(??,?) ? ?,? ?
Our Construction A general framework (similar to [MRS17]) Two building blocks: (i) Straight-line extractable NIWH arguments (ii) Equivocal commitment ?,?,? ?? KeyGen(??) ??,? Verify ? ? (?,?) Commit(??,?) (? ,? ) Commit(??, ) ?,? ?,?,? ,? Checks the following: = RO(?,?,?) Verify ?,? = Verify ? ,? = 1
Instantiations GroRO [Pas03][Fis05][Ks22] [IKOS07] Straight-line extractable NIWH arguments 2-Special sound Sigma Protocols MPC [MY04] Equivocal Commitment OWF Observation: No MPC-in-the-head based Sigma protocols achieve 2-special sound under minimal assumption! Our contribution: Based on [KKW18], we proposed the first 2-special sound MPC-in-the-head based Sigma protocols under minimal assumption!
Conclusion We study the commitment in the GroRO model: Ref. [CJS14] [MRS17] [BGM19] [Bra21] Ours #Round 5 3 5 6 3 Assumptions DL DL Lattice-based Code-based OWF Lower bound: We proved that 2-round GUC static-secure commitment is impossible in the GroRO model. Optimal Construction: We constructed the first round-optimal GUC static-secure under minimal assumption in the GroRO model. Comparison of GUC static-secure commitments in the GroRO model
Future Work Open Question 1: What is the situation in the GrpRO model? Known Result: We proved that 2-round GUC static-secure commitment is impossible in the GrpRO model. (Eprint: 2022/1127) We are exploring: Is it possible to construct a 3-round GUC-secure commitment under minimal assumptions in the GrpRO model? Open Question 2: What if we consider the simultaneous rounds? Known Result: We constructed the first 2-round (assuming simultaneous rounds) GUC static-secure commitment under CDH assumption in the GroRO model. (In Submission, Eprint: 2022/1525) We are exploring: Is it possible to construct a 2-round (assuming simultaneous rounds) GUC-secure commitment under minimal assumption in the GroRO/GrpRO model?
