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.