Mathematical Methods of Cryptography

Oracle Diffie — Hellman problem with equivalence relation

A. O. Bakharev, K. D. Tsaregorodtsev


Abstract: When using certain cryptographic mechanisms (such as key encapsulation schemes) in specific applied protocols, questions concerning the so-called “benign malleability” arise: the generated value might allow limited modification (forgery) that does not affect the correctness of its further processing. At the same time, in the context of a broader protocol, such a property may be undesirable: e.g., if session keys of an AKE-protocol are generated based on a specific ciphertext that allows benign modification, then the adversary can theoretically obtain a situation in which the participants considers the protocol session to be completed correctly, but both have established different session keys. In this paper, for key exchange schemes (such as $\mathbf{VKO}$) a property similar to that of benign forgery is studied. The standard problem of distinguishing whether the key is generated via specified algorithm or random is considered, with the modification that some keys are considered equivalent (the equivalence relation is specified via $\mathsf{Eq}$ function), which allows one to obtain more fine-grained analysis of benign forgeries. In the proposed $\mathsf{eq}$-$\mathsf{mODH}$ model the adversary is given access to two oracles: (a) $\mathcal{O}_{\mathrm{kgen}}()$ generating a new session key pair and the corresponding session secret key; (b) $\mathcal{O}_{\mathrm{comb}}(epk')$ generating session secret key based on a given ephemeral key $epk'$, with the modification that on equivalent ephemeral keys $\mathcal{O}_{\mathrm{comb}}$ must provide equal outputs. The reduction of a model with several adaptive queries to $\mathcal{O}_{\mathrm{kgen}}$ to a non-adaptive model $\mathsf{eq}$-$\mathsf{ODH}$ is shown. For the $\mathbf{VKO}$ scheme, an upper bound of the complexity of the $\mathsf{eq}$-$\mathsf{ODH}$-problem was obtained under additional assumptions (generic group model).

Keywords: provable security, VKO, Diffie — Hellman problem.

UDC: 519.7

DOI: 10.17223/2226308X/18/24