Back to search

University of Victoria (Canada)

Computational soundness of formal reasoning about indistinguishability and non-malleability of cryptographic expressions

Abstract

dc:description.abstract

Analysis and verification of security protocols are typically carried out in two different models of cryptography: formal cryptography and computational cryptography. Formal cryptography, originally inspired by the work of Dolev and Yao [14], takes an abstract and idealized view of security, and develops its proof techniques based on methods and ideas from logic and theory of programming languages. It makes strong assumptions about cryptographic operations by treating them as perfectly-secure symbolic operations. Computational cryptography, on the other hand, has developed its foundations based on complexity theory. Messages are viewed as bit-strings, and cryptographic operations are treated as actual transformations on bit-strings with certain asymptotic properties.In this thesis, we explore the relation between the Dolev-Yao model and the computational model of public-key cryptography in two contexts: indistinguishability and non-malleability of expressions. This problem in the absence of key-cycles is partially addressed in [20, 21] by Herzog. We adapt our approach to use the co-inductive definition of symbolic security, whose private-key treatment was considered in coinduction, and establish our main results as follow: Using a co-inductive approach, we extend the indistinguishability and non-malleability results of Herzog in the presence of key-cycles. By providing a counter-example, we show that the indistinguishability property in this setting is strictly stronger than the non-malleability property, which gives a negative answer to Herzog's conjecture that they are equivalent. we prove that despite the fact that IND-CCA2 security provides non-malleability in our setting, the same result does not hold for IND-CCA1 security. We prove that, under certain hypothesis, our co-inductive formal indistinguishability is computationally-complete in the absence of key-cycles and with respect to any \emph{length-revealing} encryption scheme. In the presence of key-cycles, we prove that the completeness does not hold even with respect to IND-CPA security.

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hajiabadi, Mohammad
Advisor dc:contributor.supervisor
  • Kapron, Bruce

Subjects

dc:subject × 5

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
http://hdl.handle.net/1828/3496

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

Hajiabadi, Mohammad. Computational soundness of formal reasoning about indistinguishability and non-malleability of cryptographic expressions. Master of Science M.Sc. thesis, 2011. http://hdl.handle.net/1828/3496