Paper 2018/051

Semantic Security Invariance under Variant Computational Assumptions

Eftychios Theodorakis and John C. Mitchell


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

Available format(s)
Publication info
Preprint. MINOR revision.
semantic security proofverificationautomationcomputational assumptionsymmetryinvariance
Contact author(s)
eftychis @ alumni stanford edu
2019-02-23: last of 2 revisions
2018-01-15: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.