Statistical Zero-Knowledge and Efficient Reductions to MKTP
Abstract
This paper is a summary of the dissertation with the same title. In the dissertation we study the complexity of computational problems that are candidates for NP-intermediate status. In this process, we connect the comple- xity class SZK, related to zero-knowledge proofs, to the computational problem MKTP, related to algorithmic information theory. As original contributions, we highlight randomized reductions from the HIDDEN SUBGROUP PROBLEM (HSP) and other problems in computational group theory to MKTP, and statis- tical zero-knowledge proofs for decisions versions ofHSP
Keywords:
Computational Complexity, NP-intermediate, Zero-Knowledge Proofs, MKTP, Randomized Reduction, Hidden Subgroup Problem, Group Equivalence.
References
Allender, E., Buhrman, H., Kouck´y, M., van Melkebeek, D., and Ronneburger, D. (2006). Power from random strings. SIAM Journal on Computing, 35(6):1467–1493.
Allender, E., Grochow, J. A., van Melkebeek, D., Moore, C., and Morgan, A. (2018). Minimum Circuit Size, Graph Isomorphism, and Related Problems. In Karlin, A. R., editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), vo- lume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1– 20:20, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
Arora, S. and Barak, B. (2009). Computational Complexity: A Modern Approach. Cam- bridge University Press, New York, NY, USA, 1st edition.
Arvind, V. and Das, B. (2008). Szk proofs for black-box group problems. Theory of Computing Systems, 43(2):100–117.
Babai, L. and Beals, R. (1998). A Polynomial-time Theory of Black-box Groups I (ma- nuscrito).
Boppana, R. B., Hastad, J., and Zachos, S. (1987). Does co-np have short interactive proofs? Inf. Process. Lett., 25(2):127–132.
Fenner, S. A. and Zhang, Y. (2005). Quantum algorithms for a set of group theoretic problems. In Coppo, M., Lodi, E., and Pinna, G. M., editors, Theoretical Computer Science, pages 215–227, Berlin, Heidelberg. Springer Berlin Heidelberg.
Goldwasser, S., Micali, S., and Rackoff, C. (1989). The knowledge complexity of inte- ractive proof systems. SIAM J. Comput., 18(1):186–208.
Hirahara, S. and Watanabe, O. (2015). Limits of minimum circuit size problem as oracle. Electronic Colloquium on Computational Complexity (ECCC), 22:198.
Ladner, R. E. (1975). On the structure of polynomial time reducibility. J. ACM, 22(1):155–171.
Li, M. and Vit´anyi, P. (1997). An introduction to Kolmogorov complexity and its applica- tions. Springer-Verlag, 2 edition.
Murray, C. and Williams, R. (2014). On the (non) np-hardness of computing circuit complexity. Electronic Colloquium on Computational Complexity (ECCC), 21:164.
Sdroievski, N. M. (2018). Conhecimento Zero Estatıstico e Reducoes Eficientes para o Problema MKTP. Dissertacao de mestrado, Departamento de Informatica, Universidade Federal do Parana (UFPR).
Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509.
Vadhan, S. P. (1999). A Study of Statistical Zero-knowledge Proofs. PhD thesis, Massa- chusetts Institute of Technology, Cambridge, MA, USA. AAI0801528.
Allender, E., Grochow, J. A., van Melkebeek, D., Moore, C., and Morgan, A. (2018). Minimum Circuit Size, Graph Isomorphism, and Related Problems. In Karlin, A. R., editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), vo- lume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1– 20:20, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
Arora, S. and Barak, B. (2009). Computational Complexity: A Modern Approach. Cam- bridge University Press, New York, NY, USA, 1st edition.
Arvind, V. and Das, B. (2008). Szk proofs for black-box group problems. Theory of Computing Systems, 43(2):100–117.
Babai, L. and Beals, R. (1998). A Polynomial-time Theory of Black-box Groups I (ma- nuscrito).
Boppana, R. B., Hastad, J., and Zachos, S. (1987). Does co-np have short interactive proofs? Inf. Process. Lett., 25(2):127–132.
Fenner, S. A. and Zhang, Y. (2005). Quantum algorithms for a set of group theoretic problems. In Coppo, M., Lodi, E., and Pinna, G. M., editors, Theoretical Computer Science, pages 215–227, Berlin, Heidelberg. Springer Berlin Heidelberg.
Goldwasser, S., Micali, S., and Rackoff, C. (1989). The knowledge complexity of inte- ractive proof systems. SIAM J. Comput., 18(1):186–208.
Hirahara, S. and Watanabe, O. (2015). Limits of minimum circuit size problem as oracle. Electronic Colloquium on Computational Complexity (ECCC), 22:198.
Ladner, R. E. (1975). On the structure of polynomial time reducibility. J. ACM, 22(1):155–171.
Li, M. and Vit´anyi, P. (1997). An introduction to Kolmogorov complexity and its applica- tions. Springer-Verlag, 2 edition.
Murray, C. and Williams, R. (2014). On the (non) np-hardness of computing circuit complexity. Electronic Colloquium on Computational Complexity (ECCC), 21:164.
Sdroievski, N. M. (2018). Conhecimento Zero Estatıstico e Reducoes Eficientes para o Problema MKTP. Dissertacao de mestrado, Departamento de Informatica, Universidade Federal do Parana (UFPR).
Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509.
Vadhan, S. P. (1999). A Study of Statistical Zero-knowledge Proofs. PhD thesis, Massa- chusetts Institute of Technology, Cambridge, MA, USA. AAI0801528.
Published
2019-06-26
How to Cite
SDROIEVSKI, Nicollas M.; DA SILVA, Murilo V. G.; VIGNATTI, André L..
Statistical Zero-Knowledge and Efficient Reductions to MKTP. In: THESIS AND DISSERTATION CONTEST (CTD), 32. , 2019, Belém.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2019.6336.
