CertiCrypt is a framework that enables the machine-checked construction and verification of cryptographic proofs in the Coq proof assistant. CertiCrypt instruments the code-based game-based approach to cryptographic proofs, and builds upon many areas, including probability and complexity theory, algebra, semantics of programming languages, and program optimizations. In this thesis, we illustrate the application of CertiCrypt on two examples: the Hashed ElGamal encryption scheme and zero-knowledge protocols. Like previous case studies in CertiCrypt, these examples demonstrate the feasibility of formalizing complex cryptographic proofs. However, using CertiCrypt requires a high level of expertise in Coq, and is time consuming. In order to ease the adoption of formal proofs by the cryptographic community, we develop a semi-automated tool, called EasyCrypt, for elaborating security proofs of cryptographic systems from proof sketches. Proof sketches are checked automatically using SMT solvers and automated theorem provers, and then compiled into verifiable proofs in the CertiCrypt framework. We illustrate the application of EasyCrypt with two examples: the Hashed ElGamal encryption system, and the Cramer-Shoup encryption system. Finally, we extend the language of CertiCrypt with a formalization of polytime functions.
When initializing cryptographic systems or running cryptographic protocols, the randomness of critical parameters, like keys or key components, is one of the most crucial aspects. But, randomly chosen parameters come with the intrinsic chance of duplicates, which finally may cause cryptographic systems including RSA, ElGamal and Zero-Knowledge proofs to become insecure. When concerning digital identifiers, we need uniqueness in order to correctly identify a specific action or object. Unfortunately we also need randomness here. Without randomness, actions become linkable to each other or to their initiator’s digital identity. So ideally the employed (cryptographic) parameters should fulfill two potentially conflicting requirements simultaneously: randomness and uniqueness. This article proposes an efficient mechanism to provide both attributes at the same time without highly constraining the first one and never violating the second one. After defining five requirements on random number generators and discussing related work, we will describe the core concept of the generation mechanism. Subsequently we will prove the postulated properties (security, randomness, uniqueness, efficiency and privacy protection) and present some application scenarios including system-wide unique parameters, cryptographic keys and components, identifiers and digital pseudonyms.
We define a new notion of relatively-sound non-interactive zeroknowledge (NIZK) proofs, where a private verifier with access to a trapdoor continues to be sound even when the Adversary has access to simulated proofs and common reference strings. It is likely that this weaker notion of relative-soundness suffices in most applications that need simulation-soundness. We show that for certain languages whicharediversegroups,and henceallowsmoothprojectivehashfunctions, one can obtain more efficient single-theorem relatively-sound NIZKsas opposed to simulation-sound NIZKs. We alsoshow that such relatively-sound NIZKs can be used to build rather efficient publiclyverifiable CCA2-encryption schemes. By employing this new publicly-verifiable encryption scheme along withanassociatedsmoothprojective-hash,weshowthatarecentPAKmodel single-round password-basedkey exchange protocol of Katz and
Commitment schemes, secret sharing schemes, interactive zero-knowledge proofs which underlie the offered interactive secrete sharing schemes are considered. Such schemes are one of the main computing primitives in the theory of secure computations. Base elements of the theory of secure computations and schemes of construction of synchronous verifiable secrete sharing as schemes of secure function evaluation are resulted.
In this paper, based on the verifiable pair and identity-based threshold cryptography, a novel identity-based (ID-based) threshold decryption scheme (IDTDS) is proposed, which is provably secure against adaptive chosen ciphertext attack under the computational bilinear Diffie-Hellman (CBDH) problem assumption in the random oracle. The pubic checkability of ciphertext in the IDTDS is given by simply creating a signed ElGamal encryption instead of a noninteractive zero-knowledge proof. Furthermore, we introduce a modified verifiable pairing to ensure all decryption shares are consistent. Our scheme is more efficient in verification than the schemes considered previously.
This paper presents a new zero-knowledge protocol for SDH pair,which based on TOO/BB-E encryption from DBDH as-sumption.This protocal's security is stronger than reference[1].
A zero-knowledge proof of identity protocol is a special cryptographic algorithm for identity verification. The security of most of the zero-knowledge proof of identity protocols is based on complex mathematical algorithms and requires heavy computations for both parties involved, the proverb and the verifier. Thus, the two parties must depend on computing devices (computers) to perform these computations. Visual cryptography is a special kind of the cryptography that does not require one to know the cryptography and the corresponding complex mathematical computations. In this paper, we propose a new method of zero-knowledge proof of identity based on a non-expansion visual cryptography to overcome the disadvantage of complex computation in the current zero-knowledge proof of identity protocols, thus overcoming the dependence on computing devices.
Advanced Steganography and Watermarking Techniques
We put forward the concepts of universal authentication, restrictive authentication and designated authentication. We then revisit a popular signcryption scheme using a technique similar to the one developed in Schnorr's signature, allowing it respects the restrictive authentication property. Comparing with the modification suggested by Baek et al in 2007, which uses a zero-knowledge proof run between the recipient and the third party, our scheme saves about 1/2 cost. Besides, the security of the revisited scheme can be reduced to that of Schnorr's signature.
Abstract. We present a variant of Regev’s cryptosystem first presented in [Reg05], but with a new choice of parameters. By a recent classical re-duction by Peikert we prove the scheme semantically secure based on the worst-case lattice problem GapSVP. From this we construct a threshold cryptosystem which has a very efficient and non-interactive decryption protocol. We prove the threshold cryptosystem secure against passive adversaries corrupting all but one of the players, and againts active ad-versaries corrupting less than one third of the players. We also describe how one can build a distributed key generation protocol. In the final part of the paper we show how one can, in zero-knowledge- prove knowledge of the plaintext contained in a given ciphertext from Regev’s original cryptosystem or our variant. The proof is of size only a constant times the size of the public key. 1
We proposed a new zero-knowledge proof of identity protocol based on Mandelbrot and Julia Fractal sets. The Fractal based zero-knowledge protocol was possible because of the intrinsic connection between the Mandelbrot and Julia Fractal sets. In the proposed protocol, the private key was used as an input parameter for Mandelbrot Fractal function to generate the corresponding public key. Julia Fractal function was then used to calculate the verified value based on the existing private key and the received public key. The proposed protocol was designed to be resistant against attacks. Fractal based zero-knowledge protocol was an attractive alternative to the traditional number theory zero-knowledge protocol.
Nowadays it is widely accepted to formulate the security of a protocol carrying out a given task via the “trusted-party paradigm,” where the protocol execution is compared with an ideal process where the outputs are computed by a trusted party that sees all the inputs. A protocol is said to securely carry out a given task if running the protocol with a realistic adversary amounts to “emulating” the ideal process with the appropriate trusted party. In the Universal Composability (UC) framework the program run by the trusted party is called an ideal functionality. While this simulation-based security formulation provides strong security guarantees, its usefulness is contingent on the properties and correct specification of the ideal functionality, which, as demonstrated in recent years by the coexistence of complex, multiple functionalities for the same task as well as by their “unstable” nature, does not seem to be an easy task. In this paper we address this problem, by introducing a general methodology for the sound specification of ideal functionalities. First, we introduce the class of canonical ideal functionalities for a cryptographic task, which unifies the syntactic specification of a large class of cryptographic tasks under the same basic template functionality. Furthermore, this representation enables the isolation of the individual properties of a cryptographic task as separate members of the corresponding class. By endowing the class of canonical functionalities with an algebraic structure we are able to combine basic functionalities to a single final canonical functionality for a given task. Effectively, this puts forth a bottom-up approach for the specification of ideal functionalities: first one defines a set of basic constituent functionalities for the task at hand, and then combines them into a single ideal functionality taking advantage of the algebraic structure. In our framework, the constituent functionalities of a task can be derived either directly or, following a translation strategy we introduce, from existing game-based definitions; such definitions have in many cases captured desired individual properties of cryptographic tasks, albeit in less adversarial settings. Our translation methodology entails a sequence of steps that systematically derive a corresponding canonical functionality given a game-based definition, effectively “lifting” the game-based definition to its composition-safe version. We showcase our methodology by applying it to a variety of basic cryptographic tasks, including commitments, digital signatures, zero-knowledge proofs, and oblivious transfer. While in some cases our derived canonical functionalities are equivalent to existing formulations, thus attesting to the validity of our approach, in others they differ, enabling us to “debug” previous definitions and pinpoint their shortcomings.
This paper presents a new zero knowledge protocol for knowledge of (A,x,y),which is based on Cramer-shoup encryptionfrom linear assumption. Compared with reference,this protocol has one more parameter.
Zero-knowledge set is a primitive introduced by Micali, Rabin, and Kilian (FOCS 2003) which enables a prover to commit a set to a verifier, without revealing even the size of the set. Later the prover can give zero-knowledge proofs to convince the verifier of membership/nonmembership of elements in/not in the committed set. We present a new primitive called Statistically Hiding Sets (SHS), similar to zero-knowledge sets, but providing an information theoretic hiding guarantee. This is comparable to relaxing zero-knowledge proofs to witness independent proofs. More precisely, we continue to use the simulation paradigm for our definition, but do not require the simulator (nor the distinguisher) to be efficient. We present a new scheme for statistically hiding sets, which does not fit into the “Merkletree/mercurial-commitment” paradigm used for all zero-knowledge set constructions so far. This not only provides some efficiency gains compared to the best possible schemes in that paradigm, but also lets us provide statistical hiding, without the prover having to maintain growing amounts of state with each new proof; this is not known to be possible with the previous approach.
2 source records
Advanced Steganography and Watermarking Techniques
This work addresses the subject of mathematics education at secondary schools from a current and stimulating point of view intimately related to computational science. Cryptology is a captivating way of introducing into the classroom different mathematical subjects such as functions, matrices, modular arithmetic, combinatorics, equations, statistics and proofs, which usually are recognized as difficult for many students. Special attention is paid here to the concepts of proof and verification through the definition of zero-knowledge cryptographic protocols. Many other different cryptographic and cryptanalytic activities (building and breaking ciphers, respectively) and modern cryptographic applications such as secret-sharing protocols are also proposed as resources for motivating mathematics learning and for achieving a significant improvement in student understanding of several algebraic, analytical and statistical concepts.