Paper Info
Title
SZK Proofs for Black-Box Group Problems
Abstract
In this paper we classify several algorithmic problems in group theory in the complexity classes PZK and SZK (problems with perfect/statistical zero-knowledge proofs respectively). Prior to this, these problems were known to be in $\mbox {\rm AM}\cap \mbox {\rm coAM}$. As $\mbox {\rm PZK}\subseteq \mbox {\rm SZK}\subseteq \mbox {\rm AM}\cap \mbox {\rm coAM}$, we have a tighter upper bound for these problems. Specifically: We show that the permutation group problems Coset Intersection, Double Coset Membership, Group Conjugacy are in PZK. Further, the complements of these problems also have perfect zero knowledge proofs (in the liberal sense). We also show that permutation group isomorphism for solvable groups is in PZK. As an ingredient of this protocol, we design a randomized algorithm for sampling short presentations of solvable permutation groups. We show that the complement of all the above problems have concurrent zero knowledge proofs. We prove that the above problems for black-box groups are in SZK. Finally, we also show that some of the problems have SZK protocols with efficient provers in the sense of Micciancio and Vadhan (Lecture Notes in Comput. Sci. 2729, 282–298, 2003).
Year
DOI
Venue
2008
10.1007/s00224-007-9028-3
Theory of Computing Systems \/ Mathematical Systems Theory
Keywords
Field
DocType
Permutation Group,Solvable Group,Double Coset,Short Presentation,Composition Series
Discrete mathematics,Composition series,Combinatorics,Computational problem,Upper and lower bounds,Permutation group,Mathematical proof,Solvable group,Double coset,Time complexity,Mathematics
Journal
Volume
Issue
ISSN
43
2
1432-4350
ISBN
Citations 
PageRank 
3-540-34166-8
2
0.36
References 
Authors
15
2
Name
Order
Citations
PageRank
V. Arvind112212.03
Bireswar Das26610.61