6.5.3Protocols
A number of protocols can be defined over elliptic curves. This document will refer to the most widespread: Elliptic Curve Digital Signature Algorithm (ECDSA) [ansi962][fips186][ieee][rfc], Elliptic Curve DiffieHellman (ECDH) [ansi963][ieee][rfc], Elliptic Curve MenesezQuVanstone (ECMQV) [ansi963][ieee], Elliptic Curve Integrated Encryption Standard (ECIES).
ECDH is an analogue of the common DiffieHellman key exchange, with the same purpose. The pseudocode that describes ECDH algorithm is the following:

Alice and Bob share the domain parameters T=(q, a, b, P, n, h)

Alice generates randomly and calculates

Bob generates randomly and calculates

Alice e Bob exchange (they are called ephemeral keys)

Alice calculates_{ }

Bob calculates

Alice e Bob share: in particular the shared secret is the x – coordinate of the point just obtained.
The ECDSA algorithm is a digital sign algorithm analogue to the common DSA algorithm: this signature scheme is a standard that is recognized from NIST and IEEE. The pseudocode that describes ECDSA algorithm is the following:
INPUT: domain parameters, message to sign m
OUTPUT:
SIGN PROCEDURE:

randomly


If back to the beginning

has been used an hash function

; if back to the beginning

Return (s,r)
VERIFICATION PROCEDURE:

otherwise reject



and

; If reject


If accept, otherwise reject.
DEMONSTRATION:
This protocol is secure if ECDLP is untreatable and the hash function is strong; the parameter k is called per message secret and must be generated and destroyed immediately after: if k was known it would be easy to derive the private key.
6.5.3.1ElGamal  Message Encryption
ElGamal is an encryption protocol based on DLP. Thus ECDH problem is equivalent to solving the problem of decrypting simple encryption scheme ciphertexts. Since ECDH is equivalent to EC El Gamal, we immediately can infer the equivalence of the problem of decrypting EC EL Gamal ciphertexts and decrypting simple encryption scheme ciphertexts. If Alice wants to send Bob a message encrypted with ElGamal, Bob has to set up a public key as follows. He picks an elliptic curve defined over a finite field such that the DLP is hard for the group E(). He chooses a point on such that the order of is (divisible by) a large prime. He picks a random integer s and computes . Bob’s public key then is , his private key is the integer s.
Table  The ElGamal public key cryptosystem.
Alice

Eve

Bob

Alice picks a random integer and computes as well as , and sends to Bob


Bob decrypts the message by computing

This works because. If Alice uses the same “random” integer for two messages and , and if Eve knows the plaintext , then she can compute .
6.5.3.2MasseyOmura (Shamir’s nokey protocol)  Message Encryption
The following cryptosystem was described in an unpublished mansucript of Shamir; it is also called MasseyOmura, and was first discovered by M. Williamson but not published since he was working at the GCHQ (a British Intelligence service) at the time.
Table explains the protocol, which is clearly based on the difficulty of the discrete log problem. The advantage of Shamir’s nokey protocol is the fact that no keys are involved; the main disadvantage is that for sending one message, Alice has to send two ciphertexts, and wait for Bob’s ciphertext to arrive.
Here Alice and Bob agree on an elliptic curve defined over a finite field , where is chosen in such a way that the DLP in is hard. They compute the group order and use a method for embedding messages as points on the elliptic curve . Then they basically follow the classical protocol of Shamir:
Table  MasseyOmura
In fact, since etc.
6.5.3.3KMOV  Message Encryption
This protocol, which was suggested by Koyama, Maurer, Okamoto & Vanstone, works as follows. Alice picks primes and forms the RSAkey . It is easy to see that for all primes and elliptic curves over . Her public encryption key is a random integer chosen coprime to , and her private decryption key is computed via . Although is not a group, it is still true that for (almost) all points on .
For sending a message to Alice, Bob computes and computes on the elliptic curve ; then he sends the pair to Alice, who decrypts it by computing on and recovers the original message by dropping the last 10 bits.
6.5.3.4Demytko  Message Encryption
Let be an elliptic curve over , and let denote a quadratic nonresidue . Then the cubic can be brought into Weierstrass form by multiplying through with ands setting : this gives . The elliptic curve is called a quadratic twist of .
It is an easy exercise to show that if , then . Moreover, if is not the coordinate of a point on , then it is the coordinate of a point on . For a point , let denote the coordinate of the point .
Now Alice chooses an RSAmodulus and an elliptic curve defined over . She also finds quadratic nonresidues and , and defines the quadratic twists , and . Let be an integer coprime to the groups orders of these four curves (i.e., coprime to and ). In order to encrypt a message , she first computes and ; if both symbols are positive, then is the coordinate of some point . and , then is the coordinate of some point etc. Bob now computes and sends to Alice. For decrypting the message, Alice sets
where . Then she computes and decrypts the message via .
The blind signature scheme is a protocol for obtaining a signature from a signer, but the signer can neither learn the messages nor see the signatures the recipients obtain afterwards. In proxy signature scheme, the original signer delegates his signing capacity to a proxy signer who can sign a message submitted on behalf of the original signer. A verifier can validate its correctness and can distinguish between a normal signature and a proxy signature. In multiproxy signature scheme, an original signer is allowed to authorize a group of proxy members to generate the multi signature on behalf of the original signer.
A proxy blind signature scheme is a digital signature scheme that ensures the properties of proxy signature and blind signature. In a proxy blind signature, an original signer delegates his signing capacity to proxy signer. A proxy blind signature scheme is a special form of blind signature which allows a designated person called proxy signer to sign on behalf of two or more original signers without knowing the content of the message or document. It combines the advantages of proxy signature, blind signature and multisignature.
A proxy blind signature scheme consists of the following three phases:

Proxy key generation

Proxy blind multisignature scheme

Signature verification
Most of the proxy blind signature schemes were developed based on the mathematical hard problems integer factorization (IFP) and simple discrete logarithm (DLP) which take subexponential time to solve. Alghazzawi et al. [7] describe a simple proxy blind signature scheme based on Elliptic Curve Discrete Logarithm Problem (ECDLP), which is solved in fullyexponential time. The algorithms for solving the ECDLP become infeasible much more rapidly as the problem size increases more than those algorithms for the IFP and DLP. Thus, ECC offers security equivalent to RSA and DSA while using far smaller key sizes. The benefits of this higherstrength perbit include higher speeds, lower power consumption, bandwidth savings, storage efficiencies, and smaller certificates. This can be implemented in low power and small processor mobile devices such as smart card, PDA etc. which work in low power and small processor.
6.5.3.5.1Proposed Protocol
The protocol involves three entities:

Original signer S,

Proxy signer s P and

Verifier V.
It is described as follows.
Proxy Phase
The original signer S selects random integer k in the interval . Computes and . Where is regarded as an integer between 0 and q–1, then computes and computes .
The original signer S sends to the proxy signer and make public.
After receiving the secret key pairs , the proxy signer checks the validity of the secret key pairs with the following equation.
(1)
Signing Phase

The Proxy signer chooses random integer and computes and sends it to the verifier V.

After receiving the verifier chooses randomly and computes the following
(2)
(3)
(4)
and verifier V sends e to the proxy signer P_{s}.

After receiving e, P_{s} computes the following
(5)
and sends it to V.

Now V computes (6)
The tuples is the proxy blind signature.
Verification Phase
The verifier V computes the following equation.
(7)
and verifies the validity of proxy blind signature with the equality .
6.5.3.5.2Proxy blind multisignature scheme
Kar [6] describes an efficient proxy blind multisignature scheme. It satisfies the security properties of both proxy and blind signature scheme. In the proposed scheme the security is based on the difficulty of breaking the oneway hash function and the elliptic curve discrete logarithm problem (ECDLP). Signatures can only be generated during valid delegation period. A trusted third party called certificate authority is utilized to ensure that.
6.5.3.5.3Security properties
The security properties for a secure blind multisignature scheme are as follows:

Distinguishability: The proxy blind multisignature must be distinguishable from the ordinary signature.

Strong unforgeability: Only the designated proxy signer can create the proxy blind signature for the original signer.

Nonrepudiation: The proxy signer cannot claim that the proxy signer is disputed or illegally signed by the original signer.

Verifiability: The proxy blind multisignature can be verified by everyone. After verification, the verifier can be convinced of the original signer's agreement on the signed message.

Strong undeniably: Due to fact that the delegation information is signed by the original signer and the proxy signature are generated by the proxy signer's secret key. Both the signer cannot deny their behaviour.

Unlinkability: When the signer is revealed, the proxy signer cannot identify the association between the message and the blind signature he generated.

Secret key dependencies: Proxy key or delegation pair can be computed only by the original signer's secret key.

Prevention of misuse: The proxy signer cannot use the proxy secret key for purposes other than generating valid proxy signatures. In case of misuse, the responsibility of the proxy signer should be determined explicitly.
