4-Move Perfect ZKIP for Some Promise Problems

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we consider ZKIPs for promise problems. A promise problem is a pair of predicates (Q, R). A Turning machine T solves the promise problem (Q, R) if, for every x satisfying Q(x), machine T halts and it answers "yes" iff R(x). When ¬Q(x), we do not care what T does. First, we define "promised BPP" which is a promise problem version of BPP. Then, we prove that a promise problem (Q, R) has a 3-move interactive proof system which is black-box simulation zero knowledge if and only if (Q, R)∈promised BPP. Next, we show a "4-move" perfect ZKIPs (black-box simulation) for a promise problem of Quadratic Residuosity and that of Blum Numbers under no cryptographic assumption.

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

著者

• OGATA Wakaha

  Faculty of Engineering, Himeji Institute of Technology

• KUROSAWA Kaoru

  Faculty of Engineering, Tokyo Institute of Technology

• Tsujii S

  Chuo Univ. Tokyo Jpn

• Tsujii Shigeo

  Faculty Of Science And Engineering Chuo University

• Tsujii Shigeo

  Faculty Of Engineering Tokyo Institute Of Technology

• Ogata W

  Tokyo Inst. Of Technol. Tokyo Jpn

• Ogata Wakaha

  Faculty Of Engineering Himeji Institute Of Technology

• Kurosawa Kaoru

  Faculty Of Engineering Tokyo Institute Of Technology

関連論文

• Analysis on Secret Sharing Schemes with Non-Graphical Access Structures (Special Section on Cryptography and Information Security)
• Electronic Ticket Scheme for ITS(Special Section on Cryptography and Information Security)
• Comments on the Security Proofs of Some Signature Schemes Based on Factorization(Information Security)
• New Identity-Based Blind Signature and Blind Decryption Scheme in the Standard Model
• Collision-Based Power Attack for RSA with Small Public Exponent
• Attack on Yagisawa Cryptosystem (Special Section on Cryptography and Information Security)
• Forgery Attacks on Time-Stamp, Signed PDF and X.509 Certificate
• Towards Secure and Fast Hash Functions
• General Conversion for Obtaining Strongly Existentially Unforgeable Signatures
• On Some Variations of Kurosawa-Desmedt Public-Key Encryption Scheme(Cryptography and Information Security)
• Efficient Divisible Voting Scheme(Application)(Cryptography and Information Security)
• Some new results on nonperfect secret sharing schemes
• Efficient Almost Secure 1-Round Message Transmission Schemes for 3t+1 Channels
• k out of n Oblivious Transfer without Random Oracles (Protocol) (Cryptography and Information Security)
• 4-Move Perfect ZKIP for Some Promise Problems
• Relationship between Standard Model Plaintext Awareness and Message Hiding
• A Secure Broadcast Communication Method with Short Messages (Special Section on Information Theory and Its Applications)
• Provably Secure On-Line Secret Sharing Scheme
• On Claw Free Families (Special Section on Cryptography and Information Security)
• New ElGamal Type Threshold Digital Signature Scheme (Special Section on Cryptography and Information Security)
• Authentication Codes Based on Association Schemes
• Matching Oblivious Transfer : How to Exchange Valuable Data(Special Section on Cryptography and Information Security)
• k out of n Oblivious Transfer without Random Oracles
• On the Practical Secret Sharing Scheme : Special Section on Cryptography and Information Security
• Reshufflable and Laziness Tolerant Mental Card Game Protocol (Special Section on Cryptography and Information Security)
• A Key Distribution Protocol for Mobile Communication Systems
• A Simple and Efficient Secret Sharing Scheme Secure against Cheating

もっと見る 閉じる

スポンサーリンク