Abstract. Most prior designated confirmer signature schemes either prove security in the random oracle model (ROM) or use general zeroknowledge proofs for NP statements (making them impractical). By slightly modifying the definition of designated confirmer signatures, Goldwasser and Waisbard presented an approach in which the Confirm and ConfirmedSign protocols could be implemented without appealing to general zero-knowledge proofs for NP statements (their Disavow protocol still requires them). The Goldwasser-Waisbard approach could be instantiated using Cramer-Shoup, GMR, or Gennaro-Halevi-Rabin signatures. In this paper, we provide an alternate generic transformation to convert any signature scheme into a designated confirmer signature scheme, without adding random oracles. Our key technique involves the use of a signature on a commitment and a separate encryption of the random string used for commitment. By adding this “layer of indirection, ” the underlying protocols in our schemes admit efficient instantiations (i.e., we can avoid appealing to general zero-knowledge proofs for NP statements) and furthermore the performance of these protocols is not tied to the choice of underlying signature scheme. We illustrate this using the Camenisch-Shoup variation on Paillier’s cryptosystem and Pedersen commitments. The confirm protocol in our resulting scheme requires 10 modular exponentiations (compared to 320 for Goldwasser-Waisbard) and our disavow protocol requires 41 modular exponentiations (compared to using a general zero-knowledge proof for Goldwasser-Waisbard). Previous schemes use the encryption of a signature paradigm, and thus run into problems when trying to implement the confirm and disavow protocols efficiently. 1
In this paper, we present a fair non-repudiation protocol as an early effort to achieve fairness in the wireless environment. We propose a pseudo-resilient channel to satisfy the common assumption of fair protocols. We also use the RSA-based convertible signature schemes and non-interactive zero-knowledge proofs to reduce bandwidth and computation consumptions.
Gustavo A. Santana Torrellas, Andrés Tamayo Domínguez
Businesses are deploying Public Key Infrastructures (PKIs) to support internal business processes, implement virtual private networks, and secure corporate assets. The ability to establish business relations inside the company as well as with other companies in a secure way is important for the operability of business in today's world; corporate PKIs may implement different architectures, security policies, and cryptographic suites in order to accomplish this goal. But communication beyond the PKI is established with other companies based on a trust relationship (B2B), which brings vulnerability provided by PKIs from different companies. A flexible mechanism is needed to link these corporate PKIs and translate corporate relationships with security mechanisms and policies. This is accomplished through a Password Authentication Protocol (PAK), which provides means to authenticate or validate users across Bridge Certification Authorities (BCA), where certificates authorities (CA) are limited and cannot reach over to the other side of the BCA. In such a way, PAK can guarantee authentication of end points without modifying the original PKI structure of companies and offer flexibility in the process of implementation. Additional to this, there are several other issues that must be solved; such as the ability to connect different company PKI without compromising any sensible information that might cause a conflict of commercial interests and still guarantee a certain level of security through an accreditation and validation of the parties in order to be certain with whom we are doing business. In order to achieve accreditation and validation of PKIs and not expose any sensible information that could compromise either parties, we also based our work on a zero-knowledge security protocol, letting each PKI continue with their security policies without having to adjust to specific needs, achieving a better security level of commercial transactions through such hardening process.
Previous designated confirmer signature schemes were less e#cient because complex zero-knowledge proof employed in confirmation and disavowal protocol. In this paper, we propose a new e#cient signature scheme which is recipient-specific and confirmer-specific. The new scheme is transformed from ID-based chameleon signature and inherits its advantage in simplicity and e#ciency. The scheme's security relies on the underlying secure chameleon signature and public key encryption scheme. We also considers the case of confirmer as an adversary in security proof.
A zero-knowledge proof of identity protocol on conic is proposed in this paper.The security of this protocol is based on the discrete logarithm problem on conic over finite fields.These kinds of identity protocols can be designed and implemented easier than those on elliptic curve,and faster than those based on discrete logarithm.Security and feasibility are discussed.A simple solution is proposed to a potential leak of this protocol.
Abstract. We propose the first distributed discrete-log key generation (DLKG) protocol from scratch which is adaptively-secure in the nonerasure model, and at the same time completely avoids the use of interactive zero-knowledge proofs. As a consequence, the protocol can be proven secure in a universally-composable (UC) like framework which prohibits rewinding. We prove the security in what we call the singleinconsistent-player UC model, which guarantees arbitrary composition as long as all protocols are executed by the same players. As an application, we propose a fully UC threshold Schnorr signature scheme. Our results are based on a new adaptively-secure Feldman VSS scheme. Although adaptive security was already addressed by Feldman in the original paper, the scheme requires secure communication, secure erasure, and either a linear number of rounds or digital signatures to resolve disputes. Our scheme overcomes all of these shortcomings, but on the other hand requires some restriction on the corruption behavior of the adversary, which however disappears in some applications including our new DLKG protocol. We also propose several new adaptively-secure protocols, which may find other applications, like a sender non-committing encryption scheme, a distributed trapdoor-key generation protocol for Pedersen’s commitment scheme, or distributed-verifier proofs for proving relations among commitments or even any NP relations in general. 1
Zero-knowledge proofs are one of the most important cryptographic notions. Since their introduction in the early 80's by Goldwasser, Micali and Racko, they have proven very useful in the design of cryptographic protocols. Nevertheless, many limitations (in terms of e ciency and robustness under concurrent executability of protocols) have also been noticed. In order to overcome these limitations two lines of research have been investigated in the literature: 1. Models with some limited intervention of a trusted party (for example during a set-up phase). 2. Weakenings of the notion of zero-knowledge. In this thesis we attempt to further the understanding of the notion of zero-knowledge proofs by addressing both the above lines of research. More precisely, 1. Concerning the rst line of research, we show that the de nition of zeroknowledge in certain popular models (namely the Common Reference
Ma and Chen have proposed an authenticated encryption scheme with public verifiability. The scheme claims that the TTP can publicly verify the sender's signature without running a zero knowledge proof protocol. The problem in verification which causes the TTP to reject a valid signature with non-negligible probability is pointed out.
Ma and Chen proposed a new authenticated encryption scheme with public verifiability. This scheme requires less computational costs and communication overheads than the conventional signature-then-encryption approaches. In this letter, we show that the Ma-Chen scheme does not satisfy three security properties: unforgeability, confidentiality and non-repudiation. Introduction: For electronical commercial applications, evidence of possession of documents is especially important. A digital signature is analogous to an ordinary hand-written signature and establishes both of signer authenticity and data integrity assurance. However, it is necessary to keep commercial documents confident to protect the privacy of users in many applications. One simple way to implement such authenticated encryption scheme is to sign and encrypt message separately, first-sign-then-encrypt or first-encrypt-then-sign. This way perhaps results in separation of signature and ciphertext. Other way is to combine signature and encryption together in order to reduce the amount of computational cost and communication overheads. In 1997, Zheng proposed two new combined schemes [1], called signcryption scheme, in which message encryption and digital signature are simultaneously fulfilled in a logically single step. Besides some security shortcomings [2, 3], the Zheng schemes are not efficient as a zero-knowledge proof is required in its non-repudiation protocol. Recently, Ma and Chen proposed a new authenticated encryption scheme with public verifiability [4]. They claimed that their scheme is as efficient as the Zheng signcryption schemes with respect to both computational costs and communication overheads. In addition, their scheme has an efficient non-repudiation procedure without using a zero-knowledge proof protocol. Ma and Chen further claimed that their scheme satisfy three security properties: unforgeability, confidentiality and non-repudiation. In this letter, we would show the Ma-Chen scheme is not only erroneous but also insecure. The honest receiver cannot convince the judge that the valid signature is signed by the true signer, while the dishonest receiver can deceive the judge into believing the forged signature of any message. Moreover, if the scheme is adapted for the case of a long message, it cannot withstand the known plaintext-ciphertext attack. Belief review of the Ma-Chen scheme: Initially, two large primes p and q with q|(p – 1) and an element g ∈ Zp of order q are computed by a trusted third party (TTP for short) and are authenticated to each user. Each user i ∈{A, B} chooses a secret key xi∈ Zqand computes his public key yi = i x g mod p. He publishes yi which is 1 of 4 Tuesday , September 09, 2003
Jung Min Park, Edwin K. P. Chong, Howard Jay Siegel
Fueled by the exponential growth in the number of people with access to the Internet, electronic-commerce (e-commerce) transactions via the Internet have become a major part of our economy. For a wider range of e-commerce applications to take advantage of the untapped business potential of the Internet, some challenging and interesting security problems need to be solved. In this thesis, we study two such problems, and provide efficient solutions for both. In the foreseeable future, some e-commerce vendors will generate revenue by providing digital streaming applications such as information broadcasts (e.g., stock quotes). For the first issue, we investigate the problem of authenticating packet streams in multicast or broadcast networks. Our approach is to encode the hash values and digital signatures with Rabin's Information Dispersal Algorithm (IDA) to construct an authentication scheme that amortizes a single signature operation over multiple packets. This strategy is especially efficient in terms of space overhead because just the essential elements needed for authentication (i.e., one hash per packet and one signature per group of packets) are used in conjunction with an erasure code that is space optimal. We evaluate the performance of our scheme using both analytical and empirical results. Applications such as e-commerce payment protocols using electronic money require that fair exchange be assured. For the second issue, we investigate the problem of constructing fair-exchange protocols. Our approach uses a novel signature paradigm---the gradational signature scheme---to construct protocols that are efficient and scalable. Unlike previous approaches, our scheme does not employ any costly zero-knowledge proof systems in the exchange protocol. Use of zero-knowledge proofs is needed only in the protocol setup phase-this is a one-time cost. The resulting exchange protocol is more efficient than the previous solutions in terms of computation and communication overhead.
This thesis is written for the Swedish degree Licentiate ofScience, Teknisk Licentiat.It is a university degree, between that of master andthat of doctor.The main focus of the thesis is on the construction ofsecure protocols for comparing the underlying plain-texts inElGamal encryptions. The protocols make use of the malleabilityof the ElGamal encryption scheme. More specifically they usethe multiplicative homomorphic property of ElGamal.We present fully verifiable protocols for both thetwo-party setting and the multi-party setting. These protocolsare built on sub-protocols, which are specially constructed tofit the present setting. We also present full proofs forcompleteness, soundness, and zero-knowledge for all the givenprotocols, in the random oracle model.
Sung Jun Park, Tae‐Hoon Kim, Dong Ho Won, Young Hwa An
We propose a new notion of an entrusted undeniable signature which is a variant of the undeniable signature. Also we propose a provably entrusted undeniable signature whose security can be proved. The proposed entrusted undeniable signature is a new type of undeniable signature in which the signer confirms his(her) signature to any verifier without the help of court but the verifier can't run the disavowal protocol in the undeniable signature which only court can run to solve the dispute later. The proposed scheme is constructed by a combination of the undeniable signature and zero-knowledge interactive proof system. The proposed provably entrusted undeniable signature is much the same as our entrusted undeniable signature but using the public key residue cryptosystem, which is polynomially secure, for the commitment scheme.
A new framework is proposed for the analysis of communication protocols that require accountability, such as those for electronic commerce. Informal arguments are presented to show that a heretofore un-explored property "provability" is pertinent to examine the potential use of communication protocols in the context of litigation, and in the context of audit. A set of postulates which are applicable to the analysis of proofs in general (e.g., zero knowledge proofs), and the proofs of accountability in particular, are proposed. The proposed approach is more natural for the analysis of accountability then the existing belief logics that have been used in the past for the analysis of key distribution protocols. Some recently proposed protocols for electronic commerce and public-key delegation are analyzed to illustrate the use of the new analysis framework in detecting (and suggesting remedies for eliminating) their lack of accountability, and in detecting and eliminating redundancies.>
We suggest a systematic way to design secure password-based authentication protocols, which is the password verifier model. The method makes use of zero-knowledge interactive proof (ZKIP), which has been known not to be useful for the protection of passwords. For the proper usage of ZKIP, we introduce a specialized form of ZKIP, which has a secret coin tossing stage.
We consider the problem of designing an efficient oblivious transfer (OT) protocol that is provably secure in a concurrent setting, i.e., where many OT sessions may be running concurrently with their messages interleaved arbitrarily. Known OT protocols use zero-knowledge proofs, and no concurrent zero-knowledge proofs are known that use less than a poly-logarithmic number of rounds (at least without requiring a pre-processing phase, a public random string, an auxiliary string, timing constraints, or pre-distributed public keys). We introduce a model for proving security of concurrent OT protocols, and present a protocol that is proven secure in this model based on the decisional Diffie-Hellman problem. The protocol is efficient, requiring only a slightly non-constant number of rounds.
In this paper, we propose the absentee e-voting system based on security, completeness and verifiability. We use r-th residue cryptography for homomorphic encryption, ZKIP (Zero-Knowledge interactive proofs), RSA algorithm for the secure absentee e-voting.
A new multiple secrets sharing scheme, based on the intractability of the discrete logarithm (DL) and the RSA encryption algorithm is presented, in which the participants' shadows remain secret and can be reused, even if all subshadows are made public. Meanwhile, by using a zero-knowledge proof protocol, the validity verification of shadow and subshadow is also provided to prevent both dealer cheating and other participant cheating, and any freely given secrets without pre-computation by dealer can be reconstructed. The scheme can be applied to many areas such as conference key distribution, secure multi-part-computation, threshold signature etc.
In this paper we examine the role of Identification Protocols in the field of Cryptography. Firstly, the rationale behind the need for Identification Protocols is discussed. Secondly, we examine, in detail, challenge-response protocols, based upon zero-knowledge proofs, that form a subset of Identification Protocols in general. Thirdly, the mathematical tools necessary for the understanding of how these protocols work is given. Finally, we discuss four main Identification Protocols: Fiat-Shamir, Feige-Fiat-Shamir, Schnorr and Guillou- Quisquater. This discussion includes the theory, practical examples and the security aspects of each protocol.
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
Magdi El-Soudani, Heba S. El-Refaey, Hebat-Allah M. Mourad
Zero knowledge proofs form an important category in the public key identification protocols, they are depending on number theory. In 1989, Stern announced his protocol which is based on syndrome-decoding problem, he also studied the attacks against this type of problems. In this paper, we propose a broadcasting variant based on the Stern’ s Identification scheme. Broadcasting is applied when there are one prover and many verifiers. In the proposed broadcasting scheme, the prover is communicating with verifiers through a broadcasting channel so he is running the identification session once, which minimizes the time and the communication complexity. We have developed Stern basic scheme to be adequate for broadcasting applications, but the underlying hard problem that the security of Stern identification scheme depends on, is used as it is.