On Possibility of Universally Composable Commitments Based on Noisy Channels
Resumo
Universally Composable (UC) Commitment is a strong notion that guarantees security even when the commitment protocol is composed with arbitrary protocols running many of their copies in parallel. It is impossible to implement a protocol that realizes UC Commitment without set-up assumptions. However, it has been implemented using such assumptions as common reference string, certified public keys and random oracles. In this paper we prove that the existence of a binary symmetric channel between the parties makes possible the accomplishment of UC Commitment.
Referências
R. Ahlswede, I. Csiszár, Common Randomness in Information Theory and Cryptography – Part I: Secret Sharing, IEEE Trans. Inf. Theory, vol. 39, no. 4, pp. 1121–1132, 1993.
B. Barak, R. Canetti, J. B. Nielsen, R. Pass, Universally Composable Protocols with Relaxed Set-Up Assumptions, 36th FOCS, pp.186-195, 2004.
C. H. Bernett, G. Brassard, C. Crépeau and U. M. Maurer, Generalized Privacy Amplification, IEEE Transaction on Information Theory, Volume 41, Number 6, November 1995, pp. 1915-1923.
C. H. Bernett, G. Brassard, C. Crépeau and M. H. Skubiszewska, Practical Quantum Oblivious Transfer, In Advances in Cryptology: Proceedings of Crypto ‘91, Vol. 576, page 351-366, 1992.
C. H. Bennett , G. Brassard , J. Robert, Privacy Amplification by Public Discussion, SIAM Journal on Computing, v.17, n.2, p.210-229, April 1988.
G. Brassard, D. Chaum and C. Crépeau, Minimum Disclosure Proofs of Knowledge, JCSS, Vol. 37, No. 2, pages 156-189, 1988.
G. Brassard, C. Crépeau, R. Jotza and D. Langlois, A Quantum Bit Commitment Scheme Provably Unbreakable by Both Parties. Proceeding of the 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 362-371.
R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols. 2005, Available at http://eprint.iacr.org/2000/067, Extended Abstract appeared in proceedings of the 42nd Symposium on Foundations of Computer Science (FOCS), 2001.
R. Canetti and M. Fischlin, Universally Composable Commitments. In Advances in Cryptology - Crypto 2001, Volume 2139, pages 19-40, 2001.
R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai, Universally Composable Two Party and Multi-party Secure Computation, 34th STOC, pp. 494-503, 2002.
J. L. Carter and M. N.Wegman, Universal Classes of Hash Functions, Journal of Computer and System Sciences, Vol. 18, pp. 143-154, 1979.
C. Crépeau, J. Kilian, “Achieving Oblivious Transfer Using Weakened Security Assumptions”, Proc. 29th FOCS, pp. 42–52, 1988, IEEE.
C. Crépeau. Efficient Cryptographic Protocols Based on Noisy Channels. Advances in Cryptology: Proceedings of Eurocrypt ‘97 , pages 306-317, 1997.
H. Chernoff, A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on The Sum of Observations, Ann. Math. Statistics, vol. 23, pp. 493–507, 1952.
T. Cover, J. Thomas, Elements of Information Theory. Wiley. 1991.
I. Damgard, S. Fehr, K. Morozov, L. Salvail: Unfair Noisy Channels and Oblivious Transfer. TCC 2004: 355-373
I. Damgard, J. Groth, Non Interactive and Reusable Non-malleable Commitment Schemes, 34th STOC, pp. 426-437, 2003.
I. Damgard, J. Kilian, L. Salvail, “On the (Im)possibility of Basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions”, Advances in Cryptology: EUROCRYPT 1999, pp. 56–73, Springer 1999.
I. Damgard and J. B. Nielsen, Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor, CRYPTO 2002, pp.581-596, 2002.
Y. Dodis, R. Pass and S. Walfish. Fully Simulatable Multiparty Computation. Manuscript, 2005.
S. Even, O. Goldreich, A. Lempel. A Randomized Protocol for Signing Contracts. Communications of the ACM 28(6), 637-647, 1985.
O. Goldreich, Foundations of Cryptography : Volume 1 - Basic Tools, Cambridge University Press, 2001.
O. Goldreich, S. Micali and A. Wigderson, How to Play Any Mental Game or a Completeness Theorem for Protocols with Honest Majority, STOC ’87.
O. Goldreich, S. Micali and A.Wigderson, Proofs that Yield Nothing but their Validity or All Languages in NP have Zero-Knowledge Proof System, J. ACM38(3): 691-729. 1991.
S. Goldwasser, S. Micali and C. Rackoff, The Knowledge Complexity of Interactive Proof Systems, SIAM Journal on Comput., Vol. 18, No. 1, 1989, pp. 186-208.
V. Guruswami, P. Indyk, Efficiently Decodable Low-Rate Codes Meeting Gilbert Varshamov Bound, invited to the 41st Annual Allerton Conference on Communication, Control and Computing, 2003.
D. Hofheinz and J.Müller-Quade, Universally Composable Commitments Using Random Oracles, Theory of Cryptography Conference (TCC), LNCS 2951 pp, 58- 74, 2004.
T. Holenstein, Strengthening Key Agreement Using Hard-core Sets, PhD thesis, Swiss Federal Institute of Technology (ETH) Zurich.
T. Holenstein and R. Renner, On the Randomness of Independent Experiments, http://arxiv.org/abs/cs.IT/0608007.
H. Imai, A. C. A. Nascimento, A. Winter, Commitment Capacity of Discrete Memoryless Channels, IMA Int. Conf. 2003: 35-51
R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random Generation From Oneway Functions, Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, p.12-24, May 14-17, 1989.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.
U. Maurer, Protocols for Secret Key Agreement by Public Discussion Based on Common Information, CRYPTO 1992, pp. 461–470, Springer 1993., Secret Key Agreement by Public Discussion,IEEE Trans. Inf. Theory, vol. 39, no. 3, pp. 733–742, 1993.
M. Prabhakaran and A. Sahai, New Notions of Security: Achieving Universal Composability without Trusted Setup, In Proc. of STOC, 2004.
A. D. Wyner, The Wire Tap Channel, Bell System Tech. Journal, vol. 54, pp. 1355–1387, 1975.
B. Barak, R. Canetti, J. B. Nielsen, R. Pass, Universally Composable Protocols with Relaxed Set-Up Assumptions, 36th FOCS, pp.186-195, 2004.
C. H. Bernett, G. Brassard, C. Crépeau and U. M. Maurer, Generalized Privacy Amplification, IEEE Transaction on Information Theory, Volume 41, Number 6, November 1995, pp. 1915-1923.
C. H. Bernett, G. Brassard, C. Crépeau and M. H. Skubiszewska, Practical Quantum Oblivious Transfer, In Advances in Cryptology: Proceedings of Crypto ‘91, Vol. 576, page 351-366, 1992.
C. H. Bennett , G. Brassard , J. Robert, Privacy Amplification by Public Discussion, SIAM Journal on Computing, v.17, n.2, p.210-229, April 1988.
G. Brassard, D. Chaum and C. Crépeau, Minimum Disclosure Proofs of Knowledge, JCSS, Vol. 37, No. 2, pages 156-189, 1988.
G. Brassard, C. Crépeau, R. Jotza and D. Langlois, A Quantum Bit Commitment Scheme Provably Unbreakable by Both Parties. Proceeding of the 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 362-371.
R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols. 2005, Available at http://eprint.iacr.org/2000/067, Extended Abstract appeared in proceedings of the 42nd Symposium on Foundations of Computer Science (FOCS), 2001.
R. Canetti and M. Fischlin, Universally Composable Commitments. In Advances in Cryptology - Crypto 2001, Volume 2139, pages 19-40, 2001.
R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai, Universally Composable Two Party and Multi-party Secure Computation, 34th STOC, pp. 494-503, 2002.
J. L. Carter and M. N.Wegman, Universal Classes of Hash Functions, Journal of Computer and System Sciences, Vol. 18, pp. 143-154, 1979.
C. Crépeau, J. Kilian, “Achieving Oblivious Transfer Using Weakened Security Assumptions”, Proc. 29th FOCS, pp. 42–52, 1988, IEEE.
C. Crépeau. Efficient Cryptographic Protocols Based on Noisy Channels. Advances in Cryptology: Proceedings of Eurocrypt ‘97 , pages 306-317, 1997.
H. Chernoff, A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on The Sum of Observations, Ann. Math. Statistics, vol. 23, pp. 493–507, 1952.
T. Cover, J. Thomas, Elements of Information Theory. Wiley. 1991.
I. Damgard, S. Fehr, K. Morozov, L. Salvail: Unfair Noisy Channels and Oblivious Transfer. TCC 2004: 355-373
I. Damgard, J. Groth, Non Interactive and Reusable Non-malleable Commitment Schemes, 34th STOC, pp. 426-437, 2003.
I. Damgard, J. Kilian, L. Salvail, “On the (Im)possibility of Basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions”, Advances in Cryptology: EUROCRYPT 1999, pp. 56–73, Springer 1999.
I. Damgard and J. B. Nielsen, Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor, CRYPTO 2002, pp.581-596, 2002.
Y. Dodis, R. Pass and S. Walfish. Fully Simulatable Multiparty Computation. Manuscript, 2005.
S. Even, O. Goldreich, A. Lempel. A Randomized Protocol for Signing Contracts. Communications of the ACM 28(6), 637-647, 1985.
O. Goldreich, Foundations of Cryptography : Volume 1 - Basic Tools, Cambridge University Press, 2001.
O. Goldreich, S. Micali and A. Wigderson, How to Play Any Mental Game or a Completeness Theorem for Protocols with Honest Majority, STOC ’87.
O. Goldreich, S. Micali and A.Wigderson, Proofs that Yield Nothing but their Validity or All Languages in NP have Zero-Knowledge Proof System, J. ACM38(3): 691-729. 1991.
S. Goldwasser, S. Micali and C. Rackoff, The Knowledge Complexity of Interactive Proof Systems, SIAM Journal on Comput., Vol. 18, No. 1, 1989, pp. 186-208.
V. Guruswami, P. Indyk, Efficiently Decodable Low-Rate Codes Meeting Gilbert Varshamov Bound, invited to the 41st Annual Allerton Conference on Communication, Control and Computing, 2003.
D. Hofheinz and J.Müller-Quade, Universally Composable Commitments Using Random Oracles, Theory of Cryptography Conference (TCC), LNCS 2951 pp, 58- 74, 2004.
T. Holenstein, Strengthening Key Agreement Using Hard-core Sets, PhD thesis, Swiss Federal Institute of Technology (ETH) Zurich.
T. Holenstein and R. Renner, On the Randomness of Independent Experiments, http://arxiv.org/abs/cs.IT/0608007.
H. Imai, A. C. A. Nascimento, A. Winter, Commitment Capacity of Discrete Memoryless Channels, IMA Int. Conf. 2003: 35-51
R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random Generation From Oneway Functions, Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, p.12-24, May 14-17, 1989.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.
U. Maurer, Protocols for Secret Key Agreement by Public Discussion Based on Common Information, CRYPTO 1992, pp. 461–470, Springer 1993., Secret Key Agreement by Public Discussion,IEEE Trans. Inf. Theory, vol. 39, no. 3, pp. 733–742, 1993.
M. Prabhakaran and A. Sahai, New Notions of Security: Achieving Universal Composability without Trusted Setup, In Proc. of STOC, 2004.
A. D. Wyner, The Wire Tap Channel, Bell System Tech. Journal, vol. 54, pp. 1355–1387, 1975.
Publicado
01/09/2008
Como Citar
DOWSLEY, Rafael; MÜLLER-QUADE, Jörn; NASCIMENTO, Anderson C. A..
On Possibility of Universally Composable Commitments Based on Noisy Channels. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 8. , 2008, Gramado.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2008
.
p. 103-114.
DOI: https://doi.org/10.5753/sbseg.2008.20891.
