Generalized Powering Functions and Their Application to Digital Signatures

Hisayoshi SATO; Tsuyoshi TAKAGI; Satoru TEZUKA; Kazuo TAKARAGI

doi:10.1093/ietfec/e89-a.1.81

Generalized Powering Functions and Their Application to Digital Signatures

Hisayoshi SATO, Tsuyoshi TAKAGI, Satoru TEZUKA, Kazuo TAKARAGI

Full Text Views

0

Cite this

Summary :

This paper investigates some modular powering functions suitable for cryptography. It is well known that the Rabin encryption function is a 4-to-1 mapping and breaking its one-wayness is secure under the factoring assumption. The previously reported encryption schemes using a powering function are variants of either the 4-to-1 mapping or higher n-to-1 mapping, where n > 4. In this paper, we propose an optimized powering function that is a 3-to-1 mapping using a p²q-type modulus. The one-wayness of the proposed powering function is as hard as the infeasibility of the factoring problem. We present an efficient algorithm for computing the decryption for a p²q-type modulus, which requires neither modular inversion nor division. Moreover, we construct new provably secure digital signatures as an application of the optimized functions. In order to achieve provable security in the random oracle model, we usually randomize a message using random hashing or padding. However, we have to compute the randomization again if the randomized message is a non-cubic residue element--it is inefficient for long messages. We propose an algorithm that can deterministically find the unique cubic residue element for a randomly chosen element.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.1 pp.81-89

Publication Date: 2006/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.1.81

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Digital Signature

Cite this

Copy

Hisayoshi SATO, Tsuyoshi TAKAGI, Satoru TEZUKA, Kazuo TAKARAGI, "Generalized Powering Functions and Their Application to Digital Signatures" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 1, pp. 81-89, January 2006, doi: 10.1093/ietfec/e89-a.1.81.
Abstract: This paper investigates some modular powering functions suitable for cryptography. It is well known that the Rabin encryption function is a 4-to-1 mapping and breaking its one-wayness is secure under the factoring assumption. The previously reported encryption schemes using a powering function are variants of either the 4-to-1 mapping or higher n-to-1 mapping, where n > 4. In this paper, we propose an optimized powering function that is a 3-to-1 mapping using a p²q-type modulus. The one-wayness of the proposed powering function is as hard as the infeasibility of the factoring problem. We present an efficient algorithm for computing the decryption for a p²q-type modulus, which requires neither modular inversion nor division. Moreover, we construct new provably secure digital signatures as an application of the optimized functions. In order to achieve provable security in the random oracle model, we usually randomize a message using random hashing or padding. However, we have to compute the randomization again if the randomized message is a non-cubic residue element--it is inefficient for long messages. We propose an algorithm that can deterministically find the unique cubic residue element for a randomly chosen element.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.1.81/_p

Copy

@ARTICLE{e89-a_1_81,
author={Hisayoshi SATO, Tsuyoshi TAKAGI, Satoru TEZUKA, Kazuo TAKARAGI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Generalized Powering Functions and Their Application to Digital Signatures},
year={2006},
volume={E89-A},
number={1},
pages={81-89},
abstract={This paper investigates some modular powering functions suitable for cryptography. It is well known that the Rabin encryption function is a 4-to-1 mapping and breaking its one-wayness is secure under the factoring assumption. The previously reported encryption schemes using a powering function are variants of either the 4-to-1 mapping or higher n-to-1 mapping, where n > 4. In this paper, we propose an optimized powering function that is a 3-to-1 mapping using a p²q-type modulus. The one-wayness of the proposed powering function is as hard as the infeasibility of the factoring problem. We present an efficient algorithm for computing the decryption for a p²q-type modulus, which requires neither modular inversion nor division. Moreover, we construct new provably secure digital signatures as an application of the optimized functions. In order to achieve provable security in the random oracle model, we usually randomize a message using random hashing or padding. However, we have to compute the randomization again if the randomized message is a non-cubic residue element--it is inefficient for long messages. We propose an algorithm that can deterministically find the unique cubic residue element for a randomly chosen element.},
keywords={},
doi={10.1093/ietfec/e89-a.1.81},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Generalized Powering Functions and Their Application to Digital Signatures
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 81
EP - 89
AU - Hisayoshi SATO
AU - Tsuyoshi TAKAGI
AU - Satoru TEZUKA
AU - Kazuo TAKARAGI
PY - 2006
DO - 10.1093/ietfec/e89-a.1.81
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2006
AB - This paper investigates some modular powering functions suitable for cryptography. It is well known that the Rabin encryption function is a 4-to-1 mapping and breaking its one-wayness is secure under the factoring assumption. The previously reported encryption schemes using a powering function are variants of either the 4-to-1 mapping or higher n-to-1 mapping, where n > 4. In this paper, we propose an optimized powering function that is a 3-to-1 mapping using a p²q-type modulus. The one-wayness of the proposed powering function is as hard as the infeasibility of the factoring problem. We present an efficient algorithm for computing the decryption for a p²q-type modulus, which requires neither modular inversion nor division. Moreover, we construct new provably secure digital signatures as an application of the optimized functions. In order to achieve provable security in the random oracle model, we usually randomize a message using random hashing or padding. However, we have to compute the randomization again if the randomized message is a non-cubic residue element--it is inefficient for long messages. We propose an algorithm that can deterministically find the unique cubic residue element for a randomly chosen element.
ER -