Shao et al. proposed a novel method for computing private set intersection based on searchable encryption. Compared with the traditional protocols, their technique requires much less computation for the client to obtain the intersection. Concretely, the client only computes m (the cardinality of the client’s input set) multiplications, m hashes, and one modular exponentiation. However, their protocol only satisfies security against semi-honest behaviors. In this paper, we aim to promote the security of Shao et al.’s protocol. Our solution woks in the CRS model, and is based on the non-interactive zero knowledge proof and the succinct non-interactive argument. The proposed protocol satisfies security against malicious adversaries and needs only one round interaction.
The problem of secure multi-party computation(SMPC) is one of the most fundamental problems in information security. First, we introduce the basic concept of SMPC and four SMPC basic agreement: key distribution,oblivious transfer, bit commitment and zero knowledge proof. Secondly, we separately illustrate commitment schemes commitment transfer protocol, commitment sharing protocol and commitment multiplication protocol. Finally, we present unconditionally secure multi-party computation with a passive adversary, an active adversary, general adversary structures.
Provable data possession (PDP) is one of the techniques to ensure the integrity of data in storage outsourcing. Here in this paper, we speak to the creation of an efficient PDP method for distributed cloud storage to maintain the scalability of service and data migration. On the basis on homomorphic verifiable response and hash index hierarchy we projected a cooperative PDP (CPDP) method. We confirm the security of our method based on multi-prover zeroknowledge proof scheme, which can satisfy knowledge soundness, fullness , and zero-knowledge properties. As well, we expressive performance optimization mechanisms for our method, and in particular present an capable method for selecting finest parameter values to reduce the addition expenses of storage service providers and client. Our experiment shows that our solution introduces lower addition and communication overheads in evaluation with noncooperative approaches.
In this paper, we propose a secure yoking proof protocol for RFID passive tags based on Zero Knowledge. The protocols that have been proposed earlier are either found to be vulnerable to certain attacks or do not comply with EPC standard for passive tags because they use complex encryption schemes. Also, the unique design requirements of yoking/grouping proofs have not been fully addressed by many. Our protocol addresses these important security and design gaps in yoking proofs. The proposed protocol uses pseudo random squares and quadratic residuosity to realize the zero knowledge property. Tag operations are limited to functions such as modulo (MOD), exclusive-or (XOR) and 128-bit Pseudo Random Number Generators (PRNG). Passive tags are capable of these operations and hence the protocol achieves EPC compliance and also meets the necessary security requirements.
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.
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.
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.
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 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.
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
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.
Technology is linking the slightest of our actions to the virtual world. In such connected environments, cryptography aims at building schemes with provable security in order to mathematically protect the users' security in electronic exchanges. Relying on the existence of pairings in bilinear groups wherein the discrete logarithm problem is hard, this thesis puts forth mechanisms to efficiently enhance the privacy in three of the most fundamental cryptographic primitives, namely, digital signatures, encryption schemes and zero-knowledge proofs. Furthermore, these mechanisms support public verifiability so as to force the honesty of all participants in the standard model. We first focus on group signatures, a primitive proposed some 20 years ago, for which we propose the first efficient revocation mechanisms, overcoming the main obstacle to the deployment of this primitive in practical applications. We then focus on P-homomorphic signatures that make it possible to modify a signed message in a controlled way. In particular, we propose new mechanisms providing structure-preserving linearly homomorphic signatures, from which we build the first constant-size non-malleable commitments compatible with standard proof systems, as well as a generalization of this construction into a generic transformation. Finally we further investigate the unexpected applications of this kind of malleable signatures to non-malleable cryptography. This leads us to new proof systems for linear languages which in turn provide the most efficient publicly verifiable CCA-secure threshold encryption to date, and other new extensions.
Secure two-party computation cannot be fair against malicious adversaries, unless a trusted third party (TTP) or a gradual-release type super-constant round protocol is employed. Existing optimistic fair two-party computation protocols with constant rounds are either too costly to arbitrate (e.g., the TTP may need to re-do almost the whole computation), or require the use of electronic payments. Furthermore, most of the existing solutions were proven secure and fair via a partial simulation, which, we show, may lead to insecurity overall. We propose a new framework for fair and secure two-party computation that can be applied on top of any secure two party computation protocol based on Yao’s garbled circuits and zero-knowledge proofs. We show that our fairness overhead is minimal, compared to all known existing work. Furthermore, our protocol is fair even in terms of the work performed by Alice and Bob. We also prove our protocol is fair and secure simultaneously, through one simulator, which guarantees that our fairness extensions do not leak any private information. Lastly, we ensure that the TTP never learns the inputs or outputs of the computation. Therefore, even if the TTP becomes malicious and causes unfairness by colluding with one party, the security of the underlying protocol is still preserved.
Nico Döttling, Daniel Kraschewski, Jörn Müller‐Quade, Tobias Nilges
Universally composable secure computation was assumed to require trusted setups, until it was realized that parties exchanging (untrusted) tamper-proof hardware tokens allow an alternative approach (Katz; EUROCRYPT 2007). This discovery initialized a line of research dealing with two different types of tokens. Using only a single stateful token, one can implement general statistically secure two-party computation (Dottling, Kraschewski, Muller-Quade; TCC 2011); though all security is lost if an adversarial token receiver manages to physically reset and rerun the token. Stateless tokens, which are secure by definition against any such resetting-attacks, however, do provably not suffice for statistically secure computation in general (Goyal, Ishai, Mahmoody, Sahai; CRYPTO 2010). We investigate the natural question of what is possible if an adversary can reset a token at most a bounded number of times (e.g., because each resetting attempt imposes a significant risk to trigger a self-destruction mechanism of the token). Somewhat surprisingly, our results come close to the known positive results with respect to non-resettable stateful tokens. In particular, we construct polynomially many instances of statistically secure and universally composable oblivious transfer, using only a constant number of tokens. Our techniques have some abstract similarities to previous solutions, which we grasp by defining a new security property for protocols that use oracle access. Additionally, we apply our techniques to zero-knowledge proofs and obtain a protocol that achieves the same properties as bounded-query zero-knowledge PCPs (Kilian, Petrank, Tardos; STOC 1997), even if a malicious prover may issue stateful PCP oracles.