Blockchain Papers

Fajiang Yu, Chen Jing, Xiang Yang, Zhu Jiacheng · 5 authors

No abstract is available for this record.

Xiaoqiang Guo, Yan Yan, Lihong Li, Hong Wang

The problem of secure multi-party computation(SMPC) is one of the most fundamental problems in information security. First, we introduce the basic concept of SMPC and four SMPC basic agreement: key distribution,oblivious transfer, bit commitment and zero knowledge proof. Secondly, we separately illustrate commitment schemes  commitment transfer protocol, commitment sharing protocol and commitment multiplication protocol. Finally, we present unconditionally secure multi-party computation with a passive adversary, an active adversary, general adversary structures.

Israa Alqassem, Davor Svetinović

Bit coin is a new protocol with a potential to revolutionize financial system. Bit coin has a complex structure, where several interacting components build a peer-to-peer currency and a payment system without relying on any trusted third party. Bit coin is continually improved by an open source community, and various Bit coin libraries, APIs, and alternative implementations are being developed. Nevertheless, there is no up-to-date protocol specification or architecture description since the official whitepaper was published back in 2008. In this paper, we provide an up-to-date protocol specification and architectural analysis of the Bit coin system. We perform this analysis as the first step towards specification of the crypto currency reference architecture. The future reference architecture will serve as a starting architectural point for the development of new systems that leverage Bit coin protocol in different contexts and for various purposes. We also discuss whether the current architecture satisfies the system's primary purpose, i.e., Providing a pure decentralized version of the crypto currency.

Yong Yu, Man Ho Au, Yi Mu, Shaohua Tang · 7 authors

No abstract is available for this record.

Padraig Flood, Michael Schukat

With an estimated 50 billion internet-enabled devices deployed by 2020, the arrival of the Internet of Things (IoT) or Internet of Everything (IoE) raises many questions regarding the suitability and adaptability of current computer security standards to provide privacy, data integrity and end entity authentication between communicating peers. In this paper we present a new protocol which combines zero-knowledge proofs and key exchange mechanisms to provide secure and authenticated communication in static machine-to-machine (M2M) networks. This approach addresses all of the aforementioned issues while also being suitable for devices with limited computational resources and can be deployed in wireless sensor networks. While the protocol requires an a-priori knowledge about the network setup and structure, it guarantees perfect forward secrecy.

Andris Ambainis, Ansis Rosmanis, Dominique Unruh

Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently\ndifficult to analyze because their security analysis uses rewinding. Certain\ncases of quantum rewinding are handled by the results by Watrous (SIAM J\nComput, 2009) and Unruh (Eurocrypt 2012), yet in general the problem remains\nelusive. We show that this is not only due to a lack of proof techniques:\nrelative to an oracle, we show that classically secure proofs and proofs of\nknowledge are insecure in the quantum setting.\n More specifically, sigma-protocols, the Fiat-Shamir construction, and\nFischlin's proof system are quantum insecure under assumptions that are\nsufficient for classical security. Additionally, we show that for similar\nreasons, computationally binding commitments provide almost no security\nguarantees in a quantum setting.\n To show these results, we develop the "pick-one trick", a general technique\nthat allows an adversary to find one value satisfying a given predicate, but\nnot two.\n

Michael Backes, Cătălin Hriţcu, Matteo Maffei

We present a new type system for verifying the security of reference implementations of cryptographic protocols written in a core functional programming language. The type system combines prior work on refinement types, with union, intersection, and polymorphic types, and with the novel ability to reason statically about the disjointness of types. The increased expressivity enables the analysis of important protocol classes that were previously out of scope for the type-based analyses of reference protocol implementations. In particular, our types can statically characterize: (i) more usages of asymmetric cryptography, such as signatures of private data and encryptions of authenticated data; (ii) authenticity and integrity properties achieved by showing knowledge of secret data; (iii) applications based on zero-knowledge proofs. The type system comes with a mechanized proof of correctness and an efficient type-checker.

V V Jagtap, Shiva Aher

Cloud computing is the vast computing utility, where users can remotely store their data into the cloud so to have the benefit of the on-demand availability of huge and different applications and services from a shared pool of configurable computing resources.Cloud-based outsourced storage space reduces the patron load of storage management. It also reduces the maintenance load of customer by providing a comparably low-cost, scalable, locationindependent platform.This new model of data hosting service commence a new security challenges, which requires an independent auditing service which audit the data integrity of cloud. There are different existing auditing services available in cloud which audit data integrity remotely in static motion but these are not applicable whenever data is dynamically updated in cloud. Since it require efficient and secure dynamic auditing method for data owner. However in cloud, the clients no have direct physical possession of data. It shows client faces different formidable risk like missing or corruption of data. To keep away from the security and integrity risk of data, audit services are essential to ensure the integrity and availability of outsourced data and to achieve digital forensics and credibility on cloud computing.Provable data possession (PDP), which is a cryptographic technique for verifying the integrity of data without retrieving it at an untrusted server, can be used to realize audit services. In this paper, profiting from the interactive proof system, we address the construction of an interactive PDP protocol to prevent the fraudulence of prove (soundness property) and the leakage of verified data (zero-knowledge property).

Genqiang Wu, Yeping He, Yi Lu, Liping Ding

Abstract. We consider the following problem: Assuming that Alice and Bob have an integer interval [a, e] and an integer b respectively, for a commitment c to b, Alice and Bob jointly check whether b is within [a, e] without revealing their inputs, where either party may behave malicious-ly. A special case of the problem is the secure integer comparison in the malicious model. This problem mainly arises from location-based access control systems where one party needs to assure to the other party that its location is within some definite area. Our main result is a constant-round protocol that exhibit the square of log e communication and the square of log e exponentiations with simulation-based security. At the heart of the construction is perfec-t k-ary index and corresponding zero-knowledge proof techniques. We consider a more general case of the problem where the interval is substi-tuted by a union of intervals.

Naomi Benger, Joop van de Pol, Nigel P. Smart, Yuval Yarom

No abstract is available for this record.

Hongda Li, Qihua Niu, Guifang Huang

Abstract. Garg, Jain, and Sahai first consider zero knowledge proofs in the presence of leakage on the local state of the prover, and present a leakage-resilient-zero-knowledge proof system for HC (Hamiltonian Cycle) problem. Their construction is called (1 + ε)-leakage-resilient zero-knowledge, for any constant ε> 0, because the total length of the leakage the simulator needs is (1 + ε) times as large as that of the leakage received by the verifier. In recent, Pandey provides a constant-round leakage-resilient zero-knowledge argument satisfying the ideal requirement of ε = 0. Whether there exist constant round leakage-resilient zero-knowledge arguments of knowledge for all NP languages is an interesting problem. This paper focuses on this problem and presents a constant-round construction of leakage-resilient zero-knowledge arguments of knowledge for the HC problem. Key word: zero-knowledge proofs, proofs of knowledge, leakage-resilient, non-black-box simulation, constant-round. 1

Handan Kılınç, Alptekın Küpçü

Secure two-party computation cannot be fair against malicious adversaries, unless a trusted third party (TTP) or a gradual-release type super-constant round protocol is employed. Existing optimistic fair two-party computation protocols with constant rounds are either too costly to arbitrate (e.g., the TTP may need to re-do almost the whole computation), or require the use of electronic payments. Furthermore, most of the existing solutions were proven secure and fair via a partial simulation, which, we show, may lead to insecurity overall. We propose a new framework for fair and secure two-party computation that can be applied on top of any secure two party computation protocol based on Yao’s garbled circuits and zero-knowledge proofs. We show that our fairness overhead is minimal, compared to all known existing work. Furthermore, our protocol is fair even in terms of the work performed by Alice and Bob. We also prove our protocol is fair and secure simultaneously, through one simulator, which guarantees that our fairness extensions do not leak any private information. Lastly, we ensure that the TTP never learns the inputs or outputs of the computation. Therefore, even if the TTP becomes malicious and causes unfairness by colluding with one party, the security of the underlying protocol is still preserved.

Payman Mohassel, Seyed Saeed Sadeghian, Nigel P. Smart

Abstract. We propose the first general framework for designing actively secure private function eval-uation (PFE), not based on universal circuits. Our framework is naturally divided into pre-processing and online stages and can be instantiated using any generic actively secure multiparty computation (MPC) protocol. Our framework helps address the main open questions about efficiency of actively secure PFE. On the theoretical side, our framework yields the first actively secure PFE with linear complexity in the circuit size. On the practical side, we obtain the first actively secure PFE for arithmetic circuits with O(g · log g) complexity where g is the circuit size. The best previous construction (of practical interest) is based on an arithmetic universal circuit and has complexity O(g5). We also introduce the first linear Zero-Knowledge proof of correctness of “extended permutation ” of ciphertexts (a generalization of ZK proof of correct shuffles) which maybe of independent interest.

Moni Naor, Asaf Ziv

We consider Primary-Secondary-Resolver Membership Proof Systems (PSR for short) and show different constructions of that primitive. A PSR system is a 3-party protocol, where we have a primary, which is a trusted party which commits to a set of members and their values, then generates a public and secret keys in order for secondaries (provers with knowledge of both keys) and resolvers (verifiers who only know the public key) to engage in interactive proof sessions regarding elements in the universe and their values. The motivation for such systems is for constructing a secure Domain Name System (DNSSEC) that does not reveal any unnecessary information to its clients. We require our systems to be complete, so honest executions will result in correct conclusions by the resolvers, sound, so malicious secondaries cannot cheat resolvers, and zero-knowledge, so resolvers will not learn additional information about elements they did not query explicitly. Providing proofs of membership is easy, as the primary can simply precompute signatures over all the members of the set. Providing proofs of non-membership, i.e. a denial-of-existence mechanism, is trickier and is the main issue in constructing PSR systems.

Prabhanjan Ananth, Vipul Goyal, Omkant Pandey

We consider the task of constructing interactive proofs for NP which can provide meaningful security for a prover even in the presence of continual memory leakage. We imagine a setting where an adversarial verifier participates in multiple sequential interactive proof executions for a fixed NP statement x. In every execution, the adversarial verifier is additionally allowed to leak a fraction of the (secret) memory of the prover. This is in contrast to the recently introduced notion of leakage-resilient zero-knowledge (Garg-Jain-Sahai’11) where there is only a single execution. Under multiple executions, in fact the entire prover witness might end up getting leaked thus leading to a complete compromise of prover security. Towards that end, we define the notion of non-transferable proofs for all languages in NP. In such proofs, instead of receiving w as input, the prover will receive an “encoding ” of the witness w such that the encoding is sufficient to prove the validity of x; further, this encoding can be “updated ” to a fresh new encoding for the next execution. We then require that if (x,w) are sampled from a “hard” distribution, then no PPT adversary A ∗ can gain the ability to prove x (on its own) to an honest verifier, even if A ∗ has participated in polynomially many interactive proof executions (with leakage) with an honest prover whose input is (x,w). Non-transferability is a strong security guarantee which suffices for

Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, Łukasz Mazurek

Bitcoin is a peer-to-peer cryptographic currency system. Since its introduction in 2008, Bitcoin has gained noticeable popularity, mostly due to its following properties: (1) the transaction fees are very low, and (2) it is not controlled by any central authority, which in particular means that nobody can "print" the money to generate inflation. Moreover, the transaction syntax allows to create the so-called contracts, where a number of mutually-distrusting parties engage in a protocol to jointly perform some financial task, and the fairness of this process is guaranteed by the properties of Bitcoin. Although the Bitcoin contracts have several potential applications in the digital economy, so far they have not been widely used in real life. This is partly due to the fact that they are cumbersome to create and analyze, and hence risky to use. In this paper we propose to remedy this problem by using the methods originally developed for the computer-aided analysis for hardware and software systems, in particular those based on the timed automata. More concretely, we propose a framework for modeling the Bitcoin contracts using the timed automata in the UPPAAL model checker. Our method is general and can be used to model several contracts. As a proof-of-concept we use this framework to model some of the Bitcoin contracts from our recent previous work. We then automatically verify their security in UPPAAL, finding (and correcting) some subtle errors that were difficult to spot by the manual analysis. We hope that our work can draw the attention of the researchers working on formal modeling to the problem of the Bitcoin contract verification, and spark off more research on this topic.

Gus Gutoski, Douglas Stebila

No abstract is available for this record.

Tobias Bamert, Christian Decker, Roger Wattenhofer, Samuel Welten

No abstract is available for this record.

Marcelo Arenas, Juan L. Reutter, Etienne Toussaint, Martín Ugarte · 6 authors

In the consensus protocols used in most cryptocurrencies, participants called miners must find valid blocks of transactions and append them to a shared tree-like data structure. Ideally, the rules of the protocol should ensure that miners maximize their gains if they follow a default strategy, which consists on appending blocks only to the longest branch of the tree, called the blockchain. Our goal is to understand under which circumstances are miners encouraged to follow the default strategy. Unfortunately, most of the existing models work with simplified payoff functions, without considering the possibility that rewards decrease over time because of the game rules (like in Bitcoin), nor integrating the fact that a miner naturally prefers to be paid earlier than later (the economic concept of discount). In order to integrate these factors, we consider a more general model where issues such as economic discount and decreasing rewards can be set as parameters of an infinite stochastic game. In this model, we study the limit situation in which a miner does not receive a full reward for a block if it stops being in the blockchain. We show that if rewards are not decreasing, then miners do not have incentives to create new branches, no matter how high their computational power is. On the other hand, when working with decreasing rewards similar to those in Bitcoin, we show that miners have an incentive to create such branches. Nevertheless, this incentive only occurs when a miner controls a proportion of the computational power which is close to half of the computational power of the entire network.

Prabhjot Singh, B. R. Chandavarkar, Srishti Arora, Neha Agrawal

In this paper, we study Bit coin network for electronic cash transactions, and compare the extension to the BTCs network which inculcates provision of executing fast transactions with greater security and assurance with the former method of Proof-Of-Work for executing transactions. Above milestones are achieved by introducing the concepts of mutual trust and verifiable code execution between the payer and the payee in the network. Our work proposes a significant modification of the Pioneer model to provide a two-party trust framework for Bit coin transactions, considerably faster compared to the generic trust platform of Bit coin networks based on slow proof-of-work. The scheme proposed can promote the use of Bit coin transactions in real life scenarios, where fast transactions are desirable due time constraints between the payment and the service.

Jyri Rajamäki, Paresh Rathod, J. EDWIN HOLMSTROM

This paper focuses on future requirements of broadband data transmission of public protection and disaster relief, critical infrastructure protection and military, and presents the concept of redundant and secure data communication network system in the multi-organizational environment. We are proposing a fully decentralized architecture with optimized critical communication channels. Here, network actors and elements identify and authenticate by establishing physical connection. This concept also recommends, group level user-authorization mechanism for each participating organization. Their respective users of command and control centers are identified, authorized and authenticated to various data sources. The decentralized architecture concept is using the Distributed Systems intercommunication Protocol (DSiP). The concept is highly fault-tolerant in routine as well as crises operations. The software-based approach is independent of heterogeneous data communication technologies, IP networks and telecommunication operator services. The solution enables to build an effective and lasting cyber secure data network for multi organizational environment. Being a fully decentralized concept, networks of individual member organizations are virtually autonomous and hard to upset each other. That allows smooth message and information exchange to enable interoperability.

Matteo Maffei, Kim Pecina, Manuel Reinert

The privacy of users has rapidly become one of the most pervasive and stringent requirements in distributed computing. Designing and implementing privacy-preserving distributed systems, however, is challenging since these systems also have to fulfill seemingly conflicting security properties and system requirements: e.g., authorization and accountability require some form of user authentication and session management necessarily involves some form of user tracking. In this work, we present a solution based on declarative design. The core component of our framework is a logic-based declarative API for data processing that exports methods to conveniently specify the system architecture and the intended security properties, and conceals the cryptographic realization. Invisible to the programmer, the implementation of this API relies on a powerful combination of digital signatures, non-interactive zero-knowledge proofs of knowledge, pseudonyms, and reputation lists. We formally proved that the cryptographic implementation enforces the security properties expressed in the declarative specification. The systems produced by our framework enjoy interoperability and open-endedness: they can easily be extended to offer new services and cryptographic data can be shared and processed by different services, without requiring any extra bootstrapping phase or interaction among parties. We implemented the API in Java and conducted an experimental evaluation to demonstrate the practicality of our approach.

J.A. Bergstra, Karl de Leeuw

The famous new money Bitcoin is classified as a technical informational money (TIM). Besides introducing the idea of a TIM, a more extreme notion of informational money will be developed: exclusively informational money (EXIM). The informational coins (INCOs) of an EXIM can be in control of an agent but are not owned by any agent. INCOs of an EXIM cannot be stolen, but they can be lost, or thrown away. The difference between an EXIM and a TIM shows up when considering a user perspective on security matters. Security for an EXIM user is discussed in substantial detail, with the remarkable conclusion that computer security (security models, access control, user names, passwords, firewalls etc.) is not always essential for an EXIM, while the application of cryptography based information security is unavoidable for the use of an EXIM. Bitcoin seems to meet the criteria of an EXIM, but the assertion that "Bitcoin is an EXIM", might also be considered problematic. As a thought experiment we will contemplate Bitguilder, a hypothetical copy of Bitcoin that qualifies as an EXIM. A business ethics assessment of Bitcoin is made which reveals a number of worries. By combining Bitguilder with a so-called technical informational near-money (TINM) a dual money system, having two units with a fluctuating rate, may be obtained. It seems that a dual money can remedy some, but not all, of the ethical worries that arise when contemplating Bitcoin after hypothetically having become a dominant form of money. The contributions that Bitcoin's designers can potentially make to the evolution of EXIMs and TIMs is analyzed in terms of the update of the portfolio of money related natural kinds that comes with Bitcoin.

J.A. Bergstra, Karl de Leeuw

The famous new money Bitcoin is classified as a technical informational money (TIM). Besides introducing the idea of a TIM, a more extreme notion of informational money will be developed: exclusively informational money (EXIM). The informational coins (INCOs) of an EXIM can be in control of an agent but are not owned by any agent. INCOs of an EXIM cannot be stolen, but they can be lost, or thrown away. The difference between an EXIM and a TIM shows up when considering a user perspective on security matters. Security for an EXIM user is discussed in substantial detail, with the remarkable conclusion that computer security (security models, access control, user names, passwords, firewalls etc.) is not always essential for an EXIM, while the application of cryptography based information security is unavoidable for the use of an EXIM. Bitcoin seems to meet the criteria of an EXIM, but the assertion that "Bitcoin is an EXIM", might also be considered problematic. As a thought experiment we will contemplate Bitguilder, a hypothetical copy of Bitcoin that qualifies as an EXIM. A business ethics assessment of Bitcoin is made which reveals a number of worries. By combining Bitguilder with a so-called technical informational near-money (TINM) a dual money system, having two units with a fluctuating rate, may be obtained. It seems that a dual money can remedy some, but not all, of the ethical worries that arise when contemplating Bitcoin after hypothetically having become a dominant form of money. The contributions that Bitcoin's designers can potentially make to the evolution of EXIMs and TIMs is analyzed in terms of the update of the portfolio of money related natural kinds that comes with Bitcoin.