Paper 2018/051

Semantic Security Invariance under Variant Computational Assumptions

Eftychios Theodorakis and John C. Mitchell

Abstract

A game-based cryptographic proof is a relation that establishes equivalence between probabilistic sequences of actions by real and ideal world players. The author of a proof selects a hardness assumption system for their proof upon which to base their subsequent statements. In this paper, we prove the existence of proof-invariant transformations for varying hardness assumptions. We show that for two systems satisfying certain algebraic properties any proof in one system has an equivalent valid proof in the other. This validates Kurosawa’s remark about the existence of proof similarities. Our result implies a correspondence between the Learning With Errors (LWE) problems and both the Elliptic Curve Discrete Log problem (ECDLP) and the Discrete Logarithm (DLOG) problem. To illustrate this result, we provide a series of example transformations in the appendix. The concrete result of this paper is a prototype proof translation tool.

Note: full version

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
semantic security proofverificationautomationcomputational assumptionsymmetryinvariance
Contact author(s)
eftychis @ alumni stanford edu
History
2019-02-23: last of 2 revisions
2018-01-15: received
See all versions
Short URL
https://ia.cr/2018/051
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/051,
      author = {Eftychios Theodorakis and John C.  Mitchell},
      title = {Semantic Security Invariance under Variant Computational Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/051},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/051}},
      url = {https://eprint.iacr.org/2018/051}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.