A structural comparison of the computational difficulty of breaking discrete log cryptosystems (Q1382147)

Many cryptosystems base their security properties on the assumption that the so called \textit{discrete logarithm problem} is (computationally) difficult to solve. In other words, an efficient algorithm for the discrete logarithm problem (DLP) would make all these cryptosystems insecure. On the other hand, generally it is not known whether the existence of a polynomial-time algorithm to break one of these cryptosystems implies feasibility of the DLP. In the paper another approach to the investigation of security properties of DLP-based cryptosystems is explored. Instead of seeking an answer to the question whether breaking of a particular cryptosystem is computationally equivalent to the DLP the authors investigate the relation among DLP-based cryptosystem. In particular, the question whether a cryptosystem remains secure even if a polynomial-time algorithm to break another cryptosystem exists is studied. To compare the relative complexity of breaking different DLP-based cryptosystems the concept of \textit{polynomial-time reducibility} is used. Various DLP-based cryptographic schemes are considered here, namely the Diffie-Hellman key exchange scheme (DH), the Bellare-Micali noninteractive oblivious transfer scheme (BM), the ElGamal public key cryptosystem (EG), the Okamoto conference-key sharing scheme (CONF) and the Shamir 3-pass key-transmission scheme (3PASS). To study the relation among them the notions of \textit{polynomial-time functional many-to-one reducibility} and \textit{polynomial-time functional Turing reducibility} are used. First, it is shown that with respect to polynomial-time functional many-to-one reducibility, EG, BM and DH are equivalent, and 3PASS is reducible to CONF which in turn is reducible to EG. Then, some conditions under which these problems have equivalent difficulty are given. Particularly, it is shown that if instead of usual DLP one considers elliptic-curve discrete logarithm problem, then respective variants of all of the above cryptographic schemes are equivalent with respect to polynomial-time functional many-to-one reducibility. Finally, the complexity of languages associated with the above mentioned cryptographic schemes is briefly investigated. While all these languages are known to be in NP \(\cap\) co-NP, only the language corresponding to the DLP (\(L_{\text{DLP}}\)) is known to be in P. However, it is shown that if \(L_{3\text{PASS}}\) is in P, then DH is expected polynomial-time functionally Turing reducible to 3PASS. It is also shown that \(L_{DH}\) is random self-reducible, and therefore is in the class of languages that have perfect zero-knowledge interactive proof.