## Abstract

In this paper, we show that without any unproven assumption, there exists a 'four' move blackbox simulation perfect zero-knowledge interactive proof system of computational ability for any random self-reducible relation R whose domain is in B P P, and that without any unproven assumption, there exists a 'four' move blackbox simulation perfect zero-knowledge interactive proof system of knowledge on the prime factorization. These results are optimal in the light of the round complexity, because it is shown that if a relation R has a three move blackbox simulation (perfect) zero-knowledge interactive proof system of computational ability (or of knowledge), then there exists a probabilistic polynomial time algorithm that on input x ε {0, 1}, outputs y such that (x,y) ε R with overwhelming probability if x ε dom R, and outputs '⊥' with probability 1 if x ε dom R.

Original language | English |
---|---|

Pages (from-to) | 1225-1233 |

Number of pages | 9 |

Journal | IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences |

Volume | E76-A |

Issue number | 7 |

Publication status | Published - Jul 1993 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Signal Processing
- Applied Mathematics
- Electrical and Electronic Engineering
- Computer Graphics and Computer-Aided Design