ºìÐÓÊÓƵ

Topic

Two Views of Cryptography and the Gap In-Between

Department of Computer Science

Date & location

• Wednesday, April 16, 2025

• 11:00 A.M.

• Engineering Computer Science Building

• Room 227

Reviewers

Supervisory Committee

• Dr. Bruce Kapron, Department of Computer Science, University of Victoria (Co-Supervisor)

• Dr. Yun Lu, Department of Computer Science, UVic (Co-Supervisor) 

External Examiner

• Dr. Riham AlTawy, Department of Electrical and Computer Engineering, University of Victoria 

Chair of Oral Examination

• Dr. Ruohong Jiao, School of Earth and Ocean Sciences, UVic

   

Abstract

There are two popular views of cryptography. One is formal (symbolic), which uses expressions to model the ideal functionality of encryption functions and is easy to verify. The other is computational, which is what cryptographic assumptions rely on and is used for most security definitions. The challenge of reconciling these two views of cryptography lies in security under the presence of encryption cycles. In this thesis, we provide a proof of completeness for Abadi-Rogaway symbolic logic with respect to KDM security, a strong form of circular security. Further, we provide a larger set of expressions for which Micciancio’s symbolic logic is complete with respect to CPA security, extending Micciancio’s completeness, which holds only for the set of acyclic expressions. We also give an alternate characterization of Micciancio’s logic. On the computational side, we give a proof that circular insecurity is maintained as cycle length decreases, which is not a previously shown result.