Commitment Schemes: Information-Theoretic Security

Hiding and binding for commitment schemes, in their information-theoretic forms ([BS23], Section 8.12). Perfect hiding: every message yields the same commitment distribution. Statistical hiding: any two commitment distributions are within statistical distance ε. Perfect binding: no commitment can be opened to two different messages, even by an unbounded committer.

Each definition is about a single, fixed scheme; statistical hiding carries an explicit error bound, and the perfect notions have no error at all. The asymptotic notions in the book — negligible statistical distance for families of distributions ([BS23], Definition 3.6), or security against efficient adversaries (Section 8.12) — can be layered on top of these later.

Main definitions

• Scheme.PerfectlyHiding: the commitment distributions are equal for every pair of messages
• Scheme.StatisticallyHiding: the commitment distributions are statistically close with error ε
• Scheme.PerfectlyBinding: no commitment has accepted openings to two different messages

References

• D. Boneh, V. Shoup, A Graduate Course in Applied Cryptography, Version 0.6

def Cslib.Crypto.Protocols.Commitment.Scheme.PerfectlyHiding {Message : Type u_1} {Commitment : Type u_2} {Opening : Type u_3} (scheme : Scheme Message Commitment Opening) : Prop

A scheme is perfectly hiding when every message yields the same commitment distribution, so a commitment reveals nothing about the message as long as its opening is withheld ([BS23], Section 8.12).

Equations

• scheme.PerfectlyHiding = ∀ (message₀ message₁ : Message), scheme.commitmentDist message₀ = scheme.commitmentDist message₁

def Cslib.Crypto.Protocols.Commitment.Scheme.StatisticallyHiding {Message : Type u_1} {Commitment : Type u_2} {Opening : Type u_3} [Fintype Commitment] (scheme : Scheme Message Commitment Opening) (ε : NNReal) : Prop

A scheme is statistically hiding with error ε when the commitment distributions of any two messages are within statistical distance ε ([BS23], Definition 3.5 and Section 8.12).

Equations

• scheme.StatisticallyHiding ε = ∀ (message₀ message₁ : Message), Cslib.Probability.PMF.StatisticallyClose (scheme.commitmentDist message₀) (scheme.commitmentDist message₁) ε

def Cslib.Crypto.Protocols.Commitment.Scheme.PerfectlyBinding {Message : Type u_1} {Commitment : Type u_2} {Opening : Type u_3} (scheme : Scheme Message Commitment Opening) : Prop

A scheme is perfectly binding when a commitment can be opened to at most one message: any two accepted openings of the same commitment agree on the message ([BS23], Section 8.12). Different openings of the same message are still allowed.

Equations

• One or more equations did not get rendered due to their size.