×

zbMATH — the first resource for mathematics

On the cryptographic value of the \(q^{th}\) root problem. (English) Zbl 1014.94553
Varadharajan, Vijay (ed.) et al., Information and communication security. 2nd international conference, ICICS ’99, Sydney, Australia, November 9-11, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1726, 135-142 (1999).
Summary: The authors show that, for a prime \(q\) and a group \(G\), if \(\text{ord}(G)= q^kr\), \(k> 1\), and \(r\) is smooth, then finding a \(q\)th root in \(G\) is equivalent to the discrete logarithm problem over \(G\) (note that the discrete logarithm problem over the group \(G\) reduces to the discrete logarithm problem over a subgroup of order \(q\) – see S. Pohlig and M. Hellman [IEEE Trans. Inf. Theory 24, 106-110 (1978; Zbl 0375.68023)]. Several publications describe techniques for computing \(q\)th roots. All have the stated or implied requirement of computing discrete logarithms in a subgroup of order \(q\).
The emphasis here will be on demonstrating that with a fairly general \(q\)th root oracle, discrete logarithms in a subgroup of order \(q\) may be found, describing the cryptographic significance of this problem, and in introducing two new public key signature schemes based on it.
For the entire collection see [Zbl 0931.00051].

MSC:
94A60 Cryptography
11Y16 Number-theoretic algorithms; complexity
PDF BibTeX XML Cite