Paper 2006/178 Original: eprint.iacr.org/2006/178 ↗
A New Cryptosystem Based On Hidden Order Groups
Abstract
Let $G_1$ be a cyclic multiplicative group of order $n$. It is known that the Diffie-Hellman problem is random self-reducible in $G_1$ with respect to a fixed generator $g$ if $\phi(n)$ is known. That is, given $g, g^x\in G_1$ and having oracle access to a ``Diffie-Hellman Problem solver'' with fixed generator $g$, it is possible to compute $g^{1/x} \in G_1$ in polynomial time (see theorem 3.2). On the other hand, it is not known if such a reduction exists when $\phi(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 \emph{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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2007-03-05: last updated
- 2006-05-30: published
- Short URL
- https://ia.cr/2006/178
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2006/178,
author = {Amitabh Saxena and Ben Soh},
title = {A New Cryptosystem Based On Hidden Order Groups},
howpublished = {Cryptology {ePrint} Archive, Paper 2006/178},
year = {2006},
url = {https://eprint.iacr.org/2006/178}
}