International Association
for Cryptologic Research

Inductive reasoning in form of hybrid arguments is prevalent in cryptographic security proofs, but they are not integrated into formalisms used to model cryptographic security proofs, such as, for example, state-separating proofs. In this paper we present an induction principle for hybrid arguments that says that two games are many-steps indistinguishable if they are, respectively, indistinguishable from the end points of an iterated one-step indistinguishability argument. We demonstrate how to implement this induction rule in Nominal-SSProve by taking advantage of the nominal character of state-variables and illustrate its versatility by proving a general reduction from many-time CPA-security to one-time CPA-security for any asymmetric encryption scheme. We then specialize the result to ElGamal and reduce CPA-secure to the decisional Diffie Hellman-assumption.