In this article, we introduce a Prover–Verifier model for analysing the computational complexity of a class of constraint satisfaction problems (CSPs) termed boolean binary constraint satisfaction problems (BBCSPs). BBCSPs represent an extremely general class of CSPs and find applications in a wide variety of domains including constraint programming, puzzle solving and program testing. The constraints in a BBCSP permit the combination of multiple theories as opposed to traditional constraint systems in which all constraints belong to the same theory. We establish that each instance of a BBCSP admits a coin-flipping Turing machine that halts in time polynomial in the size of the input. Furthermore, the algorithm is oblivious in that it never sees more than one constraint at a time. The prover, P, in the Prover–Verifier model is endowed with very limited powers. In particular, it has no memory and it can only pose restricted queries to the verifier. The verifier, on the other hand, is both omniscient in that it is cognisant of all the problem details and insincere in that it does not have to decide a priori on the intended proof. However, the verifier must stay consistent in its responses, i.e. it cannot rule out a certain possibility in one response to a query from the prover and then rule in the same possibility in response to a subsequent query. We note that the combination of the resources required by the prover and the type of certificate demanded of the verifier, determine the resources required by an algorithm. Inasmuch as our provers will be memoryless and our verifiers will be asked for extremely simple certificates, our work establishes the existence of a simple, randomised algorithm for BBCSPs. Our model itself serves as a basis for the design of zero-knowledge machine learning algorithms in that the prover ends up learning the proof desired by the verifier. Likewise, our work finds applications in the domain of certifying algorithm design, wherein the goal is to provide a proof of correctness of the algorithm on the input instance by providing an easily checkable certificate.
Learning is a central task in computer science, and there are various formalisms for capturing the notion. One important model studied in computational learning theory is the PAC model of Valiant (CACM 1984). On the other hand, in cryptography the notion of "learning nothing'' is often modelled by the simulation paradigm: in an interactive protocol, a party learns nothing if it can produce a transcript of the protocol by itself that is indistinguishable from what it gets by interacting with other parties. The most famous example of this paradigm is zero knowledge proofs, introduced by Goldwasser, Micali, and Rackoff (SICOMP 1989). Applebaum et al. (FOCS 2008) observed that a theorem of Ostrovsky and Wigderson (ISTCS 1993) combined with the transformation of one-way functions to pseudo-random functions (Hastad et al. SICOMP 1999, Goldreich et al. J. ACM 1986) implies that if there exist non-trivial languages with zero-knowledge arguments, then no efficient algorithm can PAC learn polynomial-size circuits. They also prove a weak reverse implication, that if a certain non-standard learning task is hard, then zero knowledge is non-trivial. This motivates the question we explore here: can one prove that hardness of PAC learning is equivalent to non-triviality of zero-knowledge? We show that this statement cannot be proven via the following techniques: 1. Relativizing techniques: there exists an oracle relative to which learning polynomial-size circuits is hard and yet the class of languages with zero knowledge arguments is trivial. 2. Semi-black-box techniques: if there is a black-box construction of a zero-knowledge argument for an NP-complete language (possibly with a non-black-box security reduction) based on hardness of PAC learning, then NP has statistical zero knowledge proofs, namely NP is contained in SZK. Under the standard conjecture that NP is not contained in SZK, our results imply that most standard techniques do not suffice to prove the equivalence between the non-triviality of zero knowledge and the hardness of PAC learning. Our results hold even when considering non-uniform hardness of PAC learning with membership queries. In addition, our technique relies on a new kind of separating oracle that may be of independent interest.
We consider the question of whether P ne NP implies that there exists some concept class that is efficientlyrepresentable but is still hard to learn in the PAC model of Valiant (CACM '84), where the learner is allowed to output any efficient hypothesis approximating the concept, including an "improper" hypothesis that is not itself in the concept class. We show that unless the polynomial hierarchy collapses, such a statement cannot be proven via a large class of reductions including Karp reductions, truth-table reductions, and a restricted form of non-adaptive Turing reductions. Also, a proof that uses a Turing reduction of constant levels of adaptivity would imply an important consequence in cryptography as it yields a transformation from any average-case hard problem in NP to a one-way function. Our results hold even in the stronger model of agnostic learning. These results are obtained by showing that lower bounds for improper learning are intimately related to the complexity of zero-knowledge arguments and to the existence of weak cryptographic primitives. In particular, we prove that if alanguage L reduces to the task of improper learning of circuits, then, depending on the type of the reduction in use, either (1) L has a statistical zero-knowledge argument system, or (2) the worst-case hardness of L implies the existence of a weak variant of one-way functions defined by Ostrovsky-Wigderson (ISTCS '93). Interestingly, we observe that the converse implication also holds. Namely, if (1) or (2) hold then the intractability of L implies that improper learning is hard.
We prove a number of general theorems about CZK, the class of problems possessing computational zero knowledge proofs. Our results are unconditional, in contrast to most previous works on CZK which rely on the assumption that one-way functions exist. We establish several new characterizations of CZK, and use these characterizations to prove results such as: 1) Honest-verifier CZK equals general CZK. 2) Public-coin CZK equals private-coin CZK. 3) CZK is closed under union (and more generally, "monotone formula closure"). 4) CZK with imperfect completeness equals CZK with perfect completeness. 5) Any problem in CZK /spl cap/ NP can be proven in computational zero knowledge by a BPP/sup NP/ prover. 6) CZK with black-box simulators equals CZK with general, non-black-box simulators. The above equalities refer to the resulting class of problems (and do not necessarily preserve other efficiency measures such as round complexity). Our approach is to combine the conditional techniques previously used in the study of CZK with the unconditional techniques developed in the study of SZK, the class of problems possessing statistical zero knowledge proofs. To enable this combination, we prove that every problem in CZK can be decomposed into a problem in SZK together with a set of instances from which a one-way function can be constructed.
The nature of zero-knowledge is re-examined and the evidence for the following belief is shown: the classic simulation based definitions of zero- knowledge (simulation zero-knowledge) may be somewhat too strong to include some “nice” protocols in which the malicious verifier seems to learn nothing but we do not know how to construct a zero-knowledge simulator for it. To overcome this problem a new relaxation of zero-knowledge, reduction zero-knowledge, is introduced. It is shown that reduction zero- knowledge just lies between simulation zero-knowledge and witness indistinguishability. Under the assumption of existence of one-way permutations a 4-round public-coin reduction zero-knowledge proof system for NP is presented and in practice this protocol works in 3 rounds since the first verifier's message can be fixed once and for all.
We consider which aspects of the two prover model are necessary for their striking language recognition and zero-knowledge capabilities. We approach this question by looking at an alternative, more symmetric model which we call the double verifier model. We find that in this model the shared randomness of the verifiers is key to the language recognition power: if the verifiers don't share randomness the power is PSPACE; otherwise it is MIP=NEXPTIME. We find that the shared randomness of the provers is necessary for zero-knowledge: if the provers don't share randomness, statistical zero-knowledge is only possible for languages in BPP/sup NP/; else it is possible for all of NEXPTIME. These results have immediate implications for the standard two-prover model. We see that correlations between the verifier's queries is crucial for the language recognition power of two prover proofs. In particular, the natural analog of IP=AM does not hold in the two-prover model unless NEXPTIME=PSPACE. Similarly, we see that shared randomness, or correlation of the provers answers, is necessary for the statistical zero-knowledge of two prover proofs.>
We consider the problem of constructing Concurrent Zero Knowledge Proofs [6], in which the fascinating and useful "zero knowledge" property is guaranteed even in situations where multiple concurrent proof sessions are executed with many colluding dishonest verifiers. Canetti et al. [3] show that blackbox concurrent zero knowledge proofs for non-trivial languages require #4 k) rounds where k is the security parameter. Till now the best known upper bound on the number of rounds for NP languages was #(log k), due to Kilian and Petrank [16]. We establish an upper bound of #(log k) on the number of rounds for NP languages, thereby closing the gap between the upper and lower bounds, up to a #(log log k) factor.
A proof is concurrent zero-knowledge if it remains zero-knowledge when run in an asynchronous environment, such as the Internet. It is known that zero-knowledge is not necessarily preserved in such an environment; Kilian, Petrank and Rackoff have shown that any 4 rounds zero-knowledge interactive proof (for a non-trivial language) is not concurrent zero-knowledge. On the other hand, Richardson and Kilian have shown that there exists a concurrent zero-knowledge argument for all languages in NP, but it requires a polynomial number of rounds. In this paper, we present a concurrent zero-knowledge proof for all languages in NP with a drastically improved complexity: our proof requires only a poly-logarithmic, specifically, ω(log 2 k) number of rounds. Thus, we narrow the huge gap between the known upper and lower bounds on the number of rounds required for a zero-knowledge proof that is robust for asynchronous composition. 1
We present a new technique, inspired by zero-knowledge proof systems, for proving lower bounds on approximating the chromatic number of a graph. To illustrate this technique we present simple reductions from max-3-coloring and max-3-sat, showing that it is hard to approximate the chromatic number within /spl Omega/(N/sup /spl delta//), for some /spl delta/>0. We then apply our technique in conjunction with the probabilistically checkable proofs of Bellare, Goldreich and Sudan (1995), and of Hastad (1996), and show that it is hard to approximate the chromatic number to within /spl Omega/(N/sup 1-/spl epsiv//) for any E>0, assuming NP/spl sub/ ZPP. Here, ZPP denotes the class of languages decidable by a random expected polynomial-time algorithm that makes no errors. Our result matches (up to low order terms) the known gap for approximating the size of the largest independent set. Previous 0(N/sup /spl delta//) gaps for approximating the chromatic number (such as those by Lund and Yannakakis (1994), and by Furer (1995)) did not match the gap for independent set, and do not extend beyond /spl Omega/(N/sup 1/2-/spl epsiv//).
The zero knowledge properties of interactive proof systems (IPSs) are studied in the case that the verifier is a 2-way probabilistic finite state automaton (2pfa). The following results are proved: A new definition of zero knowledge is introduced. This definition captures a concept of “zero knowledge” for IPSs that are used for language recognition.
An investigation of interactive proof systems (IPSs) where the verifier is a 2-way probabilistic finite state automaton (2pfa) is initiated. In this model, it is shown: Additional results concern two other classes of verifiers: 2pfa's that halt in polynomial expected time, and 2-way probabilistic pushdown automata that halt in polynomial time. In particular, IPSs with verifiers in the latter class are as powerful as IPSs where verifiers are polynomial-time probabilistic Turing machines. In a companion paper [7], zero knowledge IPSs with 2pfa verifiers are investigated.
In the present study, we investigated how the symmetry/asymmetry of cell division in mitotic CD34(+) cells can be evaluated by determining the plane of cell division and the potential distribution of proteins between daughter cells. The orientation of the mitotic spindle is dependent upon the positioning of the centrosomes, which determine the plane of cell division and the sharing of proteins. If the functions of unequally shared proteins are relevant to the kinetics of cell division, they could determine whether the daughter cells undergo self-renewal or differentiation. The kinetic function of the proteins of interest was investigated using a colony-replating assay and carboxyfluorescein succinimidyl ester (CFSE) staining. We used Notch/Numb as a model system, since they have a role in balancing symmetric/asymmetric divisions. Mitotic cells were examined microscopically and centrosomal markers γ-tubulin/pericentrin were used with activated Notch-1 and Numb. We monitored the first crucial divisions by CFSE staining and found an inverse relationship between activated Notch and Numb expression, suggesting a reciprocal regulation. We suggest that the subpopulations expressing activated Notch or Numb have different cell fates. To determine the influence of Notch signaling on progenitor cell self-renewal, we used the γ-secretase inhibitor N-[N-(3,5-Difluorophenacetyl-L-alanyl)]-S-phenylglycine t-Butyl ester (DAPT). DAPT influences self-renewal/differentiation outcome by affecting the frequency of symmetric renewal divisions without affecting the rate of divisions. Overall, the purpose of this study was to establish a cellular system for predicting the symmetry/asymmetry of hematopoietic progenitor divisions at the level of centrosomes and protein distribution and to investigate the influence of these proteins on progenitor cell kinetics.