Application of Leftover Hash Lemma to Public Key Encryptions Based on Conjugacy Search Problem (New contact points of algebraic systems, logics, languages, and computer sciences)
明弘 山村 · Kyoto University Research Information Repository (Kyoto University) · 2015
We show flaws in a one of public key encryptions based on conjugacy search problem which has fatal flaw and apply the leftover hash lemma to remedy.1 Flaws CSP-EIG Three public key encryptions, CSP-EIG, CSP-hElG and CSP-CS schemes, are proposed by L.Wang, L.Wang, Z.Cao, E.Okamoto and J. Shao in Inscrypt 2010 [7].Each scheme is claimed to have certain provable security.It is reported a fatal flaw in CSP-EIG and indicated that there are more erros in the design of the other two schemes in [8].In this paper, we review the results obtained in [8] and consider the future research problems.Let $M$ be $a$ (not necessarily commutative) monoid.We denote the set of invertible elements $x$ of $M$ by $G(M)$ .The conjugacy search problem is to find an element $9\in G(M)$ such that $f=9^{d_{9^{-1}}}$ for given $d,$ $f\in M$ provided that such an element $g$ exists.Suppose that $d\in M$ and $g\in G(M)$ and the order of $g$ is $n$ .If the order of 9 is infinite, then $n$ is specified to be a large enough.The CSP-DDH problem is a decisional problem to decide whether or not $f=9^{a+b}d9^{-(a+b)}$ for given $d\in M,$ $g\in G(M)$ , $g^{a}dg^{-a},$ $9^{b}d_{9^{-b}}$ and $f=g^{c}dg^{-c}$ , where $a$ and $b$ and are randomly chosen from $\{$ 1, . . ., $n\}$ and either $c$ is randomly chosen from $\{$ 1, ... , $n\}$ or $c=a+b$ with probability $\frac{1}{2}$ .We say that the CSP-DDH assumption holds for $M$ if there is no efficient algorithm to answer correctly