Watrous had presented the first proof of zero-knowledge property of a proof system against a quantum verifier. The key of the proof is the construction of a quantum simulator. In the construction, the 'failure state' is rotated to the 'success' state by a tricky operation which is initially developped for the amplification of QMA proof systems. This manuscript presents a new and simpler construction of a simulator. In the construction, we simply amplify the success probability of a classical simulator using Grover's amplification.
In this paper, we propose a proof scheme of shuffle, which is an honest verifier zero-knowledge proof of knowledge such as the protocols by Groth and Furukawa. Unlike the previous schemes proposed by Furukawa-Sako, Groth, and Furukawa, our scheme can be used as the shuffle of the elements encrypted by Paillier's encryption scheme, which has an additive homomorphic property in the message part. The ElGamal encryption scheme used in the previous schemes does not have this property.
The need for cryptography has been recognized since ancient times. One of its main goals, private communication in the presence of adversary, is traced back to the ancient Roman empire, whose emperor Julius Ceasar used to communicate to his allies by replacing each letter in his message with the third next letter in the alphabet. Classical cryptography went on until the end of last century focusing on the art of designing and breaking secrecy codes. Modern cryptography has significantly enlarged its scope to the rigorous analysis of any system that is potentially subject to malicious threats and the design of solution that can guarantee the system to withstand such threats. As a consequence, many goals have been added to that of private communication in the presence of adversary, and cryptography has moved from an engineering art built on a number of heuristic techniques to a scientific discipline based on mathematically rigorous design requirements, solution techniques and correctness proofs. We present here an introduction to some basic topics in the foundation of modern cryptography; specifically: one-way functions, pseudo-random generators, pseudo-random functions and zero-knowledge protocols.
Recently, two generic watermarking protocols were proposed, based on a popular zero-knowledge identification protocol. In this paper, we show that both protocols are flawed and therefore fail to achieve their purpose of allowing a prover to prove to a verifier of his ownership of a watermarked image. We also give some suggestions to fix these flaws.
2 source records
Advanced Steganography and Watermarking Techniques
Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran, Arun Sahai
We investigate the feasibility of a variety of cryptographic tasks with imperfect randomness. The kind of imperfect randomness we consider are entropy sources, such as those considered by Santha and Vazirani, Chor and Goldreich, and Zuckerman. We show the following: (1) certain cryptographic tasks like bit commitment, encryption, secret sharing, zero-knowledge, non-interactive zero-knowledge, and secure two-party computation for any non-trivial junction are impossible to realize if parties have access to entropy sources with slightly less-than-perfect entropy, i.e., sources with imperfect randomness. These results are unconditional and do not rely on any un-proven assumption. (2) On the other hand, based on stronger variants of standard assumptions, secure signature schemes are possible with imperfect entropy sources. As another positive result, we show (without any unproven assumption) that interactive proofs can be made sound with respect to imperfect entropy sources.
Cryptography and Data Security
Chaos-based Image/Signal Encryption
Advanced Steganography and Watermarking Techniques
We present a protocol for verification of ``no such entry'' replies from databases. We introduce a new cryptographic primitive as the underlying structure, the keyed hash tree, which is an extension of Merkle's hash tree. We compare our scheme to Buldas et al.'s Undeniable Attesters and Micali et al.'s Zero Knowledge Sets.
The editors of SIAM Review are delighted to present a SIGEST paper about cryptography, a topic that appears frequently these days in mainstream news media. Stories about computer security, defenses against terrorism, privacy, and file swapping invariably refer to cryptographic systems, which thus represent an extraordinarily visible example of the practical application of mathematics and computer science. Encryption systems depend on a stream of new mathematical results and algorithms; it may take years of study by experts to prove that a proposed technique is secure (or not). An additional wrinkle is that humans tend to avoid any encryption procedure that they perceive to be too much trouble, which means that researchers in cryptography need to consider criteria like ease of use as well as more precise properties. Cryptographers are blessed with, and continue to devise, engaging terminology and even some implied personalities. No discussion of cryptography is complete without Alice and Bob---so much more appealing than A and B---whose roles may, however, vary. For example, Alice and Bob are sometimes friends eager to communicate secrets without others learning them, and sometimes two people who need to communicate but do not know or trust each other; new variations on Alice, Bob, and their relationship are constantly emerging. Another fixture in cryptography is the presumably evil adversary, who may be passive (an eavesdropper limited to observing the information traffic sent between Alice and Bob) or active (someone who can see and modify the traffic). Wide use is made of "zero knowledge proof systems" (an apparently contradictory term), and this paper defines an evocatively named "garbage/not garbage" oracle that is useful in validity checks. The standard requirement of semantic security for cryptosystems means that an adversary learns nothing about the original text (the "plaintext") from its encrypted form (the "ciphertext"). The stricter requirement of nonmalleability, needed to hide information from active adversaries, means, roughly speaking, that an adversary cannot use the ciphertext associated with an original plaintext to produce an encryption of a related plaintext. This issue's SIGEST paper, "Nonmalleable Cryptography," by D. Dolev, C. Dwork, and M. Naor, which first appeared in 2000 in volume 30 of the SIAM Journal on Computing, identified and addressed the concept of nonmalleability. The paper has been extremely influential, is widely cited, and has inspired a substantial level of related research. For the paper's appearance in SIGEST, the authors have added an extended and completely new preface, intended for the general SIREV reader, that introduces much of the terminology, presents easily understood examples, and brings the reader up-to-date on related problems. Section 1.4, on deniable authentication, clarifies some of the many complications in defining new protocols and their desired (or undesired) security features. The original paper itself explores in detail the implications of nonmalleability, presenting nonmalleable schemes for three key problem classes and proving security against strong ciphertext attacks. We are grateful indeed to the authors for their extra efforts to make this important paper accessible to nonexperts in cryptography.
S. Armeni, D. Christodulakis, Ioannis Kostopoulos, Yannis C. Stamatiou · 5 authors
In this work, a method for proving copyright ownership is presented that is based on Zero Knowledge Interactive Proof (ZKIP) protocols for computationally intractable problems. The utilized problem is the 3-coloring problem, which consists in assigning one of three available colors to the vertices of a graph so that no two adjacent vertices have the same color. Using the presumed computational intractability of this problem, the construction of large signatures is proposed so that they represent adjacency matrices of random, 3-colorable graphs. Since it is easy to construct large graphs with a prescribed 3-coloring of their vertices whereas it is difficult to discover such a 3-coloring, the owner of a copyrighted digital piece of work (e.g. image, audio, video) may easily generate a random 3-colorable graph, embed it in the digital object and then use the knowledge of the 3-coloring in debates over the object’s ownership. Due to the intractability of the 3-coloring problem, only the owner is able to produce it sufficiently fast in an ownership challenge so as to convince a third party that the graph was indeed embedded in the object by herself/himself. Since graphs with maximum possible resistance to well-known coloring algorithms is required, we exploit some relatively recent experimental and theoretical findings suggesting that hard 3-coloring instances are found among graphs having a vertices to edges ratio around a specific threshold value. The proposed scheme has the additional advantage that disclosing the signature is of no consequences since it is essentially the knowledge of a characteristic of the signature, i.e. the 3-coloring of the graph it represents, that enables one to use it as proof of ownership of some digital object that contains it. Even if someone managed to locate and extract the signature, to use it would require a fast solution to a computationally intractable problem on some hard instance. Our proposal represents a shift from signatures that are simply viewed as bit sequences to signatures with properties that stem from their interpretation as instances of computationally intractable problems.
Advanced Steganography and Watermarking Techniques
Vanesa Daza, Javier Herranz, Carles Padró, Germán Sáez
In [16], Naor, Pinkas and Reingold introduced schemes in which some groups of servers distribute keys among a set of users in a distributed way. They gave some specic proposals both in the unconditional and in the computational security framework. Their computationally secure scheme is based on the Decisional DiÆe-Hellman Assumption. This model assumes secure communication between users and servers. Furthermore it requires users to do some expensive computations in order to obtain a key. In this paper we modify the model introduced in [16], requiring au-thenticated channels instead of assuming the existence of secure channels. Our model makes the user's computations easier, because most compu-tations of the protocol are carried out by servers, keeping to a more re-alistic situation. We propose a basic scheme, that makes use of ElGamal cryptosystem, and that ts in with this model in the case of a passive ad-versary. We then add zero-knowledge proofs and veriable secret sharing to prevent from the action of an active adversary. We consider general structures (not only the threshold ones) for those subsets of servers that can provide a key to a user and for those tolerated subsets of servers that can be corrupted by the adversary. We nd necessary combinatorial conditions on these structures in order to provide security to our scheme. 1
A new electronic cash scheme based on zero knowledge proof is proposed Unlike the other proposed schemes,our electronic cash scheme is not based on any specific scheme Thus we have provided an approach to construct electronic cash with any blind signature scheme or zero knowledge proof system The security of our scheme is proved based on some cryptographic assumptions
A family $(S_t)$ of sets is $p$-bounded Diophantine if $S_t$ has a representing $p$-bounded polynomial $R_{S,t}$, s.t.~$x\\in S_t \\iff (\\exists y)[R_{S}(x;y)=0]$. We say that $(S_t)$ is unbounded Diophantine if additionally, $R_{S,t}$ is a fixed $t$-independent polynomial. We show that $p$-bounded (resp., unbounded) Diophantine set has a polynomial-size (resp., constant-size) statistical zero-knowledge proof system that a committed tuple $x$ belongs to $S$. We describe efficient SZK proof systems for several cryptographically interesting sets. Finally, we show how to prove in SZK that an encrypted number belongs to $S$.
Abstract. In this work we use cryptography to solve a game-theoretic problem which arises naturally in the area of two party strategic games. The standard game-theoretic solution concept for such games is that of an equilibrium, which is a pair of “self-enforcing ” strategies making each player’s strategy an optimal response to the other player’s strategy. It is known that for many games the expected equilibrium payoffs can be much higher when a trusted third party (a “mediator”) assists the players in choosing their moves (correlated equilibria), than when each player has to choose its move on its own (Nash equilibria). It is natural to ask whether there exists a mechanism that eliminates the need for the mediator yet allows the players to maintain the high payoffs offered by mediator-assisted strategies. We answer this question affirmatively provided the players are computationally bounded and can have free communication (so-called “cheap talk”) prior to playing the game. The main building block of our solution is an efficient cryptographic protocol to the following Correlated Element Selection problem, which is of independent interest. Both Alice and Bob know a list of pairs (a1, b1)... (an, bn) (possibly with repetitions), and they want to pick a random index i such that Alice learns only ai and Bob learns only bi. Our solution to this problem has constant number of rounds, negligible error probability, and uses only very simple zero-knowledge proofs. We then show how to incorporate our cryptographic protocol back into a game-theoretic setting, which highlights some interesting parallels between cryptographic protocols and extensive form games. 1