Language Dependent Secure Bit Commitment

  • Toshiya Itoh
  • Yuji Ohta
  • Hiroki Shizuya
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


In this paper, we define two classes of languages, one induces opaque/transparent bit commitments and the other induces transparent/opaque bit commitments. As an application of opaque/transparent and transparent/opaque properties, we first show that if a language L induces an opaque/transparent bit commitment, then there exists a prover-practical perfect zero-knowledge proof for L, and we then show that if a language L induces a transparent/opaque bit commitment, then there exists a bounded round perfect zero-knowledge proof for L.


  1. 1.
    Brassard, G., Chaum, D., and Crépeau, C., “Minimum Disclosure Proofs of Knowledge,” J. Comput. System Sci., Vol.37, No.2, pp.156–189 (1988).zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Ben-Or, M., Goldreich, O., Goldwasser, S., Håstad, J., Kilian, J., Micali, S., and Rogaway, P., “Everything Provable is Provable in Zero-Knowledge,” Proceedings of Crypto’88, Lecture Notes in Computer Science 403, pp.37–56 (1990).Google Scholar
  3. 3.
    Boyar, J., Friedl, K., and Lund, C., “Practical Zero-Knowledge Proof: Giving Hints and Using Deficiencies,” J. Cryptology, Vol.4, No.3, pp.185–206 (1991).zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    Bellare, M., Micali, S., and Ostrovsky, R., “The (True) Complexity of Statistical Zero-Knowledge,” Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp.494–502 (1990).Google Scholar
  5. 5.
    Feige, U., Fiat, A., and Shamir, A., “Zero-Knowledge Proofs of Identity,” J. Cryptology, Vol.1, No.2, pp.77–94 (1988).zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Feige, U. and Shamir, A., “Zero-Knowledge Proofs of Knowledge in Two Rounds,” Proceedings of Crypto’89, Lecture Notes in Computer Science 435, pp.526–544 (1990).Google Scholar
  7. 7.
    Goldreich, O. and Krawczyk, H., “On the Composition of Zero-Knowledge Proof Systems,” Proceedings of ICALP’90, Lecture Notes in Computer Science 443, pp.268–282 (1990).Google Scholar
  8. 8.
    Goldwasser, S., Micali, S., and Rackoff, C., “The Knowledge Complexity of Interactive Proof Systems,” SIAM J. Comput., Vol.18, No.1, pp.186–208 (1989).zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    Goldreich, O., Micali, S., and Wigderson, A., “Proofs That Yield Nothing But Their Validity or All Languages in \( \mathcal{N}\mathcal{P} \) Have Zero-Knowledge Proof Systems,” J. Assoc. Comput. Mach., Vol.38, No.1, pp.691–729 (1991).zbMATHMathSciNetGoogle Scholar
  10. 10.
    Goldreich, O. and Oren, Y., “Definitions and Properties of Zero-Knowledge Proof Systems,” J. Cryptology, Vol.7, No.1, pp.1–32 (1994).zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    Naor, M., Ostrovsky, R., Venkatesan, R., and Yung, M., “Perfect Zero-Knowledge Arguments for \( \mathcal{N}\mathcal{P} \) Can Be Based on General Complexity Assumptions,” Proceedings of Crypto’92, Lecture Notes in Computer Science 740, pp.196–214 (1993).Google Scholar
  12. 12.
    Ostrovsky, R., “Comparison of Bit-Commitment and Oblivious Transfer Protocols when Players have Different Computing Power,” DIMACS Technical Report #90-41, pp.27–29 (1990).Google Scholar
  13. 13.
    Tompa, M. and Woll, H., “Random Self-Reducibility and Zero-Knowledge Interactive Proofs of Possession of Information,” Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, pp.472–482 (1987).Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Toshiya Itoh
    • 1
  • Yuji Ohta
    • 1
  • Hiroki Shizuya
    • 2
  1. 1.Department of Information Processing, Interdisciplinary Graduate School of Science and EngineeringTokyo Institute of TechnologyYokohamaJapan
  2. 2.Education Center for Information ProcessingTohoku UniversitySendaiJapan

Personalised recommendations