본 논문에서는 미리 알려진 임의의 다항식과 암호화된 다항식의 곱셈을 수행한 후, 해당 곱셈이 정당하게 수행되었음을 보이기 위해 증명자 (Prover)와 검증자 (Verifier)간의 다항식 상등성 영지식증명 (Zero-knowledge Proof) 프로토콜을 일반화할 수 있는 방법을 다룬다. 이를 위하여 다항식의 상등성을 증명하는 일반화된 프로토콜을 제시하고 랜덤오라클 (Random Oracle) 모델에서 안전성을 증명한다. 이러한 기법은 안전한 집합연산 기법을 포함하여 다항식에 기반한 다자간 연산기법 (Secure Multi-party Computation)에 적용될 수 있다. In this paper, we are interested in a generalization of zero-knowledge interactive protocols between prover and verifier, especially to show that the product of an encrypted polynomial and a random polynomial, but published by a secure commitment scheme was correctly computed by the prover. To this end, we provide a generalized protocol for proving that the resulting polynomial is correctly computed by an encrypted polynomial and another committed polynomial. Further we show that the protocol is also secure in the random oracle model. We expect that our generalized protocol can play a role of building blocks in implementing secure multi-party computation including private set operations.
The recent increase in reported incidents of surveillance and security breaches compromising users' privacy call into question the current model, in which third-parties collect and control massive amounts of personal data. Bit coin has demonstrated in the financial space that trusted, auditable computing is possible using a decentralized network of peers accompanied by a public ledger. In this paper, we describe a decentralized personal data management system that ensures users own and control their data. We implement a protocol that turns a block chain into an automated access-control manager that does not require trust in a third party. Unlike Bit coin, transactions in our system are not strictly financial -- they are used to carry instructions, such as storing, querying and sharing data. Finally, we discuss possible future extensions to block chains that could harness them into a well-rounded solution for trusted computing problems in society.
Notice of Violation of IEEE Publication Principles"Bitcoin for Smart Trading in Smart Grid"by M.T. Alam, H. Li, and A. Patidarin the Proceedings of the 21st IEEE International Workshop on Local and Metropolitan Area Networks, April 2015After careful and considered review of the content and authorship of this paper by a duly constituted expert committee, this paper has been found to be in violation of IEEE's Publication Principles.This paper duplicates original text from the papers cited below. The original text was copied with insufficient attribution (including appropriate references to the original author(s) and/or paper title) and without permission."Privacy-friendly Tasking and Trading of Energy in Smart Grids"by Tassos Dimitriou and Ghassan Karamein the Proceedings of the 28th Annual ACM Symposium on Applied Computing, March 2013"NRGcoin: Virtual Currency for Trading of Renewable Energy in Smart Grids,"by M. Mihaylov, S. Jurado, N. Avellana, K. Van Moffaert, I. M. de Abril and A. Nowein the Proceedings of the 11th International Conference on the European Energy Market, May 2014Privacy aware anonymous trading for smart grid using digital currency has received very low attention so far. In this paper, we analyze the possibility of Bitcoin serving as the user friendly and effective privacy aware trading currency to facilitate energy exchange for smart grid.
Paul Lajoie-Mazenc, Emmanuelle Anceaume, Gilles Guette, Thomas Sirvent · 5 authors
—Open and large-scale systems do not encourage their users to behave trustworthily, which may entail non-negligible risks when interacting with unknown users, for instance when buying an item on an e-commerce platform. Reputation mech-anisms reduce these risks by associating a reputation score to each user, summarizing their past behavior. To be useful to users, reputation mechanisms need to guarantee two main properties: the non-monotonicity of reputation scores, in order to exactly reflect the users' behavior, and the privacy of their users, so that the history of their transactions is not publicly available. We propose a distributed privacy-preserving reputation mechanism handling non-monotonic ratings. Our proposition relies on two distinct distributed third parties and on cryptographic tools, including zero-knowledge proofs of knowledge, anonymous proxy signatures, and verifiable secret sharing. We show that this proposal is computationally efficient, and thus practical. To the best of our knowledge, this solution is the first one that preserves users' privacy and handles both positive and negative ratings without relying on a central authority.
We give a new proof of the existence of public-coin concurrent zero-knowledge arguments for NP in the plain model under standard assumptions (the existence of one-to-one one-way func-tions and collision-resistant hash functions), which was originally proven by Goyal (STOC’13). In the proof, we use a new variant of the non-black-box simulation technique of Barak (FOCS’01). An important property of our simulation technique is that the simulator runs in a straight-line manner in the fully concurrent setting. Compared with the simulation technique of Goyal, which also has such a property, the analysis of our simulation technique is (arguably) simpler. This article is a minor revision of the version that appears in the proceedings of TCC 2015. 1
As for the security of digital signature,this paper takes advantage of the discrete logarithm problem and zeroknowledge proof protocol,combines with( t,n) threshold signature scheme and the identity of the participants,and presents a digital signature scheme based on secret sharing. In the scheme,there is no trusted key distribution center,and the secret share of the participants is generated by the participants themselves and can be used repeatedly,furthermore,the identity of the participants is generated by their own secret share. Only the public information can be updated,which will not affect the participants' secret share. Anyone can detect whether the dealer is cheating the participants or whether there is cheating between participants. Only the authorized subset client can represent group to sign; the generation and verification of the partial signature and group signature are effective. The discrete logarithm problem and zero-knowledge proof protocol guarantees the security of information transmission,which further improves the security of the scheme. The analysis indicates that the scheme is safe and efficient.
Can an exchange be “dark,” so that orders are not displayed, while simultaneously trustworthy, so that the execution of trades and flow of information occur as promised? SEC actions against dark pools suggest cause for concern, and regulators seem to be moving towards requiring more disclosure. Yet there is a clear tension: trading order information is widely exploited. Therefore, institutional investors have a strong interest in keeping pre-trade information about large trades hidden. Secrecy-preserving proofs of correctness can be used to build trust without revealing unnecessary information. By performing operations on obfuscated representations of orders (perhaps encrypted or otherwise hidden), a zero knowledge proof can be provided, allowing anyone to verify correctness of trades. Crucially, this can be done without revealing any information beyond this correctness. This technology can be usefully applied to construct provably trustworthy dark pools. Additional practical protocols relax the definition of “zero knowledge" to reveal limited information, providing necessary transparency for efficient market operation while limiting information that can be exploited by observers. Coupled with Trusted Computing hardware, these protocols can provide an excellent balance of practicality with secrecy
Abstract. Functional encryption (FE) enables sophisticated control over decryption rights in a multi-user scenario, while functional signature (FS) allows to enforce complex constraints on sign-ing capabilities. This paper introduces the concept of functional signcryption (FSC) that aims to provide the functionalities of both FE and FS in an unified cost-effective primitive. FSC provides a solution to the problem of achieving confidentiality and authenticity simultaneously in digital communication and storage systems involving multiple users with better efficiency compared to a sequential implementation of FE and FS. We begin by providing formal definition of FSC and formu-lating its security requirements. Next, we present a generic construction of this challenging primitive that supports arbitrary polynomial-size signing and decryption functions from known cryptographic building blocks, namely, indistinguishability obfuscation (IO) and statistically simulation-sound non-interactive zero-knowledge proof of knowledge (SSS-NIZKPoK). Finally, we exhibit a number of rep-resentative applications of FSC: (I) We develop the first construction of attribute-based signcryption (ABSC) supporting signing and decryption policies representable by general polynomial-size circuits from FSC. (II) We show how FSC can serve as a tool for building SSS-NIZKPoK system and IO, a result which in conjunction with our generic FSC construction can also be interpreted as establishing an equivalence between FSC and the other two fundamental cryptographic primitives.
Michele Ciampi, Giuseppe Persiano, Luisa Siniscalchi, Ivan Visconti
The Fiat-Shamir (FS) transform is a popular technique for obtaining practical zero-knowledge argument systems. The FS transform uses a hash function to generate, without any further over-head, non-interactive zero-knowledge (NIZK) argument systems from public-coin honest-verifier zero-knowledge (public-coin HVZK) proof systems. In the proof of zero knowledge, the hash function is modeled as a programmable random oracle (PRO). In TCC 2015, Lindell embarked on the challenging task of obtaining a similar transform with improved heuristic security. Lindell showed that, for several interesting and practical languages, there exists an efficient transform in the non-programmable random oracle (NPRO) model that also uses a common reference string (CRS). A major contribution of Lindell’s transform is that zero knowledge is proved without random oracles and this is an important step towards achieving efficient NIZK arguments in the CRS model without random oracles. In this work, we analyze the efficiency and generality of Lindell’s transform and notice a significant gap when compared with the FS transform. We then propose a new transform that aims at filling this gap. Indeed our transform is almost as efficient as the FS transform and can be applied to a broad class of public-coin HVZK proof systems. Our transform requires a CRS and an NPRO in the proof of soundness, similarly to Lindell’s transform. 1
We show a general connection between various types of statistical zero-knowledge (SZK) proof systems and (unconditionally secure) secret sharing schemes. Viewed through the SZK lens, we obtain several new results on secret-sharing: Characterizations: We obtain an almost-characterization of access structures for which there are secret-sharing schemes with an ecient sharing algorithm (but not necessarily ecient reconstruction). In particular, we show that for every language L2 SZKL (the class of languages that have statistical zero knowledge proofs with log-space veriers and simulators), a (monotonized) access structure associated with L has such a secretsharing scheme. Conversely, we show that such secret-sharing schemes can only exist for languages in SZK. Constructions: We show new constructions of secret-sharing schemes with ecient sharing and reconstruction for access structures that are in P, but are not known to be in NC, namely Bounded-Degree Graph Isomorphism and constant-dimensional lattice problems. In particular, this gives us the rst combinatorial access structure that is conjectured to be outside NC but has an ecient secret-sharing scheme. Previous such constructions (Beimel and Ishai; CCC 2001) were algebraic and number-theoretic in nature. Limitations: We show that universally-ecie nt secret-sharing schemes, where the complexity of computing the shares is a polynomial independent of the complexity of deciding the access structure, cannot exist for all (monotone languages in) P, unless there is a polynomial q such that P DSPACE(q(n)).
Matteo Maffei, Giulio Malavolta, Manuel Reinert, Dominique Schröder
Cloud storage has rapidly become a cornerstone of many IT infrastructures, constituting a seamless solution for the backup, synchronization, and sharing of large amounts of data. Putting user data in the direct control of cloud service providers, however, raises security and privacy concerns related to the integrity of outsourced data, the accidental or intentional leakage of sensitive information, the profiling of user activities and so on. Furthermore, even if the cloud provider is trusted, users having access to outsourced files might be malicious and misbehave. These concerns are particularly serious in sensitive applications like personal health records and credit score systems. To tackle this problem, we present GORAM, a cryptographic system that protects the secrecy and integrity of outsourced data with respect to both an untrusted server and malicious clients, guarantees the anonymity and unlink ability of accesses to such data, and allows the data owner to share outsourced data with other clients, selectively granting them read and write permissions. GORAM is the first system to achieve such a wide range of security and privacy properties for outsourced storage. In the process of designing an efficient construction, we developed two new, generally applicable cryptographic schemes, namely, batched zero-knowledge proofs of shuffle and an accountability technique based on chameleon signatures, which we consider of independent interest. We implemented GORAM in Amazon Elastic Compute Cloud (EC2) and ran a performance evaluation demonstrating the scalability and efficiency of our construction.
Abstract. Multiparty computation can be used for privacy-friendly out-sourcing of computations on private inputs of multiple parties. A com-putation is outsourced to several computation parties; if not too many are corrupted (e.g., no more than half), then they cannot determine the inputs or produce an incorrect output. However, in many cases, these guarantees are not enough: we need correctness even if all computation parties may be corrupted; and we need that correctness can be verified even by parties that did not participate in the computation. Protocols satisfying these additional properties are called “universally verifiable”. In this paper, we propose a new security model for universally verifi-able multiparty computation, and we present a practical construction, based on a threshold homomorphic cryptosystem. We also develop a multiparty protocol for jointly producing non-interactive zero-knowledge proofs, which may be of independent interest.
Gaby G. Dagher, Benedikt Bünz, Joseph Bonneau, Jeremy Clark · 5 authors
Bitcoin exchanges function like banks, securely holding their cus-tomers ’ bitcoins on their behalf. Several exchanges have suffered catastrophic losses with customers permanently losing their sav-ings. A proof of solvency demonstrates that the exchange controls sufficient reserves to settle each customer’s account. We introduce Provisions, a privacy-preserving proof of solvency whereby an ex-change does not have to disclose its Bitcoin addresses; total hold-ings 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.