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 selfcertified public key systems, this paper presents efficient and computationally indistinguishable selfcertified CAE schemes for strengthening the security of ECommerce 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.
1. Introduction
I
n the field of cryptography, how to satisfy the requirements of integrity
[1]
, confidentiality
[2]
, authenticity
[1]
and nonrepudiation
[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 selfchosen 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 certificatebased 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 IDbased 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 oneway 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 IDbased public key systems places great dependence on the SA and users cannot freely choose his own private key, Girault
[10]
proposed a selfcertified public key system to eliminate these drawbacks in 1991. A selfcertified 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 selfcertified 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 flatout way would be the conventional twostep approach
[11]
, i.e., first sign then encrypt. However, the twostep 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 twostep 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 WuHsu and the ChenJan 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 selfcertified CAE were proposed, for instance, selfcertified proxy CAE
[18
,
19]
and convertible multiauthenticated 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 selfcertified public key systems, the authors will propose efficient and computationally indistinguishable selfcertified 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 Ecommerce 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 Ecommerce application.
2. SelfCertified CAE Schemes Based on Discrete Logarithms
The proposed selfcertified 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 (p1);

g: a generator of orderqover GF(p);

h(·): a secure oneway 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
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
:
Illustration of proposed selfcertified CAE schemes based on Discrete Logarithms
The user registration stage:
To join the system, each user
U_{i}
associated with the identifier
ID_{i}
has to perform the following interactive steps with the SA to obtain a privatepublic key pair:
Step 1
U_{i}
first chooses an integer
to compute

and then deliveries (vi,IDi) to the SA.
Step 2
Upon receiving (
v_{i}
,
ID_{i}
), the SA chooses
to compute

and sends (yi,wi) back toUi.
Step 3
U_{i}
computes his private key
x_{i}
as

and then ensures its validity by checking
it holds,
U_{i}
accepts (
x_{i}
,
y_{i}
) as his privatepublic key pair. The correctness of Eq. (6) can be easily confirmed as Theorem 1, which also validates the authenticity of
y_{i}
with respect to
x_{i}
.
Theorem 1.
A valid key pair (
x_{i}
,
y_{i}
) can pass the test of Eq. (6).
Proof:
From the lefthand side of Eq. (6), we have
which equals to the righthand side of Eq. (6).
The signature generation and verification stage:
When
U_{a}
wants to send
U_{b}
the signature of a confidential message
m
with embedded redundancy.
U_{a}
first chooses an integer
to compute (
C
,
r
_{1}
,
r
_{2}
) as Eqs. (7), (8) and (9), respectively:
U_{a}
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
,
x_{a}
and
r
_{2}
.
Equations to generate signatures
Equations to generate signature s
Here, (
r
_{1}
,
r
_{2}
,
s
) is the signature for
m
, which is then delivered to the designated recipient
U_{b}
. After receiving the signature,
U_{b}
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 compute K
The message
m
with the embedded redundancy can be recovered by Eq. (13).
U_{b}
finally verifies signature (
r
_{1}
,
r
_{2}
,
s
) by checking the following equation:
If it holds, the signature is valid. In the mean time, the signer’s public key
y_{a}
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
U_{b}
can recover the message
m
with Eq. (13).
Proof:
From the righthand side of Eq. (13), we have
which equals to the lefthand side of Eq. (13).
Theorem 3.
The tasks of verifying the signature (
r
_{1}
,
r
_{2}
,
s
) and authenticating the public key
y_{a}
can be simultaneously achieved with Eq. (14).
Proof:
From the righthand side of Eq. (14), we have
which equals to the lefthand side of Eq. (14).
The signature conversion stage:
When a later dispute of signer’s repudiation occurs, the recipient
U_{b}
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
U_{a}
.
The recipient proof stage:
For convincing someone, say,
U_{c}
, that he is the real recipient, the recipient
U_{b}
can perform the following interactive steps with
U_{c}
:
Step 1
U_{b}
sends (
r
_{2}
,
s
,
C'
) and
m
to
U_{c}
.
Step 2
U_{c}
first computes
K
with the corresponding Eq. (11.*) and then checks the signature’s validity with Eq. (14). If it holds,
U_{c}
proceeds to the next step; otherwise, the protocol is terminated.
Step 3
U_{c}
randomly chooses an integer
e
to compute
E
=
K^{e}
mod
p
and then transmits
E
to
U_{b}
.
Step 4
Upon receiving
E
,
U_{b}
computes
mod
p
and returns it to
U_{c}
.
Step 5
U_{c}
computes
W'
=
C'
^{e}
mod
p
and checks whether
W
=
W'
. If it holds,
U_{c}
is convinced that
U_{b}
is the designated recipient.
3. SelfCertified 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 oneway 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
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
E_{p}
(
a
,
b
). Details of each stage are shown as follows:
The user registration stage:
To become a legitimate user,
U_{i}
associated with the identifier
ID_{i}
performs the registration process with the SA.
Step 1
U_{i}
first chooses an integer

and then sends (Vi,IDi) to the SA.
Step 2
After receiving (
V_{i}
,
ID_{i}
), the SA chooses
to compute

and returns (Yi,wi) toUi.
Step 3
U_{i}
computes
x_{i}
as

and checks its validity with the following equality.
If the above equation holds,
U_{i}
accepts (
x_{i}
,
Y_{i}
) as his private and public keys. Theorem 4 proves the correctness of Eq. (20) which also validates the authenticity of
Y_{i}
with respect to
x_{i}
.
Theorem 4.
U_{i}
can perform Eq. (20) to authenticate the public key
Y_{i}
with respect to his private key
x_{i}
.
Proof:
From the lefthand side of Eq. (20), we have
which equals to the righthand side of Eq. (20).
The signature generation and verification stage:
When
U_{a}
wants to send
U_{b}
the signature of a confidential message
m
with embedded redundancy.
U_{a}
first chooses an integer
and computes (
C
,
r
_{1}
,
r
_{2}
,
s
) as Eqs. (21), (8), (12) and (10.*) of
Table 1
, respectively.
(
r
_{1}
,
r
_{2}
,
s
) is the signature for
m
, which is then sent to the designated recipient
U_{b}
. Upon receiving the signature,
U_{b}
first computers the corresponding
K
from Eq. (23.*) of
Table 3
and
C'
from Eq. (24).
Equations to computeKbased on the ECDLP
Equations to compute K based on the ECDLP
The message
m
with the embedded redundancy can be recovered from Eq. (13). After that,
U_{b}
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
y_{a}
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
U_{b}
can recover the message
m
with Eq. (13).
Proof:
From the righthand side of Eq. (13), we have
which equals to the lefthand side of Eq. (13).
Theorem 6.
A valid signature (
r
_{1}
,
r
_{2}
,
s
) should satisfy Eq. (14) which also authenticates the public key
Y_{a}
.
Proof:
From the righthand side of Eq. (14), we have
which equals to the lefthand side of Eq. (14).
The signature conversion stage:
To handle the case of a later dispute, the recipient
U_{b}
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
U_{a}
.
The recipient proof stage:
For convincing someone, say,
U_{c}
, that he is the real recipient, the recipient
U_{b}
can perform the following interactive steps with
U_{c}
:
Step 1
U_{b}
sends (
r
_{2}
,
s
,
C'
) to
U_{c}
.
Step 2
U_{c}
first computes
K
with corresponding Eq. (23.*) and then checks the signature’s validity with Eq. (14). If it holds,
U_{c}
proceeds to the next step; otherwise, the protocol is terminated.
Step 3
U_{c}
randomly chooses an integer
e
to compute
E
=
eK
and then transmits
E
to
U_{b}
.
Step 4
Upon receiving
E
,
U_{b}
computes
W
=
x_{b}E
and returns it to
U_{c}
.
Step 5
U_{c}
computes
W'
=
eC'
and checks whether
W
=
W'
. If it holds,
U_{c}
is convinced that
U_{b}
is the designated recipient.
4. Security Considerations and Performance Evaluation
In this section, we first defined some security notions for selfcertified 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 Userregistration, Signatureencryptionandverification, Signatureconversion and Recipientproof from each phase of the proposed schemes. The security notions of message confidentiality and unforgeability with respect to selfcertified CAE schemes are defined below.
Message Confidentiality.
A selfcertified 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 selfcertified CAE scheme is said to be semantically secure against chosen ciphertext attacks if there exits no polynomialtime adversary with a nonnegligible advantage in the following game:
Setup:
A challenger
C
first generates necessary system parameters and then obtains the signer
U_{a}
’s key pair (
x_{a}
,
y_{a}
) by the Userregistration algorithm. System parameters and the signer
U_{a}
’s public key are given to an adversary
A
. Upon receiving these parameters, the adversary
A
determines one designated recipient
U_{b}
*. The recipient
U_{b}
*’s public key
y_{b}
* can be acquired from the Userregistration algorithm, but the corresponding private key
x_{b}
* is unknown to
A
.
Phase 1:
The adversary
A
can issue several kinds of queries adaptively:
– Signatureencryptionandverification queries: The adversary
A
can query either Signatureencryption or Signatureverification. In the Signatureencryption queries, the adversary
A
produces a message
m
with respect to
U_{a}
and sends it to the challenger
C
which then returns the result of Signatureencryption (
m
,
x_{a}
,
y_{b}
*) to
A
. In the Signatureverification queries, the adversary
A
produces an authenticated ciphertext
σ
= (
r
_{1}
,
r
_{2}
,
s
) and requests the result of Signatureverification (
σ
,
y_{a}
,
x_{b}
*) with respect to
U_{a}
and
U_{b}
* 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.
– Signatureconversion queries: The adversary
A
produces an authenticated ciphertext
σ
= (
r
_{1}
,
r
_{2}
,
s
) and requests the result of Signatureconversion (
σ
,
y_{a}
,
x_{b}
*) with respect to
U_{a}
and
U_{b}
* 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.
– Recipientproof queries: The adversary
A
produces an authenticated ciphertext
σ
= (
r
_{1}
,
r
_{2}
,
s
) and requests the result of Recipientproof (
σ
,
y_{a}
,
x_{b}
*) with respect to
U_{a}
from the challenger
C
. If
U_{b}
* 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
σ
* = Signatureencryption (
m_{λ}
,
x_{a}
,
y_{b}
*) 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 Signatureverification or Signatureconversion 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 selfcertified CAE scheme against chosen message attacks. In this model, the adversary attempts to forge a valid signature of one target message.
Definition 2.
A selfcertified CAE scheme is said to achieve existential unforgeability against chosenmessage attacks if there exists no polynomialtime adversary with a nonnegligible advantage in the following game:
Setup:
A challenger
C
first generates necessary system parameters, and then obtains the signer
U_{a}
’s key pair (
x_{a}
,
y_{a}
) and a designated recipient
U_{b}
’s key pair (
x_{b}
,
y_{b}
) by the Userregistration algorithm. The challenger
C
then gives the forger
F
system parameters, the signer
U_{a}
’s public key
y_{a}
and the designated recipient’s public key
y_{b}
.
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 Signatureencryption 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 NybergRueppel signature schemes
[32
,
33]
. For the details of NybergRueppel signature schemes, we recommend the interested readers to refer to
[32
,
33]
. Instead of separate discussions, we only take the DLPbased 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 selfcertified CAE scheme is
(
t
,
ε
)
secure against chosen ciphertext attacks if there exists no polynomialtime algorithm
β
_{1}
that can
(
t
_{1}
,
ε
_{1}
)
break the DLP
.
Proof.
Suppose that
A
is a (
t
,
ε
)algorithm that breaks the selfcertified 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.
–Signatureencryption queries: When
A
issues a Signatureencryption query on a message
m
, the algorithm
β
_{1}
first randomly chooses an integer
and computes
Then,
β
_{1}
computes
r
_{1}
=
mh
(
C
)
^{1}
mod
p
,
r
_{2}
=
h
(
m
,
h
(
g^{k}
mod
p
),
C
) mod
q
, and
s
=
k
(1 +
x_{a}r
_{2}
)
^{1}
mod
q
. Here, (
r
_{1}
,
r
_{2}
,
s
) is the authenticated ciphertext
σ
which is returned as the result of the Signatureencryption on the message
m
.
– Signatureverification queries: When
A
issues a Signatureverification query on an authenticated ciphertext
σ
= (
r
_{1}
,
r
_{2}
,
s
),
β
_{1}
first computes
and
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.
– Signatureconversion queries: When
A
issues a Signatureconversion query on an authenticated ciphertext
σ
= (
r
_{1}
,
r
_{2}
,
s
), the algorithm
β
_{1}
first computes
and
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.
– Recipientproof queries: When
A
issues a Recipientproof query on an authenticated ciphertext
σ
= (
r
_{1}
,
r
_{2}
,
s
),
β
_{1}
first performs the same steps as those in Signatureconversion queries, and then chooses an integer e to compute
E
=
K^{e}
mod
p
,
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
σ
* = Signatureencryption (
m_{λ}
,
x_{a}
,
y_{b}
*). The algorithm
β
_{1}
first randomly chooses an integer
and computes
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 +
x_{a}r
_{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 Signatureencryption 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 Signatureverification or Signatureconversion 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,
where Pr
_{A}
[Succ] stands for the probability that
A
succeeds. When
Z
is uniformly distributed in
the adversary
A
has no information about the value of
λ
and hence the probability of
λ'
=
λ
is at most 1/2. Therefore, we conclude that
Theorem 8.
The proposed selfcertified CAE scheme is
(
t
,
ε
)
secure against existential forgery under chosen plaintext attacks if there exists no polynomialtime algorithm
β
_{2}
that can forge the NybergRueppel signature in time
t
_{2}
with the probability
ε
_{2}
.
Proof.
Suppose that
F
is a (
t
,
ε
)algorithm that breaks the selfcertified 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 NybergRueppel signature scheme. We will construct a (
t
_{2}
,
ε
_{2}
)algorithm
β
_{2}
that forges the NybergRueppel signature in time
t
_{2}
with the probability
ε
_{2}
from the algorithm
F
. The objective of the algorithm
β
_{2}
is to derive a valid NybergRueppel signature. In this proof,
β
_{2}
simulates
F
’s challenger in the game of Definition 2 with the target signer
U_{a}
’s public key
y_{a}
* where
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 Signatureencryption query (
m
*,
x_{a}
*,
y_{b}
).
Analysis:
F
outputs an authenticated ciphertext
σ
* which can be converted to the message
m
* and its corresponding signature (
r
_{2}
*,
s
*,
C'
*) with a nonnegligible 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 NybergRueppel signature of the message
m
* with respect to the public key
y_{a}
*. It can be seen that
is hence at least Pr
_{F}
[Succ]. We conclude that
 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 rolebased 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 modelcheckers to analyze if the security goals are violated. There are four different verification back end tools use to analyze the IF specification namely, OFMC (OntheFly ModelChecker), CLAtSe (Constraint Logic based Attack Searcher), SATMC (SATbased 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.
The result of the analysis using OFMC on our scheme
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 WuHsu 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 selfcertified 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 timeconsuming operation, we ignore others such as the oneway 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 WuHsu scheme and Lv
et al
.’s scheme in terms of the computation efficiency for the entire protocol. Note that the WuHsu 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
T_{e}
. 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.
Remarks: 1. Let T_{e} be the time for performing a modular exponentiation computation. 2. WH and LWK separately represent the WuHsu 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 WuHsu scheme is implemented with ElGamal signature verification [6], i.e., T_{m} + 3T_{e}.
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 selfcertified CAE schemes based on discrete logarithms along with their elliptic curve variants. Implemented with selfcertified 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 1022221E019041.
BIO
TzongSun 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 ecommerce.
YihSen 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.
HanYu Lin received his Ph.D. degree in computer science and engineering from the National Chiao Tung University, Taiwan in 2010. He served as a parttime 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 Ecommerce Security.
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 nonrepudiation 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)
IT22
(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)
IT31
(4)
469 
472
DOI : 10.1109/TIT.1985.1057074
Rivest R.
,
Shamir A.
,
Adleman L.
1978
“A method for obtaining digital signatures and publickey cryptosystems”
Communications of the ACM
Article (CrossRef Link)
21
(2)
120 
126
DOI : 10.1145/359340.359342
2001
ISO/IEC 95948, Information technology open systems interconnection the directory: publickey and attribute certificate frameworks
International Organization for Standardization
Shamir A.
1984
“Identitybased cryptosystems and signature schemes”
Advances in Cryptology CRYPTO’84
SpringerVerlag
Article (CrossRef Link)
47 
53
Girault M.
1991
“Selfcertified public keys”
Advances in Cryptology EUROCRYPT’91
SpringerVerlag
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 KnowledgeBased 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)
E82A
(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/S01641212(01)001431
Chen Y. H.
,
Jan J. K.
2005
“Enhancement of digital signature with message recovery using selfcertified 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 selfcertified 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 selfcertified 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
“Selfcertified 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 identitybased keyinsulated convertible multiauthenticated 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 multiauthenticated 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 148883, Information technology security techniques digital signature with appendix part 3: certificatebased mechanisms
International Organization for Standardization
2002
ISO/IEC 159463, Information technology – security techniques – cryptographic techniques based on elliptic curves – part 3: key establishment
International Organization for Standardization
Miller V.
1985
“Use of elliptic curves in cryptography,” Advances in Cryptology CRYPTO’85
SpringerVerlag
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
SpringerVerlag
Article (CrossRef Link)
182 
193
AVISPA. Automated validation of internet security protocols and applications.
http://www.avispaproject.org/
Das A. K.
,
Bruhadeshwar B.
2013
“An improved and effective secure passwordbased 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/s1091601399699
AVISPA. AVISPA web tool.
http://www.avispaproject.org/webinterface/expert.php/