1 Introduction
1.1 Motivation and contribution
1.2 Related work
bob@uestc.edu.cn
, she encrypts her message using the string “bob@uestc.edu.cn
”. In this process, Alice does not need to obtain Bob’s public key certificate. When Bob receives the encrypted e-mail, he applies for a private key from the PKG and then decrypts his e-mail. Note that unlike the PKI-based e-mail systems, Alice can send an encrypted e-mail to Bob even if Bob has not obtained his key pair information. In 2001, Boneh and Franklin [5] designed a practical identity-based encryption (IBE) scheme using bilinear pairings and proved its security in the random oracle model. Park and Lee [6] proposed another IBE scheme that achieves a tight security reduction to the decisional bilinear Diffie–Hellman assumption in the random oracle model. In 2002, Hess [7] constructed an identity-based signature (IBS) whose security depends on the hardness of the Diffie–Hellman problem in the random oracle model. In 2003, Cha and Cheon [8] designed a new IBS using gap Diffie–Hellman groups. In 2011, Hsu and Lin [9, 10] extended AE into the identity-based environment and constructed identity-based authenticated encryption (IBAE). However, these two IBAE schemes have non-repudiation. That is, they are not deniable. Some identity-based signcryption (IBSC) [11‐13] also were proposed to achieve both confidentiality and authentication. However, these IBSC schemes still have non-repudiation.1.3 Organization
2 IBDAE
2.1 Syntax
-
Setup
is a probabilistic algorithm run by a PKG that takes as input a security parameter k, and outputs a master secret key s and the system parameters param including a master public key \(P_{pub}\). Here we assume that param are public so that we do not need to include them in other algorithms. -
Extract
is a key extraction algorithm run by the PKG that takes as input an identity ID and the master secret key s, and outputs the corresponding private key \(S_{ID}\). The PKG transmits the private key to its owner in a secure way. -
Encrypt
is a probabilistic deniable authenticated encryption algorithm run by a sender that takes as input a message m, a sender’s private key \(S_{ID_s}\) and a receiver’s identity \(ID_r\), and outputs a ciphertext \(\sigma \). -
Decrypt
is a deterministic deniable authenticated decryption algorithm run by a receiver that takes as input a ciphertext \(\sigma \), a sender’s identity \(ID_s\) and a receiver’s private key \(S_{ID_r}\), and outputs a plaintext m or the symbol \(\bot \) if \(\sigma \) is an invalid ciphertext between the sender and the receiver.
Encrypt
and Decrypt
are different from common Encrypt and Decrypt in public key encryption schemes. Here Encrypt
means deniable authenticated encryption and Decrypt
means deniable authenticated decryption. In the following contents, encryption and decryption usual mean deniable authenticated encryption and deniable authenticated decryption, respectively.2.2 Security notions
-
Initial
\({\mathcal {C}}\) runsSetup
algorithm with a security parameter k and sends the system parameters param to \({\mathcal {A}}\). -
Phase 1
\({\mathcal {A}}\) performs a polynomially bounded number of queries (these queries may be made adaptively, i.e. each query may depend on the answer to the previous queries).-
Key extraction queries \({\mathcal {A}}\) chooses an identity ID. \({\mathcal {C}}\) runs
Extract
algorithm and sends the corresponding private key \(S_{ID}\) to \({\mathcal {A}}\). -
Encryption queries \({\mathcal {A}}\) produces a plaintext m and two identities \(ID_i\) and \(ID_j\). \({\mathcal {C}}\) first runs
Extract
algorithm to generate the sender’s private key \(S_{ID_i}\). Then \({\mathcal {C}}\) runsEncrypt
\((m,S_{ID_i},ID_j)\) algorithm and sends \(\sigma \) to \({\mathcal {A}}\). -
Decryption queries \({\mathcal {A}}\) produces a ciphertext \(\sigma \) and two identities \(ID_i\) and \(ID_j\). \({\mathcal {C}}\) first runs
Extract
algorithm to generate the receiver’s private key \(S_{ID_j}\). Then \({\mathcal {C}}\) runsDecrypt
\((\sigma ,ID_i,S_{ID_j})\) algorithm and sends the result to \({\mathcal {A}}\) (this result can be the \(\bot \) symbol if \(\sigma \) is an invalid ciphertext).
-
-
Challenge
\({\mathcal {A}}\) decides when phase 1 ends. \({\mathcal {A}}\) generates two equal length plaintexts \(m_0\) and \(m_1\) and two identities \(ID_s\) and \(ID_r\) on which it wants to be challenged. It can not have asked the private key corresponding to \(ID_r\) in the phase 1. \({\mathcal {C}}\) takes a random bit \(\beta \in \{0,1\}\) and computes \(\sigma ^*=\mathtt{Encrypt}(m_\beta ,S_{ID_s},ID_r)\) which is sent to \({\mathcal {A}}\). -
Phase 2
\({\mathcal {A}}\) can ask a polynomially bounded number of queries adaptively again as in the phase 1. This time, it can not ask a key extraction query on \(ID_r\) and can not ask a decryption query on \((\sigma ^*,ID_s,ID_r)\) to obtain the corresponding plaintext. -
Guess
\({\mathcal {A}}\) produces a bit \(\beta '\) and wins the game if \(\beta '=\beta \).
-
Initial
\({\mathcal {C}}\) runsSetup
algorithm with a security parameter k and sends the system parameters param to \({\mathcal {F}}\). -
Attack
\({\mathcal {F}}\) performs a polynomially bounded number of queries just like in the Game-I. -
Forgery
\({\mathcal {F}}\) produces a triple \((\sigma ^*,ID_s,ID_r)\) and wins the game if the following conditions hold:1.Decrypt
\((\sigma ^*,ID_s,S_{ID_r})=m^*\).2.\({\mathcal {F}}\) has not asked key extraction queries on \(ID_s\) and \(ID_r\).3.\({\mathcal {F}}\) has not asked an encryption query on \((m^*,ID_s,ID_r')\). Here \(ID_r'\) may be different from \(ID_r\).
3 IBDATK
3.1 Syntax
-
Setup
is a probabilistic algorithm run by a PKG that takes as input a security parameter k, and outputs the system’s parameters param, including a master public key \(P_{pub}\) and a master secret key s. We also assume that param are public so that we do not need to include them in other algorithms. -
Extract
is a key extraction algorithm run by the PKG that takes as input an identity ID and the master secret key s, and outputs the corresponding private key \(S_{ID}\). The PKG transmits the private key to its owner in a secure way. -
Sym
is a probabilistic symmetric key generation algorithm run by a sender that takes as input a sender’s private key \(S_{ID_s}\) and a receiver’s identity \(ID_r\), and outputs a symmetric key K together with internal state information \(\omega \). Here \(K\in \mathcal {K}_\mathrm{IBDATK}\) is a key in the space of possible session keys at a given security level. \(\mathcal {K}_\mathrm{IBDATK}\) is the key space. -
Encap
is a probabilistic key encapsulation algorithm which takes as input the state information \(\omega \) and an arbitrary tag \(\tau \), and returns an encapsulation \(\psi \in \mathcal {E}_\mathrm{IBDATK}\). Here \(\mathcal {E}_\mathrm{IBDATK}\) is the encapsulation space. -
Decap
is a deterministic decapsulation algorithm run by a receiver that takes as input an encapsulation \(\psi \), a tag \(\tau \), a sender’s identity \(ID_s\) and a receiver’s private key \(S_{ID_r}\), and outputs the corresponding key K or a special symbol \(\bot \) indicating invalid encapsulation.
3.2 Security notions
-
Initial
\({\mathcal {C}}\) runsSetup
algorithm with a security parameter k and sends the system parameters param to \({\mathcal {A}}\). -
Phase 1
\({\mathcal {A}}\) performs a polynomially bounded number of queries (these queries may be made adaptively, i.e. each query may depend on the answer to the previous queries).-
Key extraction queries \({\mathcal {A}}\) chooses an identity ID. \({\mathcal {C}}\) runs
Extract
algorithm and sends the corresponding private key \(S_{ID}\) to \({\mathcal {A}}\). -
Symmetric key generation queries \({\mathcal {A}}\) produces a sender’s identity \(ID_i\) and a receiver’s identity \(ID_j\). \({\mathcal {C}}\) first runs
Extract
algorithm to generate the sender’s private key \(S_{ID_i}\) and runs \((K,\omega )=\mathtt{Sym}(S_{ID_i},ID_j)\). It then stores the value \(\omega \) (hidden from the view of the adversary, and overwriting any previously stored values), and sends the symmetric key K to \({\mathcal {A}}\). -
Key encapsulation queries \({\mathcal {A}}\) produces an arbitrary tag \(\tau \). \({\mathcal {C}}\) checks whether there exists a stored value \(\omega \). If not, it returns \(\bot \) and terminates. Otherwise it erases the value from storage and returns \(\psi =\mathtt{Encap}(\omega ,\tau )\) to \({\mathcal {A}}\).
-
Key decapsulation queries \({\mathcal {A}}\) chooses an encapsulation \(\psi \), a tag \(\tau \), a sender’s identity \(ID_i\) and a receiver’s identity \(ID_j\). \({\mathcal {C}}\) first runs
Extract
algorithm to generate the receiver’s private key \(S_{ID_j}\). Then \({\mathcal {C}}\) runs \(\mathtt{Decap}(\psi ,\tau ,ID_i,S_{ID_j})\) algorithm and sends the result to \({\mathcal {A}}\).
-
-
Challenge
\({\mathcal {A}}\) decides when phase 1 ends. \({\mathcal {A}}\) generates a sender’s identity \(ID_s\) and a receiver’s identity \(ID_r\) on which it wishes to be challenged. The identity \(ID_r\) should not appear in any key extraction queries in phase 1. \({\mathcal {C}}\) first runs \((K_1,\omega ^*)=\mathtt{Sym}(S_{ID_s},ID_r)\). Then \({\mathcal {C}}\) chooses \(K_0\in \mathcal {K}_\mathrm{IBDATK}\) and a bit \(\beta \in \{0,1\}\) randomly, and sends \(K_\beta \) to \({\mathcal {A}}\). When \({\mathcal {A}}\) receives \(K_\beta \), it may ask the same queries as previously. Then \({\mathcal {A}}\) generates a tag \(\tau ^*\). Finally, \({\mathcal {C}}\) computes \(\psi ^*=\mathtt{Encap(\omega ^*,\tau ^*)}\) and sends it to \({\mathcal {A}}\) as a challenge encapsulation. -
Phase 2
\({\mathcal {A}}\) can ask a polynomially bounded number of queries adaptively again as in phase 1 with the restriction that it can not ask a key extraction query on \(ID_r\) and can not ask a decapsulation query on \((\psi ^*,\tau ^*,ID_s,ID_r)\) to obtain the corresponding key. -
Guess
\({\mathcal {A}}\) produces a bit \(\beta '\) and wins the game if \(\beta '=\beta \).
-
Initial
\({\mathcal {C}}\) runsSetup
algorithm with a security parameter k and sends the system parameters param to \({\mathcal {F}}\). -
Attack
\({\mathcal {F}}\) performs a polynomially bounded number of queries just like in the Game-III. -
Forgery
\({\mathcal {F}}\) produces a quaternion \((\psi ^*,\tau ^*,ID_s,ID_r)\) and wins the game if the following conditions hold:1.\(\mathtt{Decap}(\psi ^*,\tau ^*,ID_s,S_{ID_r})=K^*\).2.\({\mathcal {F}}\) has not asked key extraction queries on \(ID_s\) and \(ID_r\).3.\({\mathcal {F}}\) has not asked a key encapsulation query on \(\tau ^*\).
4 A hybrid IBDAE scheme
IBDATK
with a DEM scheme DEM
(the definition of DEM can be found in Appendix 1) to form a hybrid IBDAE scheme IBDAE
. Our method is described in Fig. 1. Note that the tag is the ciphertext output by the DEM. Such construction yields simpler scheme descriptions and better generic security reductions.
IBDAE
be a hybrid IBDAE scheme constructed from an IBDATK scheme IBDATK
and a DEM scheme DEM
. If the IBDATK
is \((\epsilon _{datk},t,q_k,q_s,q_e,q_d)\)-IND-CCA2 secure and the DEM
is \((\epsilon _{dem},\bar{t})\)-IND-PA secure, then the IBDAE
is \((\epsilon _{dae},t',q_k',q_e',q_d')\)-IND-CCA2 secure, where \(\epsilon _{datk}\ge (\epsilon _{dae}-\epsilon _{dem})/2\), \(t=t'+\bar{t}+O(q_e'T_{enc}+q_d'T_{dec})\), \(q_k=q_k'\), \(q_s=q_e=q_e'\), \(q_d=q_d'\). Here \(T_{enc}\) and \(T_{dec}\) are the maximum time for computing an encryption in DEM
and a decryption in DEM
.IBDAE
be a hybrid IBDAE scheme constructed from an IBDATK scheme IBDATK
and a DEM scheme DEM
. If the IBDATK
is \((\epsilon _{datk},t,q_k,q_s,q_e,q_d)\)-DA-CMA secure, then the IBDAE
is \((\epsilon _{dae},t',q_k',q_e',q_d')\)-DA-CMA secure, where \(\epsilon _{datk}\ge \epsilon _{dae}\), \(t=t'+O(q_e'T_{enc}+q_d'T_{dec})\), \(q_k=q_k'\), \(q_s=q_e=q_e'\), \(q_d=q_d'\). Here \(T_{enc}\) and \(T_{dec}\) are the maximum time for computing an encryption in DEM
and a decryption in DEM
.5 An efficient IBDATK scheme
5.1 Bilinear pairings
5.2 Our scheme
-
Setup
Define \(G_1\), \(G_2\) and \(\hat{e}\) as in Sect. 5.1. Let \(H_1\), \(H_2\) and \(H_3\) be three hash functions where \(H_1:\{0,1\}^*\rightarrow G_1\), \(H_2:G_2\rightarrow \{0,1\}^{n}\) and \(H_3:\{0,1\}^*\times G_2\rightarrow {\mathbb {Z}}_q^*\). Here n is the key length of a DEM and \(q\ge 2^k\), where k is a security parameter. Let P be a generator of \(G_1\). The PKG chooses a master secret key \(s\in {\mathbb {Z}}_q^*\) randomly and computes \(P_{pub}=sP\). The PKG publishes system parameters \(param=\{G_1,G_2,q,n,\hat{e},P,P_{pub},H_1,H_2,H_3\}\) and keeps the master secret key s secret. -
Extract
Given an identity ID, the PKG computes the corresponding private key \(S_{ID}=sQ_{ID}\) and sends it to its owner in a secure way. Here \(Q_{ID}=H_1(ID)\). -
Sym
Given a sender’s private key \(S_{ID_s}\) and a receiver’s identity \(ID_r\), this algorithm works as follows.1.Choose x from \({\mathbb {Z}}_q^*\) randomly.2.Compute \(z=\hat{e}(P_{pub},Q_{ID_r})^x\).3.Output \(K=H_2(z)\) and \(\omega =(x,z,S_{ID_s},ID_s,ID_r)\). -
Encap
Given the state information \(\omega \) and an arbitrary tag \(\tau \), this algorithm works as follows.1.Compute \(u=H_3(\tau ,z)\).2.Compute \(V=uS_{ID_s}+xP_{pub}\) and \(T=\hat{e}(V,Q_{ID_r})\).3.Compute \(R=uQ_{ID_s}\).4.Output \(\psi =(R,T)\). -
Decap
Given an encapsulation \(\psi =(R,T)\), a tag \(\tau \), a sender’s identity \(ID_s\) and a receiver’s private key \(S_{ID_r}\), this algorithm works as follows.1.Compute \(z=T/\hat{e}(R,S_{ID_r})\).2.Compute \(u=H_3(\tau ,z)\).3.If \(R=uQ_{ID_s}\), output the \(K=H_2(z)\), otherwise output the symbol \(\bot \).
5.3 Consistency
5.4 Deniability
Encap
algorithm in Sect. 5.2. Let \(\psi '=(R',T')\) be an encapsulation that is randomly chosen in the set of all valid sender’s encapsulation intended to receiver. The probability \(\mathrm{Pr}[\bar{\psi }=\psi ']\) is \(1/(q-1)\) because \(\bar{\psi }\) is generated from a randomly chosen value \(\bar{x}\in {\mathbb {Z}}_q^*\). Likewise, the probability \(\mathrm{Pr}[\psi =\psi ']\) has the same value \(1/(q-1)\) because it is generated from \(x\in {\mathbb {Z}}_q^*\). That is, both distributions are the same.5.5 Security
Schemes | Computational cost | Communication overhead | Formal security | ||
---|---|---|---|---|---|
PM | EC | PC | |||
SL+BF | 6 | 3 | 7 |
\(3|G_1|+|{\mathbb {Z}}_q^*|+|MAC|+2|m|\)
| No |
LXJ+BF | 5 | 1 | 4 |
\(2|G_1|+|G_2|+2|m|\)
| No |
Ours | 4 | 1 | 3 |
\(|G_1|+|G_2|+|m|\)
| Yes |
6 Performance discussion
Security level | Size of p
| Size of q
|
---|---|---|
80-bit | 512 | 160 |
112-bit | 1024 | 224 |
128-bit | 1536 | 256 |
7 Application
alice@uestc.edu.cn
and the receiver’s identity \(ID_r\) is bob@uestc.edu.cn
. The sender first applies a private key \(S_{ID_s}\) from the PKG and then runs \(\mathtt{Encrypt}(m,S_{ID_s},ID_r)\) to get a ciphertext \(\sigma \). The sender transmits its identity \(ID_s\), the receiver’s identity \(ID_r\) and the ciphertext \(\sigma \) to its mail server. Then the sender’s mail server transfers \((ID_s,ID_r,\sigma )\) to the receiver’s mail server. The receiver’s mail server keeps \((ID_s,ID_r,\sigma )\) and waits for the receiver. When the receiver hopes to receive its mail, it submits its identity \(ID_r\) and password to its mail server for authentication. If the receiver passes this authentication, the mail server sends the \((ID_s,ID_r,\sigma )\) to the receiver. The receiver can apply a private key \(S_{ID_r}\) from the PKG and then runs \(\mathtt{Decrypt}(\sigma ,ID_s,S_{ID_r})\) to obtain the message m. Of course, the receiver can registers a private key \(S_{ID_s}\) in advance. The hybrid technique is very suitable for sending a large e-mail.