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
-
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},
url = {https://eprint.iacr.org/2018/051}
}
