Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn
A signature scheme is malleable if, on input a message m and a signature σ, it is possible to efficiently compute a signature σ ′ on a related message m ′ = T (m), for a transformation T that is allowable with respect to this signature scheme. Previous work considered various useful flavors of allowable transformations, such as quoting and sanitizing messages. In this paper, we explore a connection between malleable signatures and anonymous credentials, and give the following contributions: • We define and construct malleable signatures for a broad category of allowable transformation classes, with security properties that are stronger than those that have been achieved previously. Our construction of malleable signatures is generically based on malleable zero-knowledge proofs, and we show how to instantiate it under the Decision Linear assumption. • We construct delegatable anonymous credentials from signatures that are malleable with respect to an appropriate class of transformations; we also show that our construction of malleable signatures works for this class of transformations. The resulting concrete instantiation is the first to achieve security under a standard assumption (Decision Linear) while also scaling linearly with the number of delegations. 1
Thesis (M.S.C.S.) PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you.
Cryptography and Residue Arithmetic
Cryptography and Data Security
Advanced Steganography and Watermarking Techniques
By analyzing the definition of the platform configuration registers(PCRs) in the trusted computing platform(TCP) by the trusted computing group(TCG) and combining related researches for techniques of data sealing,a method for property representation of the trusted platform.This method not only can fully illustrate all the characteristics of a trusted computing platform is proposed,but also can make the verification process of the properties with the zero-knowledge proof more conveniently.As well known,one major and inherent defect of trusted computing platform is its exposure for user's privacy.Aiming at overcoming such a drawback,a method of data sealing based on property with zero-knowledge proof is proposed.And in this method,a Trusted Third Party is invited to make proof for verifying the trusted platform.The analysis for security of the method is presented and verification is made for it by experiment.Results from the experiment shows that,this method maintains as the same advantages as other existed schemes,whereas only with a small quantity of data cost.Such small data incrementation not only supports unsealing at remote server,but also works well for preventing privacy disclosure in a trusted platform.
There is the advantage of zero-knowledge proofs of identity without letting out any users' secret when prover and verifier are communicating.But most of existing zero-knowledge proofs are iterative in nature,and require multiple communication rounds.To solve this problem,a new protocol was proposed based on challenge-response mode and elliptic curve algorithm.The interactive process of the new scheme was analyzed in detail.The analysis shows that the scheme ensures high security and also is resettable with only one-round communication,and low computing cost.
Cryptography and Data Security
Cryptography and Residue Arithmetic
Advanced Steganography and Watermarking Techniques
The zero knowledge proof protocol is a powerful cryptographic system.The security of most of the zero knowledge proof identification protocols is based on complex mathematical algorithms and requires heavy interactive computations for both parties,involving the prover and the verifier.However,visual cryptography is special since it does not require one to know the cryptography and the corresponding complex mathematical computations.In this paper,a new zero knowledge proof identification method based on the visual cryptography is proposed,it reduces current zero knowledge proof identification protocol’s dependence on computing devices and the complex computation.
Advanced Steganography and Watermarking Techniques
Lattice-based cryptography is one of the most active research topics in cryptography in recent years. In many cryptographic constructions based on lattice assumptions, the building block is a proof of knowledge of a solution to an instance of the Inhomogeneous Small Integer Solution (ISIS) problem. However, all known such proof \n \nsystems have relatively weak security guarantees: Breaking each of these protocols is potentially easier than solving the underlying instance of the ISIS problem. As a consequence, cryptographic constructions relying on these proof systems typically inherit the sub-optimal security guarantees. Therefore, proof systems with stronger security guarantees are highly desirable. Such protocols are not only interesting from a theoretical point of view, but they also lead to lattice-based cryptographic constructions relying on weaker hardness assumptions than the contemporary schemes. \n \n \n \nIn this thesis, we construct a series of zero-knowledge proofs of knowledge with strong security guarantees and reasonable communication costs, that can find various applications in lattice-based cryptography. Our constructions rely on a simple, yet versatile and effective technique, called Decomposition-Extension. When adapting this technique to the Stern-KTX proof system (Stern ‘96 - Kawachi, Tanaka, Xagawa ‘08), we obtain a zero-knowledge proof of knowledge for the ISIS problem (in the infinity norm) with a very strong security guarantee: Breaking the protocol is as least as hard as solving the underlying ISIS instance. We then develop our technique to design the following lattice-based cryptographic constructions: \n \n \n \n- Efficient zero-knowledge proofs of plaintext knowledge with strong security guarantees \n \nfor 4 encryption schemes based on the Learning with Errors problem: Regev’s scheme (Regev ‘05); the Dual-Regev scheme (Gentry, Peikert, Vaikuntanathan ‘08); the PVW scheme (Peikert, Vaikuntanathan, Waters ‘08); and the GHV scheme (Gentry, Halevi, Vaikuntanathan ‘10). Our results immediately yield 4 lattice-based interactive encryption protocols that are secure under chosen ciphertext attacks. Previously, only zero-knowledge proofs of plaintext knowledge for Regev’s scheme were known, and they are relatively inefficient with rather weak security guarantees. \n \n \n \n- A lattice-based identity-based identification scheme relying on a weaker hardness assumption than in the previous works. Furthermore, we introduce an identity-based ring identification scheme based on the worst-case hardness of lattice problems. To the best of our knowledge, this is the first such scheme. \n \n \n \n- An improved lattice-based group signature scheme relying on relatively weak hardness assumptions, in which the signature size is logarithmic in the number of group users. Earlier lattice-based group signature schemes, which were published before 2013, rely on relatively weak hardness assumptions but have the undesirable property that the size of the signature is linear in the number of group users. A recent scheme (Laguillaumie, Langlois, Libert, Stehlé ‘13) achieves logarithmic signature size but it has to rely on relatively strong hardness assumptions. Our construction, thus, simultaneously achieves the good features of the existing schemes.
Abstract Crypto-computing is a set of well-known techniques for com-puting with encrypted data. The security of the corresponding proto-cols are usually proven in the semi-honest model. In this work, we pro-pose a new class of zero-knowledge proofs, which are tailored for crypto-computing protocols. First, these proofs directly employ properties of the underlying crypto systems and thus many facts have more concise proofs compared to generic solutions. Second, we show how to achieve univer-sal composability in the trusted set-up model where all zero-knowledge proofs share the same system-wide parameters. Third, we derive a new protocol for multiplicative relations and show how to combine it with several crypto-computing frameworks.
By analyzing the existed solutions of sealed storage and combining the definition of the Platform Configuration Register(PCR) by the Trusted Computing Group(TCG),a method for property representation is proposed.This method not only illustrates all the characteristics of a Trusted Computing Platform fully and classifies the Trusted Computing Platform by its property readily,but it also able to make the validation process of the property with the zero-knowledge proof more conveniently.The paper invites a Trusted Third Party(TTP) to define the property of a Trusted Computing Platform and illustrates the principle of the property definition.Aiming at overcoming the inherent defect of Trusted Computing Platform,privacy disclosure,this paper proposes a method of sealed storage based on zero-knowledge proof with Trusted Third Party by introducing zero-knowledge proof into the process of property verifying of the trusted platform.Analysis shows that this method supports remote unseal of the data and avoids the privacy disclosure while maintaining the strengths of existed solutions.It gains stronger security.
Abstract Password-authenticated key exchange (PAKE) protocols allow two players to agree on a shared high entropy secret key, that depends on their own passwords only. Following the Gennaro and Lindell’s approach, with a new kind of smooth-projective hash functions (SPHFs), Katz and Vaikuntanathan recently came up with the first concrete one-round PAKE protocols, where the two players just have to send simultaneous flows to each other. The first one is secure in the Bellare-Pointcheval-Rogaway (BPR) model and the second one in the Canetti’s UC framework, but at the cost of simulation-sound non-interactive zero-knowledge (SS-NIZK) proofs (one for the BPR-secure protocol and two for the UC-secure one), which make the overall constructions not really efficient. This paper follows their path with, first, a new efficient instantiation of SPHF on Cramer-Shoup ciphertexts, which allows to get rid of the SS-NIZK proof and leads to the design of the most efficient one-round PAKE known so far, in the BPR model, and in addition without pairings. In the UC framework, the security proof required the simulator to be able to extract the hashing key of the SPHF, hence the additional SS-NIZK proof. We improve the way the latter extractability is obtained by introducing the notion of trapdoor smooth projective hash functions (TSPHFs). Our concrete instantiation leads to the most efficient one-round PAKE UC-secure against static corruptions to date. We additionally show how these SPHFs and TSPHFs can be used for blind signatures and zero-knowledge proofs with straight-line extractability. 1
Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proved. Their direct applications in cryptography are numerous, where they are typically used to force malicious parties to behave according to a predetermined protocol. In addition, zero-knowledge proofs serve as an excellent bench-mark for the study of various problems regarding cryptographic protocols.
The notion of zero-knowledge [GMR85] is formalized by requiring that for every malicious efficient verifier V ∗ , there exists an efficient simulator S that can reconstruct the view of V ∗ in a true interaction with the prover, in a way that is indistinguishable to every polynomialtime distinguisher. Weak zero-knowledge weakens this notions by switching the order of the quantifiers and only requires that for every distinguisher D, there exists a (potentially different) simulator SD. In this paper we consider various notions of zero-knowledge, and investigate whether their weak variants are equivalent to their strong variants. Although we show (under complexity assumption) that for the standard notion of zero-knowledge, its weak and strong counterparts are not equivalent, for meaningful variants of the standard notion, the weak and strong counterparts are indeed equivalent. Towards showing these equivalences, we introduce new non-black-box simulation techniques permitting us, for instance, to demonstrate that the classical 2-round graph non-isomorphism protocol of Goldreich-Micali-Wigderson [GMW91] satisfies a “distributional” variant of zero-knowledge. Our equivalence theorem has other applications beyond the notion of zero-knowledge. For instance, it directly implies the dense model theorem of Reingold et al (STOC ’08), and the leakage lemma of Gentry-Wichs (STOC ’11), and provides a modular and arguably simpler proof of these results (while at the same time recasting these result in the language of zeroknowledge). 0 1
As recent studies show, the notions of program obfuscation and zero knowledge are intimately connected. In this work, we explore this connection further, and prove the following general result. If there exists differing input obfuscation (diO) for the class of all polynomial time Turing machines, then there exists a four message, fully concurrent zero-knowledge proof system for all languages in NP with negligible soundness error. This result is constructive: given diO, our reduction yields an explicit protocol along with an explicit simulator that is “straight line” and runs in strict polynomial time. Our reduction relies on a new non-black-box simulation technique which does not use the PCP theorem. In addition to assuming diO, our reduction also assumes (standard and polynomial time) cryptographic assumptions such as collision-resistant hash functions. The round complexity of our protocol also sheds new light on the exact round complexity of concurrent zero-knowledge. It shows, for the first time, that in the realm of non-black-box simulation, concurrent zero-knowledge may not necessarily require more rounds than stand alone zero-knowledge!
We define a novel notion of quasi-adaptive non-interactive zero knowledge (NIZK) proofs for probability distributions on parametrized languages. It is quasi-adaptive in the sense that the common reference string (CRS) generator can generate the CRS depending on the parameters defining the language. However, the simulation is required to be uniform, i.e., a single efficient simulator should work for the whole class of parametrized languages. For distributions on languages that are linear subspaces of vector spaces over bilinear groups, we give quasi-adaptive NIZKs that are shorter and more efficient than Groth-Sahai NIZKs. For many cryptographic applications quasi-adaptiveNIZKs suffice, and our constructionscan lead to significant improvements in the standard model. Our construction can be based on any k-linear assumption, and in particular under the Symmetric eXternal Diffie Hellman (SXDH) assumption our proofs are even competitive with Random-Oracle based Σ-protocol NIZK proofs. We also show that our system can be extended to include integer tags in the defining equations, where the tags are provided adaptively by the adversary. This leads to applicability of our system to many applications that use tags, e.g. applications using Cramer-Shoup projective
Abstract. Groth-Sahai proofs are efficient non-interactive zero-knowledge proofs that have found widespread use in pairingbased cryptography. We propose efficiency improvements of Groth-Sahai proofs in the SXDH setting, which is the one that yields the most efficient non-interactive zero-knowledge proofs. – We replace some of the commitments with ElGamal encryptions, which reduces the prover’s computation and for some types of equations reduces the proof size. – Groth-Sahai proofs are zero-knowledge when no public elements are paired to each other. We observe that they are also zero-knowledge when base elements for the groups are paired to public constants. – The prover’s computation can be reduced by letting her pick her own common reference string. By giving a proof she has picked a valid common reference string this does not compromise soundness. – We define a type-based commit-and-prove scheme, which allows commitments to be reused in many different proofs.
Bryan Parno, Jon Howell, Craig Gentry, Mariana Raykova
To instill greater confidence in computations outsourced to the cloud, clients should be able to verify the correctness of the results returned. To this end, we introduce Pinocchio, a built system for efficiently verifying general computations while relying only on cryptographic assumptions. With Pinocchio, the client creates a public evaluation key to describe her computation; this setup is proportional to evaluating the computation once. The worker then evaluates the computation on a particular input and uses the evaluation key to produce a proof of correctness. The proof is only 288 bytes, regardless of the computation performed or the size of the inputs and outputs. Anyone can use a public verification key to check the proof. Crucially, our evaluation on seven applications demonstrates that Pinocchio is efficient in practice too. Pinocchio’s verification time is typically 10ms: 5-7 orders of magnitude less than previous work; indeed Pinocchio is the first general-purpose system to demonstrate verification cheaper than native execution (for some apps). Pinocchio also reduces the worker’s proof effort by an additional 19-60×. As an additional feature, Pinocchio generalizes to zero-knowledge proofs at a negligible cost over the base protocol. Finally, to aid development, Pinocchio provides an end-to-end toolchain that compiles a subset of C into programs that implement the verifiable computation protocol. 1
A secure anonymous authentication scheme was proposed based on elliptic curve and zero-knowledge proof,which adopts a bidirectional anonymous authentication algorithm to preserve users’ privacy during the certification process.In the case of a high density traffic scenario,a message aggregation technology was proposed to realize fast authentication by the assistant of RSU,and to avoid the loss of massive messages unauthenticated promptly.The simulation and analytical results show that the proposed scheme yields a much better performance than previously reported counterparts with lower communication overhead,message loss rate and message delay.