The Bitcoin network of decentralized payment transactions has attracted a lot of attention from both Internet users and researchers in recent years. Bitcoin utilizes a peer-to-peer network to issue anonymous payment transactions between different users. In the currently used Bitcoin clients, the full transaction history is available at each node of the network to prevent double spending without the need for a central authority, forming a valuable source for empirical research on network structure, network dynamics, and the implied anonymity challenges, as well as guidance on the future evolution of complex payment systems. We found dynamical effects of which some increase anonymity while others decrease it. Most importantly, several parameters of the Bitcoin transaction graph seem to have become stationary over the last 12–18 months. We discuss the implications.
Ian Miers, Christina Garman, Matthew Green, Aviel D. Rubin
Bitcoin is the first e-cash system to see widespread adoption. While Bitcoin offers the potential for new types of financial interaction, it has significant limitations regarding privacy. Specifically, because the Bitcoin transaction log is completely public, users' privacy is protected only through the use of pseudonyms. In this paper we propose Zerocoin, a cryptographic extension to Bitcoin that augments the protocol to allow for fully anonymous currency transactions. Our system uses standard cryptographic assumptions and does not introduce new trusted parties or otherwise change the security model of Bitcoin. We detail Zerocoin's cryptographic construction, its integration into Bitcoin, and examine its performance both in terms of computation and impact on the Bitcoin protocol.
Blind signature-based electronic voting is the simplest paradigm for implementing remote voting platforms due to the fact that it does not employ complicated zero-knowledge proofs. Unfortunately, the existence of a trusted entity (the "Authentication Server") that, in case of corruption, would be able to cast indistinguishable fake votes reduces the acceptance of the paradigm in non fully trusted environments. Trust on the system can be increased by splitting this entity into of a set of parties that are unlikely to collaborate in a dishonest manner. Nevertheless, this technique increases the risk of failure of some of them causing a service interruption during the voting period. Better fault tolerance is provided by proposals which permit to anticipate the interaction with the distributed authentication server before the voting period begins, so that, in case of failure, there is a broad time margin for system restoration. Previous proposals following this approach have been proven to be cryptographically weak or just provide individual verifiability. In this paper, a system that employs blind certificates is presented. Unlike previous proposals, it provides universal verifiability and permits to detect double voting without putting voters' privacy at risk.
최근 스마트 기기는 결제, 할인쿠폰 등 각종 기능을 제공하는 수단으로 진화되면서 통신과 금융이 융합된 모바일 NFC 서비스의 시장이 급성장할 것으로 전망되고 있다. 특히 모바일 NFC 결제 서비스 시장의 활성화가 예상됨에 따라 모바일 NFC 결제 서비스는 국내 외적으로 널리 주목받고 있다. 하지만 이에 따른 NFC 기술 활용 증가로 개인정보 이용이 늘면서 침해요소 또한 증가하고 있다. 최근 한국인터넷진흥원에서 발표한 "NFC 개인정보보호 대책 최종보고서"에 따르면 개인정보 암호화를 부분적으로 미지원하거나 불필요한 개인정보의 과도한 수집 및 저장 등이 문제점으로 제기되었으며 Google사의 Google Wallet 서비스의 개인정보 유출 사고 또한 이러한 문제점을 뒷받침하는 근거가 되고 있다. 본 논문에서는 기존에 서비스되고 있는 NFC 모바일 결제 서비스 상에서 결제정보의 이동 경로 별 결제 기술의 위협을 분석하고 OTA(Over the Air) 상에서 안전한 정보교환을 위한 NTRU 기반 상호인증 기법과 사용자와 은행 간의 결제 단계에서 결제정보를 직접적으로 사용하지 않고 결제자를 증명할 수 있는 NTRU기반 영지식 증명 기법에 대해 제안한다. Recently, smart devices for various services have been developed using converged telecommunications, and the markets for near field communication (NFC) mobile services is expected to grow rapidly. In particular, the realization of mobile NFC payment services is expected to go commercial, and it is widely attracting attention both on a domestic and global level. However, this realization would increase privacy infringement, as personal information is extensively used in the NFC technology. One example of such privacy infringement would be the case of the Google wallet service. In this paper, we propose an mutual authentication scheme based on NTRU for secure channel in OTA and an zero-knowledge proof scheme NTRU based on for protecting user information in NFC mobile payment systems without directly using private financial information of the user.
Bid validity proof and verification is an efficiency bottleneck and privacy drawback in homomorphic e‐auction. The existing bid validity proof technique is inefficient and only achieves honest‐verifier zero knowledge (ZK). In this study, an efficient proof and verification technique is proposed to guarantee bid validity in homomorphic e‐auction. The new proof technique is mainly based on hash function operations and only needs a very small number of costly public key cryptographic operations. Moreover, it can handle untrusted verifiers and achieve perfect ZK. As a result, efficiency and privacy of homomorphic e‐auction applications are significantly improved. To the best of authors’ knowledge, it proof technique is the first to handle untrusted verifiers in e‐auction applications.
El termino privacidad engloba un amplio campo de investigacion compuesto por diferentes areas. Esta tesis doctoral se centra en dos de ellas. La primera son las comunicaciones privadas en grupos restringidos, o secure multicast. Un grupo de participantes desea mantener comunicaciones de forma que ningun oyente externo al grupo sea capaz de interpretar la informacion transmitida. Este problema tiene diferentes aplicaciones como servicios pay-per-view en plataformas de streaming multimedia o multiconferencias privadas en el ambito empresarial e incluso militar.
La solucion estandar al problema consiste en establecer una clave de cifrado simetrico comun al grupo, llamada session key o clave de sesion, con la cual todos los participantes cifran o descifran la informacion transmitida. Sin embargo, las implicaciones practicas de esta solucion no son triviales por dos motivos: el uso de una misma clave de cifrado durante largo tiempo la hace vulnerable a ataques, y los cambios en la composicion del grupo (un fenomeno conocido como churn), de ocurrir, fuerzan a cambiar la clave despues de cada entrada o salida de participantes. Por ello es necesario refrescar la clave de sesion periodicamente, y en especial despues de cada cambio en la composicion del grupo. El capitulo 1 introduce mas formalmente estos conceptos y da al lector una vision mas amplia del problema.
Las propuestas de secure multicast existentes pueden clasificarse en tres categorias dependiendo de como realicen la renovacion de la clave de sesion: centralizadas, descentralizadas y distribuidas. En las primeras, una entidad central, el Key Server o Servidor de Claves, esta a cargo del establecimiento de nuevas claves de sesion y la distribucion a toda la red. Esta es la forma mas sencilla y popular de resolver el problema a cambio de soportar tamanos de grupo limitados. La segunda categoria, las propuestas descentralizadas, es una extension natural de la primera: para conseguir mayores tamanos de grupo los participantes se distribuyen en subgrupos disjuntos, cada uno gestionado por un Servidor de Claves secundario mediante secure multicast centralizado. Finalmente, en las propuestas distribuidas no existe una unica entidad a cargo del proceso de renovacion de claves. En su lugar, todos los participantes colaboran en la generacion del material criptografico cada vez que sea necesario. Los esquemas distribuidos ofrecen por tanto mas fiabilidad al evitar un unico punto de fallo a cambio de una escalabilidad muy limitada.
Esta tesis se enfoca hacia la categoria centralizada debido a su importancia como solucion en si misma y como pilar de construcciones descentralizadas. El capitulo 2 realiza una amplia revision del estado del arte, y el capitulo 3 presenta (i) un nuevo esquema centralizado, discute sus propiedades y pone a prueba su rendimiento. Los fundamentos matematicos del esquema se basan principalmente en el Algoritmo Extendido de Euclides, gracias al cual tambien hemos desarrollado (ii) una solucion de autenticacion para los mensajes de renovacion provenientes del Servidor de Claves, y (iii) una prueba de conocimiento cero (zero-knowledge proof) que permite a miembros legales del grupo verificar la legalidad de otros.
Los tres esquemas han sido ya objeto de criptoanalisis por parte de otros investigadores, los cuales han hallado algunas vulnerabilidades en el segundo y tercero (autenticacion de mensajes y prueba de conocimiento cero). Sin embargo, el esquema principal de secure multicast sigue siendo seguro a dia de hoy. Mencionaremos las vulnerabilidades encontradas por el criptoanalisis, asi como soluciones propuestas por otro conjunto de investigadores. Dichas soluciones no son merito del autor de esta tesis y se muestran aqui con el unico proposito de dar al lector una perspectiva completa.
La segunda parte de esta tesis se centra en computaciones distribuidas con preservacion de privacidad. En este caso, los nodos que conforman una red desean seguir la evolucion de una variable global a la que todo el mundo contribuye. Sin embargo, las contribuciones individuales hechas por cada nodo no deberian ser conocidas por los demas. Un ejemplo tipico, muy ilustrativo, es el Problema de los millonarios: dos millonarios quieren saber quien es mas rico sin revelar la cuantia de sus fortunas. Situaciones similares, especialmente aquellas que involucran un numero indeterminado de participantes y el computo de otras funciones, son utiles a la hora realizar agregacion de datos, calculo de confianza y mineria de datos, operaciones todas de creciente interes.
El problema de la preservacion de privacidad en computacion distribuida no es nuevo: existen ya un amplio numero de soluciones. Sin embargo, la mayoria de ellas es aplicable solo a un grupo reducido de participantes y no suelen ser tolerantes a fallos. El autor de esta tesis cree que esas dos caracteristicas van a cobrar mucha importancia con el tiempo debido a la popularizacion de diferentes tipos de redes. Por ejemplo, en redes peer-to-peer los nodos pueden entrar y salir de la red de forma inesperada (tal y como hemos comentado previamente para los escenarios de secure multicast), y los calculos no deberian detenerse o reiniciarse por ello. En redes de sensores (wireless sensor networks) el medio de transmision es propenso a fallos, y tambien los participantes pueden aparecer y desaparecer sin previo aviso. El capitulo 4 repasa de la literatura disponible en este campo.
En vista de la importancia de la tolerancia a fallos y al dinamismo de las redes, en el capitulo 5 hemos desarrollado un algoritmo de computo distribuido iterativo con preservacion de privacidad enfocado a redes peer-to-peer que se adapta a ese tipo de situaciones practicas. Nuestro algoritmo sigue un modelo de paso de mensajes asincrono que tolera churn y perdida o retraso de mensajes de forma natural, en oposicion a los algoritmos sincronos. Para demostrarlo, lo comparamos con una propuesta sincrona parecida tomada de la literatura. Creemos que nuestro algoritmo es el primero de este tipo.
La literatura en este campo considera dos modelos de adversario a tener en cuenta: semi-honestos y maliciosos. Los primeros analizan cualquier dato a su disposicion para obtener informacion privada de otros participantes, pero se asume que ejecutan el protocolo de forma correcta. De los segundos se espera que lleven a cabo acciones arbitrarias para obtener la informacion privada deseada, tales como enviar mensajes falsos. Nuestro algoritmo tolera adversarios semi-honestos.
A modo de resumen de lo anterior, la presente tesis (i) analiza el estado del arte en algoritmos de secure multicast centralizado, (ii) presenta una solucion de secure multicast centralizada con bajos requerimientos computacionales asi como algoritmos complementarios para la autenticacion de los mensajes de refresco y los miembros, (iii) repasa el estado del arte en computacion distribuida con preservacion de privacidad y (iv) presenta un algoritmo iterativo asincrono para computacion distribuida con preservacion de privacidad que tolera churn y fallos en el envio de mensajes.
Lately,Canard et al.(CANARD S,JAMBERT A.Untraceability and profiling are not mutually exclusive [C]// TrustBus 2010:Proceedings of the 7th International Conference on Trust,Privacy and Security in Digital Business,LNCS 6264.Berlin:Springer-Verlag,2010:117-128) introduced the notion of multi-service subscription and proposed several instantiations.Unfortunately,their systems only satisfied a weaker variant of anonymity called revocable-anonymity and they were not fit for services.To this end,a revised multi-service subscription system was put forward to extending Canard et al's system.The new system achieved pay-per-use subscriptions by incorporating the anonymous payment system raised by Liu et al.(LIU J K,AU M H,SUSILO W,et al.Enhancing location privacy for electric vehicles(at the right time).[2012-08-01].http://eprint.iacr.org/2012/342).To allow users to prove in zero-knowledge that their account balance is enough for making a payment for the required access,it also utilized the Peng-Bao range proof for small ranges.Furthermore,it was constructed on several 4-round perfect zero-knowledge proofs of knowledge,which were obtained by applying a technique by Cramer et al.to the underlying Sigma-protocols.Compared with typical systems in the literature,the new solution gains advantages in terms of security.Concretely,it can be proved secure in the standard model.Moreover,it matches the strongest level of three crucial security notions,such as inseparability for spendable tokens,anonymity for users,and zero-knowledge for underlying proof systems.
Georg Neugebauer, Lucas Brutschy, Ulrike Meyer, Susanne Wetzel
Abstract. The problem of fair and privacy-preserving ordered set reconciliation arises in a variety of applications like auctions, e-voting, and appointment reconciliation. While several multi-party protocols have been proposed that solve this problem in the semi-honest model, there are no multi-party protocols that are secure in the malicious model so far. In this paper, we close this gap. Our newly proposed protocols are shown to be secure in the malicious model based on a variety of novel non-interactive zero-knowledge-proofs. We describe the implementation of our protocols and evaluate their performance in comparison to protocols solving the problem in the semi-honest case.
Abstract. Verifiably encrypted signatures (VES) are signatures encrypted by a public key of a trusted third party and we can verify their validity without decryption. This paper proposes a new VES scheme which is secure under the decisional linear (DLIN) assumption in the standard model. We also propose new obfuscators for encrypted signatures (ES) and encrypted VES (EVES) which are secure under the DLIN assump-tion. All previous efficient VES schemes in the standard model are either secure under standard assumptions (such as the computational Diffie-Hellman assumption) with large verification (or secret) keys or secure under (non-standard) dynamic q-type assumptions (such as the q-strong Diffie-Hellman extraction assumption) with short verification keys. Our construction is the first efficient VES scheme with short verification (and secret) keys secure under a standard assumption (DLIN). As by-products of our VES scheme, we construct new obfuscators for ES/EVES based on our new VES scheme. They are more efficient than previous obfuscators with respect to the public key size. Previous ob-fuscators for EVES are secure under non-standard assumption and use zero-knowledge (ZK) proof systems and Fiat-Shamir heuristics to obtain non-interactive ZK, i.e., its security is considered in the random oracle model. Thus, our construction also has an advantage with respect to as-sumptions and security models. Our new obfuscator for ES is obtained from our new obfuscator for EVES.
Michael Backes, Aniket Kate, Sebastian Meiser, Tim Ruffing
Cryptographic protocols are commonly designed and their security proven under the assumption that the protocol parties have access to perfect (uniform) randomness. Physical randomness sources deployed in practical implementations of these protocols often fall short in meeting this assumption, but instead provide only a steady stream of bits with certain high entropy. Trying to ground cryptographic protocols on such imperfect, weaker sources of randomness has thus far mostly given rise to a multitude of impossibility results, including the impossibility to construct provably secure encryption, commitments, secret sharing, and zero-knowledge proofs based solely on a weak source. More generally, indistinguishability-based properties break down for such weak sources. In this paper, we show that the loss of security induced by using a weak source can be meaningfully quantified if the source is bounded, e.g., for the well-studied Santha-Vazirani (SV) sources. The quantification relies on a novel relaxation of indistinguishability by a quantitative parameter. We call the resulting notion dierential indistinguishability in order to reflect its structural similarity to dierential privacy. More concretely, we prove that indistinguishability with uniform randomness implies dierential indistinguishability with weak randomness. We show that if the amount of weak randomness is limited (e.g., by using it only to seed a PRG), all cryptographic primitives and protocols still achieve dierential indistinguishability.
Electronic voting is a popular application of cryptographic and network techniques to e-government. Most of the existing e-voting schemes can be classified into two categories: homomorphic voting and shuffling-based voting. In a homomorphic voting, an encryption algorithm with special homomorphic property (e.g. ElGamal encryption or Paillier encryption) is employed to encrypt the votes such that the sum of the votes can be recovered without decrypting any single vote. An advantage of homomorphic voting is efficient tallying. Tallying in homomorphic voting only costs one single decryption operation for each candidate. In this chapter, the existing e-voting solutions in both categories are surveyed and analysed. The key security properties in both categories are presented and then the existing e-voting schemes in each category are checked against the corresponding security properties. Security and efficiency of the schemes are analysed and the strongest security and highest efficiency achievable in each category is estimated. Problems and concerns about the existing solutions including vulnerability to malicious voters and (or) talliers, possible failure of complete correctness, imperfect privacy, dependence on computational assumptions, and exaggerated efficiency are addressed. New approaches will be proposed in both kinds of solutions to overcome the existing drawbacks in them. In homomorphic e-voting, the authors deal with possibly malicious voters and aim at efficient vote validity check to achieve strong and formally provable soundness and privacy. It can be implemented through new zero knowledge proof techniques, which are both efficient and provably secure. In mix-network-based e-voting, the authors deal with possibly deviating operations of both voters and talliers and aim at efficient proof of validity of shuffling, which guarantees the desired security properties and prevent attacks from malicious participants. It can be based on inspiring linear algebra knowledge and the new zero knowledge proof of existence of secret permutation.
Sherman S. M. Chow, Matthew Franklin, Haibin Zhang
Abstract. We reformalize and recast dual-receiver encryption (DRE) proposed in CCS ’04, a public-key encryption (PKE) scheme for encrypting to two independent recipients in one shot. We start by defining the crucial soundness property for DRE, which ensures that two recipients will get the same decryption result. While conceptually simple, DRE with soundness turns out to be a powerful primitive for various goals for PKE, such as complete non-malleability (CNM) and plaintext-awareness (PA). We then construct practical DRE schemes without random oracles under the Bilinear Decisional Diffie-Hellman assumption, while prior approaches rely on random oracles or inefficient non-interactive zero-knowledge proofs. Finally, we investigate further applications or extensions of DRE, including DRE with CNM, combined use of DRE and PKE, strengthening two types of PKE schemes with plaintext equality test, off-the-record messaging with a stronger notion of deniability, etc.
Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn
A signature scheme is malleable if, on input a message m and a signature σ, it is possible to efficiently compute a signature σ ′ on a related message m ′ = T (m), for a transformation T that is allowable with respect to this signature scheme. Previous work considered various useful flavors of allowable transformations, such as quoting and sanitizing messages. In this paper, we explore a connection between malleable signatures and anonymous credentials, and give the following contributions: • We define and construct malleable signatures for a broad category of allowable transformation classes, with security properties that are stronger than those that have been achieved previously. Our construction of malleable signatures is generically based on malleable zero-knowledge proofs, and we show how to instantiate it under the Decision Linear assumption. • We construct delegatable anonymous credentials from signatures that are malleable with respect to an appropriate class of transformations; we also show that our construction of malleable signatures works for this class of transformations. The resulting concrete instantiation is the first to achieve security under a standard assumption (Decision Linear) while also scaling linearly with the number of delegations. 1
Abstract Crypto-computing is a set of well-known techniques for com-puting with encrypted data. The security of the corresponding proto-cols are usually proven in the semi-honest model. In this work, we pro-pose a new class of zero-knowledge proofs, which are tailored for crypto-computing protocols. First, these proofs directly employ properties of the underlying crypto systems and thus many facts have more concise proofs compared to generic solutions. Second, we show how to achieve univer-sal composability in the trusted set-up model where all zero-knowledge proofs share the same system-wide parameters. Third, we derive a new protocol for multiplicative relations and show how to combine it with several crypto-computing frameworks.
The notion of zero-knowledge [GMR85] is formalized by requiring that for every malicious efficient verifier V ∗ , there exists an efficient simulator S that can reconstruct the view of V ∗ in a true interaction with the prover, in a way that is indistinguishable to every polynomialtime distinguisher. Weak zero-knowledge weakens this notions by switching the order of the quantifiers and only requires that for every distinguisher D, there exists a (potentially different) simulator SD. In this paper we consider various notions of zero-knowledge, and investigate whether their weak variants are equivalent to their strong variants. Although we show (under complexity assumption) that for the standard notion of zero-knowledge, its weak and strong counterparts are not equivalent, for meaningful variants of the standard notion, the weak and strong counterparts are indeed equivalent. Towards showing these equivalences, we introduce new non-black-box simulation techniques permitting us, for instance, to demonstrate that the classical 2-round graph non-isomorphism protocol of Goldreich-Micali-Wigderson [GMW91] satisfies a “distributional” variant of zero-knowledge. Our equivalence theorem has other applications beyond the notion of zero-knowledge. For instance, it directly implies the dense model theorem of Reingold et al (STOC ’08), and the leakage lemma of Gentry-Wichs (STOC ’11), and provides a modular and arguably simpler proof of these results (while at the same time recasting these result in the language of zeroknowledge). 0 1
We define a novel notion of quasi-adaptive non-interactive zero knowledge (NIZK) proofs for probability distributions on parametrized languages. It is quasi-adaptive in the sense that the common reference string (CRS) generator can generate the CRS depending on the parameters defining the language. However, the simulation is required to be uniform, i.e., a single efficient simulator should work for the whole class of parametrized languages. For distributions on languages that are linear subspaces of vector spaces over bilinear groups, we give quasi-adaptive NIZKs that are shorter and more efficient than Groth-Sahai NIZKs. For many cryptographic applications quasi-adaptiveNIZKs suffice, and our constructionscan lead to significant improvements in the standard model. Our construction can be based on any k-linear assumption, and in particular under the Symmetric eXternal Diffie Hellman (SXDH) assumption our proofs are even competitive with Random-Oracle based Σ-protocol NIZK proofs. We also show that our system can be extended to include integer tags in the defining equations, where the tags are provided adaptively by the adversary. This leads to applicability of our system to many applications that use tags, e.g. applications using Cramer-Shoup projective