Abstract

A game-based cryptographic proof is a relation that estab-lishes equivalence between probabilistic sequences of actions by real andideal world players. The author of a proof selects ahardness assumptionsystemfor their proof upon which to base their subsequent statements. Inthis paper, we prove the existence of proof-invariant transformations forvarying hardness assumptions. We show that for two systems satisfyingcertain algebraic properties any proof in one system has an equivalentvalid proof in the other. This validates Kurosawa’s remark about theexistence 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 thisresult, we provide a series of example transformations in the appendix. The concrete result of this paper is a prototype proof translation tool.