Blockchain Papers

Chao Yang, Mingyue Zhang, Qi Jiang, Junwei Zhang · 7 authors

No abstract is available for this record.

Thibaut Lajoie-Mazenc, Romaric Ludinard, Emmanuelle Anceaume

Double spending and blockchain forks are two main issues that the Bitcoin crypto-system is confronted with. The former refers to an adversary's ability to use the very same coin more than once while the latter reflects the occurrence of transient inconsistencies in the history of the blockchain distributed data structure. We present a new approach to tackle these issues: it consists in adding some local synchronization constraints on Bitcoin's validation operations, and in making these constraints independent from the native blockchain protocol. Synchronization constraints are handled by nodes which are randomly and dynamically chosen in the Bitcoin system. We show that with such an approach, content of the blockchain is consistent with all validated transactions and blocks which guarantees the absence of both double-spending attacks and blockchain forks.

Stefano Bistarelli, Marco Mantilacci, Paolo Santancini, Francesco Santini

In this work we re-adapt the Bitcoin e-payment system and propose it as a decentralised end-to-end voting platform (from voters to candidates). We describe the main architectural choices behind the implementation, which consists of the pre-voting, voting, and post-voting phases. The resulting implementation is completely decentralised: it is possible to directly cast a vote in the block-chain without any collecting intermediate-level. All the votes can be verified by anyone reading such a public ledger. We also exploit digital asset coins to directly keep track of votes (through the Open Asset Protocol), and we show the election cost for n voters.

Dmitry Khovratovich, Jason Law

We show how to adapt the Bitcoin BIP32 proposal for deterministic key generation for the Ed25519 curve which has non-linear key space. We also demonstrate that the alternative proposal by Chain.com is insecure and deviates from the EdDSA standard.

Zhu Yan, Guhua Gan, Khaled Riad

In the Big Data era, personal metadata may will become a new type of corporate asset, however there have already been a growing public concern about user's privacy mined from metadata. In this paper we address the problem of implementing the self-sovereignty of personal metadata on the existing OpenPDS/SafeAnswers framework according to the Windhover Principle. In order to do that, we propose a new framework, called BlocakChain-based Personal Data Store (BCPDS), to realize two basic properties: notary and autonomy. This framework, firstly introduces the BlockChain as a notary, into OpenPDS/SafeAnswers for secure storage of personal meta-data instead of the original database. Next, we present an AutoNomybased Access Control (ANAC) to improve the SafeAnswers module, where ANAC is a new mechanism that enforces access based on the relationship among all authorized users and metadata's owner. In addition, we also propose General Access Structure (GAS) and threshold secret sharing scheme in BlockChain as an implementation method for our BC-PDS framework.

Masashi Sato, Shin’ichiro Matsuo

Blockchain technology realizes unforgeable and decentralized ledger by applying P2P network, cryptography and consensus mechanism over distributed network. Its security relies on all of these technologies. One of fundamental problem of the security of blockchain technology is compromise of underlying cryptographic algorithms. This paper shows the impact of compromise of underlying cryptography and the way to extend the validity of blockchain applying the long-term signature scheme which was standardized in ETSI. The long-term signature scheme assume the existence of centralized PKI and secure time-stamp service. In this paper, we propose a method to apply similar concept and data structure with de-centralized manner. Our scheme avoids hard-fork of original blockchain, in the case of compromise of hash function and provides smooth-fork in the case of compromise of digital signature scheme.

Anwar Kh. Faraj, Areej M. Abduldaim, Shatha A. Salman, Nadia M. G. Al-Saidi

Algebra is one of the important fields of mathematics. It concerns in the study and manipulates of mathematical symbols. It also concerns with study of abstractions such as groups, rings and fields. Ring theory is the most attractive category of algebra in the area of cryptography. Recently, many algebraic cryptosystem protocols based on non-commutative algebraic structures such as; authentication, key exchange, and encryption-decryption processes are adopted. In this paper, we employ the algebraic structure called nil Armendariz (NA) rings to design a neoteric algorithm for zero knowledge proof. The proposed protocol is implemented and illustrated through numerical example, and its soundness and completeness are proved.

Ken Naganuma, Masayuki Yoshino, Hisayoshi SATO, Takayuki Suzuki

Bitcoin is the first widely adopted decentralized digitale-cash system. All Bitcoin transactions that include addresses of senders and receivers are stored in the public blockchain which could cause privacy problems. The Zerocoin protocol hides the link between individual Bitcoin transactions without adding trusted third parties. However such an untraceable remittance system could cause illegal transfers such as money laundering. In this paper we address this problem and propose an auditable decentralized e-cash scheme based on the Zerocoin protocol. Our scheme allows designated auditors to extract link information from Zerocoin transactions while preventing other users including miners from obtaining it. Respecting the mind of the decentralized system, the auditor doesn't have other authorities such as stopping transfers, confiscating funds, and deactivating accounts. A technical contribution of our scheme is that a coin sender embeds audit information with a non-interactive zeroknowledge proof of knowledge (NIZKP). This zero-knowledge prevents malicious senders from embedding indiscriminate audit information, and we construct it simply using only the standard Schnorr protocol for discrete logarithm without zk-SNARKs or other recent techniques for zero-knowledge proof.

Wei‐Tek Tsai, Xiaoying Bai, Lian Yu

A permissioned blockchain (BC) is a secure distributed ledger maintained by a number of trusted validation nodes. However, a validator may become compromised and send inconsistent messages to different nodes. To counter the problem, consensus protocols like Practical Byzantine Fault Tolerance (PBFT) can be used. The paper presents a permissioned BC system and discusses various design issues including control messages, block size and window size of block creation time. Furthermore, it is necessary to identify those compromised nodes discovered during the consensus protocol. This paper then proposes a reputation system to track the trustworthiness of nodes as it is necessary to distinguish failed nodes from compromised nodes. A compromised node may send inconsistent messages to others or accuse other nodes compromised, and it should be removed as soon as it is identified and confirmed.

Yupeng Zhang, Jonathan Katz, Charalampos Papamanthou

We present a new construction of an expressive set accumulator. Unlike existing cryptographic accumulators, ours provides succinct proofs for a large collection of operations over accumulated sets, including intersection, union, set difference, SUM, COUNT, MIN, MAX, and RANGE, as well as arbitrary nestings of the above. We also show how to extend our accumulator to be zero-knowledge. The security of our accumulator is based on extractability assumptions and other assumptions that hold in the generic group model. Our construction has asymptotically optimal verification complexity and proof size, constant update complexity, and public verifiability/updatability-namely, any client who knows the public key and the last accumulator value can verify the supported operations and update the accumulator. The expressiveness of our accumulator comes at the cost of quadratic prover time. However, we show that the cryptographic operations involved are cheap compared to those incurred by generic approaches (e.g., SNARKs) that are equally expressive: our prover runs faster for sets of up to 5 million items. Our accumulator serves as a powerful cryptographic tool with many applications. For example, it can be applied to efficiently support verification of a rich collection of SQL queries when used as a drop-in replacement in existing verifiable database systems (e.g., IntegriDB, CCS 2015).

Igor Zikratov, Alexander Kuzmin, Vladislav Akimenko, Viktor Niculichev · 5 authors

Blockchain is a relatively new technology that has shown a lot of possibilities. It emerged in 2009 as a public ledger of all Bitcoin transactions. Blockchain technology is finding applications in wide range of areas: digital assets and stocks, smart contracts, record keeping, ID systems, cloud storage, ride sharing, etc. We investigate the blockchains' activity in terms of how to store, retrieve and share files in decentralized network.

Harry Halpin, Marta Piekarska

The blockchain has fueled one of the most enthusiastic bursts of activity in applied cryptography in years, but outstanding problems in security and privacy research must be solved for blockchain technologies to go beyond the hype and reach their full potential. At the first IEEE Privacy and Security on the Blockchain Workshop (IEEE S&B), we presented peer-reviewed papers bringing together academia and industry to analyze problems ranging from deploying newer cryptographic primitives on Bitcoin to enabling usecases like privacy-preserving file storage. We overview not only the larger problems the workshop has set out to tackle, but also outstanding unsolved issues that will require further cooperation between academia and the blockchain community.

Lin Chen, Lei Xu, Nolan Shah, Nour Diallo · 7 authors

User privacy is an important issue in a blockchain based transaction system. Bitcoin, being one of the most widely used blockchain based transaction system, fails to provide enough protection on users' privacy. Many subsequent studies focus on establishing a system that hides the linkage between the identities (pseudonyms) of users and the transactions they carry out in order to provide a high level of anonymity. Examples include Zerocoin, Zerocash and so on. It thus becomes an interesting question whether such new transaction systems do provide enough protection on users' privacy. In this paper, we propose a novel and effective approach for de-anonymizing these transaction systems by leveraging information in the system that is not directly related, including the number of transactions made by each identity and time stamp of sending and receiving. Combining probability studies with optimization tools, we establish a model which allows us to determine, among all possible ways of linking between transactions and identities, the one that is most likely to be true. Subsequent transaction graph analysis could then be carried out, leading to the de-anonymization of the system. To solve the model, we provide exact algorithms based on mixed integer linear programming. Our research also establishes interesting relationships between the de-anonymization problem and other problems studied in the literature of theoretical computer science, e.g., the graph matching problem and scheduling problem.

Juan A. Garay

As the first decentralized cryptocurrency, Bitcoin [1] has ignited much excitement, not only for its novel realization of a central bank-free financial instrument, but also as an alternative approach to classical distributed computing problems, such as reaching agreement distributedly in the presence of misbehaving parties, as well as to numerous other applications-contracts, reputation systems, name services, etc. The soundness and security of these applications, however, hinges on the thorough understanding of the fundamental properties of its underlying blockchain data structure, which parties ("miners") maintain and try to extend by generating "proofs of work" (POW, aka "cryptographic puzzle"). In this talk we follow the approach introduced in [2], formulating such fundamental properties of the blockchain, and then showing how applications such as consensus and a robust public transaction ledger can be built ``on top'' of them. The properties are as follows, assuming the adversary's hashing power (our analysis holds against arbitrary attacks) is strictly less than ½ and high network synchrony:

Alexandra Dmitrienko, David Noack, Moti Yung

Bitcoin seems to be the most successful cryptocurrency so far given the growing real life deployment and popularity. While Bitcoin requires clients to be online to perform transactions and a certain amount of time to verify them, there are many real life scenarios that demand for offline and immediate payments (e.g., mobile ticketing, vending machines, etc). However, offline payments in Bitcoin raise non-trivial security challenges, as the payee has no means to verify the received coins without having access to the Bitcoin network. Moreover, even online immediate payments are shown to be vulnerable to double-spending attacks. In this paper, we propose the first solution for Bitcoin payments, which enables secure payments with Bitcoin in offline settings and in scenarios where payments need to be immediately accepted. Our approach relies on an offline wallet and deploys several novel security mechanisms to prevent double-spending and to verify the coin validity in offline setting. These mechanisms achieve probabilistic security to guarantee that the attack probability is lower than the desired threshold. We provide a security and risk analysis as well as model security parameters for various adversaries. We further eliminate remaining risks by detection of misbehaving wallets and their revocation.

Wenting Li, Alessandro Sforzin, Sergey Fedorov, Ghassan Karame

The blockchain emerges as an innovative tool that has the potential to positively impact the way we design a number of online applications today. In many ways, the blockchain technology is, however, still not mature enough to cater for industrial standards. Namely, existing Byzantine tolerant permission-based blockchain deployments can only scale to a limited number of nodes. These systems typically require that all transactions (and their order of execution) are publicly available to all nodes in the system, which comes at odds with common data sharing practices in the industry, and prevents a centralized regulator from overseeing the full blockchain system. In this paper, we propose a novel blockchain architecture devised specifically to meet industrial standards. Our proposal leverages the notion of satellite chains that can privately run different consensus protocols in parallel - thereby considerably boosting the scalability premises of the system. Our solution also accounts for a hands-off regulator that oversees the entire network, enforces specific policies by means of smart contracts, etc. We implemented our solution and integrated it with Hyperledger Fabric v0.6.

Hui Wang, Yuanyuan Cen, LI Xue-feng

Cross-chain communication is one of the major design considerations in current blockchain systems [4-7] such as Ethereum[8]. Currently, Blockchain operates like information isolated island, they cannot obtain external data or execute transactions on their own.

Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi · 8 authors

We propose a new class of post-quantum digital signature schemes that: (a) derive their security entirely from the security of symmetric-key primitives, believed to be quantum-secure, and (b) have extremely small keypairs, and, (c) are highly parametrizable. In our signature constructions, the public key is an image y=f(x) of a one-way function f and secret key x. A signature is a non-interactive zero-knowledge proof of x, that incorporates a message to be signed. For this proof, we leverage recent progress of Giacomelli et al. (USENIX’16) in constructing an efficient sigma protocol for statements over general circuits. We improve this sigma protocol to reduce proof sizes by a factor of two, at no additional computational cost. While this is of independent interest as it yields more compact proofs for any circuit, it also decreases our signature sizes. We consider two possibilities for making the proof non-interactive, the Fiat-Shamir transform, and Unruh’s transform (EUROCRYPT’12,’15,’16). The former has smaller signatures, while the latter has a security analysis in the quantum-accessible random oracle model. By customizing Unruh’s transform to our application, the overhead is reduced to 1.6x when compared to the Fiat-Shamir transform, which does not have a rigorous post-quantum security analysis. We implement and benchmark both approaches and explore the possible choice of f, taking advantage of the recent trend to strive for practical symmetric ciphers with a particularly low number of multiplications and end up using LowMC.

Henry Corrigan-Gibbs, Dan Boneh

This paper presents Prio, a privacy-preserving system for the collection of aggregate statistics. Each Prio client holds a private data value (e.g., its current location), and a small set of servers compute statistical functions over the values of all clients (e.g., the most popular location). As long as at least one server is honest, the Prio servers learn nearly nothing about the clients' private data, except what they can infer from the aggregate statistics that the system computes. To protect functionality in the face of faulty or malicious clients, Prio uses secret-shared non-interactive proofs (SNIPs), a new cryptographic technique that yields a hundred-fold performance improvement over conventional zero-knowledge approaches. Prio extends classic private aggregation techniques to enable the collection of a large class of useful statistics. For example, Prio can perform a least-squares regression on high-dimensional client-provided data without ever seeing the data in the clear.

Alberto Blanco Justicia

The latest Eurobarometer published in December 2016, reflecting the perceptions of the European citizens on privacy and security in telecommunications shows that, although people are not always informed on the privacy regulations or the implications of privacy breaches, they demand specific privacy protection. In particular, citizens want their data, their communications and the data that they give or outsource to online services to be well protected and not shared with unwanted parties. The demands of the public can be partly covered by the application of the privacy-by-design principle and the use of Privacy Enhancing Techniques (PETs) in commercial applications. The privacy-by-design principle requires application designers to gather only the personal data that are essential to the correct operation of their applications. That is, applications following this principle should only ask the users to input those personal data that the specific application explicitly needs. Most applications in the market (and especially smartphone applications) clearly disregard this principle ---a look at the permissions they request is conclusive---: they collect contextual information too, even if it is not needed. The privacy policies of major service providers explain that all data may be used for commercial purposes. Although major service providers collect more data than strictly necessary, the privacy-by-design principle demands that users be empowered with the decision about when to grant access to their data, when to modify them and when to delete them. While this is more or less being taken into account by service providers, sometimes the procedures to modify or delete personal data are not transparent enough or too cumbersome. Privacy Enhancing Techniques (PET) are cryptographic and non-cryptographic tools that, when used appropriately, minimize the amount of personal data being handled by applications, and therefore help developers to more easily comply with regulations on personal data processing. Therefore, research on privacy enhancing techniques and on the practical deployment of the privacy-by-design principle is backed by the demands of the general population. In this work we aim at demonstrating that, if appropriate techniques are used, privacy does not necessarily work against security and/or utility. We focus on three specific application cases described below: - Group discounts are offered by vendors and public authorities to encourage a more sustainable (or profitable) way to access their services or use public resources. An example of this are high-occupancy vehicle (HOV) tolls in highways, which offer discounts for vehicles carrying more than a given number of passengers (2 or more, 3 or more, etc). There are several ways to ascertain the number of members of a group: employees at access points that count them, cameras that take photos and analyze them in toll booths, or registration procedures that require the names of all members of groups, among others. We argue that automated mechanisms, such as cameras and registration procedures, take more information from the participants that is actually needed (thus violating the privacy-by-design principle), and that the only really necessary information is the size of the groups. - Loyalty programs are marketing efforts implemented by vendors, especially retailers, that are aimed at establishing a lasting relationship with consumers. In a loyalty program, the vendor pursues two main goals: i) to encourage the consumer to make more purchases in the future (returning customer); ii) to allow the vendor to profile the consumer in view of conducting market research and segmentation (profiled customer). In order to lure consumers into a loyalty program, the vendor offers them rewards, typically loyalty points that consumers can later exchange for discounts, gifts or other benefits offered by the vendor. Normally, enrollment to loyalty programs involves some kind of registration procedure, in which customers fill out a form with their personal information and are granted a loyalty card, be it a physical card (magnetic stripe or smartcard) or a smartphone application. Although loyalty programs have become widespread, they are experiencing a loss of active participants and they have been criticized by business experts and consumer associations. Criticism is mainly due to privacy issues, because it is not always clear whether the benefits offered by vendors in their loyalty programs are worth the loss of consumer privacy caused by profiling. - Implicit authentication refers to a software system authenticating individuals based on the way they interact with their device, i.e. their behavior. In this context, the user's behavior can be determined by collecting a variety of features, such as keystroke patterns, browser history and configuration, IP addresses, location, visible antennas, etc. Implicit authentication can be viewed as a complement of the usual explicit authentication based on identifiers and credentials. Note that a common trait in these three application cases is that users need to prove something about themselves or their context without revealing more than what is strictly necessary. We believe these cases can be used as an example for other applications in which the goal is similar. The main contributions of this thesis are: 1. A group size accreditation method that preserves anonymity of the members of the groups. The anonymity provided by the scheme is congurable. The method rests on two building blocks: (a) A new parameterized key management scheme for identity-based signatures that allows setting the anonymity level of users by providing them with multiple keys that are shared by many other users, but that are extracted from a unique identity. (b) A novel IBDT signature scheme based on asymmetric bilinear pairings, that combines the properties of identity-based and threshold signature schemes. Signatures produced with this scheme reveal only the public keys of the group members, which are called identities, and the size of the signing group. The signature scheme is efficient, and the sizes of the signatures are constant. 2. A privacy-preserving loyalty program protocol suite, whereby vendors can issue and verify loyalty points, and customers can maintain their anonymity and con gure the level of generalization for their purchase receipts before submitting them for additional loyalty points. This allows vendors to still carry out client profiling in a privacy-aware way. This protocol suite combines the following techniques: (a) A new construction for anonymous (untransferable) tokens with controlled linkability based on partially blind signatures and zero-knowledge proofs. The construction allows issuing and verifying tokens, while the verifier cannot link tokens to a specific user or between concrete executions of the issuance and verification procedures, unless such a linkage is authorized by the user. Moreover, if a hardware based keystore is available, the tokens can be made untransferable, so that only users who originally received the tokens can submit them. (b) Generalization techniques to select the level of anonymization of purchase receipts. 3. A mechanism to compute the distance between user profiles (expressed as feature sets of different data types) based on the size of the intersectionof the feature sets. 4. A privacy-preserving implicit authentication mechanism using the homomorphic properties of the Paillier cryptosystem, that protects the privacy of the sensitive data in the user's profile and ensures that the server does not learn anything about the user's behavior. 5. A second privacy-preserving implicit authentication with similar functionalities and higher speed compared to the previous one, based on the intersection of Bloom filters. While this mechanism provides slightly less protection than the previous one, its substantially better performance makes it ideal for implementation in existing authentication suites.

Masayuki Fukumitsu, Shingo Hasegawa, Junya Iwazaki, Masao Sakai · 5 authors

We propose a new secure online storage scheme based on an open P2P network without a central server. In the proposed scheme, attackers cannot detect target user data in the online storage because the user data is divided into some parts by the secret sharing, and they are distributed to P2P nodes via the anonymous communication. The proposed scheme can prevent the direct attack on the target user node because metadata for the reconstruction also hidden in the online storage, hence nothing remains in the user node. Even if the state of the P2P network varies over time between the storing and restoring operation, the proposed scheme ensures that the user can identify the target nodes which stored his metadata by utilizing the Blockchain technology with only memorable secure information for user authentication. Furthermore, a malicious node to attack on others can be detected and ruled out by the mutual monitoring among the nodes and the majority decision rule.

M. Suguna, R. Anusia, S. Mercy Shalinie, S. Renu Deepti

Mobile cloud computing (MCC) is a platform that allows mobile users to offload the computationally rigorous and storage demanding tasks on available cloud resources using wireless access. The major concern with MCC is the privacy of data. Mobile users give confidential information through the network, that if not safeguarded may lead to security issues. Identity Management (IDM) is the management of user identities, their authentication, and authorization in the cloud environment. The existing Consolidated Identity Management (CIDM) overcomes the network traffic interception in the traditional IDM but is prone to Identity theft in case of Identity Management Server (IDMS) compromise. This work is focused on the development of a Secure Identity Management (SIDM) that alleviates the attacks in the CIDM by using techniques that strengthens the authentication process and identity privacy. A secure IDM is developed using two-step authentication process which involves Zero Knowledge Proof (ZKP) and token verification. The proposed SIDM model reduces the consequences of Identity server compromise attack. There is a marginal increase in the communication overhead of SIDM compared to that of CIDM but it can be compromised to realize the benefits of identity privacy. The analysis of the experimental results shows that there is an overall increase of thirty percent in communication overhead when compared to CIDM.

Xavier Bultel, Jannik Dreier, Pascal Lafourcade, Malika More

At the main cryptography conference, CRYPTO, in 1989, Quisquater and colleagues published a paper showing how to explain the complex notion of zero-knowledge proof in a simpler way that children can understand. In the same line of work, this article presents simple and intuitive explanations of various modern security concepts and technologies, including symmetric encryption, public key encryption, homomorphic encryption, intruder models (CPA, CCA1, CCA2), and security properties (OW, IND, NM). The explanations given in this article may also serve in demystifying such complex security notions for non-expert adults.

Areej M. Abduldaim, Ahmed M. Ajaj

Authentication is a process by whichaparty (could be a person or intended computer) establishes its identity to another party. In private and public communication channels including the Internet, authentication is usually done via the use of login passwords. Knowing of the password is supposed to guarantee that the user is authentic. Online business and many other deals need a stricter authentication procedure. With this type of protocols, many cryptographic operations, such as; authentication, identification, key exchange, etc. are implemented without presenting any secret information through the commination process. In this article, a novel approach for zero knowledge protocol is proposed using different perspective. The category of ring theory is adopted to design a new algorithm for zero knowledge proof using the π-Armendariz rings. The key idea of our algebraic zero knowledge protocol is the condition in the definition of this ring, in addition to its the properties. The proposed approach used a secret polynomial whose coefficients are in a π-Armendariz ring, this polynomial is kept by the prover and the algebraic zero knowledge protocol does not reveal any information about the polynomial.