2006/04/30 by Amitabh Saxena, Saxena, Amitabh, Ben Soh +1
Computer Science · Mathematics · #Coding theory and cryptography #Computational Complexity (cs.CC) #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Geometric and Algebraic Topology #cs.CC #cs.CR
paper · pdf · doi:10.48550/arxiv.cs/0605003
removed examples for multiparty key agreement and join protocols, since they are redundant
openalex publication_date 2006/04/30 · arxiv created 2006/05/03 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G1 be a cyclic multiplicative group of order n. It is known that the Diffie-Hellman problem is random self-reducible in G1 with respect to a fixed generator g if ϕ(n) is known. That is, given g, gx∈ G1 and having oracle access to a `Diffie-Hellman Problem' solver with fixed generator g, it is possible to compute g1/x ∈ G1 in polynomial time (see theorem 3.2). On the other hand, it is not known if such a reduction exists when ϕ(n) is unknown (see conjuncture 3.1). We exploit this ``gap'' to construct a cryptosystem based on hidden order groups and present a practical implementation of a novel cryptographic primitive called an Oracle Strong Associative One-Way Function (O-SAOWF). O-SAOWFs have applications in multiparty protocols. We demonstrate this by presenting a key agreement protocol for dynamic ad-hoc groups.