Michel Abdalla⋆, Fabrice Benhamouda, David Pointcheval
Indistinguishability under adaptive chosen-ciphertext attack (IND-CCA) is now consid- ered the de facto security notion for public-key encryption. However, the security guarantee that it oers is sometimes stronger than what is needed by certain applications. In this paper, we consider a weaker notion of security for public-key encryption, termed indistinguishability under plaintext- checking attacks (IND-PCA), in which the adversary is only given access to an oracle which says whether or not a given ciphertext encrypts a given message. After formalizing the IND-PCA notion, we then design a new public-key encryption scheme satisfying it. The new scheme is a more e- cient variant of the Cramer-Shoup encryption scheme with shorter ciphertexts and its security is also based on the plain Decisional Die-Hellman ( DDH) assumption. Additionally, the algebraic properties of the new scheme also allow for proving plaintext knowledge using Groth-Sahai non- interactive zero-knowledge proofs or smooth projective hash functions. Finally, in order to illustrate the usefulness of the new scheme, we further show that, for many password-based authenticated key exchange (PAKE) schemes in the Bellare-Pointcheval-Rogaway security model, one can safely replace the underlying IND-CCA encryption schemes with our new IND-PCA one. By doing so, we were able to reduce the overall communication complexity of these protocols and obtain the most ecient PAKE schemes to date based on the plain DDH assumption.
Gyan Prakash, B. N. VYAS, Product Design Specialist, Cognizant Technology Solutions, Kolkata, India
Cloud-based outsourced storage relieves the client's load for storage management and maintenance by providing a comparably low-cost, scalable, locationindependent platform. Though, the information that clients no longer have physical control of data specifies that they are facing a potentially formidable risk for missing or corrupted data. To avoid the security risks, inspection services are serious to ensure the integrity and availability of outsourced data and to achieve digital forensics and reliability on cloud computing. Provable data possession (PDP), which is a cryptographic method for validating the reliability of data without retrieving it at an untrusted server, can be used to realize audit services. In this project, profiting from the interactive zero-knowledge proof system, the construction of an interactive PDP protocol to prevent the fraudulence of prover (soundness property) and the leakage of verified data (zero knowledge property).To prove that our construction holds these properties based on the computation Diffie-Hellman assumption and the rewindable black-box knowledge extractor. An efficient mechanism on probabilistic queries and periodic verification is proposed to reduce the audit costs per verification and implement abnormal detection timely. Also, we present an efficient method for choosing an optimal parameter value to reduce computational overheads of cloud audit services.
Joseph A. Akinyele, Gilles Barthe, Benjamin Grégoire, Benedikt Schmidt · 5 authors
Many algorithms admit very efficient batch versions that compute simultaneously the output of the algorithms on a set of inputs. Batch algorithms are widely used in cryptography, especially in the setting of pairing-based computations, where they deliver significant speed-ups. Auto Batch is an automated tool that computes highly optimized batch verification algorithms for pairing-based signature schemes. Thanks to finely tuned heuristics, Auto Batch is able to rediscover efficient batch verifiers for several signature schemes of interest, and in some cases to output batch verifiers that outperform the best known verifiers from the literature. However, Auto Batch only provides weak guarantees (in the form of a LaTeX proof) of the correctness of the batch algorithms it outputs. In this paper, we verify the correctness and security of these algorithms using the Easy Crypt framework. To achieve this goal, we define a domain-specific language to describe verification algorithms based on pairings and provide an efficient algorithm for checking (approximate) observational equivalence between expressions of this language. By translating the output of Auto Batch to this language and applying our verification procedure, we obtain machine-checked correctness proofs of the batch verifiers. Moreover, we formalize notions of security for batch verifiers and we provide a generic proof in Easy Crypt that batch verifiers satisfy a security property called screening, provided they are correct and the original signature is unforgeable against chosen-message attacks. We apply our techniques to several well-known pairing-based signature schemes from the literature, and to Groth-Sahai zero-knowledge proofs.
During the execution of a business process users need to be authenticated by multiple component service providers, while their identities need to be shared and propagated across multi-domain in a privacy-preserving fashion. An anonymous credential-based identity verification scheme is proposed to address privacy issue. Users establish trust relationship with the federation by running the enrollment protocol, which is based on zero-knowledge proof of a set of committed attributes. The IdP cannot learn identity-related information about the user. Anonymous credentials issued by the IdP allow users to selectively disclose attributes as required and prove them in an untraceable and unlinkable way, where the IdP cannot trace the showing of credential and component service providers cannot address multiple transactions to the same user even if they collude either. With the proposed attributes proof protocols, users can prove AND and OR relation over multiple attributes, and interval and inequality relation over a single attribute as well.
Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn
A signature scheme is malleable if, on input a message and a signature, it is possible to efficiently compute a signature on a related message, for a transformation that is allowed with respect to this signature scheme. In this paper, we first provide new definitions for malleable signatures that allow us to capture a broader range of transformations than was previously possible. We then give a generic construction based on malleable zero-knowledge proofs that allows us to construct malleable signatures for a wide range of transformation classes, with security properties that are stronger than those that have been achieved previously. Finally, we construct delegatable anonymous credentials from signatures that are malleable with respect to an appropriate class of transformations (that we show our malleable signature supports). The resulting instantiation satisfies a stronger security notion than previous schemes while also scaling linearly with the number of delegations.
With an estimated 50 billion internet-enabled devices deployed by 2020, the arrival of the Internet of Things (IoT) or Internet of Everything (IoE) raises many questions regarding the suitability and adaptability of current computer security standards to provide privacy, data integrity and end entity authentication between communicating peers. In this paper we present a new protocol which combines zero-knowledge proofs and key exchange mechanisms to provide secure and authenticated communication in static machine-to-machine (M2M) networks. This approach addresses all of the aforementioned issues while also being suitable for devices with limited computational resources and can be deployed in wireless sensor networks. While the protocol requires an a-priori knowledge about the network setup and structure, it guarantees perfect forward secrecy.
We study decentralized cryptocurrency protocols in which the participants do not deplete physical scarce resources. Such protocols commonly rely on Proof of Stake, i.e., on mechanisms that extend voting power to the stakeholders of the system. We offer analysis of existing protocols that have a substantial amount of popularity. We then present our novel pure Proof of Stake protocols, and argue that they help in mitigating problems that the existing protocols exhibit.
Electronic cash is an electronic form of currency, which allows the cash transactions over communication networks under privacy protections. However, it still has some aspects that have not been well studied. Known constructions suffer from at least one of the following limitations: (1) relying on a random oracle, (2) not supporting multiple bank setting and users dynamically joining or (3) prohibitively expensive. In this paper, we propose a new electronic cash system that avoids all these limitations. In other words, our system is anonymous against chosen-ciphertext attack (CCA) in the standard model, and supports multiple banks enrolling and users dynamically joining, which is achieved by the utilization of non-interactive zero-knowledge proof and dynamic group signature. Finally, in the standard model, a formal security proof is given to claim that our system has CCA anonymity, unforgeability, traceability and no double-spending. Compared with the existing systems, ours has advantages of both the efficiency and security.
In this paper, we propose a novel cryptographic notion called subset membership encryption (SME), and provide a very efficient SME scheme. Given a system parameter generated by an encryptor (Alice), a decryptor (Bob) generates a randomized privacy-preserved attribute token P(G) from a set of attributes G. A message is encrypted using an attribute set A chosen by Alice and P(G) provided by Bob. It requires that A is a subset of G for Bob to decrypt the message. We propose a very efficient SME scheme, where both the size of P(G) and ciphertext are short and independent of G and A. In particular, it has three useful and practical applications to oblivious transfer as follows. 1) k-Out-of-n Oblivious Transfer (OT): SME can be naturally applied to a two-round OT, which features a great communication efficiency especially for the receiver, where the receiver only sends two group elements to the message sender. 2) Priced Oblivious Transfer (POT): Our POT protocol allows a buyer to purchase any number of items in each transaction and hide selected items, price and balance from the vendor. In comparison with previous POT protocols, our protocol is more flexible and eliminates the restriction that a buyer can only purchase one item in a transaction. Our POT scheme is very efficient since it does not require any zero-knowledge proof or homomorphic encryption. 3) Restricted Priced Oblivious Transfer (RPOT): We introduce a novel POT named RPOT where a vendor can set restrictions on items or prices in POT. For example, a seller could offer a discounted price to those buyers who have purchased some specific items previously from the same seller.
Privacy is of the utmost importance in genomic matching. Therefore a number of privacy-preserving protocols have been presented using secure computation. Nevertheless, none of these protocols prevents inferences from the result. Goodrich has shown that this resulting information is sufficient for an effective attack on genome databases. In this paper we present an approach that can detect and mitigate such an attack on encrypted messages while still preserving the privacy of both parties. Note that randomization, e.g.~using differential privacy, will almost certainly destroy the utility of the matching result. We combine two known cryptographic primitives -- secure computation of the edit distance and fuzzy commitments -- in order to prevent submission of similar genome sequences. Particularly, we contribute an efficient zero-knowledge proof that the same input has been used in both primitives. We show that using our approach it is feasible to preserve privacy in genome matching and also detect and mitigate Goodrich's attack.
Nesrine Kaaniche, Ethmane El Moustaine, Maryline Laurent
Recent technological advances have given rise to the popularity and success of cloud storage. However, the prospect of outsourcing an increasing amount of data to a third party and the abstract nature of the cloud foster the proliferation of security and privacy challenges, namely, the remote data possession checking. This paper addresses this critical security concern, when storing sensitive data in a cloud storage service, and the need for users to trust commercial cloud providers. It proposes a deterministic Proof of Data Possession (PDP) scheme based on Interactive Proof System(IPS) and an original usage of the GPS scheme. Our approach has several advantages. First, it supports public verifiability which releases data owners from the burden of a periodical verification. Second, it provides constant communication complexity, where the exchanged messages between the storage server and the client are composed of constant number of group elements. Third, our solution is efficient and provably secure, as it is resistant to the fraudulence of the prover and the leakage of verified data.
Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently\ndifficult to analyze because their security analysis uses rewinding. Certain\ncases of quantum rewinding are handled by the results by Watrous (SIAM J\nComput, 2009) and Unruh (Eurocrypt 2012), yet in general the problem remains\nelusive. We show that this is not only due to a lack of proof techniques:\nrelative to an oracle, we show that classically secure proofs and proofs of\nknowledge are insecure in the quantum setting.\n More specifically, sigma-protocols, the Fiat-Shamir construction, and\nFischlin's proof system are quantum insecure under assumptions that are\nsufficient for classical security. Additionally, we show that for similar\nreasons, computationally binding commitments provide almost no security\nguarantees in a quantum setting.\n To show these results, we develop the "pick-one trick", a general technique\nthat allows an adversary to find one value satisfying a given predicate, but\nnot two.\n
Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently difficult to analyze because their security analysis uses rewinding. Certain cases of quantum rewinding are handled by the results by Watrous (SIAM J Comput, 2009) and Unruh (Eurocrypt 2012), yet in general the problem remains elusive. We show that this is not only due to a lack of proof techniques: relative to an oracle, we show that classically secure proofs and proofs of knowledge are insecure in the quantum setting. More specifically, sigma-protocols, the Fiat-Shamir construction, and Fischlin's proof system are quantum insecure under assumptions that are sufficient for classical security. Additionally, we show that for similar reasons, computationally binding commitments provide almost no security guarantees in a quantum setting. To show these results, we develop the "pick-one trick", a general technique that allows an adversary to find one value satisfying a given predicate, but not two.
In this article, the authors propose an approach for privacy preserving distributed clustering that assumes malicious model. In the literature, there do exist, numerous approaches that assume a semi honest model. However, such an assumption is, at best, reasonable in experimentations; rarely true in real world. Hence, it is essential to investigate approaches for privacy preservation using a malicious model. The authors use the Pederson's Verifiable Secret Sharing scheme ensuring the privacy using additively homomorphic secret sharing scheme. The trustworthiness of the data is assured using homomorphic commitments in Pederson's scheme. In addition, the authors propose two variants of the proposed approach - one for horizontally partitioned dataset and the other for vertically partitioned dataset. The experimental results show that the proposed approach is scalable in terms of dataset size. The authors also carry out experimentations to highlight the effectiveness of Verifiable Secret Sharing scheme against Zero Knowledge Proof scheme.
Abstract Mix network plays a key role in electronic voting to preserve anonymity and lots of mixnet schemes have been proposed so far. However, they requires complex and costly zero-knowledge proofs to provide their correct mixing operations. In 2010, Sebe et al. proposed an efficient and lightweight mixnet scheme based on a cryptographic secure hash function instead of zero-knowledge proofs. In this paper, we present a more efficient and faster mixnet scheme than Sebe et al.'s scheme under the same assumption. Also, our scheme is secure. Key Words : Zero-knowledge proof, e-Voting, Anonimity, Mixnet, hash function Ⅰ. Introduction Mixes are a means of untraceable communication based on a public key cryptosystem, as published by D.Chaum in 1981 [1] . A mix-network or mixnet accepts as input a collection of ciphertexts, and outputs associated plaintexts(or ciphertexts) in a randomly permuted order. A well constructed mixnet makes it infeasible for an adversary to determine which plaintext output corresponds to which ciphertext input more efficiently than by guessing at random. Proposed by D.Chaum in 1981 as a technique for anonymous e-mail and e-voting, mixnet can be categorized into decryption mix-nets and re-encryption mix-nets
Internet Traffic Analysis and Secure E-voting
Cryptography and Data Security
Advanced Steganography and Watermarking Techniques
In this short note we show that the Bitcoin network can allow remote parties to gamble with their bitcoins by tossing a fair or biased coin, with no need for a trusted party, and without the possibility of extortion by dishonest parties who try to abort. The superfluousness of having a trusted party implies that there is no house edge, as is the case with centralized services that are supposed to generate a profit.
The cloud storage offers users with infrastructure flexibility, faster deployment of applications and data, cost control, adaptation of cloud resources to real needs, improved productivity, etc. Inspite of these advantageous factors, there are several deterrents to the widespread adoption of cloud computing remain. Among them, security towards the correctness of the outsourced data and issues of privacy lead a major role. In order to avoid security risk for the outsourced data, we propose the dynamic audit services that enables integrity verification of untrusted and outsourced storages. An interactive proof system (IPS) with the zero knowledge property is introduced to provide public auditability without downloading raw data and protect privacy of the data. In the proposed system data owner stores the large number of data in cloud after e encrypting the data with private key and also send public key to third party auditor (TPA) for auditing purpose. TPA in clouds and it's maintained by CSP. An Authorized Application (AA), which holds a data owners secret key (sk) and manipulate the outsourced data and update the associated IHT stored in TPA. Finally Cloud users access the services through the AA. Our system also provides secure auditing while the data owner outsourcing the data in the cloud. And after performing auditing operations, security solutions are enhanced for the purpose of detecting malicious users with the help of Certificate Authority.
Zero-knowledge proofs were introduced by Goldwasser, Micali, and Rackoff. A zero-knowledge proof allows a prover to demonstrate knowledge of some information, for example that they know an element which is a member of a list or which is not a member of a list, without disclosing any further information about that element. Existing constructions of zero-knowledge proofs which can be applied to all languages in NP are impractical due to their communication and computational complexity. However, it has been known since Guillou and Quisquater's identification protocol from 1988 and Schnorr's identification protocol from 1991 that practical zero-knowledge protocols for specific problems exist. Because of this, a lot of work was undertaken over the recent decades to find practical zero-knowledge proofs for various other specific problems, and in recent years many protocols were published which have improved communication and computational complexity. Nevertheless, to find more problems which have an efficient and practical zero-knowledge proof system and which can be used as building blocks for other protocols is an ongoing challenge of modern cryptography. This work addresses the challenge, and constructs zero-knowledge arguments with sublinear communication complexity, and achievable computational demands. The security of our protocols is only based on the discrete logarithm assumption. Polynomial evaluation arguments are proposed for univariate polynomials, for multivariate polynomials, and for a batch of univariate polynomials. Furthermore, the polynomial evaluation argument is applied to construct practical membership and non-membership arguments. Finally, an efficient method for proving the correctness of a shuffle is proposed. The proposed protocols have been tested against current state of the art versions in order to verify their practicality in terms of run-time and communication cost. We observe that the performance of our protocols is fast enough to be practical for medium range parameters. Furthermore, all our verifiers have a better asymptotic behavior than earlier verifiers independent of the parameter range, and in real life settings our provers perform better than provers of existing protocols. The analysis of the results shows that the communication cost of our protocols is very small; therefore, our new protocols compare very favorably to the current state of the art.
Bitcoin is a "crypto currency", a decentralized electronic payment scheme based on cryptography. Bitcoin economy grows at an incredibly fast rate and is now worth some 10 billions of dollars. Bitcoin mining is an activity which consists of creating (minting) the new coins which are later put into circulation. Miners spend electricity on solving cryptographic puzzles and they are also gatekeepers which validate bitcoin transactions of other people. Miners are expected to be honest and have some incentives to behave well. However. In this paper we look at the miner strategies with particular attention paid to subversive and dishonest strategies or those which could put bitcoin and its reputation in danger. We study in details several recent attacks in which dishonest miners obtain a higher reward than their relative contribution to the network. In particular we revisit the concept of block withholding attacks and propose a new concrete and practical block withholding attack which we show to maximize the advantage gained by rogue miners. RECENT EVENTS: it seems that the attack was recently executed, see Section XI-A.
Open access
2 source records
Blockchain Technology Applications and Security
Cryptography and Data Security
Advanced Steganography and Watermarking Techniques
A scheme for anonymous tag based anonymous credentials is enhanced. Different from existing zero knowledge proof based anonymous credential schemes that require numbers of challenges and responses between verifiers and credential holders, the anonymous tag based scheme requires only small number of challenges and responses between verifiers and credential holders. This is because the scheme in this paper can be easily made sound even in environments where verifiers also may behave dishonestly. However, the original scheme has probabilistic features, i.e. verifiers must generate dummy fake challenges; therefore overheads for managing anonymous systems cannot be reduced to the minimum. The enhanced anonymous tag based scheme excludes these probabilistic features from interactions between verifiers and credential holders. The scheme also corrects several design errors included in the original scheme.
This paper introduce a dynamic audit service for integrity verification of untrusted and outsourced storages. Our audit service is constructed based on the techniques, fragment structure, random sampling, and index-hash table, supporting provable updates to outsourced data and timely anomaly detection. Constructed on interactive proof system (IPS) with the zero knowledge property, our audit service can provide public auditability without downloading raw data and protect privacy of the data. Also, our audit system can support dynamic data operations and timely anomaly detection with the help of several effective techniques, such as fragment structure, random sampling, and index-hash table (IHT). We also propose an efficient approach based on probabilistic query and periodic verification for improving the performance of audit services. A proof-ofconcept prototype is also implemented to evaluate the feasibility and viability of our proposed approaches. Our experimental results not only validate the effectiveness of our approaches, but also show that our system does not create any significant computation cost and require less extra storage for integrity verification.