Cryptographic protocols based on real-quadratic A-fields (extended abstract)

Abstract

In [7] and [3] the difficulty of the Discrete-Logarithm problem in the cycle of reduced principal ideals in a real-quadratic number field was used as basis for the construction of secure cryptographic protcols. In [14] a Diffie-Hellman key exchange variant based on a real-quadratic congruence function fields is presented. We generalize and extend these results by investigating real-quadratic A-fields. We define the Distance problem, the Discrete-Logarithm problem and the Diffie-Hellman problem in the cycle of reduced principal ideals in real-quadratic A-fields and discuss their difficulty. We show that with respect to probabilistic polynomial time reductions the Distance problem and the Discrete-Logarithm problem are equivalent and are at least as difficult as the Diffie-Hellman problem. Moreover we introduce the problem of computing square roots of reduced principal ideals in real-quadratic A-fields as another computationally difficult problem. In real-quadratic number fields this again is at least as difficult as the integer factorization problem. In congruence function fields the problem of computing square roots is supposed to be even more difficult than in number fields. We present a secure bit commitment scheme based on the difficulty of the square root problem and an oblivious transfer protocol based on the Diffie-Hellman problem. These protocols are important since they may serve as components for the construction of more sophisticated cryptographic protocols.