Advanced
Toward Efficient Convertible Authenticated Encryption Schemes Using Self-Certified Public Key System
Toward Efficient Convertible Authenticated Encryption Schemes Using Self-Certified Public Key System
KSII Transactions on Internet and Information Systems (TIIS). 2014. Mar, 8(3): 1157-1177
Copyright © 2014, Korean Society For Internet Information
  • Received : November 15, 2013
  • Accepted : March 05, 2014
  • Published : March 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Tzong-Sun Wu
Yih-Sen Chen
Han-Yu Lin

Abstract
Convertible authenticated encryption (CAE) schemes enable the signer to send a confidential message and its corresponding signature to the designated recipient. The recipient can also convert the signature into a conventional one which can be verified by anyone. Integrating the properties of self-certified public key systems, this paper presents efficient and computationally indistinguishable self-certified CAE schemes for strengthening the security of E-Commerce applications. Additionally, we also adapt the proposed schemes to elliptic curve systems for facilitating the applications of limited computing power and insufficient storage space. The proposed schemes are secure against known existential active attacks, satisfy the semantic security requirement, and have the following advantages: (i) No extra certificate is required since the tasks of authenticating the public key and verifying the signature can be simultaneously carried out within one step, which helps reducing computation efforts and communication overheads. (ii) In case of a later dispute, the recipient can convert the signature into an ordinary one for the public arbitration. (iii) The signature conversion can be solely performed by the recipient without additional computation efforts or communication overheads. (iv) The recipient of the signature can prove himself, if needed, to anyone that he is actually the designated recipient.
Keywords
1. Introduction
I n the field of cryptography, how to satisfy the requirements of integrity [1] , confidentiality [2] , authenticity [1] and non-repudiation [3] over open environments of the Internet is always an important issue. In 1976, Diffie and Hellman [4] introduced the first public key system based on the intractability of the discrete logarithm problem (DLP) [4 , 5] . In the system, each user owns a self-chosen private key and a corresponding public key stored in the public key directory. One can use his private key along with the designated user’s public key to compute a shared common key and thus to construct a secure channel between them. With the public key cryptosystems [6 , 7] , we can further perform the functions of the public key encryption or the digital signature. However, a malicious adversary can plot an active attack by substituting a fake public key for the genuine one.
To withstand the above attack, a certificate-based approach (e.g., X.509) [8] is a commonly used solution. Each public key is accompanied with a certificate issued by the certification authority to guarantee its authenticity. One should first verify the public key before using it. However, it requires extra communication overheads and computation efforts owing to the processes of transmitting and verifying the certificate.
In 1984, Shamir [9] addressed the concept of ID-based public key systems in which each user’s public key is straightly his public identifier, so as to be explicitly verified without any extra certificate. The corresponding private key is derived by the system authority (SA) through a trapdoor one-way hash function which is computationally infeasible to invert. Without the SA’s secret information, no one can obtain a valid private key. Nevertheless, the SA can still impersonate any legitimate user without being detected since he has the control over every user’s private key. That is, the SA should be always trusted.
Seeing that the security of ID-based public key systems places great dependence on the SA and users cannot freely choose his own private key, Girault [10] proposed a self-certified public key system to eliminate these drawbacks in 1991. A self-certified public key system has the property that the public key validation can be combined with other subsequent cryptographic mechanisms such as the signature verification. That is, the tasks of authenticating the public key and verifying the signature can be simultaneously achieved in one step, which reduces the costs of the certificate transmission and public key verification. As compared with the stated two systems, a self-certified public key system is more efficient. It might be a better alternative for implementing cryptographic systems.
To meet requirements of some specific applications that digital signatures must simultaneously fulfill the need of confidentiality, such as the delivery of military documents or transactions of credit cards, a flat-out way would be the conventional two-step approach [11] , i.e., first sign then encrypt. However, the two-step approach is inefficient since the costs equal to the sum of those of signing and encryption. To improve the efficiency, an authenticated encryption scheme was proposed by Horster et al . [12] in 1994, which only allows a designated recipient to verify the signature rather than anyone else for the purpose of confidentiality. Obviously, the authenticated encryption scheme outperforms the traditional two-step approach in terms of computation complexities and communication overheads. In 2005, Yoon and Yoo [13] extended the applications for message linkages. Yet, a later dispute that the signer disclaims having generated a signature might occur. To convince anyone of the signer’s dishonesty, the designated recipient must have the ability to convert the signature into an ordinary one for protecting his rights or benefits. In 1999, Araki et al . [14] put the concept of signature conversion into practice and proposed a convertible limited verifier signature scheme. However, the process of signature conversion requires the assistance of the signer, which might be infeasible if the signer is unwilling to cooperate with. To improve the conversion mechanism and obtain better performance, Wu and Hsu [15] proposed a convertible authenticated encryption (CAE) scheme in which the signature conversion process is rather simple and can be solely done by the recipient without any computation efforts. Their scheme has to perform extra public key verification before any cryptographic mechanism and does not provide the property of recipient proof. Chen and Jan [16] further proposed an enhanced scheme in the same year. However, both the Wu-Hsu and the Chen-Jan schemes cannot provide the semantic security, i.e., the ciphertext is computationally distinguishable with respect to two candidate messages. To eliminate such security weakness, Lv et al . [17] proposed a secure and practical solution. Yet, the computation complexity of their scheme is rather high. Since then, many variations of self-certified CAE were proposed, for instance, self-certified proxy CAE [18 , 19] and convertible multi-authenticated encryption scheme [20 , 21] , which can be used in different application situations. Interested readers can refer to these literatures [15 , 17 - 21] for more detailed discussions. Elaborating on the merits inherent in the self-certified public key systems, the authors will propose efficient and computationally indistinguishable self-certified CAE schemes in this paper.
With the coming of the digitalized time, lots of mobile devices like mobile phones have been widely used around. Equipped with less powerful computing capability and small storage space, those devices can only be used to execute fewer computations and store limited personal sensitive data. No one can gain the access to the data inside without authorization. Due to the limited computing power and storage space, the computation complexity and the storage requirement are concerned the most when we implement a cryptographic scheme for those devices. The elliptic curve cryptography (ECC) [22 - 27] first introduced by Koblitz [28] and Miller [29] is applicable to this kind of applications used in mobile devices. A significant characteristic of the ECC is that the key length is shorter than that of the conventional cryptography under the same level of security, which helps faster execution and more bandwidth savings. As we elevate the security level, the difference of the key length between the ECC and the conventional cryptography dramatically increases. Therefore, we also adapt the proposed schemes to elliptic curve systems for facilitating the gradually widely used applications of limited computing power and insufficient storage. To ensure the authenticity of transaction certificates is the foundation for any secure E-commerce application. In our proposed schemes, the tasks of authenticating the public key, corresponding certificates and the signature can be simultaneously carried out in one logical step, which greatly reduces the costs of transmitting certificates and verifying public keys. Moreover, under the same security level, the elliptic curve variants with shorter key length helps with faster execution and more bandwidth savings. Therefore, our proposed schemes can strengthen the security of E-commerce application.
2. Self-Certified CAE Schemes Based on Discrete Logarithms
The proposed self-certified CAE schemes are divided into four stages: the user registration, the signature generation and verification, the signature conversion, and the recipient proof stages. There is also a system authority (SA) whose tasks are to initialize the system and to help users generating their key pairs. Initially, the SA chooses the following necessary parameters:
  • p,q: two large primes satisfying thatq| (p-1);
  • g: a generator of orderqover GF(p);
  • h(·): a secure one-way hash function which accepts input of any length and generates a fixed length output;
  • γ: the SA’s private key
  • β: the SA’s public key computed as
PPT Slide
Lager Image
All the above parameters are made public except for the SA’s private key γ . Details of each stage are described as below and shown in Fig. 1 :
PPT Slide
Lager Image
Illustration of proposed self-certified CAE schemes based on Discrete Logarithms
The user registration stage: To join the system, each user Ui associated with the identifier IDi has to perform the following interactive steps with the SA to obtain a private-public key pair:
Step 1 Ui first chooses an integer
PPT Slide
Lager Image
to compute
PPT Slide
Lager Image
  • and then deliveries (vi,IDi) to the SA.
Step 2 Upon receiving ( vi , IDi ), the SA chooses
PPT Slide
Lager Image
to compute
PPT Slide
Lager Image
PPT Slide
Lager Image
  • and sends (yi,wi) back toUi.
Step 3 Ui computes his private key xi as
PPT Slide
Lager Image
  • and then ensures its validity by checking
PPT Slide
Lager Image
it holds, Ui accepts ( xi , yi ) as his private-public key pair. The correctness of Eq. (6) can be easily confirmed as Theorem 1, which also validates the authenticity of yi with respect to xi .
Theorem 1. A valid key pair ( xi , yi ) can pass the test of Eq. (6).
Proof: From the left-hand side of Eq. (6), we have
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
which equals to the right-hand side of Eq. (6).
The signature generation and verification stage: When Ua wants to send Ub the signature of a confidential message m with embedded redundancy. Ua first chooses an integer
PPT Slide
Lager Image
to compute ( C , r 1 , r 2 ) as Eqs. (7), (8) and (9), respectively:
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Ua then compute s as Eq. (10.*) in Table 1 , where ‘*’ represents one letter of ‘a’ to ‘f’. Each equation is a secure combination of three parameters k , xa and r 2 .
Equations to generate signatures
PPT Slide
Lager Image
Equations to generate signature s
Here, ( r 1 , r 2 , s ) is the signature for m , which is then delivered to the designated recipient Ub . After receiving the signature, Ub first computes K from Eq. (11.*) of Table 2 and C' from Eq. (12). Note that the computation of K depends on the generation of s , e.g., generating s with Eq. (10.c) implies deriving K with Eq. (11.c).
Equations to computeK
PPT Slide
Lager Image
Equations to compute K
PPT Slide
Lager Image
The message m with the embedded redundancy can be recovered by Eq. (13).
PPT Slide
Lager Image
Ub finally verifies signature ( r 1 , r 2 , s ) by checking the following equation:
PPT Slide
Lager Image
If it holds, the signature is valid. In the mean time, the signer’s public key ya is simultaneously authenticated.
Take scheme I (with s and K separately computed as Eqs. (10.a) and (11.a)) as an example. We demonstrate that Eqs. (13) and (14) work correctly as the proofs of Theorems 2 and 3, respectively. The correctness of the other schemes can be assured with the similar way.
Theorem 2. The designated recipient Ub can recover the message m with Eq. (13).
Proof: From the right-hand side of Eq. (13), we have
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
which equals to the left-hand side of Eq. (13).
Theorem 3. The tasks of verifying the signature ( r 1 , r 2 , s ) and authenticating the public key ya can be simultaneously achieved with Eq. (14).
Proof: From the right-hand side of Eq. (14), we have
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
which equals to the left-hand side of Eq. (14).
The signature conversion stage: When a later dispute of signer’s repudiation occurs, the recipient Ub can show the dishonesty of the signer by releasing the converted signature ( r 2 , s , C' ) along with the recovered message m . Anyone can first compute K from Eq. (11.*) and then validate the signature with Eq. (14). If the checking of Eq. (14) holds, he assures that the signature is generated by Ua .
The recipient proof stage: For convincing someone, say, Uc , that he is the real recipient, the recipient Ub can perform the following interactive steps with Uc :
Step 1 Ub sends ( r 2 , s , C' ) and m to Uc .
Step 2 Uc first computes K with the corresponding Eq. (11.*) and then checks the signature’s validity with Eq. (14). If it holds, Uc proceeds to the next step; otherwise, the protocol is terminated.
Step 3 Uc randomly chooses an integer e to compute E = Ke mod p and then transmits E to Ub .
Step 4 Upon receiving E , Ub computes
PPT Slide
Lager Image
mod p and returns it to Uc .
Step 5 Uc computes W' = C' e mod p and checks whether W = W' . If it holds, Uc is convinced that Ub is the designated recipient.
3. Self-Certified CAE Schemes Based on Elliptic Curve Discrete Logarithms
In this section, we present elliptic curve variants of proposed schemes based on the elliptic curve discrete logarithm problem (ECDLP) [8 , 13 , 14] . The stages and the participating parties of the proposed elliptic curve variants are the same as those in the proposed schemes in Section 2. Initially, the SA determines the following parameters:
  • p: a large prime;
  • a,b: two parameters inZpsatisfying that 4a3+ 27b2modp≠0;
  • Ep(a,b): an elliptic curve over GF(p) containing a set of points (x,y) satisfying thaty2=x3+ax+b(modp);
  • O: a point at infinity overEp(a,b);
  • G: the base point of orderqoverEp(a,b), whereqis a large prime;
  • h(·): a secure one-way hash function which accepts input of various length and generates output of a fixed length; note that the input of a point overEp(a,b) represents the input of the concatenation of thex- andy- coordinates of that point;
  • γ: the SA’s private key for
  • B: the SA’s public key computed as
PPT Slide
Lager Image
All of the above parameters are made public except for the SA’s private key γ . In the following, all elliptic curve point operations are manipulated over Ep ( a , b ). Details of each stage are shown as follows:
The user registration stage: To become a legitimate user, Ui associated with the identifier IDi performs the registration process with the SA.
Step 1 Ui first chooses an integer
PPT Slide
Lager Image
PPT Slide
Lager Image
  • and then sends (Vi,IDi) to the SA.
Step 2 After receiving ( Vi , IDi ), the SA chooses
PPT Slide
Lager Image
to compute
PPT Slide
Lager Image
PPT Slide
Lager Image
  • and returns (Yi,wi) toUi.
Step 3 Ui computes xi as
PPT Slide
Lager Image
  • and checks its validity with the following equality.
PPT Slide
Lager Image
If the above equation holds, Ui accepts ( xi , Yi ) as his private and public keys. Theorem 4 proves the correctness of Eq. (20) which also validates the authenticity of Yi with respect to xi .
Theorem 4. Ui can perform Eq. (20) to authenticate the public key Yi with respect to his private key xi .
Proof: From the left-hand side of Eq. (20), we have
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
which equals to the right-hand side of Eq. (20).
The signature generation and verification stage: When Ua wants to send Ub the signature of a confidential message m with embedded redundancy. Ua first chooses an integer
PPT Slide
Lager Image
and computes ( C , r 1 , r 2 , s ) as Eqs. (21), (8), (12) and (10.*) of Table 1 , respectively.
PPT Slide
Lager Image
PPT Slide
Lager Image
( r 1 , r 2 , s ) is the signature for m , which is then sent to the designated recipient Ub . Upon receiving the signature, Ub first computers the corresponding K from Eq. (23.*) of Table 3 and C' from Eq. (24).
Equations to computeKbased on the ECDLP
PPT Slide
Lager Image
Equations to compute K based on the ECDLP
PPT Slide
Lager Image
The message m with the embedded redundancy can be recovered from Eq. (13). After that, Ub can verify the signature ( r 1 , r 2 , s ) by testing Eq. (14). If it holds, the signature is valid; meanwhile, the signer’s public key ya is simultaneously authenticated.
Taking scheme I (with s and K separately computed as Eqs. (10.a) and Eq. (23.a)) as an example, we demonstrate that the proposed elliptic variants work correctly as the proofs of Theorems 5 and 6, respectively. Interested readers can follow the similar way to check the correctness of the other schemes.
Theorem 5. The recipient Ub can recover the message m with Eq. (13).
Proof: From the right-hand side of Eq. (13), we have
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
which equals to the left-hand side of Eq. (13).
Theorem 6. A valid signature ( r 1 , r 2 , s ) should satisfy Eq. (14) which also authenticates the public key Ya .
Proof: From the right-hand side of Eq. (14), we have
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
which equals to the left-hand side of Eq. (14).
The signature conversion stage: To handle the case of a later dispute, the recipient Ub can simply reveal the recovered message m and the converted signature ( r 2 , s , C' ). Anyone can first compute K from Eq. (23.*) and then validate the signature with Eq. (14). If the checking of Eq. (14) holds, he assures that the signature is generated by Ua .
The recipient proof stage: For convincing someone, say, Uc , that he is the real recipient, the recipient Ub can perform the following interactive steps with Uc :
Step 1 Ub sends ( r 2 , s , C' ) to Uc .
Step 2 Uc first computes K with corresponding Eq. (23.*) and then checks the signature’s validity with Eq. (14). If it holds, Uc proceeds to the next step; otherwise, the protocol is terminated.
Step 3 Uc randomly chooses an integer e to compute E = eK and then transmits E to Ub .
Step 4 Upon receiving E , Ub computes W = xbE and returns it to Uc .
Step 5 Uc computes W' = eC' and checks whether W = W' . If it holds, Uc is convinced that Ub is the designated recipient.
4. Security Considerations and Performance Evaluation
In this section, we first defined some security notions for self-certified CAE schemes and then gave security proofs and the performance evaluation of our proposed schemes.
- 4.1 Security Notions
To facilitate the following proofs, we regenerate algorithms of User-registration, Signature-encryption-and-verification, Signature-conversion and Recipient-proof from each phase of the proposed schemes. The security notions of message confidentiality and unforgeability with respect to self-certified CAE schemes are defined below.
Message Confidentiality. A self-certified CAE scheme can fulfill the security requirement of message confidentiality if authenticated ciphertexts are indistinguishable under chosen ciphertext attacks. We define a security model for indistinguishability of authenticated ciphertexts under chosen ciphertext attacks. In this model, the adversary attempts to decrypt a target ciphertext of the designated recipient.
Definition 1. A self-certified CAE scheme is said to be semantically secure against chosen ciphertext attacks if there exits no polynomial-time adversary with a non-negligible advantage in the following game:
Setup: A challenger C first generates necessary system parameters and then obtains the signer Ua ’s key pair ( xa , ya ) by the User-registration algorithm. System parameters and the signer Ua ’s public key are given to an adversary A . Upon receiving these parameters, the adversary A determines one designated recipient Ub *. The recipient Ub *’s public key yb * can be acquired from the User-registration algorithm, but the corresponding private key xb * is unknown to A .
Phase 1: The adversary A can issue several kinds of queries adaptively:
– Signature-encryption-and-verification queries: The adversary A can query either Signature-encryption or Signature-verification. In the Signature-encryption queries, the adversary A produces a message m with respect to Ua and sends it to the challenger C which then returns the result of Signature-encryption ( m , xa , yb *) to A . In the Signature-verification queries, the adversary A produces an authenticated ciphertext σ = ( r 1 , r 2 , s ) and requests the result of Signature-verification ( σ , ya , xb *) with respect to Ua and Ub * from the challenger C . If the recovered message is consistent with the redundancy check and its corresponding signature is valid, C responses the message; Otherwise, the ⊥ symbol is returned as a result.
– Signature-conversion queries: The adversary A produces an authenticated ciphertext σ = ( r 1 , r 2 , s ) and requests the result of Signature-conversion ( σ , ya , xb *) with respect to Ua and Ub * from the challenger C . If the result ( r 2 , s , C' ) is a valid converted signature for the message m with suitable redundancy, C responses the result; Otherwise, the ⊥ symbol is returned as a result.
– Recipient-proof queries: The adversary A produces an authenticated ciphertext σ = ( r 1 , r 2 , s ) and requests the result of Recipient-proof ( σ , ya , xb *) with respect to Ua from the challenger C . If Ub * is the designated recipient, C responses the symbol 1; Otherwise, the ⊥ symbol is returned as a result.
Challenge: The adversary A produces two messages, m 0 and m 1 , of the same length. The challenger C flips a coin λ ← {0, 1} and generates an authenticated ciphertext σ * = Signature-encryption ( mλ , xa , yb *) which is then delivered to A as a target challenge.
Phase 2: The adversary A can issue new queries as those in Phase 1, except that the Signature-verification or Signature-conversion query for the target challenge σ * is prohibited.
Guess: At the end of the game, A outputs a bit λ' . The adversary A wins this game if λ' = λ . We define A’s advantage as Adv ( A ) = Pr[ λ' = λ ] − 1/2.
Unforgeability. A cryptographic scheme satisfies the security requirement of unforgeability if it is secure against chosen message attacks. We define a model for unforgeability of self-certified CAE scheme against chosen message attacks. In this model, the adversary attempts to forge a valid signature of one target message.
Definition 2. A self-certified CAE scheme is said to achieve existential unforgeability against chosen-message attacks if there exists no polynomial-time adversary with a non-negligible advantage in the following game:
Setup: A challenger C first generates necessary system parameters, and then obtains the signer Ua ’s key pair ( xa , ya ) and a designated recipient Ub ’s key pair ( xb , yb ) by the User-registration algorithm. The challenger C then gives the forger F system parameters, the signer Ua ’s public key ya and the designated recipient’s public key yb .
Attack: The forger F issues the same queries as those in Phase 1 of Definition 1.
Forgery: Finally, F produces an authenticated ciphertext σ *. The forger F wins if σ * can be converted into a valid signature ( r 2 *, s *, C' *) for some message m * with redundancy by the designated recipient. Note that it is not allowed to issue a Signature-encryption query for m *.
- 4.2 Security Proof
The security of the proposed schemes is based on the DLP [4 , 5] / ECDLP [25 , 30 , 31] and security of Nyberg-Rueppel signature schemes [32 , 33] . For the details of Nyberg-Rueppel signature schemes, we recommend the interested readers to refer to [32 , 33] . Instead of separate discussions, we only take the DLP-based scheme I as an instance for the following proofs. Other schemes can be proved with similar ways. The definition of DLP is briefly restated below: Let p be a large prime, g a generator, and α a random integer. It is computationally infeasible to derive α from known ( g , gα mod p ). In the following, we proved that the proposed schemes satisfy the security requirements of confidentiality and unforgeability as Theorems 7 and 8, respectively.
Theorem 7. The proposed self-certified CAE scheme is ( t , ε )- secure against chosen ciphertext attacks if there exists no polynomial-time algorithm β 1 that can ( t 1 , ε 1 )- break the DLP .
Proof. Suppose that A is a ( t , ε )-algorithm that breaks the self-certified CAE scheme under the chosen ciphertext attack, where t denotes the running time and ε the probability that A succeeds. We will show that we can use A to construct a ( t 1 , ε 1 )-algorithm β 1 that solves the DLP in time t 1 with the probability ε 1 . The algorithm β 1 is said to ( t 1 , ε 1 )-break the DLP. Let ( g , gα mod p ) be a random instance of the DLP. The objective of the algorithm β 1 is to derive α . In this proof, β 1 simulates challenger C in the game of Definition 1. In the meantime, A adaptively issues queries as those defined in the game of Definition 1.
–Signature-encryption queries: When A issues a Signature-encryption query on a message m , the algorithm β 1 first randomly chooses an integer
PPT Slide
Lager Image
and computes
PPT Slide
Lager Image
Then, β 1 computes r 1 = mh ( C ) -1 mod p , r 2 = h ( m , h ( gk mod p ), C ) mod q , and s = k (1 + xar 2 ) -1 mod q . Here, ( r 1 , r 2 , s ) is the authenticated ciphertext σ which is returned as the result of the Signature-encryption on the message m .
– Signature-verification queries: When A issues a Signature-verification query on an authenticated ciphertext σ = ( r 1 , r 2 , s ), β 1 first computes
PPT Slide
Lager Image
and
PPT Slide
Lager Image
mod p . Then, β 1 recovers m = h ( C' ) r 1 mod p . If the recovered m is consistent with the redundancy check and the equality of r 2 = h ( m , h ( K ), C' )mod q holds, β 1 outputs m ; otherwise, the ⊥ symbol is returned as a result.
– Signature-conversion queries: When A issues a Signature-conversion query on an authenticated ciphertext σ = ( r 1 , r 2 , s ), the algorithm β 1 first computes
PPT Slide
Lager Image
and
PPT Slide
Lager Image
mod p . Then, β 1 recovers m = h ( C' ) r 1 mod p . If the result ( r 2 , s , C' ) satisfies r 2 = h ( m , h ( K ), C' )mod q , outputs the result; Otherwise, the ⊥ symbol is returned as result.
– Recipient-proof queries: When A issues a Recipient-proof query on an authenticated ciphertext σ = ( r 1 , r 2 , s ), β 1 first performs the same steps as those in Signature-conversion queries, and then chooses an integer e to compute E = Ke mod p ,
PPT Slide
Lager Image
mod p , and W' = C' e mod p . If W = W' , β 1 outputs the symbol 1 as the result. Otherwise, the ⊥ symbol is returned as result.
Challenge: The adversary A generates two messages, m 0 and m 1 , of the same length. The challenger β 1 flips a coin λ ← {0, 1} and computes an authenticated ciphertext σ * = Signature-encryption ( mλ , xa , yb *). The algorithm β 1 first randomly chooses an integer
PPT Slide
Lager Image
and computes
PPT Slide
Lager Image
Then, β 1 computes r 1 * = mλ h ( C ) -1 mod p , r 2 * = h ( mλ , h ( gα mod p ), C ) mod q , and s * = Z (1 + xar 2 ) -1 mod q . The authenticated ciphertext σ * = ( r 1 *, r 2 *, s *) is sent to A as the target challenge. If Z = α , then σ * is indeed a random Signature-encryption of mλ . If Z is a random integer and does not equal to α , then r 1 * and s * are random elements. Therefore, σ * is independent of λ .
Phase 2: The adversary A issues new queries as those in Phase 1. It is not allowed to make a Signature-verification or Signature-conversion query for the target challenge σ *.
Analysis: Consider the case when Z = α , the distribution of the adversary A ’s view in the simulation is identical to that A is playing the game with C . Consequently,
PPT Slide
Lager Image
where Pr A [Succ] stands for the probability that A succeeds. When Z is uniformly distributed in
PPT Slide
Lager Image
the adversary A has no information about the value of λ and hence the probability of λ' = λ is at most 1/2. Therefore, we conclude that
PPT Slide
Lager Image
Theorem 8. The proposed self-certified CAE scheme is ( t , ε )- secure against existential forgery under chosen plaintext attacks if there exists no polynomial-time algorithm β 2 that can forge the Nyberg-Rueppel signature in time t 2 with the probability ε 2 .
Proof. Suppose that F is a ( t , ε )-algorithm that breaks the self-certified CAE scheme under chosen message attacks in time t with the probability ε . In fact, the signature verification (/message recovery) part of the proposed scheme is based on and expanded from the Nyberg-Rueppel signature scheme. We will construct a ( t 2 , ε 2 )-algorithm β 2 that forges the Nyberg-Rueppel signature in time t 2 with the probability ε 2 from the algorithm F . The objective of the algorithm β 2 is to derive a valid Nyberg-Rueppel signature. In this proof, β 2 simulates F ’s challenger in the game of Definition 2 with the target signer Ua ’s public key ya * where
PPT Slide
Lager Image
Then, F adaptively issues the same queries as those defined in the game of Definition 1.
Forgery: The algorithm F generates an authenticated ciphertext σ * = ( r 1*, r 2*, s *) for one target message m * under the private key of the designated recipient. Note that σ * is not obtained from a Signature-encryption query ( m *, xa *, yb ).
Analysis: F outputs an authenticated ciphertext σ * which can be converted to the message m * and its corresponding signature ( r 2 *, s *, C' *) with a non-negligible probability. If ( r 2 *, s *, C' *) satisfies the signature verification equation r 2 *= h ( m *, h ( K *), C' *)mod q with the probability ε , then ( r 2 *, s *, C' *) can be regarded as a valid Nyberg-Rueppel signature of the message m * with respect to the public key ya *. It can be seen that
PPT Slide
Lager Image
is hence at least Pr F [Succ]. We conclude that
PPT Slide
Lager Image
- 4.3 AVISPA
We show through the simulation for the formal security verification using the widely accepted AVISPA (automated validation of internet security protocols and applications) tool [34] that our schemes are secure against malicious attacks. This is a push button tool for the automated validation of security protocols. There is a modular and expressive formal language called HLPSL (high level protocols specification language) which is used by AVISPA to specify the security protocol and their properties. It is a role-based language; therefore, we must first determine the sequence of actions of each kind of protocol participants in a module. This specification can later be instantiated by one or more agents playing the given role, and we further specify how the resulting participants interact with one another by combining multiple basic roles together into a composed role. HLPSL specification is translated into the Intermediate Format (IF), using hlpsl2if. IF specification is then processed by model-checkers to analyze if the security goals are violated. There are four different verification back end tools use to analyze the IF specification namely, OFMC (On-the-Fly Model-Checker), CL-AtSe (Constraint Logic based Attack Searcher), SATMC (SAT-based Model Checker), TA4SP (Tree Automata based Protocol Analyser). We refer to the samples of [35] for a detailed description of HLPSL. Fig. 2 and 3 are outputs of running OFMC and ATSE tools [36] on our proposed scheme I based on discrete logarithms.
PPT Slide
Lager Image
The result of the analysis using OFMC on our scheme
PPT Slide
Lager Image
The result of the analysis using ATSE on our scheme
- 4.4 Performance Evaluation
In this subsection, we compared the performance among previously proposed schemes [15 , 17] and our DLP ones stated in Section 2. For assuring the validity of recipient’s public key, the Wu-Hsu scheme [15] has to perform extra public key verification before any cryptographic mechanisms. On the contrary, since Lv et al .’s scheme [17] and our proposed ones adapt the properties of self-certified public key systems, the tasks of verifying the signature and authenticating the public key can be achieved simultaneously, which benefits the transmission and computation performance. Since the modular exponentiation computation is the most time-consuming operation, we ignore others such as the one-way hash, multiplication, inverse and addition operation. As the detailed comparisons shown in Table 4 , it can be seen that the proposed schemes not only preserve the merit that the signature conversion process requires neither computation efforts nor communication overheads, but also outperform the Wu-Hsu scheme and Lv et al .’s scheme in terms of the computation efficiency for the entire protocol. Note that the Wu-Hsu scheme [15] has to perform extra public key verification and does not provide the property of recipient proof. Seeing that Lv et al .’s scheme will incur rather high computation complexity, we proposed six efficient variants based on the ElGamal signature scheme. Specifically, we optimize the signer’s computational cost in variants II, IV and V, i.e., 3 Te . Moreover, the last column in Table 4 shows that the proposed schemes are more efficient than the others.
Comparisons among previously proposed schemes and our DLP ones.
PPT Slide
Lager Image
Remarks: 1. Let Te be the time for performing a modular exponentiation computation. 2. WH and LWK separately represent the Wu-Hsu and Lv et al.’s schemes. I to VI denote the proposed schemes I to VI, respectively. 3. Suppose that verifying the public key certificate of the Wu-Hsu scheme is implemented with ElGamal signature verification [6], i.e., Tm + 3Te.
5. Conclusions
In some applications, the signature only needs to be verified by some specified recipients while keeping the message secret from the public. The authenticated encryption schemes can be used to achieve this purpose. In the normal procedure, only the recipient can recover the message and verify the signature. In case that the signer repudiates his signing, the recipient can release an ordinary signature for public verification. In this paper, we have proposed efficient and computationally indistinguishable self-certified CAE schemes based on discrete logarithms along with their elliptic curve variants. Implemented with self-certified public key systems, our proposed schemes require no extra certificate since the tasks of verifying the signature and authenticating the public key can be simultaneously carried out in one step. In case of a later dispute, the recipient has the ability to solely convert the signature into an ordinary one without any computation efforts or communication overheads. In addition, the recipient is capable of convincing anyone that he is the real recipient. The proposed schemes are shown to be efficient and secure against known existential active attacks. Furthermore, compared with existing CAE schemes [15 , 17] , our scheme greatly reduces the computational costs. They also satisfy the semantic security requirement. Moreover, the elliptic curve variants with shorter key length can help with faster execution and more bandwidth savings, so as to provide crucial benefits in the applications of limited computing power and insufficient storage space like mobile phones, etc.
Acknowledgements
This work was supported in part by the National Science Council of Republic of China under the contract number NSC 102-2221-E-019-041.
BIO
Tzong-Sun Wu received his B.S. degree in Electrical Engineering from National Taiwan University in 1990 and his Ph.D. in Information Management from National Taiwan University of Science and Technology in 1998. From August 1998 to July 2001, he has been an Assistant Professor in Department of Information Management, Huafan University. From August 2001 to January 2007, he has been an Associate Professor in Department of Informatics, Fo Guang University. He is currently with Department of Computer Science and Engineering, National Taiwan Ocean University, Keelung, Taiwan. His research interests include information security, watermarking, digital right management, and e-commerce.
Yih-Sen Chen received his B.A. degree in Information Management from Aletheia University, Taiwan in 1997 and his M.S. degree in Informatics from Fo Guang University of Taiwan in 2006. Now he is a doctoral candidate in the Department of Computer Science and Engineering, National Taiwan Ocean University. His main research interests include cryptography, information theory, security management, and network security.
Han-Yu Lin received his Ph.D. degree in computer science and engineering from the National Chiao Tung University, Taiwan in 2010. He served as a part-time Assistant Professor in both the Department of Information Management, Chang Gung University, Taiwan and the Department of Information Management, Kainan University, Taiwan from 2011. He was an engineer in CyberTrust Technology Institute, Institute for Information Industry, Taiwan from January 2012 to July 2012. Since August 2012, he has been an Assistant Professor in the Department of Computer Science and Engineering, National Taiwan Ocean University, Taiwan. His research interests include Cryptology, Network Security, Digital Forensics, RFID Privacy and Application, Cloud Computing Security and E-commerce Security.
References
Stallings W. 2002 Cryptography and network security: principles and practices 3rd. Ed. Prentice Hall
Hou F. , Wang Z. , Tang Y. , Liu Z. 2004 “Protecting integrity and confidentiality for data communication” Proceedings of Ninth International Symposium on Computers and Communications (ISCC) vol. 1, no. 28, Article (CrossRef Link) 357 - 362
Meng B. , Wang S. , Xiong Q. 2002 “A fair non-repudiation protocol” in Proc. of the 7th International Conference on Computer Supported Cooperative Work in Design Article (CrossRef Link) 68 - 73
Diffie W. , Hellman M. 1976 “New directions in cryptography” IEEE Transactions on Information Theory Article (CrossRef Link) IT-22 (6) 644 - 654    DOI : 10.1109/TIT.1976.1055638
Menezes A. , Oorschot P. , Vanstone S. 1997 Handbook of Applied Cryptography CRC Press, Inc
ElGamal T. 1985 “A public key cryptosystem and a signature scheme based on discrete logarithms” IEEE Transactions on Information Theory Article (CrossRef Link) IT-31 (4) 469 - 472    DOI : 10.1109/TIT.1985.1057074
Rivest R. , Shamir A. , Adleman L. 1978 “A method for obtaining digital signatures and public-key cryptosystems” Communications of the ACM Article (CrossRef Link) 21 (2) 120 - 126    DOI : 10.1145/359340.359342
2001 ISO/IEC 9594-8, Information technology open systems interconnection the directory: public-key and attribute certificate frameworks International Organization for Standardization
Shamir A. 1984 “Identity-based cryptosystems and signature schemes” Advances in Cryptology CRYPTO’84 Springer-Verlag Article (CrossRef Link) 47 - 53
Girault M. 1991 “Self-certified public keys” Advances in Cryptology EUROCRYPT’91 Springer-Verlag Article (CrossRef Link) 491 - 497
VISA and MasterCard Inc 1997 Secure Electronic Transaction (SET) Specification, Version 1.0.
Horster P. , Michel M. , Peterson H. 1994 “Authenticated encryption schemes with low communication costs” Electronics Letters Article (CrossRef Link) 30 (15) 1212 - 1213    DOI : 10.1049/el:19940856
Yoon E. J. , Yoo K. Y. 2005 “Robust authenticated encryption scheme with message linkages” in Proc. of Proceedings of the 9th International Conference on Knowledge-Based Intelligent Information and Engineering Systems (KES) Article (CrossRef Link) 281 - 288
Araki S. , Uehara S. , Imamura K. 1999 “The limited verifier signature and its application” IEICE Transactions on Fundamentals Article (CrossRef Link) E82-A (1) 63 - 68
Wu T. S. , Hsu C. L. 2002 “Convertible authenticated encryption scheme” The Journal of Systems and Software Article (CrossRef Link) 62 (3) 205 - 209    DOI : 10.1016/S0164-1212(01)00143-1
Chen Y. H. , Jan J. K. 2005 “Enhancement of digital signature with message recovery using self-certified public keys and its variants” ACM SIGOPS Operating Systems Review Article (CrossRef Link) 39 (3) 90 - 96    DOI : 10.1145/1075395.1075404
Lv J. , Wang X. , Kim K. 2005 “Practical convertible authenticated encryption schemes using self-certified public keys” Applied Mathematics and Computation Article (CrossRef Link) 169 (2) 1285 - 1297    DOI : 10.1016/j.amc.2004.10.057
Wu T. S. , Lin H. Y. 2009 “Efficient self-certified proxy CAE scheme and its variants” Journal of Systems and Software Article (CrossRef Link) 82 (6) 974 - 980    DOI : 10.1016/j.jss.2008.12.040
Xie Q. , Wang G. , Xia F. , Chen D. 2013 “Self-certified proxy convertible authenticated encryption: formal definitions and a provably secure scheme” Concurrency and Computation: Practice and Experience Article (CrossRef Link)
Hsu C. L. , Lin H. Y. 2011 “New identity-based key-insulated convertible multi-authenticated encryption scheme” Journal of Network and Computer Applications Article (CrossRef Link) 34 (5) 1724 - 1731    DOI : 10.1016/j.jnca.2011.06.005
Tsai J. L. , Lo N. W. , Wu T. C. 2012 “Efficient convertible multi-authenticated encryption scheme for group communications” Biometrics and Security Technologies (ISBAST) Article (CrossRef Link) 54 - 58
1998 ANSI X9.31, Digital signatures using reversible public key cryptography for the financial services industry (rDSA)
1998 ANSI X9.62, Public key cryptography for the financial service industry - the elliptic curve digital signature algorithm (ECDSA), Draft
2001 ANSI X9.63, Public key cryptography for the financial services industry - key agreement and key transport using elliptic curve cryptography
2000 IEEE P1363, Standard specifications for public key cryptography The Institute of Electrical and Electronics Engineers, Inc.
1998 ISO/IEC 14888-3, Information technology security techniques digital signature with appendix part 3: certificate-based mechanisms International Organization for Standardization
2002 ISO/IEC 15946-3, Information technology – security techniques – cryptographic techniques based on elliptic curves – part 3: key establishment International Organization for Standardization
Koblitz N. 1987 “Elliptic curve cryptosystems” Mathematics of Computation Article (CrossRef Link) 48 (177) 203 - 209    DOI : 10.1090/S0025-5718-1987-0866109-5
Miller V. 1985 “Use of elliptic curves in cryptography,” Advances in Cryptology CRYPTO’85 Springer-Verlag Article (CrossRef Link) 417 - 426
Blake I. , Seroussi G. , Smart N. 1999 “Elliptic curves in cryptography,” London Mathematical Society Lecture Note Series 265 Cambridge University Press Article (CrossRef Link)
Menezes A. 1993 Elliptic Curve Public Key Cryptosystems Kluwer Academic Publishers Article (CrossRef Link)
Nyberg K. , Rueppel R. A. 1993 “A new signature scheme based on the DSA giving message recovery” ACM Press in Proc. of the 1st ACM Conference on Computer and Communication Security Article (CrossRef Link) 58 - 61
Nyberg K. , Rueppel R. A. 1994 “Message recovery for signature schemes based on the discrete logarithm problem,” Advances in Cryptology EUROCRYPT’94 Springer-Verlag Article (CrossRef Link) 182 - 193
AVISPA. Automated validation of internet security protocols and applications. http://www.avispa-project.org/
Das A. K. , Bruhadeshwar B. 2013 “An improved and effective secure password-based authentication and key agreement scheme using smart cards for the telecare medicine information system” Journal of Medical Systems Article (CrossRef Link) 37 (5) 1 - 17    DOI : 10.1007/s10916-013-9969-9
AVISPA. AVISPA web tool. http://www.avispa-project.org/web-interface/expert.php/