GUC-Secure Commitments via Random Oracles: New Findings

 
 
 
Z
h
e
l
e
i
 
Z
h
o
u
,
 
 
Z
h
e
j
i
a
n
g
 
U
n
i
v
e
r
s
i
t
y
Bingsheng Zhang, Zhejiang University
Hong-Sheng Zhou, Virginia Commonwealth University
Kui Ren, Zhejiang University
Outline
Our Focus: GUC-secure commitments in the global random oracle models.
Lower bound on round complexity
Round-optimal construction under minimal assumptions
 
Motivations:
Why global random oracle?
Why GUC?
What is the difference between the local RO and the global RO?
 
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
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.
Inconsistency
 
shared states
 
No shared states
 
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.
Local RO VS Global RO
Ideal World Execution 
in UC Framework
Local RO VS Global RO
Ideal World Execution 
in GUC Framework
Different Global ROs
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 [CDGLN18]:
Restricted programmability
:
Simulator can program the unqueried points without being detected
3-round GUC-secure COM under CDH assumption
 
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
 
Comparison of GUC-secure commitments in the GroRO model
Our Research Question
 
 
Q1:
 
Lower bound on the round complexity 
of the GUC-secure
commitment in the GroRO model?
It is natural to ask:
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
Instantiations
 
 
2-Special sound
Sigma Protocols
 [Pas03][Fis05][Ks22]
Straight-line extractable
NIWH arguments
GroRO
OWF
Equivocal Commitment
 [MY04]
 
MPC
 
 [IKOS07]
 
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:
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 2: What if we consider the simultaneous rounds?
Open Question 1: What is the situation in the GrpRO model?
 
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?
 
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?
Thank you!
Slide Note

Hi, everyone. This is Zhelei Zhou, a PhD student from Zhejiang University. The topic I want to share today is GUC-Secure Commitments via Random Oracles: New Impossibility and Feasibility. It is a joint work with Bingsheng Zhang, Kui Ren from Zhejiang University, and Hong-Sheng Zhou from Virginia Commonwealth University.

Embed
Share

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.

  • Random Oracle
  • GUC
  • Security Protocols
  • UC Framework
  • Feasibility

Uploaded on Oct 04, 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. 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

  2. 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

  3. 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

  4. 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 ???? ,?,? ?

  5. Inconsistency shared states No shared states Oblivious Transfer Zero Knowledge Proof Zero Knowledge Proof Oblivious Transfer How to remove the inconsistency?

  6. 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 ????? ,?,? ? ?

  7. 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

  8. 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

  9. 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

  10. 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

  11. 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?

  12. 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.

  13. Lower Bound Proof approach [CF01][CDPW07][DSW08] Assume such a protocol exists. Then leads to a contradiction. Can be run by anyone! Violate binding! (?,??) ??() ? ??(??,?) ? ?,? ?

  14. 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

  15. 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!

  16. 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

  17. 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?

  18. Thank you!

More Related Content

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