Subscribe to IACR Eprint feed
Updated: 9 hours 26 min ago

CrowdBC: A Blockchain-based Decentralized Framework for Crowdsourcing

Wed, 07/11/2018 - 20:21
Crowdsourcing systems which utilize the human intelligence to solve complex tasks have gained considerable interest and adoption in recent years. However, the majority of existing crowdsourcing systems rely on central servers, which are subject to the weaknesses of traditional trust-based model, such as single point of failure. They are also vulnerable to distributed denial of service (DDoS) and Sybil attacks due to malicious users involvement. In addition, high service fees from the crowdsourcing platform may hinder the development of crowdsourcing. How to address these potential issues has both research and substantial value. In this paper, we conceptualize a blockchain-based decentralized framework for crowdsourcing named CrowdBC, in which a requester’s task can be solved by a crowd of workers without relying on any third trusted institution, users’ privacy can be guaranteed and only low transaction fees are required. In particular, we introduce the architecture of our proposed framework, based on which we give a concrete scheme. We further implement a software prototype on Ethereum public test network with real-world dataset. Experiment results show the feasibility, usability and scalability of our proposed crowdsourcing system.

On the Universally Composable Security of OpenStack

Wed, 07/11/2018 - 18:04
OpenStack is the prevalent open-source, non-proprietary package for managing cloud services and data centers. It is highly complex and consists of multiple inter-related components which are developed by separate, loosely coordinated groups. We initiate an effort to provide a rigorous and holistic security analysis of OpenStack. Our analysis has the following key features: -It is user-centric: It stresses the security guarantees given to users of the system, in terms of privacy, correctness, and timeliness of the services. -It provides defense in depth: It considers the security of OpenStack even when some of the components are compromised. This departs from the traditional design approach of OpenStack, which assumes that all services are fully trusted. -It is modular: It formulates security properties for individual components and uses them to assert security properties of the overall system. We base our modeling and security analysis in the universally composable (UC) security framework, which has been so far used mainly for analyzing security of cryptographic protocols. Indeed, demonstrating how the UC framework can be used to argue about security-sensitive systems which are mostly non-cryptographic in nature is another main contribution of this work. Our analysis covers only a number of core components of OpenStack. Still, it uncovers some basic and important security trade-offs in the design. It also naturally paves the way to a more comprehensive analysis of OpenStack.

Security Definitions For Hash Functions: Combining UCE and Indifferentiability

Wed, 07/11/2018 - 11:26
Hash functions are one of the most important cryptographic primitives, but their desired security properties have proven to be remarkably hard to formalize. To prove the security of a protocol using a hash function, nowadays often the random oracle model (ROM) is used due to its simplicity and its strong security guarantees. Moreover, hash function constructions are commonly proven to be secure by showing them to be indifferentiable from a random oracle when using an ideal compression function. However, it is well known that no hash function realizes a random oracle and no real compression function realizes an ideal one. As an alternative to the ROM, Bellare et al. recently proposed the notion of universal computational extractors (UCE). This notion formalizes that a family of functions ``behaves like a random oracle'' for ``real-world'' protocols while avoiding the general impossibility results. However, in contrast to the indifferentiability framework, UCE is formalized as a multi-stage game without clear composition guarantees. As a first contribution, we introduce context-restricted indifferentiability (CRI), a generalization of indifferentiability that allows us to model that the random oracle does not compose generally but can only be used within a well-specified set of protocols run by the honest parties, thereby making the provided composition guarantees explicit. We then show that UCE and its variants can be phrased as a special case of CRI. Moreover, we show how our notion of CRI leads to generalizations of UCE. As a second contribution, we prove that the hash function constructed by Merkle-Damgard satisfies one of the well-known UCE variants, if we assume that the compression function satisfies one of our generalizations of UCE, basing the overall security on a plausible assumption. This result further validates the Merkle-Damgard construction and shows that UCE-like assumptions can serve both as a valid reference point for modular protocol analyses, as well as for the design of hash functions, linking those two aspects in a framework with explicit composition guarantees.

Multiparty Non-Interactive Key Exchange and More From Isogenies on Elliptic Curves

Tue, 07/10/2018 - 08:46
We describe a framework for constructing an efficient non-interactive key exchange (NIKE) protocol for n parties for any n >= 2. Our approach is based on the problem of computing isogenies between isogenous elliptic curves, which is believed to be difficult. We do not obtain a working protocol because of a missing step that is currently an open problem. What we need to complete our protocol is an efficient algorithm that takes as input an abelian variety presented as a product of isogenous elliptic curves, and outputs an isomorphism invariant of the abelian variety. Our framework builds a cryptographic invariant map, which is a new primitive closely related to a cryptographic multilinear map, but whose range does not necessarily have a group structure. Nevertheless, we show that a cryptographic invariant map can be used to build several cryptographic primitives, including NIKE, that were previously constructed from multilinear maps and indistinguishability obfuscation.

Efficient Logistic Regression on Large Encrypted Data

Tue, 07/10/2018 - 04:37
Machine learning on encrypted data is a cryptographic method for analyzing private and/or sensitive data while keeping privacy. In the training phase, it takes as input an encrypted training data and outputs an encrypted model without using the decryption key. In the prediction phase, it uses the encrypted model to predict results on new encrypted data. In each phase, no decryption key is needed, and thus the privacy of data is guaranteed while the underlying encryption is secure. It has many applications in various areas such as finance, education, genomics, and medical field that have sensitive private data. While several studies have been reported on the prediction phase, few studies have been conducted on the training phase due to the inefficiency of homomorphic encryption (HE), leaving the machine learning training on encrypted data only as a long-term goal. In this paper, we propose an efficient algorithm for logistic regression on encrypted data, and evaluate our algorithm on real financial data consisting of 422,108 samples over 200 features. Our experiment shows that an encrypted model with a sufficient Kolmogorov Smirnow statistic value can be obtained in $\sim$17 hours in a single machine. We also evaluate our algorithm on the public MNIST dataset, and it takes $\sim$2 hours to learn an encrypted model with 96.4% accuracy. Considering the inefficiency of HEs, our result is encouraging and demonstrates the practical feasibility of the logistic regression training on large encrypted data, for the first time to the best of our knowledge.

Public Accountability vs. Secret Laws: Can They Coexist?

Mon, 07/09/2018 - 21:58
Post 9/11, journalists, scholars and activists have pointed out that secret laws --- a body of law whose details and sometime mere existence is classified as top secret --- were on the rise in all three branches of the US government due to growing national security concerns. Amid heated current debates on governmental wishes for exceptional access to encrypted digital data, one of the key issues is: which mechanisms can be put in place to ensure that government agencies follow agreed-upon rules in a manner which does not compromise national security objectives? This promises to be especially challenging when the rules, according to which access to encrypted data is granted, may themselves be secret. In this work we show how the use of cryptographic protocols, and in particular, the use of zero-knowledge proofs can ensure accountability and transparency of the government in this extraordinary, seemingly deadlocked, setting. We propose an efficient record-keeping infrastructure with versatile publicly verifiable audits that preserve perfect (information-theoretic) secrecy of record contents as well as of the rules by which the records are attested to abide. Our protocol is based on existing blockchain and cryptographic tools including commitments and zero-knowledge SNARKs, and satisfies the properties of indelibility (i.e., no back-dating), perfect data secrecy, public auditability of secret data with secret laws, accountable deletion, and succinctness. We also propose a variant scheme where entities can be required to pay fees based on record contents (e.g., for violating regulations) while still preserving data secrecy. Our scheme can be directly instantiated on the Ethereum blockchain (and a simplified version with weaker guarantees can be instantiated with Bitcoin).

Fast Secure Matrix Multiplications over Ring-Based Homomorphic Encryption

Mon, 07/09/2018 - 21:56
Secure matrix computation is one of the most fundamental and useful operations for statistical analysis and machine learning with protecting the confidentiality of input data. Secure computation can be achieved by homomorphic encryption, supporting meaningful operations over encrypted data. HElib is a software library that implements the Brakerski-Gentry-Vaikuntanathan (BGV) homomorphic scheme, in which secure matrix-vector multiplication is proposed for operating matrices. Recently, Duong et al. (Tatra Mt. Publ. 2016) proposed a new method for secure single matrix multiplication over a ring-LWE-based scheme. In this paper, we generalize Duong et al.'s method for secure multiple matrix multiplications over the BGV scheme. We also implement our method using HElib and show that our method is much faster than the matrix-vector multiplication in HElib for secure matrix multiplications.

Exploring Deployment Strategies for the Tor Network

Mon, 07/09/2018 - 21:49
In response to upcoming performance and security challenges of anonymity networks like Tor, it will be of crucial importance to be able to develop and deploy performance improvements and state-of-the-art countermeasures. In this paper, we therefore explore different deployment strategies and review their applicability to the Tor network. In particular, we consider flag day, dual stack, translation, and tunneling strategies and discuss their impact on the network, as well as common risks associated with each of them. In a simulation based evaluation, which stems on historical data of Tor, we show that they can practically be applied to realize significant protocol changes in Tor. However, our results also indicate that during the transitional phase a certain degradation of anonymity is unavoidable with current viable deployment strategies.

Capsule: A Protocol for Secure Collaborative Document Editing

Mon, 07/09/2018 - 15:17
Today's global society strongly relies on collaborative document editing, which plays an increasingly large role in sensitive workflows. While other collaborative venues, such as secure messaging, have seen secure protocols being standardized and widely implemented, the same cannot be said for collaborative document editing. Popular tools such as Google Docs, Microsoft Office365 and Etherpad are used to collaboratively write reports and other documents which are frequently sensitive and confidential, in spite of the server having the ability to read and modify text undetected. Capsule is the first formalized and formally verified protocol standard that addresses secure collaborative document editing. Capsule provides confidentiality and integrity on encrypted document data, while also guaranteeing the ephemeral identity of collaborators and preventing the server from adding new collaborators to the document. Capsule also, to an extent, prevents the server from serving different versions of the document being collaborated on. In this paper, we provide a full protocol description of Capsule. We also provide formal verification results on the Capsule protocol in the symbolic model. Finally, we present a full software implementation of Capsule, which includes a novel formally verified signing primitive implementation.

Information-theoretic Indistinguishability via the Chi-squared Method

Mon, 07/09/2018 - 11:46
Proving tight bounds on information-theoretic indistinguishability is a central problem in symmetric cryptography. This paper introduces a new method for information-theoretic indistinguishability proofs, called ``the chi-squared method''. At its core, the method requires upper-bounds on the so-called $\chi^2$ divergence (due to Neyman and Pearson) between the output distributions of two systems being queries. The method morally resembles, yet also considerably simplifies, a previous approach proposed by Bellare and Impagliazzo (ePrint, 1999), while at the same time increasing its expressiveness and delivering tighter bounds. We showcase the chi-squared method on some examples. In particular: (1) We prove an optimal bound of $q/2^n$ for the XOR of two permutations, and our proof considerably simplifies previous approaches using the $H$-coefficient method, (2) we provide improved bounds for the recently proposed encrypted Davies-Meyer PRF construction by Cogliati and Seurin (CRYPTO '16), and (3) we give a tighter bound for the Swap-or-not cipher by Hoang, Morris, and Rogaway (CRYPTO '12).

Mitigating the One-Use Restriction in Attribute-Based Encryption

Mon, 07/09/2018 - 09:05
We present a key-policy attribute-based encryption scheme that is adaptively secure under a static assumption and is not directly affected by an attribute "one-use restriction." Our construction improves upon the only other such scheme (Takashima '17) by mitigating its downside of a ciphertext size that is dependent on the maximum size of any supported attribute set.

An Efficient NIZK Scheme for Privacy-Preserving Transactions over Account-Model Blockchain

Mon, 07/09/2018 - 06:28
We introduce the abstract framework of decentralized smart contracts system with balance and transaction amount hiding property under the ACCOUNT architecture. To build a concrete system with such properties, we utilize a homomorphic public key encryption scheme and construct a highly efficient non-interactive zero knowledge (NIZK) argument based upon the encryption scheme to ensure the validity of the transactions. Our NIZK scheme is perfect zero knowledge in the common reference string model, while its soundness holds in the random oracle model. Compared to previous similar constructions, our proposed NIZK argument dramatically improves the time efficiency in generating a proof, at the cost of relatively longer proof size.

A New Blind ECDSA Scheme for Bitcoin Transaction Anonymity

Sun, 07/08/2018 - 20:28
In this paper, we consider a scenario where a bitcoin liquidity provider sells bitcoins to clients. When a client pays for a bitcoin online, the provider is able to link the client's payment information to the bitcoin sold to that client. To address the clients' privacy concern, it is desirable for the provider to perform the bitcoin transaction with blind signatures. However, existing blind signature schemes are incompatible with the Elliptic Curve Digital Signature Algorithm (ECDSA) which is used by most of the existing bitcoin protocol, thus cannot be applied directly in Bitcoin. In this paper, we propose a new blind signature scheme that allows generating a blind signature compatible with the standard ECDSA. Afterwards, we make use of the new scheme to achieve bitcoin transaction anonymity. The new scheme is built on a variant of the Paillier cryptosystem and its homomorphic properties. As long as the modified Paillier cryptosystem is semantically secure, the new blind signature scheme has blindness and unforgeability.

Ciphertext-Only Attacks against Compact-LWE Submitted to NIST PQC Project

Sun, 07/08/2018 - 08:08
In 2017, Liu, Li, Kim and Nepal submitted a new public-key encryption scheme Compact-LWE to NIST as a candidate of the standard of post-quantum cryptography. Compact-LWE features its structure similar to LWE, but with different distribution of errors. Liu, Li, Kim and Nepal thought that the special error distribution they employed would protect Compact-LWE from the known lattice-based attacks. Furthermore, they recommended a set of small parameters to improve the efficiency of Compact-LWE and claimed it can offer 192 bits of security. However, in this paper, we show that Compact-LWE is not secure with recommended parameters by presenting two efficient ciphertext-only attacks against it. \begin{itemize} \item The first one is to recover the equivalent private keys just from the public keys. By exploiting the special structure of Compact-LWE, employing some known skills such as orthogonal-lattice technique, and also developing some new techniques, we finally recovered the equivalent private keys for more than 80\% of the random generated instances in our experiments. \item The second one is to recover the corresponding message given the public keys and a ciphertext. Note that any short enough solutions of corresponding inhomogeneous linear systems can be used to decrypt a ciphertext equivalently. We recovered all the messages without knowing the private keys in our experiments. \end{itemize}

A Cryptographic Look at Multi-Party Channels

Sat, 07/07/2018 - 14:10
Cryptographic channels aim to enable authenticated and confidential communication over the Internet. The general understanding seems to be that providing security in the sense of authenticated encryption for every (unidirectional) point-to-point link suffices to achieve this goal. As recently shown (in FSE17/ToSC17), however, the security properties of the unidirectional links do not extend, in general, to the bidirectional channel as a whole. Intuitively, the reason for this is that the increased interaction in bidirectional communication can be exploited by an adversary. The same applies, a fortiori, in a multi-party setting where several users operate concurrently and the communication develops in more directions. In the cryptographic literature, however, the targeted goals for group communication in terms of channel security are still unexplored. Applying the methodology of provable security, we fill this gap by defining exact (game-based) authenticity and confidentiality goals for broadcast communication, and showing how to achieve them. Importantly, our security notions also account for the causal dependencies between exchanged messages, thus naturally extending the bidirectional case where causal relationships are automatically captured by preserving the sending order. On the constructive side we propose a modular and yet efficient protocol that, assuming only point-to-point links between users, leverages (non-cryptographic) broadcast and standard cryptographic primitives to a full-fledged broadcast channel that provably meets the security notions we put forth.

On the Menezes-Teske-Weng's conjecture

Sat, 07/07/2018 - 12:31
In 2003, Alfred Menezes, Edlyn Teske and Annegret Weng presented a conjecture on properties of the solutions of a type of quadratic equation over the binary extension fields, which had been convinced by extensive experiments but the proof was unknown until now. We prove that this conjecture is correct. Furthermore, using this proved conjecture, we have completely determined the null space of a class of linear polynomials.

Blockchained Post-Quantum Signatures

Sat, 07/07/2018 - 12:25
Inspired by the blockchain architecture and existing Merkle tree based signature schemes, we propose BPQS, an extensible post-quantum (PQ) resistant digital signature scheme best suited to blockchain and distributed ledger technologies (DLTs). One of the unique characteristics of the protocol is that it can take advantage of application-specific chain/graph structures in order to decrease key generation, signing and verification costs as well as signature size. Compared to recent improvements in the field, BPQS outperforms existing hash-based algorithms when a key is reused for reasonable numbers of signatures, while it supports a fallback mechanism to allow for a practically unlimited number of signatures if required. To our knowledge, this is the first signature scheme that can utilise an existing blockchain or graph structure to reduce the signature cost to one OTS, even when we plan to sign many times. This makes existing many-time stateful signature schemes obsolete for blockchain applications. We provide an open source implementation of the scheme and benchmark it.

Platform-independent Secure Blockchain-Based Voting System

Sat, 07/07/2018 - 12:24
Cryptographic techniques are employed to ensure the security of voting systems in order to increase its wide adoption. However, in such electronic voting systems, the public bulletin board that is hosted by the third party for publishing and auditing the voting results should be trusted by all participants. Recently a number of blockchain-based solutions have been proposed to address this issue. However, these systems are impractical to use due to the limitations on the voter and candidate numbers supported, and their security framework, which highly depends on the underlying blockchain protocol and suffers from potential attacks (e.g., force-abstention attacks). To deal with two aforementioned issues, we propose a practical platform-independent secure and verifiable voting system that can be deployed on any blockchain that supports an execution of a smart contract. Verifiability is inherently provided by the underlying blockchain platform, whereas cryptographic techniques like Paillier encryption, proof-of-knowledge, and linkable ring signature are employed to provide a framework for system security and user-privacy that are independent from the security and privacy features of the blockchain platform. We analyse the correctness and coercion-resistance of our proposed voting system. We employ Hyperledger Fabric to deploy our voting system and analyse the performance of our deployed scheme numerically.

Efficient Collision Attack Frameworks for RIPEMD-160

Sat, 07/07/2018 - 11:23
In this paper, we re-consider the connecting techniques to find colliding messages, which is achieved by connecting the middle part with the initial part. To obtain the best position of middle part, we propose two principles even when the case is not ideal. Then, we reviewed the searching strategy to find a differential path presented at Asiacrypt 2017, we observe some useful characteristics of the path which is not used in their work. To fully capture the characteristics of the differential path discovered by the searching strategy, we find an efficient attack framework under the guidance of the two principles, which in turn helps improve the searching strategy. Under our efficient attack framework, we easily improve the collision attack on 30-step RIPEMD-160 by a factor of $2^{13}$. And we believe that the collision attack can be further improved under this efficient framework if the differential path is discovered by taking the new strategies into consideration. For some interest, we also consider an opposite searching strategy and propose another efficient attack framework special for the differential path discovered by the new searching strategy. Under this new framework, we find we can control one more step than that special for the original searching strategy. Therefore, we expect that we can obtain better collision attack by adopting the new searching strategy and attack framework. Moreover, combining with the searching tool, we may give a tight upper bound of steps to mount collision attack on reduced RIPEMD-160 when adopting the two searching strategies.

Designing Proof of Transaction Puzzles for Cryptocurrency

Fri, 07/06/2018 - 21:55
One of the Bitcoin's innovations is the Proof of Work puzzle (aka scratch-off puzzle) as a consensus protocol for anonymous networks without pre-established PKI. Bitcoins based on the Proof of Work puzzle have been harshly blamed today for problems such as energy wasted and not easily scalable. In this paper, we construct a novel Proof of Transaction(PoT) puzzle, and prove that PoT puzzle satisfies the basic construction conditions of scratch-off puzzle. We also show construction of PoTcoin as application. To reduce the network load we use sequential aggregate signature. PoTcoin has many advantage but not limited as strengthening the network topology, promoting currency circulation, anti-outsourcing computing and environment-friendly.

Pages

IACR Eprint