Back to search

Cornell University

Equational Reasoning for Verified Cryptographic Security

Abstract

dc:description.abstract

Modern software systems today have increasingly complex security requirements – such as supporting privacy-preserving computations, or resistance against quantum attackers – that are fulfilled by advanced forms of cryptography. At the same time, these advanced forms of cryptography often have subtle security proofs that require careful auditing. To ensure security, it is thus crucial to formally verify the security of the underlying cryptography, and to do so in a manner that is approachable to cryptographers. This thesis explores the use of equational reasoning to conduct machine-checked security proofs. Equational reasoning is pervasive in cryptography, as it underlies the concepts of game-hopping hybrids and the simulation paradigm; thus, optimizing formal tools for equational reasoning delivers machine-checked proofs closer to their on-paper counterparts.We first present AutoLWE, a prover for cryptographic primitives that sup- ports reasoning about lattices. AutoLWE is built around deducibility, which (semi-) automatically applies hardness assumptions by partitioning the security game into an application of the hardness assumption with a context. Using AutoLWE, we deliver very short proofs of several representative constructions, including Public-Key Encryption, Identity-Based Encryption, and Inner Product Encryption. We then present IPDL, a simple calculus and equational logic for distributed, interactive cryptographic protocols in the computational model. The purpose of IPDL is to prove simulation results between real and idealized protocols in the style of Universal Composability (UC) [Can01]. IPDL does so by restricting its attention to straight-line protocols, a particularly simple but expressive subset of protocols. Using IPDL, we deliver short proofs of multiple case studies, including a semi-honest multiparty computation protocol over general circuits [GMW87], and an n-party coin toss protocol [Blu83].

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gancher, Joshua
Chair dc:contributor.chair
  • Shi, Runting
Committee members dc:contributor.committeemember
  • Rooth, Mats
  • Morrisett, Greg

Subjects

dc:subject × 4

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
15312757
Dc Identifier Other
ProQuest Submission ID: 12775
ProQuest Publication ID: 28714153

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gancher, Joshua. Equational Reasoning for Verified Cryptographic Security. Doctor of Philosophy thesis, Cornell University, 2021. https://hdl.handle.net/1813/110901