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.
Maryam Rajabzadeh Asaar, Ali Vardasbi, Mahmoud Salmasizadeh
Strong designated verifier signature (SDVS) is characterized by two properties; namely the non-transferability and the privacy of the signer's identity (PSI). Non-transferability prevents anyone else other than the designated verifier to verify the signature, while PSI prevents a third party to distinguish between two different signers. In this paper, we propose a non-delegatable SDVS which uses a trusted third party for the key generation. Our signature scheme does not use bilinear pairings which makes it suitable for the resource constraint applications. Using one-way homomorphic functions, our scheme is presented at an abstract level, the unification of which was noticed by Maurer in the context of zero knowledge proofs of knowledge in Africacrypt 2009. The security of the proposed scheme is proved in the random oracle model, provided that the homomorphism one-wayness and the gap Diffie-Hellman assumptions hold. When a Schnorr-like homomorphism is used to construct our scheme, six exponentiations are needed in the signing step and seven for the verification step. This means a meaningful gap between the performance of our scheme and that of its predecessors which use pairings in their signing and/or verification steps.
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.
The main aim of cryptography is to provide the frameworks and solutions for information security. The fundamental weapons to protect information are interactions and private randomness. Since the breakthrough result, zero-knowledge proof system, by Goldwasser, Micali, and Rackoff in mid 80s, the cryptography community has endeavored to propose the new notions of information security and the relative solutions which more closely reflect the modern computing environment. Concurrent security first introduced by Dwork, Naor, and Sahai was suggested to capture the information security in the modern internet environment. That is, the adversary may interact with a honest parties in many concurrent executions of a protocol where the messages are scheduled in any adversarial way.Resettable security was first introduced by Canetti, Goldreich, Goldwasser, and Micali, which models the security issues in which parties have a limited source of private randomness. In other words, an adversary might interact with honest parties in many executions of a protocol while the honest parties are only allowed to use the polynomially bounded number of (hard-wired) randomness.An important question is: "How much efficient protocol can we construct to achieve the above security in terms of round complexity?" Unfortunately, it has been showed that the best possible round complexity for such protocols is poly-logarithmic in the security parameter based on black-box simulation without help of external set-up assumptions. Thus, the question is now to minimize the round complexity of protocols with a minimal set-up assumption.In this thesis, we positively answer the above question with help of set-up assumptions. Specifically, we consider two set-up assumptions, the Bare Public Key (BPK) model and the Cross-Domain (CD) model. The BPK model was first introduced by Canetti, Goldreich, Goldwasser, and Micali. In the BPK model, each party is required to register their public keys before the start of interacting with each other. The CD model is a newly proposed model in this work. In the CD model, we have domains which models key certification authorities in the real world and each party belongs to one of the domains.In the BPK model, we show a constructions of constant-round simultaneously resettable zero-knowledge argument of knowledge with a standard cryptographic assumptions. As a main building block for this result, we show a construction of constant-round simultaneously resettable witness-indistinguishable argument of knowledge.In the CD model, we show a construction of constant-round concurrently secure multi-party computation protocol with the fixed number of domains. On the other hand, we prove that if the number of domains is not fixed, such a constant-round protocol does not exist.
There is a great demand for publicly verifiable encryption in key escrow,optimistic fair exchange,publicly verifiable secret sharing and secure multiparty computation,but the current schemes are either chosen plaintext secure or chosen ciphertext secure in the random oracle model,which obviously are not secure enough to be applied in the complicated circumstances.Based on the analysis of the current schemes and application of the reality,this paper proposed a new publicly verifiable encryption scheme by combining the CS encryption scheme with the non-interactive zero knowledge proof protocol.The new scheme enabled any third party other than the sender and receiver to verify the validity of the ciphertext,but leaked no information about the message.Finally,without using the random oracle,the adaptively chosen ciphertext security of the scheme is proved in the standard model.
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.
In this thesis, we construct an implementation of succinct non-interactive zero knowledge argument system. A non-interactive zero knowledge argument system is a protocol for a party (usually known as Prover) to provide a proof of knowledge to the solution of a statement to other parties (usually known as Verifier). The argument system will be able to provide such proof without leaking any other information regarding the solution. The non-interactivity allows such argument system to be done without requiring interaction between the parties involved. The statement that is proven in this work is the circuit satisfiability problem. The circuit satisfiability problem is a problem of deciding whether there exists an input that can make the final output of a circuit to be true. The argument system is based on Lipmaa's work \\cite{eprint2013:Lipmaa:NIZKSPECC} which uses span programs and linear error-correcting codes in its construction. We also try to give a very general explanation on zero knowledge argument system along the way in order to provide a simple concept to people encountering the notion for the first time. The argument system we attempt to construct is the non-adaptive version of the argument system. This version is useful for verifiable computation as pointed out by \\cite{Pinnochio2013:Parno} apart from its zero knowledge behavior. We begin by giving an overview on non-interactive zero knowledge, followed by span programs. We then proceed to describe on how to represent the circuit satisfiability problem using the mentioned tool. We present our implementation afterwards, listing out the libraries and implementation details that matters. We conclude by providing a speed measurement and possible future improvements of this work.
Bitcoin is a potentially disruptive new crypto-currency based on a decentralized opensource protocol which is gradually gaining popularity. Perhaps the most important question that will affect Bitcoin’s success, is whether or not it will be able to scale to support the high volume of transactions required from a global currency system. We investigate the restrictions on the rate of transaction processing in Bitcoin as a function of both the bandwidth available to nodes and the network delay, both of which lower the efficiency of Bitcoin’s transaction processing. The security analysis done by Bitcoin’s creator Satoshi Nakamoto [12] assumes that block propagation delays are negligible compared to the time between blocks—an assumption that does not hold when the protocol is required to process transactions at high rates. We improve upon the original analysis and remove this assumption. Using our results, we are able to give bounds on the number of transactions per second the protocol can handle securely. Building on previously published measurements by Decker and Wattenhofer [5], we show these bounds are currently more restrictive by an order of magnitude than the bandwidth needed to stream all transactions. We additionally show how currently planned improvements to the protocol, namely the use of transaction hashes in blocks (instead of complete transaction records), will dramatically alleviate these restrictions. Finally, we present an easily implementable modification to the way Bitcoin constructs its main data structure, the blockchain, that immensely improves security from attackers, especially when the network operates at high rates. This improvement allows for further increases in the number of transactions processed per second. We show that with our proposed modification, significant speedups can be gained in confirmation time of transactions as well. The block generation rate can be securely increased to more than one block per second – a 600 fold speedup compared to today’s rate, while still allowing the network to processes many transactions per second.
Cloud computing is a model for enabling convenient, on-demand network access to a shared pool of configurable computing resources (e.g., network, servers, storage, applications and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction. During the last a few years, data security and integrity in cloud computing has emerged as a significantly important research area that has attracted increasing attention from both industry and academia. The virtual environment of cloud computing allows users to access computing power that exceeds what is contained within their own physical worlds. To enter this virtual environment, cloud users must transfer data throughout the cloud. Typically, cloud users know neither the exact location of their data nor the other sources of the data collectively stored with theirs. Consequently, several data security and integrity concerns have arisen, including key management, access control, searchable encryption techniques, remote integrity checks and proof of ownership in the cloud.\nThe first aspect of the work presented in this thesis is tree-based key management in cloud computing. Data encryption before outsourcing to the cloud is a common way to protect data privacy. Thus, key management is a challenging issue in cloud computing. It is the ability to correctly assign, monitor and secure keys which defines the level of operational security provided by any encryption implementation. The fundamental idea of this work is to design a secure and flexible key management mechanism for the outsourced data in cloud computing. In this thesis, an innovative tree-based key management scheme is proposed. The outsourced database remains private and secure, while some selected data and key nodes are shared with other parties in the cloud. Flexibility of key management is achieved and the security is proved in the standard model.\nThe second aspect of the work presented in this thesis is fine-grained access control. In order to secure the outsourced data in the cloud, designing efficient and secure access control is a challenging issue. Unlike traditional access control in which the data users and storage servers are in the same trust domain, access control techniques are very different in cloud computing, as the cloud servers are not trusted by most cloud users. The key idea of this work is to attribute sets-based access control. This thesis points out that any access policy can be defined as a logical expression formula over different attribute sets. Logical expression indicates what kind of user is allowed to access the data. A fine-grained and efficient access control is proposed, based on logical expression.\nThe third aspect of the work presented in this thesis is efficient searchable encryption techniques in cloud computing. Because the data is usually encrypted before being outsourced to the cloud, searching the encrypted data in cloud computing has recently gained attention and led to the development of efficient searchable encryption techniques. The fundamental idea of this work is to reduce the search cost on encrypted data. In this thesis, a practical keyword searching mechanism is proposed. The solution is very simple. It enables efficient multi-user keyword searches and hides the private information in the search queries. The security is proved in the standard model.\nThe fourth aspect of the work presented in this thesis is public remote data integrity checks. As the clients store important data in remote cloud storage without a local copy, it is important to check the remote data integrity. Design of efficient remote integrity check protocols without downloading the data is a challenging issue in cloud computing. The key idea of this work is a public remote integrity check based on zero-knowledge proof. In this thesis, an innovative public remote integrity check scheme (PRIC) is proposed. No information of either the verified data or the homomorphic tags is leaked. In addition, the experiment result shows that PRIC is efficient, especially when the data size is large or the integrity check is frequent. The security of PRIC is proved in the random oracle model.\nThe last aspect of the work presented in this thesis is proof of multiparty ownership for encrypted data in the cloud. There are many applications of ownership sharing by different users and the design of the proof protocols of joint ownership is a challenging issue. Meanwhile, the design of proof-of-ownership mechanisms for encrypted data is even more difficult. This is because encryption of the same file by different users with random keys results in different ciphertexts, and the cloud server cannot store the same hash root value for ownership verification. In this thesis, a proof of multiparty ownership solution (PMOW) with encrypted data is proposed. Every user can prove that he/she holds the plaintext of the encrypted file when the server stores one ciphertext only. In addition, a PMOW system is constructed. The security of PMOW is proved in the ideal cipher model.\nThe major contribution of this thesis is innovative and improved approaches to secure data in cloud computing. Using these approaches developed, a trustworthy cloud environment can be achieved.
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.
Abstract. We present a set of new, efficient, universally composable two-party protocols for evaluating reactive arithmetic circuits modulo n, where n is a safe RSA modulus of unknown factorization. Our protocols are based on a homomorphic encryption scheme with message space Zn, zero-knowledge proofs of existence, and a novel “mixed ” trapdoor commitment scheme. Our protocols are proven secure against adaptive corruptions (assuming secure erasures) under standard assumptions in the CRS model (without random oracles). Our protocols appear to be the most efficient ones that satisfy these security requirements. In contrast to prior protocols, we provide facilities that allow for the use of our protocols as building blocks of higher-level protocols. An additional contribution of this paper is a universally composable construction of the variant of the Dodis-Yampolskiy oblivious pseudorandom function in a group of order n as originally proposed by Jarecki and Liu.
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.
Katz and Vaikuntanathan recently improved smooth projective hash functions in order to build oneround password-authenticated key exchange protocols (PAKE). To achieve security in the UC framework they allowed the simulator to extract the hashing key, which required simulation-sound non-interactive zero-knowledge proofs that are unfortunately inefficient. We improve the way the latter extractability is obtained by introducing the notion of trapdoor smooth projective hash function (TSPHF). A TSPHF is an SPHF with a trapdoor, which may not allow to recover the complete hashing key, but which still allows to compute the hash value, which is enough for an application to PAKE with UC-security against static corruptions. We additionally show that TSPHFs yield zero-knowledge proofs in two flows, with straight-line extractability. Besides those quite interesting applications of TSPHF, we also show how to generically build them on languages of ciphertexts, using any ElGamal-like encryption. Our concrete instantiations lead to efficient one-round UC-secure PAKE, extractable zero-knowledge arguments, and verifiable encryption of Waters signatures. In the case of the PAKE, our construction is the most efficient one-round UC-secure PAKE to date.
For various services, OTP (One-Time Password) is increasingly employed to sign in services. The most popular OTP scheme is S/KEY. However, S/KEY scheme is vulnerable to hash collision. In order to solve this problem, Choi and Kim proposed an OTP scheme based on pairing operation. This scheme overcame hash collision problem. Unfortunately, the scheme is vulnerable against insider attack. In this paper, we propose insider attack-resistant OTP scheme based on pairing operation. Our scheme employed zero-knowledge proof to generate OTP values. In short, our scheme sends an OTP and two random numbers encoded with XOR; any adversary has no sense about the random numbers. Our scheme authenticates entities with an OTP and gain a hint on next OTP value from one of random numbers. Consequently, we present insider attack-resistant OTP scheme by eliminating shared parameter among insider (e.g. time stamp).
Abstract. Consider a joint distribution (X,A) on a set X ×{0, 1}ℓ. We show that for any family F of distinguishers f: X × {0, 1}ℓ → {0, 1}, there exists a simulator h: X → {0, 1}ℓ such that 1. no function in F can distinguish (X,A) from (X,h(X)) with advantage ǫ, 2. h is only O(23ℓǫ−2) times less efficient than the functions in F. For the most interesting settings of the parameters (in particular, the cryptographic case where X has superlogarithmic min-entropy, ǫ> 0 is negligible and F consists of circuits of polynomial size), we can make the simulator h deterministic. As an illustrative application of this theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt’09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES. Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem. 1