Canetti, Goldreich, Goldwasser, and Micali (STOC 2000) introduced the notion of resettable zero-knowledge proofs, where the protocol must be zero-knowledge even if a cheating verifier can reset the prover and have several interactions in which the prover uses the same random tape. Soon afterwards, Barak, Goldreich, Goldwasser, and Lindell (FOCS 2001) studied the closely related notion of resettable soundness, where the soundness condition of the protocol must hold even if the cheating prover can reset the verifier to have multiple interactions with the same verifier's random tape. The main problem left open by this work was whether it is possible to have a single protocol that is simultaneously resettable zero knowledge and resettably sound. We resolve this question by constructing such a protocol. At the heart of our construction is a new non-black-box simulation strategy, which we believe to be of independent interest. This new strategy allows for simulators which "marry'' recursive rewinding techniques (common in the context of concurrent simulation) with non-black-box simulation. Previous non-black-box strategies led to exponential blowups in computational complexity in such circumstances, which our new strategy is able to avoid.
Nathaniel E. Baughman, Marc Liberatore, Brian Neil Levine
We explore exploits possible for cheating in real-time, multiplayer games for both client-server and serverless architectures. We offer the first formalization of cheating in online games and propose an initial set of strong solutions. We propose a protocol that has provable anti-cheating guarantees, is provably safe and live, but suffers a performance penalty. We then develop an extended version of this protocol, called asynchronous synchronization, which avoids the penalty, is serverless, offers provable anti-cheating guarantees, is robust in the presence of packet loss, and provides for significantly increased communication performance. This technique is applicable to common game features as well as clustering and cell-based techniques for massively multiplayer games. Specifically, we provide a zero-knowledge proof protocol so that players are within a specific range of each other, and otherwise have no notion of their distance. Our performance claims are backed by analysis using a simulation based on real game traces
A.J. Chakravarti, Gerald Baumgartner, Mario Lauria
The Organic Grid is a biologically inspired and fully decentralized approach to the organization of computation that is based on the autonomous scheduling of strongly mobile agents on a peer-to-peer network. Through the careful design of agent behavior, the emerging organization of the computation can be customized for different classes of applications. In this paper, we report on our experience in adapting the general framework to run two representative applications on our Organic Grid prototype: the National Center for Biotechnology Information (NCBI) basic local alignment search tool (BLAST) code for sequence alignment, and the Cannon's algorithm for matrix multiplication. The first is an example of independent task application, a type of application commonly used for grid scheduling research because of its easily decomposable nature and absence of intra-node communication. The second is a popular block algorithm for parallel matrix multiplication, and represents a challenging application for grid platforms because of its highly structured and synchronous communication pattern. Agent behavior completely determines the way computation is organized on the Organic Grid. We intentionally chose two applications at opposite ends of the distributed computing spectrum having very different requirements in terms of communication topology, resource use, and response to faults. We detail the design of the agent behavior and show how the different requirements can be satisfied. By encapsulating application code and scheduling functionality into mobile agents, we decouple both computation and scheduling from the underlying grid infrastructure. In the resulting system, every node can inject a computation onto the grid; the computation naturally organizes itself around available resources.
Fairness is the vitally necessary for application of electronic transaction.A fair protocol is presented for message transfer in electronic commerce.The protocol is designed to assure when the protocol ends,both parties get the expected messages or nothing.The protocol,based on optimistic approach,uses convertible signature scheme and non-interactive zero-knowledge proof to achieve efficient transparent TTP.Also,the protocol generates standard GDH(gap diffie-hellman) signatures as the final non-repudiation evidences.All these efforts make the protocol efficient and easy to be fitted in existing systems.
Esoteric protocols, such as electronic cash, electronic voting and selective disclosure protocols, use special message constructors that are not widely used in other types of protocols (for example, in authentication protocols). These message constructors include blind signatures, commitments and zero-knowledge proofs. Furthermore, a standard formalization of the Dolev-Yao intruder [6] does not take into account these message constructors, nor does it consider some types of attacks (such as privacy attacks, brute-force dictionary attacks and known-plaintext attacks) that esoteric as well as other types of protocols are designed to protect against. This paper aims to present an extension of typed MSR [3, 4] in order to formally specify the needed message constructors, as well as the capabilities of a Dolev-Yao intruder designed to attack esoteric protocols.
Blockchain technology has been gaining great interest from a variety of sectors including healthcare, supply chain, and cryptocurrencies. However, Blockchain suffers from a limited ability to scale (i.e., low throughput and high latency). Several solutions have been proposed to tackle this. In particular, sharding has proved to be one of the most promising solutions to Blockchain's scalability issue. Sharding can be divided into two major categories: (1) Sharding-based Proof-of-Work (PoW) Blockchain protocols, and (2) Sharding-based Proof-of-Stake (PoS) Blockchain protocols. The two categories achieve good performances (i.e., good throughput with a reasonable latency), but raise security issues. This article focuses on the second category. In this paper, we start by introducing the key components of sharding-based PoS Blockchain protocols. We then briefly introduce two consensus mechanisms, namely PoS and practical Byzantine Fault Tolerance (pBFT), and discuss their use and limitations in the context of sharding-based Blockchain protocols. Next, we provide a probabilistic model to analyze the security of these protocols. More specifically, we compute the probability of committing a faulty block and measure the security by computing the number of years to fail. We achieve a number of years to fail of approximately 4000 in a network of 4000 nodes, 10 shards, and a shard resiliency of 33%.
Asynchronous collaborative applications and systems have to deal with complexities associated with interaction nature, idiosyncrasy of groups and technical and administrative issues. Inclusion of requirements derived from them is costly (in time, resources and economically). Existing solutions addresses asynchronous collaboration via simplification of requirements and by using centralized models. In this paper we present LaCOLLA, a fully decentralized infrastructure for building collaborative applications that provides general purpose collaborative functionalities. The provision of those functionalities will avoid applications deal with most of complexities derived from groups and its members, what will help inclusion of collaborative aspects. The implementation of LaCOLLA follows the peer-to-peer paradigm and pays special attention to autonomy of its members and to self-organization of the components of the infrastructure. Another key aspect is that resources (e.g. storage) and services (e.g. authorization) are provided by its members (avoiding dependency from agents not belonging to group).
Omar Khadeer Hussain, Elizabeth Chang, Ben Soh, Tharam S. Dillon
Risk is associated with almost every activity undertaken in daily life. Analyzing the risk involved in a transaction is important to decide whether to proceed with the transaction or not. Until now, risk has been discussed extensively in the areas of investment, finance, health, environment, engineering and daily life activities. All these areas have different interpretations of risk, none of which are suitable to apply to a transaction in the area of Computer Science. In this paper, we focus on defining risk in a decentralized transaction in e-commerce.
M. Jamshed, S. Khalique, Hiroki Suguri, Hafiz Farooq Ahmad · 5 authors
Grid is an ambitious and exciting global effort to develop an environment in which individual users can access computers, databases and experimental facilities simply and transparently, without having to consider where those faculties are located. Monitoring the behavior of the resources of a distributed system, especially grid, is necessary, both for determining the cause of performance problems, and for tuning the system, which results in optimized performance. However writing monitoring and management applications for grid resource is a complex task. This is due to the geographic distribution of resources and heterogeneous environments that are owned by different organizations. We have proposed architecture for autonomous grid node monitoring agent, to address the issues of complex resource monitoring and management. The architecture is based on grid monitoring architecture (GMA) and is autonomous as it provides functionality of equality, locality and self-containment, which are main components of autonomic controllability in any sub system as part of autonomous decentralized system (ADS) (K. Mori, 1993). The evaluation results of the proposed system proved the validity of the concept for achieving autonomous resource management in dynamic systems like grid
Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan
Abstract. We provide unconditional constructions of concurrent statistical zero-knowledge proofs for a variety of non-trivial problems (not known to have probabilistic polynomial-time algorithms). The problems include Graph Isomorphism, Graph Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a restricted version of Statistical Difference, and approximate versions of the (coNP forms of the) Shortest Vector Problem and Closest Vector Problem in lattices. For some of the problems, such as Graph Isomorphism and Quadratic Residuosity, the proof systems have provers that can be implemented in polynomial time (given an NP witness) and have ~O(log n) rounds, which is known to be essentially optimal for black-box simulation.
Web services can be seen as a newly emerging research area for Service-oriented Computing and their implementation in Service-oriented Architectures. Web services are self-contained, self-describing modular applications or components providing services. Web services may be dynamically aggregated, composed, and enacted as Web services Workflows. This requires frameworks and interaction protocols for their co-ordination and transaction support. In a Service-oriented Computing setting, transactions are more complex, involve multiple parties (roles), span many organizations, and may be long-running, consisting of a highly decentralized service partner and performed by autonomous entities. A Service-oriented Transaction Model has to provide comprehensive support for long-running propositions including negotiations, conversations, commitments, contracts, tracking, payments, and exception handling. Current transaction models and mechanisms including their protocols and primitives do not sufficiently cater for quality-aware and long running transactions comprising loosely-coupled (federated) service partners and resources. Web services transactions require co-ordination behavior provided by a traditional transaction mechanism to control the operations and outcome of an application. Furthermore, Web services transactions require the capability to handle the co-ordination of processing outcomes or results from multiple services in a more flexible manner. This requires more relaxed forms of transactions—those that do not strictly have to abide by the ACID properties—such as loosely-coupled collaboration and workflows. Furthermore, there is a need to group Web services into applications that require some form of correlation, but do not necessarily require transactional behavior. The purpose of this paper is to provide a state-of-the-art review and overview of some proposed standards surrounding Web services composition, co-ordination, and transaction. In particular the Business Process Execution Language for Web services (BPEL4WS), its co-ordination, and transaction frameworks (WS-Co-ordination and WS-Transaction) are discussed.
Interactive proof and zero-knowledge proof systems are two important concepts in cryptography and complexity theory. In the past two decades, a great number of interactive proof and zero-knowledge proof protocols have been designed and applied in practice. In this paper, a simple memorizable zero-knowledge protocol is proposed for graph non-isomorphism problem, based on the memorizable interactive proof system,which is extended from the original definition of interactive proof and is more applicable in reality.
Wanzong Peng, Tongliang Lu, Wenju Peng, Zhongpan Wang
File sharing, being the foundation of the Internet, has traditionally relied on a centralized service architecture resulting in significant maintenance costs. Moreover, due to the lack of an effective file management system, instances of sensitive information going out of control and loss of confidentiality in file sharing have occurred frequently. In order to address the difficulty of tamper detection and the lack of supervision in the entire process of file transfer in the current Internet environment, this paper designs a blockchain-based system architecture for secure sharing of electronic documents. An efficient blockchain model is used in our framework, and with the help of distributed storage system and asymmetric encryption technology, file sharing can be controlled, reliable and traceable in the transfer process. Referring to existing consensus mechanisms, e.g., Delegated Proof of Stake (DPoS) and Practical Byzantine Fault Tolerance (PBFT), we propose a new consensus for efficient and secure file sharing. Our experimental results show that our framework can maintain a higher throughput than existing schemes.
The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases, distributed shared memory, multiprocessor architectures, operating systems, verification, internet, and the web.This issue consists of the paper "Reconstructing Paxos" by Romain Boichat, Partha Dutta, Svend Frølund, and Rachid Guerraoui. Many thanks to them for contributing to this issue.The celebrated Paxos algorithm of Lamport implements a fault-tolerant deterministic service by replicating it over a distributed message-passing system. In a companion paper [2], we presented a deconstruction of the algorithm by factoring out its fundamental algorithmic principles within two abstractions: an eventual leader election and an eventual register abstractions. Using those abstractions, we show in this paper how to reconstruct, in a modular manner, powerful variants of Paxos. In particular, we show how to (1) alleviate the need for stable storage access if some processes remain up for sufficiently long, (2) augment the resilience of the algorithm against unstable processes, (3) enable single process decision with shared commodity disks, and (4) reduce the number of communication steps during stable periods of the system.The Island of Paxos used to host a great civilisation which had developed a sophisticated parttime parliament protocol. Paxons codified various aspects of their parliament protocol which enabled them to easily adapt the protocol to specific functioning modes throughout the seasons. In particular, during winter, the parliament was heated and some legislators did never leave the chamber: their guaranteed presence helped alleviate the need for the writing of decrees on ledgers. This was easy to obtain precisely because the subprotocol used to "store and lock" decrees was precisely codified. In spring, and with the blooming days coming, some legislators could not stop leaving and entering the parliament. Their indiscipline prevented progress in the protocol. However, as the election subprotocol used to choose the parliament president was also precisely codified, the protocol could easily be adapted to cope with indisciplined legislators. During summer, very few legislators were in the parliament and it was hardly possible to pass any decree because of the lack of the necessary majority. Fortunately, it was easy to modify the subprotocol used to store and lock decrees and devise a powerful technique where a single legislator could pass decrees by directly accessing the ledgers of other legislators. Fall was a protest season and citizens wanted a faster procedure to pass decrees. Paxons noticed that, in most periods, messengers did not loose messages and legislators replied in time. They could devise a variant of the protocol that reduced the number of communication steps needed to pass decrees during those periods. Again, this optimisation was obtained through a simple refinement of the subprotocol used to propose new decrees.
It is proved that, when both randomization and interaction are allowed, the proofs that can be verified in polynomial time are exactly those proofs that can be generated with polynomial space. The interactive proofs introduced use only public coins, are accepted with probability one when the prover is honest, require only logarithmic workspace when the verifier is given a two-way access to his or her random tape, and by the use of known techniques can be turned into zero-knowledge proofs under the sole assumption that one-way functions exist.>
Energy management systems/supervisory control and data acquisition (EMS/SCADA) systems are usually geographically distributed and have operational organizations. They are changing in accordance with the various and varying environments, and they should be flexible enough to adapt to those changes quickly. The paper proposes a new architecture called SCOPE (System Configuration of Power Control System) to realize flexible and reliable EMS/SCADA systems. SCOPE makes application programs independent of the operational organization and system configuration of the EMS/SCADA system, i.e., application programs are not influenced by changes in them. These properties make EMS/SCADA systems flexible and reliable, and also the development of EMS/SCADA systems becomes efficient and economical. Through developing and evaluating a SCOPE prototype system, it has been confirmed that the flexibility and maintainability of EMS/SCADA systems based on the SCOPE architecture has been improved.
This paper proposes a new proof-based approach to safe evolution of distributed software systems. Specifically it extends the simple certification mechanism of proof-carrying code (PCC) to make it interactive and probabilistic, thereby devising code with interactive proof (CIP). With CIP, a code consumer is convinced, with overwhelming probability, of the existence and validity of a safety proof of a transmitted code through interaction with a code producer. The class of safety properties that are provable by CIP is larger than the class provable by PCC, provided that each code consumer is allowed to spend a reasonable amount of time on verification. Moreover, CIP can be further extended to devise code with zero-knowledge interactive proof (CZKIP). This concept is useful, for example, when the code producer wants to use the safety proof as a kind of "copyright" of the code.