Back to search

University of Victoria (Canada)

Verified commitment schemes and reduction proofs in the lean proof assistant

Abstract

dc:description.abstract

This thesis presents a formalization of commitment schemes in the Lean 4 theorem prover, together with machine-checked proofs of their core security properties. Commitment schemes allow a party to commit to a value while keeping it hidden, with guarantees of binding (the value cannot be changed) and hiding (the value remains secret until revealed). We develop a general, specification-driven framework for modelling commitment schemes and their security definitions in Lean, using a probabilistic monad to express adversarial games and reduction-based proofs. Within this framework, we formalize two canonical schemes: the Pedersen commitment scheme and the ElGamal commitment scheme. For Pedersen, we prove perfect hiding and computational binding via reduction to the discrete logarithm problem; for ElGamal, we prove perfect binding and computational hiding via reduction to the decisional Diffie–Hellman assumption. This work contributes both concrete formalizations and reusable abstractions for cryptographic reasoning in Lean, advancing the emerging area of mechanized cryptography within the system.

Degree

thesis:*
Level thesis:degree_level
Master of Science MSc
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Blacquiere, Ashley
Advisor dc:contributor.supervisor
  • Kapron, Bruce

Subjects

dc:subject × 6

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1828/23749

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Blacquiere, Ashley. Verified commitment schemes and reduction proofs in the lean proof assistant. Master of Science MSc thesis, 2026. https://hdl.handle.net/1828/23749