On the Complexity of Composite Numbers (Special Section on Cryptography and Information Security)

スポンサーリンク

概要

• 論文の詳細を見る

• Given an integer N, it is easy to determine whether or not N is prime, because a set of primes is in ZPP. Then given a composite number N, is it easy to determine whether or not N is of a specified form? In this paper, we consider a subset of odd composite numbers +1MOD4 (resp. +3MOD4), which is a subset of odd composite numbers consisting of prime factors congruent to 1 (resp. 3) modulo 4, and show that (1) there exists a four move (blackbox simulation) perfect ZKIP for the complement of +1MOD4 without any unproven assumption; (2) there exists a five move (blackbox simulation) perfect ZKIP for +1MOD4 without any unproven assumption; (3) there exists a four move (blackbox simulation) perfect ZKIP for +3MOD4 without any unproven assumption; and (4) there exists a five move (blackbox simulation) statistical ZKIP for the complement of +3MOD4 without any unproven assumption. To the best of our knowledge, these are the first results for a language L that seems to be not random self-reducible but has a constant move blackbox simulation perfect or statistical ZKIP for L and L^^-without any unproven assumption.

• 社団法人電子情報通信学会の論文
• 1993-01-25

著者

• Itoh Toshiya

  The Interdisciplinary Graduate School Of Science And Engineering

• Itoh Toshiya

  The Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of Technology

• Horikawa K

  Ntt Information Sharing Platform Lab. Musashino‐shi Jpn

• Horikawa Kenji

  the Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology

• Horikawa Kenji

  The Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of Technology

関連論文

• Practical Consequences of the Discrepancy between Zero-Knowledge Protocols and Their Parallel Execution (Special Section on Cryptography and Information Security)
• Constant Round Perfect ZKIP of Computational Ability
• On the Complexity of Composite Numbers (Special Section on Cryptography and Information Security)
• On the Complexity of Constant Round ZKIP of Possession of Knowledge (Special Section on Cryptography and Information Security)

スポンサーリンク