English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We investigate the complexity of breaking cryptosystems of which security is based on the discrete logarithm problem. We denote the algorithms of breaking the Diffie-Hellman's key exchange scheme by DH, the Bellare-Micali's non-interactive oblivious transfer scheme by BM, the ElGamal's public-key cryptosystem by EG, the Okamoto's conferencekey sharing scheme by CONF, and the Shamir's 3-pass key-transmission scheme by 3PASS, respectively. We show a relation among these cryptosystems that 3PASS ≤mFP CONF ≤mFP EG ≡mFP BM ≡mFP DH, where ≤mFP denotes the polynomial-time functionally many-teone reducibility, i.e. a function version of the ≤mp -reducibility. We further give some condition in which these algorithms have equivalent difficulty. Namely, 1. If the complete factorization of p - 1 is given, i.e. if the the discrete logarithm problem is a certified one, then these cryptosystems are equivalent w.r.t. expected polynomial-time functionally Turing reducibility. 2. If the underlying group is the Jacobian of an elliptic curve over Zp, with a prime order, then these cryptosystems are equivalent w.r.t. polynomial-time functionally many-to-one reducibility. We also discuss the complexity of several languages related to those computing problems.

Relationships among the Computational Powers of Breaking Discrete Log Cryptosystems