We present a stronger notion of zero-knowledge: precise concurrent zero-knowledge. Our notion captures the idea that the view of any verifier in concurrent interaction can be reconstructed in the almost same time (within a constant/polynomial factor). Precise zero-knowledge in stand-alone setting was introduced by Micali and Pass in STOC’06 (The original work used the term ”local zero-knowledge”.). Their notion shows that the view of any verifier can be reconstructed in the almost same time in stand-alone setting. Hence our notion is the generalization of their notion in concurrent setting. Furthermore, we propose a ω(log 2 n)-round concurrent zero-knowledge argument for NP with linear precision, which shows that the view of any verifier in concurrent interaction can be reconstructed by the simulator with linear-time overhead. Our argument is Feige-Lapidot-Shamir type which consists of a proof-preamble and a proof-body for a modified NP statement. Our result assumes the restriction of adversarial scheduling the communication that the concurrent interaction of preambles of all sessions will be scheduled before any proof-body by the adversarial verifier. 1
One of the main goals of the Semantic Web initiative [3] is to extend the current Web technology to allow for the development of intelligent agents, which can automatically and unambiguously process the information available on millions of web pages. It has been recognized very early in the development of the Semantic Web that rules are essential for the Web3 and for Semantic Web applications—e.g., description of semantic web services, rules interchange for e-business applications. The RuleML initiative is a response to the need of a shared rule markup language using XML markup, which has a precisely defined semantics and efficient implementations. In recent years, a significant amount of work has been devoted to develop knowledge representation languages suitable for the task and a variety of languages for rule markup has been proposed. The initial design [4] included a distinction (in terms of distinct DTDs) between reaction rules and derivation rules. The first type of rules is used for the encoding of event-condition-action (ECA) rules while the second is meant for the encoding of implicational/inference rules. Despite the fact that many different proposals for ECA rules encoding have appeared the work on ECA rules is still very vague. The most recent modularized description of RuleML [6] reports this area (indicated as PR RuleML in that document) as work in progress. The derivation rules component of the RuleML initiative has originated a family of languages.4, Datalog plays the role of a core language, with simplified versions (unary and binary Datalog) developed for combining RuleML with OWL (as in SWRL). Various sublanguages have been created to include features like explicit equality (e.g., fologeq), negation as failure (e.g., naffolog), and Hilog layers (e.g., hohornlog). Various authors [7] have argued that any realistic architecture for the Semantic Web must be based on various independent but interoperable languages, including logic programming languages with and without negation-as-failure. The need for these languages and their interaction have been discussed (e.g., [8, 7]). It is also of
In the past, the problem of semantic interoperability in information systems was mostly solved by means of centralization, both at a system and at a logical level. This approach has been successful to a certain extent, but offers limited scalability and flexibility. Peer-to-Peer systems as a new brand of system architectures indicate that the principles of decentralization and self-organization might offer new solutions to many problems that scale well to very large numbers of users, or to systems where central authorities do not prevail. Therefore, we suggest a new way of building global agreements, i.e., semantic interoperability, based on decentralized, self-organizing interactions only. In the first part of this thesis, we discuss traditional data integration techniques relying on global schemas, perfect schema mappings and contained query rewritings. We elaborate on the current ecology of the World Wide Web, where autonomous information sources come and go in dynamic and unpredictable ways. In the current environment, data, schemas and schema mappings can all be generated without human intervention and get encoded in syntactic structures with limited expressivity. We argue that traditional top-down integration techniques are inapplicable to that new context and propose a new integration architecture based on decentralized mappings and dynamic self-organization. In the second part of this thesis, we propose a set of principles to foster semantic interoperability in very large scale information systems. We start by introducing new metrics for the schema mappings, based on both syntactic losses (completeness) and semantic mismatch (soundness) to selectively reformulate queries in a decentralized network of heterogeneous parties. We detail analytical methods to evaluate our metrics, and show how to take advantage of those methods to gradually alleviate mapping inconsistencies across the network. We describe a totally decentralized message passing scheme using belief propagation on transitive closures of schema mapping operations to efficiently evaluate the degree of semantic mismatch between pairs of acquainted information systems. Finally, we propose a graph-theoretic analysis of the network of mappings to quantify the quality of the global agreement that can be achieved in that way. The third and last part of this thesis is devoted to the presentation of two systems illustrating the practical applicability of our ideas. The first system we introduce, GridVine, is a Semantic Overlay Network supporting decentralized data integration techniques through pairwise schema mappings and monotonic schema inheritance. GridVine follows the principle of data independence by separating a logical layer, the semantic overlay for managing and mapping data and schemas, from a physical layer consisting of a self-organizing Peer-to-Peer overlay network for efficient routing of messages. The second system, called PicShark, takes advantage of semi-structured metadata to meaningfully share pictures in collaborative settings. PicShark builds on our principles to dynamically create both annotations and mappings, and to gradually minimize information entropy – in terms of missing metadata and schematic heterogeneity – in a self-organizing and decentralized context. Throughout this thesis, we advocate a holistic view on semantics in large-scale information systems: we model semantics as bottom-up and dynamic agreements among heterogeneous parties. We consider both the representation of semantics and the discovery of the interpretation of symbols as the result of a self-organizing process performed by distributed agents whose utility functions depend on the proper interpretation of the symbols. Our view sharply contrasts with previous top-down contributions analyzing data sources in isolation or focusing on global vocabularies and rigid sets of interpretations curated off-line. In a world where digital information is abundant but human attention remains scarce, we believe that autonomous, best-effort processes such as the ones proposed throughout this thesis will play an ever increasing role in complementing traditional top-down integration approaches to handle massive amounts of digitalized and heterogeneous information assets.
Narendra Kunapareddy, Parsa Mirhaji, David Richards, S. Ward Casscells
Although the decentralized and autonomous implementation of health information systems has made it possible to extend the reach of surveillance systems to a variety of contextually disparate domains, public health use of data from these systems is not primarily anticipated. The Semantic Web has been proposed to address both representational and semantic heterogeneity in distributed and collaborative environments. We introduce a semantic approach for the integration of health data using the Resource Definition Framework (RDF) and the Simple Knowledge Organization System (SKOS) developed by the Semantic Web community.
We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of n , of optimization problems in integer lattices, specifically, the closest vector problem (CVP) and the shortest vector problem (SVP). These interactive proofs are for the coNP direction; that is, we give an interactive protocol showing that a vector is far from the lattice (for CVP) and an interactive protocol showing that the shortest-lattice-vector is long (for SVP). Furthermore, these interactive proof systems are honest-verifier perfect zero-knowledge. We conclude that approximating CVP (resp., SVP) within a factor of n is in N P ∩co A M . Thus, it seems unlikely that approximating these problems to within a n factor is NP-hard. Previously, for the CVP (resp., SVP) problem, Lagarias et al. (1990, Combinatorica 10 , 333–348), Håstad (1988, Combinatorica 8 , 75–81), and Banaszczyk (1993, Math. Annal. 296 , 625–635) showed that the gap problem corresponding to approximating CVP (resp., SVP) within n is in N P ∩co N P . On the other hand, Arora et al. (1997, J. Comput. System Sci. 54 , 317–331) showed that the gap problem corresponding to approximating CVP within 2 log 0.999 n is quasi-NP-hard.
This paper describes a new approach to design modern information systems that offer an integrated access to the data and knowledge that is available in local applications. By integrating the local data management activities into one transparent information distribution process, modern organizations can offer better support for its workers in the execution and coordination of their work activities. Observing practical applications of decentralized, autonomous and heterogeneous information systems we see deficiencies in currently available approaches to model such information systems. They do not acknowledge the pivotal role that (informal) communicating workers play in the context of an entire organization. The interaction between the members of social and informal groups of employees makes it possible that (in many of today’s information-intensive enterprises) the local structured procedures can be effectively and flexibly integrated into global work processes supporting the business goals. Traditional design techniques concentrate on either the structured local procedures (and its local database applications), the structured global process (and its global business goals), or the informal (less structured) communication between individuals. We suggest to combine an activity-based model (suited to describe the structured parts of the processes) with a goal- or conversation-based model to tie the different elements together. Using an agent architecture we show that it is possible to implement this integrated approach. The different types of cooperating agents support the individual workers by assessing the goal of the activity, the applicability of the standard procedure, and the availability of alternative knowledge and information in order to supply the necessary information.
A proof is whatever convinces me. Shimon Even (1935–2004) The glory attached to the creativity involved in finding proofs makes us forget that it is the less glorified process of verification that gives proofs their value. Conceptually speaking, proofs are secondary to the verification process, whereas technically speaking, proof systems are defined in terms of their verification procedures. The notion of a verification procedure presumes the notion of computation and furthermore the notion of efficient computation. This implicit stipulation is made explicit in the definition of NP , where efficient computation is associated with deterministic polynomial-time algorithms. However, as argued next, we can gain a lot if we are willing to take a somewhat non-traditional step and allow probabilistic verification procedures. In this chapter, we shall study three types of probabilistic proof systems, called interactive proofs, zero-knowledge proofs , and probabilistic checkable proofs . In each of these three cases, we shall present fascinating results that cannot be obtained when considering the analogous deterministic proof systems. Summary: The association of efficient procedures with deterministic polynomial-time procedures is the basis for viewing NP-proof systems as the canonical formulation of proof systems (with efficient verification procedures). Allowing probabilistic verification procedures and, moreover, ruling by statistical evidence gives rise to various types of probabilistic proof systems. Indeed, these probabilistic proof systems carry a probability of error (which is explicitly bounded and can be reduced by successive applications of the proof system), yet they offer various advantages over the traditional (deterministic and errorless) proof systems. […]