Succinct non-interactive zero-knowledge arguments of knowledge (Zk-SNARKs) are needed in many applications. Unfortunately, all previous zk-SNARKs for interesting languages are either inefficient for the prover, or are non-adaptive and based on a commitment scheme that depends both on the prover's input and on the language, i.e., they are not commit-and-prove (CaP) SNARKs. We propose a proof-friendly extractable commitment scheme, and use it to construct prover-efficient adaptive CaP succinct zk-SNARKs for different languages, that can all reuse committed data. In new zk-SNARKs, the prover computation is dominated by a linear number of cryptographic operations. We use batch-verification to decrease the verifier's computation; importantly, batch-verification can be used also in QAP-based zk-SNARKs.
We present a practical construction of an additively homomorphic commitment scheme based on structured lattice assumptions, together with a zero-knowledge proof of opening knowledge. Our scheme is a design improvement over the previous work of Benhamouda et al. in that it is not restricted to being statistically binding. While it is possible to instantiate our scheme to be statistically binding or statistically hiding, it is most efficient when both hiding and binding properties are only computational. This results in approximately a factor of 4 reduction in the size of the proof and a factor of 6 reduction in the size of the commitment over the aforementioned scheme.
Benoît Libert, San Ling, Khoa Nguyen, Huaxiong Wang
Abstract An accumulator is a function that hashes a set of inputs into a short, constant-size string while preserving the ability to efficiently prove the inclusion of a specific input element in the hashed set. It has proved useful in the design of numerous privacy-enhancing protocols, in order to handle revocation or simply prove set membership. In the lattice setting, currently known instantiations of the primitive are based on Merkle trees, which do not interact well with zero-knowledge proofs. In order to efficiently prove the membership of some element in a zero-knowledge manner, the prover has to demonstrate knowledge of a hash chain without revealing it, which is not known to be efficiently possible under well-studied hardness assumptions. In this paper, we provide an efficient method of proving such statements using involved extensions of Stern’s protocol. Under the Small Integer Solution assumption, we provide zero-knowledge arguments showing possession of a hash chain. As an application, we describe new lattice-based group and ring signatures in the random oracle model. In particular, we obtain: (i) the first lattice-based ring signatures with logarithmic size in the cardinality of the ring and (ii) the first lattice-based group signature that does not require any GPV trapdoor and thus allows for a much more efficient choice of parameters.
Philipp Winter, Roya Ensafi, Karsten Loesing, Nick Feamster
Being a volunteer-run, distributed anonymity network, Tor is vulnerable to Sybil attacks. Little is known about real-world Sybils in the Tor network, and we lack practical tools and methods to expose Sybil attacks. In this work, we develop sybilhunter, the first system for detecting Sybil relays based on their appearance, such as configuration; and behavior, such as uptime sequences. We used sybilhunter's diverse analysis techniques to analyze nine years of archived Tor network data, providing us with new insights into the operation of real-world attackers. Our findings include diverse Sybils, ranging from botnets, to academic research, and relays that hijack Bitcoin transactions. Our work shows that existing Sybil defenses do not apply to Tor, it delivers insights into real-world attacks, and provides practical tools to uncover and characterize Sybils, making the network safer for its users.
Practical anonymous credential systems are generally built around sigma-protocol ZK proofs. This requires that credentials be based on specially formed signatures. Here we ask whether we can instead use a standard say, RSA, or ECDSA signature that includes formatting and hashing messages, as a credential, and still provide privacy. Existing techniques do not provide efficient solutions for proving knowledge of such a signature: On the one hand, ZK proofs based on garbled circuits Jawurek et al. 2013 give efficient proofs for checking formatting of messages and evaluating hash functions. On the other hand they are expensive for checking algebraic relations such as RSA or discrete-log, which can be done efficiently with sigma protocols.
We design new constructions obtaining the best of both worlds: combining the efficiency of the garbled circuit approach for non-algebraic statements and that of sigma protocols for algebraic ones. We then discuss how to use these as building-blocks to construct privacy-preserving credential systems based on standard RSA and ECDSA signatures.
Other applications of our techniques include anonymous credentials with more complex policies, the ability to efficiently switch between commitments and signatures in different groups, and secure two-party computation on committed/signed inputs.
Author(s): Tim Ruffing, Pedro Moreno-Sanchez, Aniket Kate Download: Paper (PDF) Date: 27 Feb 2017 Document Type: Reports Additional Documents: Slides Video Associated Event: NDSS Symposium 2017 Abstract: Starting with Dining Cryptographers networks (DC-nets), several peer-to-peer (P2P) anonymous communication protocols have been proposed. However, despite their strong anonymity guarantees, none of them have been employed in practice so far: Most … Continued
The new technology Bitcoin has got a lot of attention since it was presented in late 2008 and implemented early 2009. However, the main attention has been to the currency and not so much the underlying blockchain technology. This paper argues that we need to look beyond the currency and investigate the potential use of the blockchain technology to enable smarter governments by utilizing the secure, distributed, open, and inexpensive database technology. The technology is discussed in the perspective of an information infrastructure to investigate its full potential. After a literature review of Bitcoin publications, with a special emphasis on eGovernment literature, the paper presents a relevant use case highlighting the innovation potential of the new technology. The literature review shows that Bitcoin is absent from the e-Government literature. The use case presented shows that Bitcoin could be a promising technology for validating many types of persistent documents in public sector.
Author(s): Ethan Heilman, Leen Alshenibr, Foteini Baldimtsi, Alessandra Scafuro, Sharon Goldberg Download: Paper (PDF) Date: 27 Feb 2017 Document Type: Reports Associated Event: NDSS Symposium 2017 Abstract: This paper presents TumbleBit, a new unidirectional unlinkable payment hub that is fully compatible with today s Bitcoin protocol. TumbleBit allows parties to make fast, anonymous, off-blockchain payments through an untrusted … Continued
3 source records
Blockchain Technology Applications and Security
Internet Traffic Analysis and Secure E-voting
Advanced Steganography and Watermarking Techniques
Although Bitcoin is often perceived to be an anonymous currency, research has shown that a user’s Bitcoin transactions can be linked to compromise the user’s anonymity. We present solutions to the anonymity problem for both transactions on Bitcoin’s blockchain and off the blockchain (in so called micropayment channel networks). We use an untrusted third party to issue anonymous vouchers which users redeem for Bitcoin. Blind signatures and Bitcoin transaction contracts (aka smart contracts) ensure the anonymity and fairness during the bitcoin ↔ voucher exchange. Our schemes are practical, secure and anonymous.
In this paper, a new notion which we call verifiably anonymous data collection protocol is introduced and formalized in the client-server model where each respondent uses a web interface to communicate with a server operated by the data miner. A construction leveraging a combination of semantically secure double trap-door encryption and OR zero-knowledge proof system is proposed and analyzed, where data sent from a respondent Alice is first encrypted using her personal partial key; Alice then proves to the data miner that the resulted ciphertext is valid and is sent by one of respondents dynamically formed by the respondent without getting the consent or assistance of the other respondents. A rigorous proof of the soundness and the zero-knowledge property of our data collection protocol in the presence of malicious adversary is presented.
The Bitcoin system is an anonymous, decentralized crypto-currency. There are some deanonymizating techniques to cluster Bitcoin addresses and to map them to users' identifications in the two research directions of Analysis of Transaction Chain (ATC) and Analysis of Bitcoin Protocol and Network (ABPN). Nowadays, there are also some anonymization methods such as coin-mixing and transaction remote release (TRR) to cover the relationship between Bitcoin address and the user. This paper studies anonymization and de-anonymization technologies and proposes some directions for further research.
To strengthen the anonymity of Bitcoin, several centralized coin-mixing providers (mixers) such as BitcoinFog.com, BitLaundry.com, and Blockchain.info assist users to mix Bitcoins through CoinJoin transactions with multiple inputs and multiple outputs to uncover the relationship between them. However, these mixers know the output address of each user, such that they cannot provide true anonymity. This paper proposes a centralized coin-mixing algorithm based on an elliptic curve blind signature scheme (denoted as Blind-Mixing) that obstructs mixers from linking an input address with an output address. Comparisons among three blind signature based algorithms, Blind-Mixing, BlindCoin, and RSA Coin-Mixing, are conducted. It is determined that BlindCoin may be deanonymized because of its use of a public log. In RSA Coin-Mixing, a user's Bitcoins may be falsely claimed by another. In addition, the blind signature scheme of Blind-Mixing executes 10.5 times faster than that of RSA Coin-Mixing.
Gaby G. Dagher, Benedikt Bünz, Joseph Bonneau, Jeremy Clark · 5 authors
Bitcoin exchanges function like banks, securely holding customers' bitcoins on their behalf. Several exchanges have suffered catastrophic losses with customers permanently losing their savings. A proof of solvency demonstrates cryptographically that the exchange controls sufficient reserves to settle each customer's account. We introduce Provisions, a privacy-preserving proof of solvency whereby an exchange does not have to disclose its Bitcoin addresses; total holdings or liabilities; or any information about its customers. We also propose an extension which prevents exchanges from colluding to cover for each other's losses. We have implemented Provisions and it offers practical computation times and proof sizes even for a large Bitcoin exchange with millions of customers.
Matthew D. Sleiman, Adrian P. Lauf, Roman V. Yampolskiy
The Bit coin currency is steadily growing in popularity as an alternative to physical currencies. This paper presents an approach for utilizing the Bit coin system for creating permanent messages that are located on computers worldwide. By manipulating the amount field of Bit coin transactions, messages can be embedded into the Bit coin block chain. This approach was implemented by extending the Bit coin-Qt v0.7.2 application and the source code is freely available.