Published in Volume XXIII, Issue 2, 2013, pages 191-228, doi: 10.7561/SACS.2013.2.191
Authors: I. Boureanu, S. Vaudenay
Abstract
Based on tamper-evident devices, i.e., a type of distinguishable, sealed envelopes, we put forward weak bit-commitment protocols which are UC-secure. These commitments are weak in that it is legitimate that a party could cheat. Unlike in several similar lines of work, in our case, the party is not obliged to cheat, but he has ability to cheat if and when needed. The empowered party is the sender, i.e., the protocols are also sender-strong.
Full Text (PDF)References
[1] D. Beaver. Adaptive Zero Knowledge and Computational Equivocation (Extended Abstract). In The 28th Annual ACM Symposium on Theory of Computing (STOC), pages 629–638, 1996. http://dx.doi.org/10.1145/237814.238014
[2] M. Bellare, M. Fischlin, S. Goldwasser, and S. Micali. Identification protocols secure against reset attacks. In Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, EUROCRYPT ’01, volume 2045 of Lecture Notes in Computer Science, pages 495–511. Springer-Verlag, 2001. http://dx.doi.org/10.1007/3-540-44987-6_30
[3] I. Boureanu and S. Vaudenay. Several weak bit-commitments using seal-once tamper-evident devices. In Tsuyoshi Takagi, Guilin Wang, Zhiguang Qin, Shaoquan Jiang, and Yong Yu, editors, Provable Security – 6th International Conference – ProvSec, volume 7496 of Lecture Notes in Computer Science, pages 70–87. Springer, 2012. http://dx.doi.org/10.1007/978-3-642-33272-2_6
[4] I. Boureanu and S. Vaudenay. Input-aware equivocable com- mitments and UC-secure commitments with atomic exchanges. In The 7th International Conference on Provable Security (ProvSec ), volume 8209 of Lecture Notes in Computer Science, pages 121–138. Springer Berlin Heidelberg, Melaka, Malaysia, October 2013. http://dx.doi.org/10.1007/978-3-642-41227-1_7
[5]G. Brassard, D. Chaum, and C. Crépeau. Minimum Disclosure Proofs of Knowledge. Journal of Computer Systems Science, 37:156–189, October 1988. http://dx.doi.org/10.1016/0022-0000(88)90005-0
[6] C. Crépeau. Efficient Cryptographic Protocols Based on Noisy Channels. In Advances in Cryptology, Proceedings of the 16th Annual International Conference on Theory and Application of Cryptographic Techniques – EUROCRYPT, volume 1233 of Lecture Notes of Computer Science, pages 306–317, Berlin, Heidelberg, 1997. Springer-Verlag. http://dx.doi.org/10.1007/3-540-69053-0_21
[7] R. Canetti. A Unified Framework for Analyzing Security of Protocols. Electronic Colloquium on Computational Complexity (ECCC), 8(16), 2001.
[8] R. Canetti. Universally Composable Signature, Certification, and Authentication. In Proceedings of the 17th IEEE workshop on Computer Security Foundations, pages 219–239, Washington, DC, USA, 2004. IEEE Computer Society. http://dx.doi.org/10.1109/CSFW.2004.24
[9] R. Canetti, Y. Dodis, R. Pass, and S. Walfish. Universally Composable Security with Global Setup. Cryptology ePrint Archive, Report 2006/432, 2006. http://eprint.iacr.org/
[10] N. Chandran, V. Goyal, and A. Sahai. New Constructions for UC Secure Computation Using Tamper-Proof Hardware. In Advances in Cryptology, Proceedings of the 27th Annual International Conference on Theory and Application of Cryptographic Techniques – EUROCRYPT, volume 4965 of Lecture Notes in Computer Science, pages 545–562, 2008. http://dx.doi.org/10.1007/978-3-540-78967-3_31
[11] C. Chin-Chen and C. Ya-Fen. Efficient Anonymous Auction Protocols with Freewheeling Bids. Computers & Security, 22(8):728–734, 2003. http://dx.doi.org/10.1016/S0167-4048(03)00013-0
[12] I. Damgård. On the existence of bit commitment schemes and zero- knowledge proofs. In Advances in Cryptology, Proceedings of the 9th Annual International Cryptology Conference, volume 435 of Lecture Notes in Computer Science, pages 17–27, New York, NY, USA, 1989. Springer-Verlag New York, Inc. http://dx.doi.org/10.1007/0-387-34805-0_3
[13] C. Dwork, M. Naor, and A. Sahai. Concurrent zero- knowledge. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, STOC ’98, pages 409–418, New York, NY, USA, 1998. ACM. http://dx.doi.org/10.1145/276698.276853
[14] G. Dane. The Implementation of an Auction Protocol over Anonymous Networks. http://research.microsoft.com/en-us/um/people/gdane/papers/partiiproj-anonauctions.pdf, 2000.
[15] R. Gennaro. Multi-trapdoor commitments and their applications to proofs of knowledge secure under concurrent man-in-the-middle attacks. In Matthew K. Franklin, editor, CRYPTO, volume 3152 of Lecture Notes in Computer Science, pages 220–236. Springer, 2004. http://dx.doi.org/10.1007/978-3-540-28628-8_14
[16] V. Goyal, Y. Ishai, A. Sahai, R. Venkatesan, and A. Wadia. Founding Cryptography on Tamper-Proof Hardware Tokens. In Proceedings of the 7th Theory of Cryptography Conference, TCC 2010, volume 5978 of Lecture Notes in Computer Science, pages 308–326, 2010. http://dx.doi.org/10.1007/978-3-642-11799-2_19
[17] J. Katz. Universally Composable Multi-party Computation Using Tamper-Proof Hardware. In Theory and Application of Cryptographic Techniques, volume 4515 of Lecture Notes in Computer Science, pages 115–128, 2007. http://dx.doi.org/10.1007/978-3-540-72540-4_7
[18] H. Kikuchi, M. Harkavy, and J.D. Tygar. Multi-round Anonymous Auction Protocols. In Proceedings of the 1st IEEE Workshop on Dependable and Real-Time E-Commerce Systems, pages 62–69. Springer- Verlag, 1998.
[19] P. Mateus and S. Vaudenay. On Tamper-Resistance from a Theoretical Viewpoint. In Proceedings of the 11th International Workshop on Cryptographic Hardware and Embedded Systems(CHES), volume 5747 of Lecture Notes in Computer Science, pages 411–428. Springer, 2009. http://dx.doi.org/10.1007/978-3-642-04138-9_29
[20] T. Moran and M. Naor. Basing Cryptographic Protocols on Tamper- Evident Seals. In L. Caires et al., editor, Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), volume 3580 of Lecture Notes in Computer Science, pages 285–297. Springer-Verlag, Jul 2005. http://dx.doi.org/10.1007/11523468_24
[21] T. Moran and M. Naor. Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol. In S. Vaudenay, editor, Advances in Cryptology, Proceedings of the 25th Annual In- ternational Conference on Theory and Application of Cryptographic Techniques – EUROCRYPT, volume 4004 of Lecture Notes in Computer Science, pages 88–108. Springer Berlin / Heidelberg, May 2006. http://dx.doi.org/10.1007/11761679_7
[22] T. Moran and M. Naor. Basing Cryptographic Protocols on Tamper- Evident Seals. Theoretical Computer Science, 411:1283–1310, March 2010. http://dx.doi.org/10.1016/j.tcs.2009.10.023
[23] T. Moran and G. Segev. David and Goliath Commitments: UC Computation for Asymmetric Parties Using Tamper-Proof Hardware. In Proceedings of the 27th Annual International Conference on the Theory and Application of Cryptographic Techniques, volume 4965 of Lecture Notes in Computer Science, pages 527–544, 2008. http://dx.doi.org/10.1007/978-3-540-78967-3_30
[24] M. Naor. Bit Commitment Using Pseudo-Randomness. Journal of Cryptology, 4:151–158, 1991. http://dx.doi.org/10.1007/BF00196774
[25] V. Shoup. Sequences of games: a tool for taming complexity in security proofs. manuscript, 2006. http://shoup.net/papers/games.pdf
Bibtex
@article{sacscuza:boureanu2013uaewbust,
title={UC and EUC Weak Bit-Commitments Using Seal-Once Tamper-Evidence},
author={I. Boureanu and S. Vaudenay},
journal={Scientific Annals of Computer Science},
volume={23},
number={2},
organization={``A.I. Cuza'' University, Iasi, Romania},
year={2013},
pages={191--228},
doi={10.7561/SACS.2013.2.191},
publisher={``A.I. Cuza'' University Press}
}