A Group-Theoretic Interface to Random Self-Reducibility

Hiroki SHIZUYA; Toshiya ITOH

A Group-Theoretic Interface to Random Self-Reducibility

Hiroki SHIZUYA, Toshiya ITOH

Full Text Views

0

Share
Cite this

Summary :

It was proven by Tompa and Woll that some specific random self-reducible problems have perfect zero-knowledge interactive proofs. In this paper, in order to determine a concrete set of random self-reducible problems, we consider a general problem of inverting a surjection from a finite group onto a finite set, and explore its random self-reducibility. The main result shows that there exist group-theoretic conditions for the random self-reducibility, and that any such random self-reducible problem has a perfect zero-knowledge interactive proof. By this result, some classes of random self-reducible problems are defined, and the inclusion relations among them are consequently clarified.

Publication: IEICE TRANSACTIONS on transactions Vol.E73-E No.7 pp.1087-1091

Publication Date: 1990/07/25

Publicized

Online ISSN

DOI

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

Category: Authentication Techniques

Authors

Hiroki SHIZUYA
Toshiya ITOH

Keyword

Cite this

Copy

Hiroki SHIZUYA, Toshiya ITOH, "A Group-Theoretic Interface to Random Self-Reducibility" in IEICE TRANSACTIONS on transactions, vol. E73-E, no. 7, pp. 1087-1091, July 1990, doi: .
Abstract: It was proven by Tompa and Woll that some specific random self-reducible problems have perfect zero-knowledge interactive proofs. In this paper, in order to determine a concrete set of random self-reducible problems, we consider a general problem of inverting a surjection from a finite group onto a finite set, and explore its random self-reducibility. The main result shows that there exist group-theoretic conditions for the random self-reducibility, and that any such random self-reducible problem has a perfect zero-knowledge interactive proof. By this result, some classes of random self-reducible problems are defined, and the inclusion relations among them are consequently clarified.
URL: https://globals.ieice.org/en_transactions/transactions/10.1587/e73-e_7_1087/_p

Copy

@ARTICLE{e73-e_7_1087,
author={Hiroki SHIZUYA, Toshiya ITOH, },
journal={IEICE TRANSACTIONS on transactions},
title={A Group-Theoretic Interface to Random Self-Reducibility},
year={1990},
volume={E73-E},
number={7},
pages={1087-1091},
abstract={It was proven by Tompa and Woll that some specific random self-reducible problems have perfect zero-knowledge interactive proofs. In this paper, in order to determine a concrete set of random self-reducible problems, we consider a general problem of inverting a surjection from a finite group onto a finite set, and explore its random self-reducibility. The main result shows that there exist group-theoretic conditions for the random self-reducibility, and that any such random self-reducible problem has a perfect zero-knowledge interactive proof. By this result, some classes of random self-reducible problems are defined, and the inclusion relations among them are consequently clarified.},
keywords={},
doi={},
ISSN={},
month={July},}

Copy

TY - JOUR
TI - A Group-Theoretic Interface to Random Self-Reducibility
T2 - IEICE TRANSACTIONS on transactions
SP - 1087
EP - 1091
AU - Hiroki SHIZUYA
AU - Toshiya ITOH
PY - 1990
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E73-E
IS - 7
JA - IEICE TRANSACTIONS on transactions
Y1 - July 1990
AB - It was proven by Tompa and Woll that some specific random self-reducible problems have perfect zero-knowledge interactive proofs. In this paper, in order to determine a concrete set of random self-reducible problems, we consider a general problem of inverting a surjection from a finite group onto a finite set, and explore its random self-reducibility. The main result shows that there exist group-theoretic conditions for the random self-reducibility, and that any such random self-reducible problem has a perfect zero-knowledge interactive proof. By this result, some classes of random self-reducible problems are defined, and the inclusion relations among them are consequently clarified.
ER -