Algorithms and Approaches of Proxy Signature: A Survey
---
paper_title: Proxy multi-signature scheme: a new type of proxy signature scheme

paper_content:

Proxy signature schemes allow a proxy signer to generate a proxy signature on behalf of an original signer. However, since in previous proxy signature schemes a proxy signature is created on behalf of only one original signer, these schemes are referred to as proxy mono-signature schemes. A new type of proxy signature scheme is presented called the proxy multi-signature scheme in which a proxy signer can generate a proxy signature on behalf of two or more original signers.
---
paper_title: Repudiation of Cheating and Non-repudiation of Zhang's Proxy Signature Schemes

paper_content:

The paper discusses the correctness of Lee, Hwang and Wang's comments on on Zhang's proxy signature schemes. In particular, it is shown that the cheating attack proposed by Lee, Hwang and Wang can be detected by the owner of the signature scheme. It is argued that considering the context in which proxy signatures are used, the attack is not a security problem. The work is concluded by a discussion about the non-repudiation controversy incorrectly observed by Lee, Hwang and Wang.
---
paper_title: The Digital Distributed System Security Architecture

paper_content:

The Digital Distributed System Security Architecture is a comprehensive speci cation for security in a distributed system that employs state-of-the-art concepts to address the needs of both commercial and government environments. The architecture covers user and system authentication, mandatory and discretionary security, secure initialization and loading, and delegation in a general-purpose computing environment of heterogeneous systems where there are no central authorities, no global trust, and no central controls. The architecture prescribes a framework for all applications and operating systems currently available or to be developed. Because the distributed system is an open OSI environment, where functional interoperability only requires compliance with selected protocols needed by a given application, the architecture must be designed to securely support systems that do not implement or use any of the security services, while providing extensive additional security capabilities for those systems that choose to implement the architecture.
---
paper_title: Proxy signature schemes based on factoring

paper_content:

The proxy signature schemes allow proxy signers to sign messages on behalf of an original signer, a company or an organization. However, most of existing proxy signature schemes are based on the discrete logarithm problem. In this paper, the author would like to propose two efficient proxy signature schemes based on the factoring problem, which combine the RSA signature scheme and the Guillou-Quisquater signature scheme. One is a proxy-unprotected signature scheme that is more efficient. No matter how many proxy signers cooperatively sign a message, the computation load for verifiers would remain almost constant. The other is a proxy-protected signature scheme that is more secure. Finally, to protect the privacy of proxy signers, the author proposes a proxy-protected signature scheme with anonymous proxy signers.
---
paper_title: Revisiting Fully Distributed Proxy Signature Schemes

paper_content:

In a proxy signature scheme, a potential signer delegates his capabilities to a proxy signer, who can sign documents on behalf of him. The recipient of the signature verifies both identities: that of the delegator and that of the proxy signer. There are many proposals of proxy signature schemes, but security of them has not been considered in a formal way until the appearance of [2,8]. ::: ::: If the entities which take part in a proxy signature scheme are formed by sets of participants, then we refer to it as a fully distributed proxy signature scheme [4]. ::: ::: In this work, we extend the security definitions introduced in [2] to the scenario of fully distributed proxy signature schemes, and we propose a specific scheme which is secure in this new model.
---
paper_title: Improved Non-Repudiable Threshold Proxy Signature Scheme with Known Signers

paper_content:

In 2001, Hsu et al. proposed a non-repudiable threshold proxy signature with known signers. In their scheme, the proxy group cannot deny having signed the proxy signature if they did. However, Hsu et al.'s scheme is vulnerable to some attacks. A malicious original signer or malicious proxy signer can impersonate some other proxy signers to generate proxy signatures. In this article, we shall present our cryptanalysis of the Hsu et al.'s scheme. After that, we shall propose a new threshold proxy signature that can overcome the weaknesses.
---
paper_title: The Hierarchy of Key Evolving Signatures and a Characterization of Proxy Signatures

paper_content:

For the last two decades the notion and implementations of proxy signatures have been used to allow transfer of digital signing power within some context (in order to enable flexibility of signers within organizations and among entities). On the other hand, various notions of the key-evolving signature paradigms (forward-secure, key-insulated, and intrusion-resilient signatures) have been suggested in the last few years for protecting the security of signature schemes, localizing the damage of secret key exposure. In this work we relate the various notions via direct and concrete security reductions that are tight. We start by developing the first formal model for fully hierarchical proxy signatures, which, as we point out, also addresses vulnerabilities of previous schemes when self-delegation is used. Next, we prove that proxy signatures are, in fact, equivalent to key-insulated signatures. We then use this fact and other results to establish a tight hierarchy among the key-evolving notions, showing that intrusion-resilient signatures and key-insulated signatures are equivalent, and imply forward-secure signatures. We also introduce other relations among extended notions. Besides the importance of understanding the relationships among the various notions that were originally designed with different goals or with different system configuration in mind, our findings imply new designs of schemes. For example, many proxy signatures have been presented without formal model and proofs, whereas using our results we can employ the work on key-insulated schemes to suggest new provably secure designs of proxy signatures schemes.
---
paper_title: Efficient proxy multisignature schemes based on the elliptic curve cryptosystem

paper_content:

For improving proxy-signature research, Sun [5] attempted to resolve problems related to defective security in the scheme of Yi [3]. However, both Yi and Sun's schemes involve a significant number of exponential operations to verify the proxy signature. Accordingly, an improvement is proposed here to change the exponential operations into elliptic curve multiplicative ones. As proposed by both Koblitz [6-7] and Miller [8] in 1985, the elliptic curve is used in developing the cryptosystems. The elliptic curve cryptosystem can achieve a level of security equal to that of RSA or DSA but has a lower computational overhead and a smaller key size than both of these. Therefore, it is used in Sun's schemes to improve their efficiency.
---
paper_title: Threshold proxy signatures

paper_content:

A (t, n) threshold proxy signature scheme allows t or more proxy signers from a designated group of n proxy signers to sign messages on behalf of an original signer. The authors review both Zhang's threshold proxy signature scheme and Kim's threshold proxy signature scheme. They show that Zhang's scheme suffers from some weaknesses and Kim's scheme suffers from a disadvantage. Based on Zhang's scheme, they propose a new threshold proxy signature scheme to defeat the weaknesses of Zhang's scheme and the disadvantage of Kim's scheme.
---
paper_title: An efficient nonrepudiable threshold proxy signature scheme with known signers

paper_content:

A (t,n) threshold proxy signature scheme allows t or more proxy signers from a designated group of n proxy signers to sign messages on behalf of an original signer. A threshold proxy signature scheme with the nonrepudiation property is a scheme with the capability that any verifier can identify the proxy group which is responsible for a proxy signature, while the proxy group cannot deny. So far, there have been two threshold proxy signature schemes proposed. Of these, Kim's scheme is nonrepudiable, but Zhang's scheme is not. In these two schemes, the t proxy signers from the group who actually sign the message are unknown and unidentified. This is very inconvenient for auditing purposes. For the responsibility of the actual signers and the traceability of adversarial signers, it is sometimes necessary to identify who the actual signers are. In this article, we propose the nonrepudiable threshold proxy signature scheme with known signers which is a nonrepudiable threshold proxy signature scheme with the property that the actual signers from the proxy group are known and identified.
---
paper_title: Convertible Nominative Signatures

paper_content:

A feasible solution to prevent potential misuse of signatures is to put some restrictions on their verification. Therefore S.J.Kim, [4] S.J.Park and D.H.Won introduced the nominative signature, in which only the nominee can verify and prove the validity of given signatures, and proposed a nominative signature scheme (called KPW scheme). In this paper, we first show that KPW scheme is not nominative because the nominator can also verify and prove the validity of given signatures. Then we extend the concept of nominative signature to the convertible nominative signature which has an additional property that the nominee can convert given nominative signatures into universally verifiable signatures. We give a formal definition for it and propose a practical scheme that implements it. The proposed scheme is secure, in which its unforgeability is the same as that of the Schnorr’s signature scheme and its untransferability relies on the hardness of the Decision-Diffie-Hellman Problem.
---
paper_title: Secure Mobile Agent Digital Signatures with Proxy Certificates

paper_content:

Security issues related to the usage of mobile agents in performing operations to which their owners have to be bound, such as payments, are of utmost importance if this kind of agents are to be used in electronic commerce. If this binding is achieved by means of digital signature techniques, this means agents have to carry the owner's private key to the host where they sign documents. This exposes the key to attacks because it is copied outside a protected environment. In this paper, we present a mechanism, called proxy certificates, that avoids the need for the agent to have access to the user's private key for digitally signing documents, but still binds the owner to the contents of those documents. In order to support our claims, we apply the mechanism to SET/A, an agent-based payment system we proposed in previous work. We also analyze the emerging technology of attribute certificates and argue that it is appropriate to implement proxy certificates.
---
paper_title: Improvement of threshold proxy signature scheme

paper_content:

Abstract A (t, n) threshold proxy signature scheme allows any t or more proxy signers to cooperatively sign messages on behalf of an original signer, but t−1 or fewer proxy signers cannot. Sun et al. proposed a new (t, n) threshold proxy signature scheme based on Zhang's threshold proxy signature scheme. Recently, Hsu et al. pointed out that Sun's scheme suffered from a drawback and proposed an improvement to counter it. However, the author of this paper shows that both Sun's scheme and Hsu's improvement are not secure against coalition attack. Some t or more malicious proxy signers can conspire together against the original signer. Finally, we propose a new improvement to counter this attack, the proxy generation and the signature computation of which is more efficient than those of Sun's scheme and Hsu's improvement. The main advantage of the new improvement is traceability, by which the original signer can identify the actual signers that are anonymous to outsiders.
---
paper_title: A SECURE NONREPUDIABLE THRESHOLD PROXY SIGNATURE SCHEME WITH KNOWN SIGNERS

paper_content:

In the (t;n) proxy signature scheme, the signature, originally signed by a signer, can be signed by t or more proxy signers out of a proxy group of n members. Recently, an efficient nonrepudiable threshold proxy signature scheme with known signers was proposed by H.-M. Sun. Sun's scheme has two advantages. One is nonrepudiation. The proxy group cannot deny that having signed the proxy signature. Any verifier can identify the proxy group as a real signer. The other is identifiable signers. The verifier is able to identify the actual signers in the proxy group. Also, the signers cannot deny that having generated the proxy signature. In this article, we present a cryptanalysis of the Sun's scheme. Further, we propose a secure, nonrepudiable and known signers threshold proxy signature scheme which remedies the weakness of the Sun's scheme.
---
paper_title: Handbook of Applied Cryptography

paper_content:

From the Publisher: ::: A valuable reference for the novice as well as for the expert who needs a wider scope of coverage within the area of cryptography, this book provides easy and rapid access of information and includes more than 200 algorithms and protocols; more than 200 tables and figures; more than 1,000 numbered definitions, facts, examples, notes, and remarks; and over 1,250 significant references, including brief comments on each paper.
---
paper_title: Threshold Proxy Signature Schemes

paper_content:

Delegation of rights is a common practice in the real world. Proxy signature schemes have been invented to delegate signing capability efficiently and transparently. In this paper, we present a new nonrepudiable proxy signature scheme. Nonrepudiation means the signature signers, both original and proxy signers, cannot falsely deny later that he generated a signature. In practice, it is important and, sometimes, necessary to have the ability to know who is the actual signer of a proxy signature for internal auditing purpose or when there is abuse of signing capability. The new nonrepudiable proxy signature scheme also has other desirable properties, such as proxy signature key generation and updating using insecure channels. We also show how to construct threshold proxy signature schemes with an example. Threshold signatures are motivated both by the need that arises in some organizations to have a group of employees agree on a given message (or a document) before signing it, as well as by the need to protect signature keys from the attack of internal and external adversaries. Our approach can also be applied to other ElGamal-like proxy signature schemes.
---
paper_title: Proxy signatures, Revisited

paper_content:

Proxy signatures, introduced by Mambo, Usuda and Okamoto allow a designated person to sign on behalf of an original signer. This paper first presents two new types of digital proxy signatures called partial delegation with warrant and threshold delegation. Proxy signatures for partial delegation with warrant combines the benefit of Mambo's partial delegation and Neuman's delegation by warrant, and then in threshold delegation the proxy signer's power to sign messages is shared. Moreover, we also propose straightforward and concrete proxy signature schemes satisfying our conditions.
---
paper_title: Further Cryptanalysis of some Proxy Signature Schemes

paper_content:

Proxy signature is a signature that an original signer delegates his or her signing capability to a proxy signer, and then the proxy signer creates a signature on behalf of the original signer. However, Sun et al. [7] showed that the proxy and multi-proxy signatures of Lee et al. [3], and the strong proxy signature scheme with proxy signer privacy protection of Shum et al. [6] are not against the original signer’s forgery attack, so these schemes do not process the property of unforgeability. In this paper, we present an extensive forgery method on these schemes, following the work due to Sun et al.
---
paper_title: Comments on "A practical (t, n) threshold proxy signature scheme based on the RSA cryptosystem"

paper_content:

In a (t, n) threshold proxy signature scheme, the original signer can delegate his/her signing capability to n proxy signers such that any t or more proxy signers can sign messages on behalf of the former, but t-1 or less of them cannot do the same thing. Such schemes have been suggested for use in a number of applications, particularly, in distributed computing where delegation of rights is quite common. Based on the RSA cryptosystem, [M. -S. Hwang et al. (2003) recently proposed an efficient (t, n) threshold proxy signature scheme. We identify several security weaknesses in their scheme and show that their scheme is insecure.
---
paper_title: An Efficient Signature Scheme from Bilinear Pairings and Its Applications

paper_content:

In Asiacrypt2001, Boneh, Lynn, and Shacham [8] proposed a short signature scheme (BLS scheme) using bilinear pairing on certain elliptic and hyperelliptic curves. Subsequently numerous cryptographic schemes based on BLS signature scheme were proposed. BLS short signature needs a special hash function [6,1,8]. This hash function is probabilistic and generally inefficient. In this paper, we propose a new short signature scheme from the bilinear pairings that unlike BLS, uses general cryptographic hash functions such as SHA-1 or MD5, and does not require special hash functions. Furthermore, the scheme requires less pairing operations than BLS scheme and so is more efficient than BLS scheme. We use this signature scheme to construct a ring signature scheme and a new method for delegation. We give the security proofs for the new signature scheme and the ring signature scheme in the random oracle model.
---
paper_title: An analysis of proxy signatures: is a secure channel necessary?

paper_content:

Montgomery Prime Hashing (MPH) is a scheme for message authentication based on universal hashing.I n MPH, roughly speaking, the hash value is computed as the Montgomery residue of the message with respect to a secret modulus.The modulus value is structured in a way that allows fast, compact implementations in both hardware and software.The set of allowed modulus values is large, and as a result, MPH achieves good, provable security. ::: ::: MPH performance is comparable to that of other high-speed schemes such as MMH. An advantage of MPH is that the secret key (i.e., the modulus) is small, typically 128-256 bits, while in MMH the secret key is typically much larger.I n applications where MMH key length is problematic, MPH may be an attractive alternative.
---
paper_title: A Digital Nominative Proxy Signature Scheme for Mobile Communication

paper_content:

Based on the development of mobile communication, the future mobile communication systems are expected to provide higher quality of multimedia services for users than today's systems. Therefore, many technical factors are needed in this systems. Especially the secrecy and the safety would be obtained through the introduction of the security for mobile communication. In this paper, we presents a digital nominative proxy signature scheme that processes a user's digital signature and encryption using the proxy-agent who has more computational power than origins in mobile communication.
---
paper_title: On Zhang's Nonrepudiable Proxy Signature Schemes

paper_content:

In 1997, Zhang proposed two new nonrepudiable proxy signature schemes to delegate signing capability. Both schemes claimed to have a property of knowing that a proxy signature is generated by either the original signer or a proxy signer. However, this paper will show that Zhang's second scheme fails to possess this property. Moreover, we shall show that the proxy signer can cheat to get the original signer's signature, if Zhang's scheme is based on some variants of ElGamal-type signature schemes. We modify Zhang's nonrepudiable proxy signature scheme to avoid the above attacks. The modified scheme also investigates a new feature for the original signer to limit the delegation time to a certain period.
---
paper_title: Design of time-stamped proxy signatures with traceable receivers

paper_content:

A proxy signature scheme is a method which allows an original signer to delegate his signing power to a proxy signer. Most proxy signature schemes use a warrant appearing in the signature verification equation to declare the valid delegation period. However, the declaration in the warrant is useless because no-one can know the exact time when the proxy signer signed a message. To avoid the proxy signer abusing the signing capability, the original signer may hope to know the identity of who received the proxy signature from the proxy signer. Recently Sun and Chen proposed the concept of time-stamped proxy signatures with traceable receivers to solve these two problems. A time-stamped proxy signature scheme with traceable receivers is a proxy signature scheme which can ascertain whether a proxy signature is created during the delegation period, and can trace who actually received the proxy signatures from the proxy signer. The author shows that Sun and Chen's scheme suffers from weaknesses and consequently proposes a new time-stamped proxy signature scheme which doesn't suffer from the same weaknesses.
---
paper_title: ID-Based Multi-Proxy Signature and Blind Multisignature from Bilinear Pairings

paper_content:

Multi-proxy signature allows the original signer delegate his singing power to a group of proxy signers. Blind proxy-signature allows the user to obtain a signature of a message from several signers in a way that each signer learns neither the message nor the resulting signature. Plenty of multi-proxy signature and blind multisignature schemes have been proposed under the certificate-based (CA-based) public key systems. In this paper, we firstly propose an identity-based (IDbased) multi-proxy signature scheme and an ID-based blind multisignature scheme from bilinear pairings. Since there seems no ID-based threshold signature schemes up to now, both the proposed schemes can be regarded as a special case of corresponding variants of ID-based threshold signature.
---
paper_title: Cryptanalysis of Nonrepudiable Threshold Proxy Signature Schemes with Known Signers

paper_content:

Sun's nonrepudiation threshold proxy signature scheme is not secure against the collusion attack. In order to guard against the attack, Hwang et al. proposed another threshold proxy signature scheme. However, a new attack is proposed to work on both Hwang et al.'s and Sun's schemes. By executing this attack, one proxy signer and the original signer can forge any valid proxy signature. Therefore, both Hwang et al.'s scheme and Sun's scheme were insecure.
---
paper_title: A strong proxy signature scheme with proxy signer privacy protection

paper_content:

Mambo et al. (1996) discussed the delegation of signature power to a proxy signer. Lee et al. (2001) constructed a strong non-designated proxy signature scheme in which the proxy signer had strong non-repudiation. In this paper, we present an enhancement to their scheme such that the identity of the proxy signer is hidden behind an alias. The identity can be revealed only by the alias authority. We also discuss other applications of this technique.
---
paper_title: New Proxy Signature, Proxy Blind Signature and Proxy Ring Signature Schemes from Bilinear Pairings

paper_content:

Proxy signatures are very useful tools when one needs to delegate his/her signing capability to other party. After Mambo et al.’s first scheme was announced, many proxy signature schemes and various types of proxy signature schemes have been proposed. Due to the various applications of the bilinear pairings in cryptography, there are many IDbased signature schemes have been proposed. In this paper, we address that it is easy to design proxy signature and proxy blind signature from the conventional ID-based signature schemes using bilinear pairings, and give some concrete schemes based on existed ID-based signature schemes. At the same time, we introduce a new type of proxy signature – proxy ring signature, and propose the first proxy ring signature scheme based on an existed ID-based ring signature scheme.
---
paper_title: A traceable proxy multisignature scheme based on the elliptic curve cryptosystem

paper_content:

This study contributes to the public delivery of the delegation parameter and reduces the number of operations required to verify a proxy signature. A new proxy-protected proxy multisignature scheme is also proposed, which is based on the elliptic curve discrete logarithm problem (ECDLP). The proposed scheme inherits most of its merits from typical solutions to the discrete logarithm problem (DLP), thereby meeting the demand for security. The scheme that is based on the elliptic curve cryptosystem (ECC) can perform more efficiently than those based on DLP.
---
paper_title: Designated-verifier proxy signatures for e-commerce

paper_content:

In a designated-verifier proxy signature scheme, a user delegates her/his signing capability to another user in such a way that the latter can sign messages on behalf of the former, but the validity of generated signatures can only be checked by the designated verifier. In this paper, we first point out that one such scheme proposed recently by Dai et al. is insecure. To overcome the weaknesses in their scheme, based on the two-party Schnorr signature by Nicolosi et al., we present a new designated-verifier proxy signature scheme which is efficient and secure. Finally, we suggest the use of our scheme in electronic commerce applications, such as sale of digital products (digital music, movies, and books etc.).
---
paper_title: On the Security of Some Proxy Signature Schemes

paper_content:

Digital signature scheme is an important research topic in cryptography. An ordinary digital signature scheme allows a signer to create signatures of documents and the generated signatures can be verified by any person. A proxy signature scheme, a variation of ordinary digital signature scheme, enables a proxy signer to sign messages on behalf of the original signer. To be used in different applications, many proxy signatures were proposed. In this paper, we review Lee et al.’s strong proxy signature scheme, multi-proxy signature scheme, and its application to a secure mobile agent, Shum and Wei’s privacy protected strong proxy signature scheme, and Park and Lee’s nominative proxy signature scheme, and show that all these proxy signature schemes are insecure against the original signer’s forgery. In other words, these schemes do not possess the unforgeability property which is a desired security requirement for a proxy signature scheme.
---
paper_title: A practical (t, n) threshold proxy signature scheme based on the RSA cryptosystem

paper_content:

In a (t, n) threshold proxy signature scheme, the original signer delegates the power of signing messages to a designated proxy group of n members. Any t or more proxy signers of the group can cooperatively issue a proxy signature on behalf of the original signer, but (t - 1) or less proxy signers cannot. Previously, all of the proposed threshold proxy signature schemes have been based on the discrete logarithm problem and do not satisfy all proxy requirements. In this paper, we propose a practical, efficient, and secure (t, n) threshold proxy signature scheme based on the RSA cryptosystem. Our scheme satisfies all proxy requirements and uses only a simple Lagrange formula to share the proxy signature key. Furthermore, our scheme requires only 5 percent of the computational overhead and 8 percent of the communicational overhead required in Kim's scheme.
---
paper_title: Security Analysis of Some Proxy Signatures

paper_content:

A proxy signature scheme allows an entity to delegate his/her signing capability to another entity in such a way that the latter can sign messages on behalf of the former. Such schemes have been suggested for use in a number of applications, particularly in distributed computing where delegation of rights is quite common. Followed by the first schemes introduced by Mambo, Usuda and Okamoto in 1996, a number of new schemes and improvements have been proposed. In this paper, we present a security analysis of four such schemes newly proposed in [14, 15]. By successfully identifying several interesting forgery attacks, we show that these four schemes -all are insecure. Consequently, the fully distributed proxy scheme in [11] is also insecure since it is based on the (insecure) LKK scheme [13, 14]. In addition, we point out the reasons why the security proofs provided in [14] are invalid.
---
paper_title: ID-Based Proxy Signature Using Bilinear Pairings

paper_content:

Identity-based (ID-based) public key cryptosystem can be a good alternative for certificate-based public key setting, especially when efficient key management and moderate security are required. A proxy signature scheme permits an entity to delegate its signing rights to another entity. But to date, no ID-based proxy signature scheme with provable security has been proposed. In this paper, we formalize a notion of security for ID-based proxy signature schemes and propose a scheme based on the bilinear pairings. We show that the security of our scheme is tightly related to the computational Diffie-Hellman assumption in the random oracle model.
---
paper_title: Verifiable Secret Sharing for General Access Structures, with Application to Fully Distributed Proxy Signatures

paper_content:

Secret sharing schemes are an essential part of distributed cryptographic systems. When dishonest participants are considered, then an appropriate tool are verifiable secret sharing schemes. Such schemes have been traditionally considered for a threshold scenario, in which all the participants play an equivalent role. In this work, we generalize some protocols dealing with verifiable secret sharing, in such a way that they run in a general distributed scenario for both the tolerated subsets of dishonest players and the subsets of honest players authorized to execute the different phases of the protocols.
---
paper_title: Proxy and threshold one-time signatures

paper_content:

One-time signatures are an important and efficient authentication utility. Various schemes already exist for the classical one-way public-key cryptography. One-time signatures have not been sufficiently explored in the literature in the branch of society-oriented cryptography. Their particular properties make them suitable, as a potential cryptographic primitive, for broadcast communication and group-based applications. In this paper, we try to contribute to filling this gap by introducing several group-based one-time signature schemes of various versions: with proxy, with trusted party, and without trusted party.
---
paper_title: Provably secure delegation-by-certification proxy signature schemes

paper_content:

In this paper, we first show that a previous proxy signature scheme by delegation with certificate is not provably secure under adaptive-chosen message attacks and adaptive-chosen warrant attacks. The scheme does not provide the strong undeniability. Then we construct a proxy signature scheme by delegation with certificate based on Co-GDH group from bilinear map. Our proxy signature scheme is existentially unforgeable against adaptive-chosen message attacks and adaptive-chosen warrant attacks in random oracle model. We adopt a straight method of security reduction in which our scheme's security is reduced to hardness of the computational co-Diffie-Hellem problem. The proposed signature scheme is the first secure delegation-by-certificate proxy signature based on co-GDH groups from bilinear maps under the formal security model in random oracle model.
---
paper_title: Efficient signature generation by smart cards

paper_content:

We present a new public-key signature scheme and a corresponding authentication scheme that are based on discrete logarithms in a subgroup of units in ? p where p is a sufficiently large prime, e.g., p ? 2512. A key idea is to use for the base of the discrete logarithm an integer ? in ? p such that the order of ? is a sufficiently large prime q, e.g., q ? 2140. In this way we improve the ElGamal signature scheme in the speed of the procedures for the generation and the verification of signatures and also in the bit length of signatures. We present an efficient algorithm that preprocesses the exponentiation of a random residue modulo p.
---
paper_title: Handbook of Applied Cryptography

paper_content:

From the Publisher: ::: A valuable reference for the novice as well as for the expert who needs a wider scope of coverage within the area of cryptography, this book provides easy and rapid access of information and includes more than 200 algorithms and protocols; more than 200 tables and figures; more than 1,000 numbered definitions, facts, examples, notes, and remarks; and over 1,250 significant references, including brief comments on each paper.
---
paper_title: A forward-secure public-key encryption scheme

paper_content:

Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious and realistic concern. In an effort to mitigate the damage caused by exposure of secret data (e.g., keys) stored on such devices, the paradigm of forward security was introduced. In a forward-secure scheme, secret keys are updated at regular periods of time; furthermore, exposure of a secret key corresponding to a given time period does not enable an adversary to "break" the scheme (in the appropriate sense) for any prior time period. A number of constructions of forward-secure digital signature schemes, key-exchange protocols, and symmetric-key schemes are known. ::: ::: We present the first constructions of a (non-interactive) forward-secure public-key encryption scheme. Our main construction achieves security against chosen plaintext attacks under the decisional bilinear Diffie-Hellman assumption in the standard model. It is practical, and all complexity parameters grow at most logarithmically with the total number of time periods. The scheme can also be extended to achieve security against chosen ciphertext attacks.
---
paper_title: New Directions in Cryptography

paper_content:

Two kinds of contemporary developments in cryptography are examined. Widening applications of teleprocessing have given rise to a need for new types of cryptographic systems, which minimize the need for secure key distribution channels and supply the equivalent of a written signature. This paper suggests ways to solve these currently open problems. It also discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing.
---
paper_title: A digital signature scheme secure against adaptive chosen-message attacks

paper_content:

We present a digital signature scheme based on the computational difficulty of integer factorization.The scheme possesses the novel property of being robust against an adaptive chosen-message attack: an adversary who receives signatures for messages of his choice (where each message may be chosen in a way that depends on the signatures of previously chosen messages) cannot later forge the signature of even a single additional message. This may be somewhat surprising, since in the folklore the properties of having forgery being equivalent to factoring and being invulnerable to an adaptive chosen-message attack were considered to be contradictory.More generally, we show how to construct a signature scheme with such properties based on the existence of a “claw-free” pair of permutations—a potentially weaker assumption than the intractibility of integer factorization.The new scheme is potentially practical: signing and verifying signatures are reasonably fast, and signatures are compact.
---
paper_title: Reducing elliptic curve logarithms to logarithms in a finite field

paper_content:

Elliptic curve cryptosystems have the potential to provide relatively small block size, high-security public key schemes that can be efficiently implemented. As with other known public key schemes, such as RSA and discrete exponentiation in a finite field, some care must be exercised when selecting the parameters involved, in this case the elliptic curve and the underlying field. Specific classes of curves that give little or no advantage over previously known schemes are discussed. The main result of the paper is to demonstrate the reduction of the elliptic curve logarithm problem to the logarithm problem in the multiplicative group of an extension of the underlying finite field. For the class of supersingular elliptic curves, the reduction takes probabilistic polynomial time, thus providing a probabilistic subexponential time algorithm for the former problem. >
---
paper_title: Short Signatures from the Weil Pairing

paper_content:

We introduce a short signature scheme based on the Computational Diffie–Hellman assumption on certain elliptic and hyperelliptic curves. For standard security parameters, the signature length is about half that of a DSA signature with a similar level of security. Our short signature scheme is designed for systems where signatures are typed in by a human or are sent over a low-bandwidth channel. We survey a number of properties of our signature scheme such as signature aggregation and batch verification.
---
paper_title: A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves

paper_content:

The aim of this paper is to show that the computation of the discrete logarithm in the m-torsion part of the divisor class group of a curve X over a finite field ko (with char(ko) prime to m), or over a local field k with residue field ko, can be reduced to the computation of the discrete logarithm in k0(4m)* . For this purpose we use a variant of the (tame) Tate pairing for Abelian varieties over local fields. In the same way the problem to determine all linear combinations of a finite set of elements in the divisor class group of a curve over k or ko which are divisible by m is reduced to the computation of the discrete logarithm in ko(Cm)* -
---
paper_title: Identity-based encryption from the Weil pairing

paper_content:

We propose a fully functional identity-based encryption (IBE) scheme. The scheme has chosen ciphertext security in the random oracle model assuming a variant of the computational Diffie--Hellman problem. Our system is based on bilinear maps between groups. The Weil pairing on elliptic curves is an example of such a map. We give precise definitions for secure IBE schemes and give several applications for such systems.
---
paper_title: An Identity Based Encryption Scheme Based on Quadratic Residues

paper_content:

We present a novel public key cryptosystem in which the public key of a subscriber can be chosen to be a publicly known value, such as his identity. We discuss the security of the proposed scheme, and show that this is related to the difficulty of solving the quadratic residuosity problem.
---
paper_title: A method for obtaining digital signatures and public-key cryptosystems

paper_content:

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intented recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n , of two large secret primer numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ≡ 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n .
---
paper_title: Threshold proxy signatures

paper_content:

A (t, n) threshold proxy signature scheme allows t or more proxy signers from a designated group of n proxy signers to sign messages on behalf of an original signer. The authors review both Zhang's threshold proxy signature scheme and Kim's threshold proxy signature scheme. They show that Zhang's scheme suffers from some weaknesses and Kim's scheme suffers from a disadvantage. Based on Zhang's scheme, they propose a new threshold proxy signature scheme to defeat the weaknesses of Zhang's scheme and the disadvantage of Kim's scheme.
---
paper_title: Repudiation of Cheating and Non-repudiation of Zhang's Proxy Signature Schemes

paper_content:

The paper discusses the correctness of Lee, Hwang and Wang's comments on on Zhang's proxy signature schemes. In particular, it is shown that the cheating attack proposed by Lee, Hwang and Wang can be detected by the owner of the signature scheme. It is argued that considering the context in which proxy signatures are used, the attack is not a security problem. The work is concluded by a discussion about the non-repudiation controversy incorrectly observed by Lee, Hwang and Wang.
---
paper_title: Robust threshold DSS signatures

paper_content:

We present threshold DSS (Digital Signature Standard) signatures where the power to sign is shared by n players such that for a given parameter t < n/2 any subset of 2t + 1 signers can collaborate to produce a valid DSS signature on any given message, but no subset of t corrupted players can forge a signature (in particular, cannot learn the signature key). In addition, we present a robust threshold DSS scheme that can also tolerate n/3 players who refuse to participate in the signature protocol. We can also endure n/4 maliciously faulty players that generate incorrect partial signatures at the time of signature computation. This results in a highly secure and resilient DSS signature system applicable to the protection of the secret signature key, the prevention of forgery, and increased system availability. ::: ::: Our results significantly improve over a recent result by Langford from CRYPTO'95 that presents threshold DSS signatures which can stand much smaller subsets of corrupted players, namely, t ≅ √n, and do not enjoy the robustness property. As in thc case of Langford's result, our schemes require no trusted party. Our techniques apply to other threshold ElGamal-like signatures as well. We prove the security of our schemes solely based on the hardness of forging a regular DSS signature.
---
paper_title: Threshold proxy signatures

paper_content:

A (t, n) threshold proxy signature scheme allows t or more proxy signers from a designated group of n proxy signers to sign messages on behalf of an original signer. The authors review both Zhang's threshold proxy signature scheme and Kim's threshold proxy signature scheme. They show that Zhang's scheme suffers from some weaknesses and Kim's scheme suffers from a disadvantage. Based on Zhang's scheme, they propose a new threshold proxy signature scheme to defeat the weaknesses of Zhang's scheme and the disadvantage of Kim's scheme.
---
paper_title: Threshold Proxy Signature Schemes

paper_content:

Delegation of rights is a common practice in the real world. Proxy signature schemes have been invented to delegate signing capability efficiently and transparently. In this paper, we present a new nonrepudiable proxy signature scheme. Nonrepudiation means the signature signers, both original and proxy signers, cannot falsely deny later that he generated a signature. In practice, it is important and, sometimes, necessary to have the ability to know who is the actual signer of a proxy signature for internal auditing purpose or when there is abuse of signing capability. The new nonrepudiable proxy signature scheme also has other desirable properties, such as proxy signature key generation and updating using insecure channels. We also show how to construct threshold proxy signature schemes with an example. Threshold signatures are motivated both by the need that arises in some organizations to have a group of employees agree on a given message (or a document) before signing it, as well as by the need to protect signature keys from the attack of internal and external adversaries. Our approach can also be applied to other ElGamal-like proxy signature schemes.
---
paper_title: On Zhang's Nonrepudiable Proxy Signature Schemes

paper_content:

In 1997, Zhang proposed two new nonrepudiable proxy signature schemes to delegate signing capability. Both schemes claimed to have a property of knowing that a proxy signature is generated by either the original signer or a proxy signer. However, this paper will show that Zhang's second scheme fails to possess this property. Moreover, we shall show that the proxy signer can cheat to get the original signer's signature, if Zhang's scheme is based on some variants of ElGamal-type signature schemes. We modify Zhang's nonrepudiable proxy signature scheme to avoid the above attacks. The modified scheme also investigates a new feature for the original signer to limit the delegation time to a certain period.
---
paper_title: An analysis of proxy signatures: is a secure channel necessary?

paper_content:

Montgomery Prime Hashing (MPH) is a scheme for message authentication based on universal hashing.I n MPH, roughly speaking, the hash value is computed as the Montgomery residue of the message with respect to a secret modulus.The modulus value is structured in a way that allows fast, compact implementations in both hardware and software.The set of allowed modulus values is large, and as a result, MPH achieves good, provable security. ::: ::: MPH performance is comparable to that of other high-speed schemes such as MMH. An advantage of MPH is that the secret key (i.e., the modulus) is small, typically 128-256 bits, while in MMH the secret key is typically much larger.I n applications where MMH key length is problematic, MPH may be an attractive alternative.
---
paper_title: Distributed provers with applications to undeniable signatures

paper_content:

This paper introduces distributed prover protocols. Such a protocol is a proof system in which a polynomially bounded prover is replaced by many provers each having partial information about the witness owned by the original prover. As an application of this concept, it is shown how the signer of undeniable signatures can distribute part of his secret key to n agents such that any k of these can verify a signature. This facility is useful in most applications of undeniable signatures, and as the proposed protocols are practical, the results in this paper makes undeniable signatures more useful. The first part of the paper describes a method for verifiable secret sharing, which allows non-interactive verification of the shares and is as secure as the Shamir secret sharing scheme in the proposed applications.
---
paper_title: Improvement of threshold proxy signature scheme

paper_content:

Abstract A (t, n) threshold proxy signature scheme allows any t or more proxy signers to cooperatively sign messages on behalf of an original signer, but t−1 or fewer proxy signers cannot. Sun et al. proposed a new (t, n) threshold proxy signature scheme based on Zhang's threshold proxy signature scheme. Recently, Hsu et al. pointed out that Sun's scheme suffered from a drawback and proposed an improvement to counter it. However, the author of this paper shows that both Sun's scheme and Hsu's improvement are not secure against coalition attack. Some t or more malicious proxy signers can conspire together against the original signer. Finally, we propose a new improvement to counter this attack, the proxy generation and the signature computation of which is more efficient than those of Sun's scheme and Hsu's improvement. The main advantage of the new improvement is traceability, by which the original signer can identify the actual signers that are anonymous to outsiders.
---
paper_title: Threshold Proxy Signature Schemes

paper_content:

Delegation of rights is a common practice in the real world. Proxy signature schemes have been invented to delegate signing capability efficiently and transparently. In this paper, we present a new nonrepudiable proxy signature scheme. Nonrepudiation means the signature signers, both original and proxy signers, cannot falsely deny later that he generated a signature. In practice, it is important and, sometimes, necessary to have the ability to know who is the actual signer of a proxy signature for internal auditing purpose or when there is abuse of signing capability. The new nonrepudiable proxy signature scheme also has other desirable properties, such as proxy signature key generation and updating using insecure channels. We also show how to construct threshold proxy signature schemes with an example. Threshold signatures are motivated both by the need that arises in some organizations to have a group of employees agree on a given message (or a document) before signing it, as well as by the need to protect signature keys from the attack of internal and external adversaries. Our approach can also be applied to other ElGamal-like proxy signature schemes.
---
paper_title: Security Analysis of Some Proxy Signatures

paper_content:

A proxy signature scheme allows an entity to delegate his/her signing capability to another entity in such a way that the latter can sign messages on behalf of the former. Such schemes have been suggested for use in a number of applications, particularly in distributed computing where delegation of rights is quite common. Followed by the first schemes introduced by Mambo, Usuda and Okamoto in 1996, a number of new schemes and improvements have been proposed. In this paper, we present a security analysis of four such schemes newly proposed in [14, 15]. By successfully identifying several interesting forgery attacks, we show that these four schemes -all are insecure. Consequently, the fully distributed proxy scheme in [11] is also insecure since it is based on the (insecure) LKK scheme [13, 14]. In addition, we point out the reasons why the security proofs provided in [14] are invalid.
---
paper_title: Security Analysis of Some Proxy Signatures

paper_content:

A proxy signature scheme allows an entity to delegate his/her signing capability to another entity in such a way that the latter can sign messages on behalf of the former. Such schemes have been suggested for use in a number of applications, particularly in distributed computing where delegation of rights is quite common. Followed by the first schemes introduced by Mambo, Usuda and Okamoto in 1996, a number of new schemes and improvements have been proposed. In this paper, we present a security analysis of four such schemes newly proposed in [14, 15]. By successfully identifying several interesting forgery attacks, we show that these four schemes -all are insecure. Consequently, the fully distributed proxy scheme in [11] is also insecure since it is based on the (insecure) LKK scheme [13, 14]. In addition, we point out the reasons why the security proofs provided in [14] are invalid.
---
paper_title: Proxy signatures, Revisited

paper_content:

Proxy signatures, introduced by Mambo, Usuda and Okamoto allow a designated person to sign on behalf of an original signer. This paper first presents two new types of digital proxy signatures called partial delegation with warrant and threshold delegation. Proxy signatures for partial delegation with warrant combines the benefit of Mambo's partial delegation and Neuman's delegation by warrant, and then in threshold delegation the proxy signer's power to sign messages is shared. Moreover, we also propose straightforward and concrete proxy signature schemes satisfying our conditions.
---
paper_title: Proxy signatures, Revisited

paper_content:

Proxy signatures, introduced by Mambo, Usuda and Okamoto allow a designated person to sign on behalf of an original signer. This paper first presents two new types of digital proxy signatures called partial delegation with warrant and threshold delegation. Proxy signatures for partial delegation with warrant combines the benefit of Mambo's partial delegation and Neuman's delegation by warrant, and then in threshold delegation the proxy signer's power to sign messages is shared. Moreover, we also propose straightforward and concrete proxy signature schemes satisfying our conditions.
---
paper_title: Proxy and threshold one-time signatures

paper_content:

One-time signatures are an important and efficient authentication utility. Various schemes already exist for the classical one-way public-key cryptography. One-time signatures have not been sufficiently explored in the literature in the branch of society-oriented cryptography. Their particular properties make them suitable, as a potential cryptographic primitive, for broadcast communication and group-based applications. In this paper, we try to contribute to filling this gap by introducing several group-based one-time signature schemes of various versions: with proxy, with trusted party, and without trusted party.
---
paper_title: New Proxy Signature, Proxy Blind Signature and Proxy Ring Signature Schemes from Bilinear Pairings

paper_content:

Proxy signatures are very useful tools when one needs to delegate his/her signing capability to other party. After Mambo et al.’s first scheme was announced, many proxy signature schemes and various types of proxy signature schemes have been proposed. Due to the various applications of the bilinear pairings in cryptography, there are many IDbased signature schemes have been proposed. In this paper, we address that it is easy to design proxy signature and proxy blind signature from the conventional ID-based signature schemes using bilinear pairings, and give some concrete schemes based on existed ID-based signature schemes. At the same time, we introduce a new type of proxy signature – proxy ring signature, and propose the first proxy ring signature scheme based on an existed ID-based ring signature scheme.
---
paper_title: A Paradoxical Indentity-Based Signature Scheme Resulting from Zero-Knowledge

paper_content:

At EUROCRYPT'88, we introduced an interactive zero-knowledge protocol (Guillou and Quisquater [13]) fitted to the authentication of tamper-resistant devices (e.g. smart cards, Guillou and Ugon [14]).Each security device stores its secret authentication number, an RSA-like signature computed by an authority from the device identity. Any transaction between a tamper-resistant security device and a verifier is limited to a unique interaction: the device sends its identity and a random test number, then the verifier tells a random large question; and finally the device answers by a witness number. The transaction is successful when the test number is reconstructed from the witness number, the question and the identity according to numbers published by the authority and rules of redundancy possibly standardized.This protocol allows a cooperation between users in such a way that a group of cooperative users looks like a new entity, having a shadowed identity the product of the individual shadowed identities, while each member reveals nothing about its secret.In another scenario, the secret is partitioned between distinct devices sharing the same identity. A group of cooperative users looks like a unique user having a larger public exponent which is the greater common multiple of each individual exponent.In this paper, additional features are introduced in order to provide: firstly, a mutual interactive authentication of both communicating entities and previously exchanged messages, and, secondly, a digital signature of messages, with a non-interactive zero-knowledge protocol. The problem of multiple signature is solved here in a very smart way due to the possibilities of cooperation between users.The only secret key is the factors of the composite number chosen by the authority delivering one authentication number to each smart card. This key is not known by the user. At the user level, such a scheme may be considered as a keyless identity-based integrity scheme. This integrity has anew and important property: it cannot be misused, i.e. derived into a confidentiality scheme.
---
paper_title: Efficient proxy multisignature schemes based on the elliptic curve cryptosystem

paper_content:

For improving proxy-signature research, Sun [5] attempted to resolve problems related to defective security in the scheme of Yi [3]. However, both Yi and Sun's schemes involve a significant number of exponential operations to verify the proxy signature. Accordingly, an improvement is proposed here to change the exponential operations into elliptic curve multiplicative ones. As proposed by both Koblitz [6-7] and Miller [8] in 1985, the elliptic curve is used in developing the cryptosystems. The elliptic curve cryptosystem can achieve a level of security equal to that of RSA or DSA but has a lower computational overhead and a smaller key size than both of these. Therefore, it is used in Sun's schemes to improve their efficiency.
---
paper_title: Design of time-stamped proxy signatures with traceable receivers

paper_content:

A proxy signature scheme is a method which allows an original signer to delegate his signing power to a proxy signer. Most proxy signature schemes use a warrant appearing in the signature verification equation to declare the valid delegation period. However, the declaration in the warrant is useless because no-one can know the exact time when the proxy signer signed a message. To avoid the proxy signer abusing the signing capability, the original signer may hope to know the identity of who received the proxy signature from the proxy signer. Recently Sun and Chen proposed the concept of time-stamped proxy signatures with traceable receivers to solve these two problems. A time-stamped proxy signature scheme with traceable receivers is a proxy signature scheme which can ascertain whether a proxy signature is created during the delegation period, and can trace who actually received the proxy signatures from the proxy signer. The author shows that Sun and Chen's scheme suffers from weaknesses and consequently proposes a new time-stamped proxy signature scheme which doesn't suffer from the same weaknesses.
---

Title: Algorithms and Approaches of Proxy Signature: A Survey

Section 1: Introduction
Description 1: Provide an introduction to digital signatures, evolution of proxy signatures, and various types of delegations in proxy signatures.

Section 2: Discrete Logarithm Problem
Description 2: Discuss the discrete logarithm problem, its relevance in cryptography, and its application in signature schemes like Schnorr's signature scheme.

Section 3: Bilinear Pairings
Description 3: Explain bilinear pairings, their properties, computational problems related to them, and their use in cryptographic protocols like Hess's signature scheme.

Section 4: Integer Factorization Problem
Description 4: Describe the integer factorization problem, its significance in cryptography, and details of RSA-based signature schemes.

Section 5: Security Properties of a Proxy Signature
Description 5: Outline the desirable security properties that proxy signatures must possess, such as strong unforgeability, identifiability, undeniability, verifiability, distinguishability, secrecy, and prevention of misuse.

Section 6: Classification of Proxy Signature
Description 6: Classify proxy signatures based on the nature of delegation capability into proxy-unprotected, proxy-protected, and threshold notions.

Section 7: Models of Proxy Signature
Description 7: Categorize existing proxy signature schemes based on their security assumptions into DLP-based, RSA-based, and pairing-based models.

Section 8: DLP-based Proxy Signature
Description 8: Review proxy signatures where the security relies on the discrete logarithm problem, detailing their procedures and security.

Section 9: RSA-based Proxy Signature
Description 9: Discuss proxy signatures that depend on the RSA algorithm, outlining their key generation, delegation capability, and signature verification processes.

Section 10: ECDSA-based Proxy Signature
Description 10: Explore proxy signatures based on the elliptic curve digital signature algorithm, addressing the reduction of computational overheads and multi-signature schemes.

Section 11: Pairing-based Proxy Signature
Description 11: Examine proxy signatures utilizing bilinear pairings, detailing the generation and verification of proxy signatures and addressing their security concerns.

Section 12: Notable Proxy Signature Schemes
Description 12: Review contributions from various researchers, highlight notable proxy signature schemes, and discuss their strengths and weaknesses.

Section 13: Conclusion
Description 13: Summarize the survey, present the overall observations, and suggest potential areas for future research in proxy signature schemes.