×

zbMATH — the first resource for mathematics

Bit commitment using pseudorandomness. (English) Zbl 0731.68033
Summary: We show how a pseudorandom generator can provide a bit-commitment protocol. We also analyze the number of bits communicated when parties commit to many bits simultaneously, and show that the assumption of the existence of pseudorandom generators suffices to assure amortized 0(1) bits of communication per bit commitment.

MSC:
68P25 Data encryption (aspects in computer science)
94A60 Cryptography
65C10 Random number generation in numerical analysis
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M. Blum, Coin flipping by telephone, Proc. 24th IEEE Campcon, 1982, pp. 133-137.
[2] Blum, M.; Micali, S., How to generate cryptographically strong sequences of pseudorandom bits, SIAM Journal on Computing, Vol. 13, 850-864 (1984) · Zbl 0547.68046
[3] Brassard, G.; Chaum, D.; Crépeau, C., Minimum disclosure proofs of knowledge, Journal of Computer and System Sciences, Vol. 37, 156-189 (1988) · Zbl 0656.68109
[4] D. Chaum, I. Damgård, and J. van de Graaf, Multiparty computations ensuring secrecy of each party’s input and correctness of the output, Proc. Crypto ’87, p. 462. · Zbl 0672.94004
[5] A. Fiat and A. Shamir, How to prove yourself, Proc. Crypto ’86, pp. 641-654. · Zbl 0636.94012
[6] Goldreich, O.; Goldwasser, S.; Micali, M., How to construct random functions, Journal of the ACM, Vol. 33, 792-807 (1986) · Zbl 0596.65002
[7] O. Goldreich, M. Micali, and A. Wigderson, Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, Proc. 27th IEEE Symposium on Foundations of Computer Science, 1986, pp. 174-187.
[8] O. Goldreich, M. Micali, and A. Wigderson, How to play any mental game, Proc. 19th ACM Symposium on Theory of Computing, 1987, pp. 218-229.
[9] J. Hastad, Pseudorandom generators under uniform assumptions, Proc. 22nd ACM Symposium on Theory of Computing, 1990, pp. 395-404.
[10] I. Impagliazzo, L. Levin, and M. Luby, Pseudorandom generation from one-way functions, Proc. 21st ACM Symposium on Theory of Computing, 1989, pp. 12-24.
[11] I. Impagliazzo and M. Luby, One-way functions are essential to computational based cryptography, Proc. 30th IEEE Symposium on Foundations of Computer Science, 1989, pp. 230-235.
[12] R. Impagliazzo and M. Yung, Direct zero-knowledge protocols, Proc. Crypto ’87, pp. 40-51.
[13] Justesen, J., A class of constructive asymptotically good algebraic codes, IEEE Transactions on Information Theory, Vol. 18, 652-656 (1972) · Zbl 0256.94008
[14] J. Kilian, S. Micali, and R. Ostrovsky, Minimum resource zero-knowledge proofs, Proc. 30th IEEE Symposium on Foundations of Computer Science, 1989, pp. 474-479.
[15] A. C. Yao, Theory and applications of trapdoor functions, Proc. 23rd Symposium on Foundations of Computer Science, 1982, pp. 80-91.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.