In this paper, we prove classical coin-flipping secure in the presence of quantum adversaries. The proof uses a recent result of Watrous [Wat09] that allows quantum rewinding for protocols of a certain form. We then discuss two applications. First, the combination of coin-flipping with any non-interactive zero-knowledge protocol leads to an easy transformation from non-interactive zero-knowledge to interactive quantum zero-knowledge. Second, we discuss how our protocol can be applied to a recently proposed method for improving the security of quantum protocols [DFL+09], resulting in an implementation without set-up assumptions. Finally, we sketch how to achieve efficient simulation for an extended construction in the common-reference-string model.
Dario Catalano, Mario Di Raimondo, Dario Fiore, Mariagrazia Messina
Zero knowledge sets (ZKS), introduced by Micali, Rabin, and Kilian in 2003, allow a prover to commit to a secret set$S$in a way such that it can later prove, non interactively, statements of the form$x\in S$(or$x\notin S$), without revealing any further information (on top of what explicitly revealed by the inclusion/exclusion statements above) on$S$, not even its size. Later, Chaseabstracted away the Micali, Rabin, and Kilian's construction by introducing an elegant new variant of commitments that they called (trapdoor) mercurial commitments. Using this primitive, it was shown how to construct zero knowledge sets from a variety of assumptions (both general and number theoretic). This paper introduces the notion of trapdoor$q$-mercurial commitments (${\ssr qTMC}$s), a notion of mercurial commitment that allows the sender to commit to an ordered sequence of exactly$q$messages, rather than to a single one. Following the previous work, it is shown how to construct ZKS from${\ssr qTMC}$s and collision resistant hash functions. Then, it is presented an efficient realization of${\ssr qTMC}$s that is secure under the so called Strong Diffie Hellman (SDH) assumption, a number theoretic conjecture recently introduced by Boneh and Boyen. Using such scheme as basic building block, it is obtained a construction of ZKS that allows for proofs that are much shorter with respect to the best previously known implementations. In particular, for an appropriate choice of the parameters, our proofs are up to 33% shorter for the case of proofs of membership, and up to 73% shorter for the case of proofs of nonmembership. Experimental tests confirm practical time performances.
A Publicly Veri able Secret Sharing (PVSS) scheme, as introduced by Stadler, has a feature
where anyone, besides the participants, can verify the validity of the shares distributed by
the dealer. Schoenmakers added a new feature, by providing a proof of correctness of the
shares released by the players in the reconstruction process. This protocol is claimed to
be an improvement on Stadler's and Fujisaki-Okamoto's, both in eciency and in the type
of intractability assumptions. However, Young-Yung improved Schoenmakers' PVSS, using a
Discrete-Log instead of a Decision Die-Hellman. In this paper, a new PVSS is presented,
having an intrinsic di erence with its predecessors, that is, the participants can prove the validity
of their given shares, implicitly, proving their membership by a zero-knowledge protocol. This
feature prevents cheaters from participating in the reconstruction process to gain valid shares.
Hence, the new proposed PVSS is more secure than previous ones. Besides, the dealer only
sends the amount of commitments limited to the threshold value, regardless of the number of
shareholders; this leads to a more dynamic protocol.
When designing and analyzing cryptosystems, it is usually assumed that the computational devices used by the honest parties have access to resources that are outside of the malicious parties' control. In such a model, it is known, under standard cryptographic assumptions, that essentially any operation can be performed securely as long as a majority of the parties are honest.
In many practical settings, however, the assumption that computational resources can be protected from an adversary does not hold. This dissertation explores various security problems in settings where honest parties wish to make use of computational resources that are under adversarial control. We focus on resources that are fundamental to cryptography, such as randomness and storage.
We first consider the problem of encrypting with a malicious random number generator. We introduce the notions of security against chosen-randomness attacks (CRA) and security against chosen-ciphertext and randomness attacks (CCRA), which formally capture the security of private-key encryption when used with sources of randomness that are under adversarial control. We study the relationships between these notions and the traditional notions of security for encryption. We also show how to design efficient schemes that are CRA-secure, and how to transform any CPA-secure scheme into a CRA-secure one, and any CRA-secure scheme into a CCRA-secure one.
We then turn to the task of authenticating data stored in unreliable memory. We propose a general framework for designing efficient proofs of data possession, which are proof systems that enable one to convince a verifier that it stores a particular piece of data. We give a compiler that transforms any sigma-protocol (i.e., a three-round public-coin zero-knowledge proof of knowledge) into a proof of data possession.
Finally, we consider the problem of storing private data in untrusted memory. We show how to design private-key encryption schemes that allow one to search over encrypted content. Our constructions are optimal in terms of search time. We also introduce searchable encryption in the multi-user setting, where search privileges can be delegated to a set of authorized users.
Many business models for smart products, like pay-per-use, require that the smart product can digitally verify whether the user has a contract with the smart product and should be granted access to privileged functionality. Traditional means to do so, e.g. password login, are very obtrusive and can thus not be applied for smart product scenarios. In this paper, we present the mechanism of association. Associations represent the abstract concept of a digitally checkable contract on the middleware level. Associations use a service for digitally representing the user that performs the tedious parts of creating a digitally checkable contract automatically. Thus, the interaction can be established unobtrusively. As this service acts on behalf of the user, the user must trust this service. We address this issue in two ways: the service is executed on the personal trusted device of the user and the user can control and inspect the actions of the service via a user interface.
In quantum zero knowledge, the assumption was made that the verifier is only using unitary operations. Under this assumption, many nice properties have been shown about quantum zero knowledge, including the fact that Honest-Verifier Quantum Statistical Zero Knowledge ($HVQSZK$) is equal to Cheating-Verifier Quantum Statistical Zero Knowledge ($QSZK$) (see ~\cite{Wat02,Wat06}). In this paper, we study what happens when we allow an honest verifier to flip some coins in addition to using unitary operations. Flipping a coin is a non-unitary operation but doesn\'t seem at first to enhance the cheating possibilities of the verifier since a classical honest verifier can flip coins. In this setting, we show an unexpected result: any classical Interactive Proof has an Honest-Verifier Quantum Statistical Zero Knowledge proof with coins. Note that in the classical case, honest verifier $SZK$ is no more powerful than $SZK$ and hence it is not believed to contain even $NP$. On the other hand, in the case of cheating verifiers, we show that Quantum Statistical Zero Knowledge where the verifier applies any non-unitary operation is equal to Quantum Zero-Knowledge where the verifier uses only unitaries. One can think of our results in two complementary ways. If we would like to use the honest verifier model as a means to study the general model by taking advantage of their equivalence, then it is imperative to use the unitary definition without coins, since with the general one this equivalence is most probably not true. On the other hand, if we would like to use quantum zero knowledge protocols in a cryptographic scenario where the honest-but-curious model is sufficient, then adding the unitary constraint severely decreases the power of quantum zero knowledge protocols.
Divisibility of e-cash helps expend digital coin exactly.Most divisible e-cash schemes are based on binary tree,but few e-cash schemes offer fairness and divisibility at the same time.Based on binary tree,blind signature and zero-knowledge proof,a new fair indivisible electronic coins scheme was proposed.
This paper introduces a natural paradigm for fair exchange protocols, called ID-based partial proxy signature scheme. A security model with precise and formal definitions is presented, and an efficient and provably secure partial proxy signature scheme is proposed. This is a full ID-based optimistic fair exchange protocol. Unlike the vast majority of previously proposed protocols, this approach does not use any zero knowledge proofs, and thus avoids most of the costly computations.
We present two universally composable and practical protocols by which a dealer can, verifiably and non-interactively, secret-share an integer among a set of players. Moreover, at small extra cost and using a distributed verifier proof, it can be shown in zero-knowledge that three shared integers a, b, c satisfy ab = c. This implies by known reductions non-interactive zero-knowledge proofs that a shared integer is in a given interval, or that one secret integer is larger than another. Such primitives are useful, e.g., for supplying inputs to a multiparty computation protocol, such as an auction or an election. The protocols use various set-up assumptions, but do not require the random oracle model.
Abhilasha Bhargav-Spantzel, Anna Squicciarini, Elisa Bertino
We develop solutions for the security and privacy of user identity information in a federation. By federation we mean a group of organizations or service providers which have built trust among each other and enable sharing of user identity information amongst themselves. We first propose a flexible approach to establish a single sign-on (SSO) ID in the federation. Then we show how a user can leverage this SSO ID to establish certified and un-certified user identity attributes without the dependence on PKI for user authentication. This makes the process more usable and privacy preserving. Our major contribution in this paper is a novel solution for protection against identity theft of these identity attributes. We provide protocols based on cryptographic techniques, namely zero knowledge proofs and distributed hash tables. We show how we can preserve privacy of the user identity without jeopardizing security. We formally prove correctness and provide complexity results for our protocols. The complexity results show that our approach is efficient. In the paper we also show that the protocol is robust enough even in case semi-trusted "honest-yet curious" service providers thus preventing against insider threat. In our analysis we give the desired properties of the cryptographic tools used and identify open problems. We believe that the approach represents a precursor to new and innovative cryptographic techniques which can provide solutions for the security and privacy problems in federated identity management.
This paper proves that several interactive proof systems are zero-knowledge against general quantum attacks. This includes the well-known Goldreich–Micali–Wigderson classical zero-knowledge protocols for graph isomorphism and graph 3-coloring (assuming the existence of quantum computationally concealing commitment schemes in the second case). Also included is a quantum interactive proof system for a complete problem for the complexity class of problems having honest verifier quantum statistical zero-knowledge proofs, which therefore establishes that honest verifier and general quantum statistical zero-knowledge are equal: $\mathrm{QSZK}= \mathrm{QSZK}_{\mathrm{HV}}$. Previously no nontrivial interactive proof systems were known to be zero-knowledge against quantum attacks, except in restricted settings such as the honest verifier and common reference string models. This paper therefore establishes for the first time that true zero-knowledge is indeed possible in the presence of quantum information and computation.