A Computational Diffie–Hellman-Based Insider Secure Signcryption with Non-interactive Non-repudiation

Abstract

An important advantage of signcryption schemes compared to one pass key exchange protocols is non-interactive non-repudiation (NINR). This attribute offers to the receiver of a signcrypted ciphertext the ability to generate a non-repudiation evidence, that can be verified by a third party without executing a costly multi-round protocol. We propose a computational Diffie–Hellman based insider secure signcryption scheme with non-interactive non-repudiation. Namely, we show that under the computational Diffie–Hellman assumption and the random oracle model, our scheme is tightly insider secure, provided the underlying encryption scheme is semantically secure. Compared to a large majority of the previously proposed signcryption schemes with NINR, our construction is more efficient and it does not use any specificity of the underlying group, such as pairings. The communication overhead of our construction, compared to Chevallier Mâmes’ signature scheme is one group element.

1 Introduction

A signcryption scheme provides simultaneously the functionalities of encryption and signature schemes [24]. A natural use of a signcryption scheme is to build an asynchronous secure channel i.e., a confidential and authenticated asynchronous channel. Given the similar uses of signcryption and (one pass) Key Exchange Protocols (KEP), to build confidential and authenticated channels, it appears, from a real world perspective, that the right security definition for signcryption schemes is insider security [3]. Informally, insider security ensures (i) confidentiality even if the sender’s static private key is revealed to the attacker, and (ii) unforgeability even if the receiver’s static private key is disclosed.

A signcryption scheme is said to provide non-repudiation, if the receiver of a signcrypted ciphertext has the ability to generate a non-repudiation evidence, that can be verified by a third party (a judge, for instance); as a result, a message sender cannot deny having signcrypted the message. The non-repudiation attribute is said to be non-interactive, if a non-repudiation evidence can be generated and verified without executing a multi-round protocol. An important advantage of signcryption schemes, compared to one pass KEP, which often outperforms signcryption schemes, is non-interactive non-repudiation (NINR).

A signcryption scheme with the aim to provide NINR was proposed for the first time by Bao and Deng [5]; unfortunately their design fails in achieving confidentiality [19]. Malone–Lee [19] proposes an efficient design with NINR he analyzes in the Random Oracle (RO) model. The scheme achieves confidentiality under the computational Diffie–Hellman ($\mathsf{{cDH}}$) assumption, and unforgeability under the gap Diffie–Hellman Assumption. Unfortunately, the security model he uses is closer to the outsider than to the insider model. Indeed, the scheme fails in providing insider confidentiality. In [8], Bjørstad and Dent (BD) propose a design based on Chevallier Mâmes’ (CM) signature scheme they show to tightly achieve insider unforgeability under the cDH assumption and outsider confidentiality under the gap DH assumption. Unfortunately, as for the ML scheme, the BD scheme does not achieve insider confidentiality.

In subsequent works [2, 13, 14, 20, 23], several insider secure schemes with NINR have been proposed. The designs offer a superior security, compared to the ML or BD schemes. However, they are less efficient and often assume some specificities of the underlying groups, such as the existence of a bilinear pairing. In [2], Arriaga et al. propose a generic insider secure signcryption scheme, with randomness reuse, in the standard model. They exhibit an insider secure instantiation of their design, under the Decisional Bilinear and the q-Strong Diffie–Hellman (DBDH and q-sDH) assumptions. Unfortunately, the unforgeability is achieved in the registered key model [20], wherein an attacker is required to register the keys pairs it uses in its attack. Matsuda et al. [20] propose a generic composition of signature and tag-based encryption schemes, which yields to different shades of security depending on the security attributes of the base schemes. They exhibit two constructions with NINR that fully achieve insider confidentiality (under the cDH and the gap DH assumptions respectively) and unforgeability (under the co-cDH assumption). Chiba et al. [13] propose a generic construction of signcryption schemes, and exhibit two insider secure constructions with NINR under the DBDH and the q-sDH assumptions. In [14], Fan et al. propose a signcryption scheme with non-interactive non-repudiation (SCNINR), based on Boneh et al.’s signature scheme [10], they show to be insider secure under the DBDH assumption, without resorting the RO model. Sarr et al. [23] propose, over the group of signed quadratic residues, a SCNINR, based on a signature scheme of their own design, they show to be insider secure under the RSA assumption and the RO model.

The basic design principle in the SCNINR schemes from [8, 14, 19, 23], is (i) a Diffie–Hellman (DH) secret derivation, using ephemeral keys from the sender and the receiver’s static public key, followed by (ii) an encryption using some part of the derived secret, and (iii) a signature generation, using the sender’s private key, on the plain text and some part of the derived DH secret. One may notice also that these schemes assume rather specific groups or have loose security reductions. As tightly secure $\mathsf{{cDH}}$-based signature schemes exist [12, 15, 17], we investigate whether such schemes can be leveraged as building blocks for tightly (multi-user) insider secure $\mathsf{{cDH}}$ based SCNINR schemes. As we aim at an efficient design, we use the random oracle (RO) model. We propose a new SCNINR, termed $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$, based on a variant of Chevallier–Mâmes’ signature scheme [12], tailored to (i) be combined with Cash et al.’s twin Diffie–Hellman key exchange [11], (ii) and to allow a use of the same randomness in the DH key exchange and in the signature generation.

And, using the trapdoor test technique [11], we show that $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ is tightly insider secure under the $\mathsf{{cDH}}$ assumption and the RO model, provided the underlying symmetric encryption scheme is semantically secure. Even better, we show the insider confidentiality attribute in the secret key ignorant multi-user model, i.e., when the sender public key is chosen by the adversary and the challenger does not know the corresponding private key. Compared to the ML and BD schemes, which do not require any specificity of the underlying group and do not achieve insider security, $\mathcal{S}\mathcal{C}_{\mathsf{{edl}}}$ offers a stronger security, even if it is less efficient. And, compared to the schemes from [2, 13, 14, 20, 23], $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ offers a tight security reduction, a better efficiency, and a comparable or a superior security.

This paper is organized as follows. In Sect. 2, we present some preliminaries on the syntax of SCNINR schemes and the insider security definitions for SCNINR. In Sect. 3, we propose the $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ scheme. We propose our security results in Sect. 4, and compare our design with previous constructions in Sect. 5.

2 Preliminaries

Notations. $\mathcal {G}=\langle G\rangle$ is a cyclic group of prime order p, $\mathcal {G}^{*}$ denotes the set $\mathcal {G}\setminus \{1\}$. We denote by $\mathsf{{Exp}}(\mathcal {G}, t)$ the computational effort required to perform t exponentiations with |p|-bits exponents in $\mathcal {G}$ ; $\mathsf{{Exp}}(\mathcal {G})$ denotes $\mathsf{{Exp}}(\mathcal {G}, 1)$. For an integer n, [n] denotes the set $\{0, \ldots , n\}$. If S is a set, $a\,{\leftarrow }_{\text {\tiny R}}\,S$ means that a is chosen uniformly at random from S; we write $a, b, c, \ldots \,{\leftarrow }_{\text {\tiny R}}\,S$ as a shorthand for $a\,{\leftarrow }_{\text {\tiny R}}\,S; b\,{\leftarrow }_{\text {\tiny R}}\,S$, etc. We denote by ${\mathsf{{sz}}}(S)$ the number of bits required to represent $a\in S$. For a probabilistic algorithm $\mathcal {A}$ with parameters $u_1, \ldots , u_n$ and output $V\in \textbf{V}$, we write $V\,{\leftarrow }_{\text {\tiny R}}\,\mathcal {A}(u_1,\ldots , u_n)$. We denote by $\{\mathcal {A}(u_1,\ldots , u_n)\}$ the set $\{v\in \textbf{V}: \Pr (V=v)\ne 0\}$. If $x_1, x_2, \ldots , x_k$ are objects belonging to different structures (group, bit-string, etc.) $(x_1, x_2, \ldots , x_k)$ denotes a representation as a bit-string of the tuple such that each element can be unequivocally parsed.

The $\mathsf{{cDH}}$ Assumption. We assume the existence of an algorithm ${\mathsf{{Setup}}}_{\mathsf{{grp}}}(\cdot )$, which on input a security parameter k outputs a system parameter $\Pi _k$ which fully identifies a group $\mathcal {G}=\langle G\rangle$ together with its order. For $X\in \mathcal {G}$, we denote the smallest non-negative integer x such that $G^x=X$ by $\log _GX$. For, $X, Y\in \mathcal {G}$, we denote $G^{(\log _GX)(\log _GY)}$ by $\mathsf{{cDH}}(X, Y)$; if $B\in \mathcal {G}$, we denote $(\mathsf{{cDH}}(X, B), \mathsf{{cDH}}(Y, B))$ by $\mathsf{{2DH}}(X, Y, B)$. The $\mathsf{{cDH}}$ assumption is said to hold in $\mathcal {G}$ if for all efficient algorithms $\mathcal {A}$, $\mathsf{{Adv}}^{\mathsf{{cDH}}}_\mathcal {A}(\mathcal {G})=\Pr [X,Y\,{\leftarrow }_{\text {\tiny R}}\,\mathcal {G}; Z\,{\leftarrow }_{\text {\tiny R}}\,\mathcal {A}(G, X, Y):Z=\mathsf{{cDH}}(X, Y)]$ is negligible in k.

A Symmetric Encryption scheme $\mathcal {E}=(\mathsf{{E}}, \mathsf{{D}}, \textbf{K}, \textbf{M}, {\textbf {C}})$ is a pair of efficient algorithms $(\mathsf{{E}}, \mathsf{{D}})$ together with a triple of sets $(\textbf{K}, \textbf{M}, {\textbf {C}})$, which depend on the security parameter k, such that for all $\tau \in \textbf{K}$ and all $m\in \textbf{M}$, it holds that $\mathsf{{E}}(\tau , m)\in {\textbf {C}}$ and $m = \mathsf{{D}}(\tau , \mathsf{{E}}(\tau , m))$. Let $\mathcal {A}=(\mathcal {A}_1, \mathcal {A}_2)$ be an adversary against $\mathcal {E}$ and let $\Pr (O_{i, i=0, 1})=\Pr \left[ \begin{array}{l} (m_0, m_1, st)\,{\leftarrow }_{\text {\tiny R}}\,\mathcal {A}_1(k); \tau \,{\leftarrow }_{\text {\tiny R}}\,\textbf{K}; c \,{\leftarrow }_{\text {\tiny R}}\,\mathsf{{E}}(\tau , m_i); \;\;\; \\ \hat{b} \,{\leftarrow }_{\text {\tiny R}}\,\mathcal {A}_2(k, c, st) \end{array} \;\;: \hat{b}=1 \right] ;$

then ${\mathsf{{Adv}}}^{\mathsf{{ss}}}_{\mathcal {A}, \mathcal {E}}(k)$ denotes the quantity ${\mathsf{{Adv}}}^{\mathsf{{ss}}}_{\mathcal {A}, \mathcal {E}}(k)= \left| \Pr (O_0) - \Pr (O_1) \right| ,$ where $m_0, m_1\in \textbf{M}$ are distinct equal length messages. The scheme $\mathcal {E}$ is said to be $(t, \varepsilon (k))$-semantically secure if for all adversaries $\mathcal {A}$ running in time t, ${{\mathsf{{Adv}}}^{\mathsf{{ss}}}_{\mathcal {A}, \mathcal {E}}(k)\leqslant \varepsilon (k)}$.

2.1 Insider Security for SCNINR

We recall the syntax of a SCNINR scheme and the insider security definitions in the Flexible Signcryption / Flexible Unsigncryption Oracle (FSO/FUO) model [4], also termed dynamic Multi-user model [2].

Definition 1

A signcryption scheme is a quintuple of algorithms $\mathcal{S}\mathcal{C}=({\mathsf{{Setup}}},$ ${\mathsf{{Gen}}}_S,$ ${\mathsf{{Gen}}}_R, {\mathsf{{Sc}}}, \mathsf{{Usc}})$ where

• (a) ${\mathsf{{Setup}}}$ takes a security parameter k as input, and outputs a public domain parameter $dp$.

• (b) ${\mathsf{{Gen}}}_S$ is the sender key pair generation algorithm. It takes as input $dp$ (an implicit parameter) and outputs a key pair $(sk_S, pk_S)$, wherein $sk_S$ is the signcrypting key.

• (c) ${\mathsf{{Gen}}}_R$ is the receiver key pair generation algorithm; it takes $dp$ as input and outputs a key pair $(sk_R, pk_R)$.

• (d) ${\mathsf{{Sc}}}$ takes as inputs $dp$, a sender private key $sk_S$, a receiver public key $pk_R$, and a message m, and outputs a signcryptext C. We write $C\,{\leftarrow }_{\text {\tiny R}}\,{\mathsf{{Sc}}}(sk_S, pk_R, m)$.

• (e) $\mathsf{{Usc}}$ is a deterministic algorithm. It takes as inputs $dp$, a receiver secret key $sk_R$, a sender public key $pk_S$, and a signcryptext C, and outputs either a valid message $m\in \textbf{M}$ or an error symbol $\bot \not \in \textbf{M}$.

And, for all $dp\in \{{\mathsf{{Setup}}}(k)\}$, all $m\in \textbf{M}$, all $(sk_S, pk_S)\in \{{\mathsf{{Gen}}}_S(dp)\}$, and all $(sk_R, pk_R)\in \{{\mathsf{{Gen}}}_R(dp)\}$, $m = \mathsf{{Usc}}(sk_R, pk_S,$ ${\mathsf{{Sc}}}(sk_S, pk_R, m)).$ The scheme is said to provide NINR if there are two algorithms ${\mathsf{{N}}}$ and ${\mathsf{{PV}}}$, termed non-repudiation evidence generation and pubic verification algorithms such that:

• ${\mathsf{{N}}}$ takes as inputs a receiver secret key $sk_R$, a sender public key $pk_S$, and a signcrypted ciphertext C, and outputs a non-repudiation evidence $nr$ or a failure symbol $\bot$; we write $nr\leftarrow {\mathsf{{N}}}(sk_R, pk_S, C)$.

• ${\mathsf{{PV}}}$ takes as inputs a signcryptext C, a message m, a non-repudiation evidence $nr$, a sender public key $pk_S$, and a receiver public key $pk_R$, and outputs $d\in \{0,1\}$; we write $d\leftarrow {\mathsf{{PV}}}(C, m, nr, pk_S, pk_R)$.

• For all $dp\in \{{\mathsf{{Setup}}}(k)\}$, all $C\in \{0, 1\}^*$, all $(sk_S, pk_S)\in \{{\mathsf{{Gen}}}_S(dp)\}$, and all $(sk_R, pk_R)\in \{{\mathsf{{Gen}}}_R(dp)\}$, if $\bot \ne m\leftarrow \mathsf{{Usc}}(sk_R, pk_S, C)$ and $nr\leftarrow {\mathsf{{N}}}(sk_R, pk_S, C)$ then $1=d\leftarrow {\mathsf{{PV}}}(C, m, nr, pk_S, pk_R)$.

Definition 2

(Secret Key Ignorant Multi-user Insider Confidentiality) A SCNINR $\mathcal{S}\mathcal{C}$ is said to be $(t, q_{\mathsf{{Usc}}},q_{{\mathsf{{N}}}}, \varepsilon )$-secure in the Secret Key Ignorant Multi-user (SKI–MU) insider confidentiality in the FSO/FUO IND–CCA2 sense, if for all adversaries $\mathcal {A}$ playing Game 1, running in time t, and issuing respectively $q_{\mathsf{{Usc}}}$ and $q_{{\mathsf{{N}}}}$ queries to the unsigncryption and non-repudiation evidence generation oracles, ${\mathsf{{Adv}}}^{\mathsf{{cca2}}}_{\mathcal {A}, \mathcal{S}\mathcal{C}}(k)\leqslant ~\varepsilon .$

Definition 3

(Multi-user Strong Insider Unforgeability) A SCNINR is said to be $(t, q_{{\mathsf{{Sc}}}}, \varepsilon )$ Multi-user Insider Unforgeable in the FSO/FUO–sUF–CMA sense if for all attackers $\mathcal {A}$ playing Game 2, running in time t, and issuing $q_{{\mathsf{{Sc}}}}$ queries to the signcryption oracle, $\mathsf{{Adv}}_{\mathcal {A}, \mathcal{S}\mathcal{C}}^{\mathsf{{suf}}}(k)\leqslant \varepsilon .$

Confidentiality and unforgeability are natural security goals for signcryption schemes. The soundness and unforgeability of non-repudiation evidence attributes are specific to SCNINR schemes.

Definition 4

(Soundness of non-repudiation) A SCNINR is said to achieve $(t, \varepsilon )$-computational soundness of non-repudiation if for all attackers $\mathcal {A}$ playing Game 3 and running in time t, ${\mathsf{{Adv}}_{\mathcal {A}, \mathcal{S}\mathcal{C}}^{\mathsf{{snr}}}(k)\leqslant \varepsilon .}$

Definition 5

(Unforgeability of non-repudiation evidence) A SCNINR is said to achieve $(t, q_{{\mathsf{{Sc}}}}, q_{\mathsf{{Usc}}}, q_{{\mathsf{{N}}}}, \varepsilon )$ unforgeability of non-repudiation evidence if for all adversaries $\mathcal {A}$ playing Game 4, running in time t, and issuing respectively $q_{{\mathsf{{Sc}}}}$, $q_{\mathsf{{Usc}}}$, and $q_{{\mathsf{{N}}}}$ queries to the signcryption, unsigncryption, and non-repudiation evidence generation oracles, ${\mathsf{{Adv}}_{\mathcal {A}, \mathcal{S}\mathcal{C}}^{\mathsf{{unr}}}(k)\leqslant \varepsilon }$.

3 The New Construction

We consider the following variant of Chevallier–Mâmes’ (CM) signature scheme [12]; $\mathsf{{H}}_1:\{0, 1\}^*\rightarrow \mathcal {G}$, $\mathsf{{H}}_2:\{0, 1\}^*\rightarrow \textbf{K}$, and $\mathsf{{H}}_3:\{0, 1\}^* \rightarrow [p-1]$ are hash functions, $\mathsf{{aux}}$ denotes some auxiliary information.  

As for CM, in the RO model, the signature generation can be efficiently simulated, and the scheme can be shown to be unforgeable under $\mathsf{{cDH}}$ assumption. An interesting property of this scheme is that when it comes to extend it to a SCNINR, in a simulation of a signcrypted ciphertext generation, we can generate $X_1, X_2\,{\leftarrow }_{\text {\tiny R}}\,\mathcal {G}$ such that for all $(B, Z_1, Z_2)\in \mathcal {G}^3$, using the trapdoor test technique [11], we can efficiently decide whether $\mathsf{{2DH}}(X_1, X_2, B)=(Z_1, Z_2)$ or not. Then, if $(B_1, B_2)\in \mathcal {G}^2$ is a receiver public key, and a twin Diffie–Hellman key exchange [11] is performed using $(X_1, X_2)$ and $(B_1, B_2)$, we can use a trapdoor test at both the sender and the receiver. Then, as for the signature scheme’s unforgeability, we can show the signcryption scheme to be tightly insider secure.

For the consistency of $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$, one can observe that, as $\sigma =x_1 + h\cdot sk_S$, $G^{\sigma }pk_S^{-h}$ yields $X_1$; similarly $R^{\sigma }W^{-h}$ yields V. Then, if $C\,{\leftarrow }_{\text {\tiny R}}\,{\mathsf{{Sc}}}(sk_S, pk_R, m)$ the same $Z_i$’s are computed in the signcryption and unsigncryption algorithms. And, the same values of $\tau _1$ and $\tau _2$ are derived both in ${\mathsf{{Sc}}}(sk_S, pk_R, m)$ and $\mathsf{{Usc}}(sk_R, pk_S, C)$. The remaining part in the definition of ${\mathsf{{Sc}}}$ (resp. $\mathsf{{Usc}}$) is essentially a proof (resp. verification) of equality of discrete logarithms (${\mathsf{{edl}}}$) modified to include $m, \tau _1$ and c. Doing so, for all $dp\in \{{\mathsf{{Setup}}}(k)\}$, all $m\in \mathcal {M}$, all $(sk_S, pk_S)\in \{{\mathsf{{Gen}}}_S(dp)\}$, and all $(sk_R, pk_R)\in \{{\mathsf{{Gen}}}_R(dp)\}$, $m = \mathsf{{Usc}}(sk_R, pk_S, {\mathsf{{Sc}}}(sk_S, pk_R, m))$. Moreover, if $nr\leftarrow {\mathsf{{N}}}(sk_R, pk_S, {\mathsf{{Sc}}}(sk_S, pk_R, m))$ then $1=d\leftarrow {\mathsf{{PV}}}(C, m, nr, pk_S, pk_R)$.

4 Security of the $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ Scheme

We have the following results; detailed proofs are given in [21].

Theorem 1

We assume the RO model. If $q_{X}$, with $X\in \{\mathsf{{H}}_2, \mathsf{{Usc}}, {\mathsf{{N}}}\}$, is an upper bound on the number of times $\mathcal {A}$ issues the $\mathcal {O}_{X}$ oracle in Game 1, the $\mathsf{{cDH}}$ problem is $(t(k), \varepsilon _{\mathsf{{cDH}}}(k))$-hard in $\mathcal {G}$, and the encryption scheme $\mathcal {E}$ is $(t(k), \varepsilon _{\mathsf{{ss}}}(k))$-semantically secure, then $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ is $(t(k), q_{\mathsf{{Usc}}}, q_{{\mathsf{{N}}}}, \varepsilon (k))$-secure in the SKI–MU insider confidentiality in the FSO/FUO–IND–CCA2 sense, where

$$\begin{aligned} \varepsilon (k)\leqslant \varepsilon _{\mathsf{{cDH}}}(k) + \varepsilon _{\mathsf{{ss}}}(k)+ 4(q_{\mathsf{{H}}_2}+ 2 q_{\mathsf{{Usc}}} +2q_{{\mathsf{{N}}}}+1)/p + 2q_{\mathsf{{H}}_3}/|\textbf{K}|. \end{aligned}$$

(1)

Theorem 2

Let $q_{X}$, where $X\in \{\mathsf{{H}}_1, \mathsf{{H}}_2, \mathsf{{H}}_3, {\mathsf{{Sc}}}\}$, be an upper bound on the number of times $\mathcal {A}$ issues the $\mathcal {O}_{X}$ oracle in Game 2. Under the RO model, if the $\mathsf{{cDH}}$ problem is $(t(k), \varepsilon _{\mathsf{{cDH}}}(k))$-hard in $\mathcal {G}$, then $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ is $(t(k), q_{{\mathsf{{Sc}}}}(k), \varepsilon (k))$-MU insider unforgeable in the FSO/FUO–sUF–CMA sense, where $\varepsilon \leqslant \varepsilon _ {\mathsf{{cDH}}} + ((q_{{\mathsf{{Sc}}}}+q_{\mathsf{{H}}_3})^2 + q_{{\mathsf{{Sc}}}}^2)/2p + (q_{\mathsf{{H}}_3} + 2q_{\mathsf{{H}}_2}+1)/p.$

Theorem 3

Under the RO model, the $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ scheme achieves $(t, \varepsilon )$-computational soundness of non-repudiation, where $\varepsilon \leqslant q_{\mathsf{{H}}_3}^2/2p$ wherein $q_{\mathsf{{H}}_3}$, is an upper bound on the number of times $\mathcal {A}$ issues queries to the $\mathcal {O}_{\mathsf{{H}}_3}$ oracle.

Theorem 4

Under the RO model, if the $\mathsf{{cDH}}$ problem is $(t(k), \varepsilon _{\mathsf{{cDH}}}(k))$ hard, then ${\mathcal{S}\mathcal{C}}_{{\mathsf{{edl}}}}$ achieves $(t, q_{{\mathsf{{Sc}}}}, q_{\mathsf{{Usc}}}, q_{{\mathsf{{N}}}}, \varepsilon )$ unforgeability of non-repudiation evidence wherein $\varepsilon \leqslant \varepsilon _{\mathsf{{cDH}}} + 1/|\textbf{K}| + 3/(2p).$

4.1 On the Concrete Choice of the Set of Domain Parameters

A concrete instance of a cryptographic problem is said to have k-bits of security if any adversary $\mathcal {A}$ running in time t and trying to solve the problem succeeds with probability $\varepsilon \leqslant t/2^k$. A cryptographic scheme is said to have k-bits of security with respect to some security attribute, if any attacker playing the security game that defines the attribute and running in time t, succeeds with probability $\varepsilon \leqslant t/2^k$.

In $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$, if the underlying group $\mathcal {G}$ and the encryption scheme $\mathcal {E}$ are chosen such that the $\mathsf{{cDH}}$ problem in $\mathcal {G}$ has $(k+1)$-bits of security and $\mathcal {E}$ has $(k+3)$-bits of security then, from (1), it follows that $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ is $(t, q_{{\mathsf{{Sc}}}}, q_{\mathsf{{Usc}}}, q_{{\mathsf{{N}}}}, \varepsilon )$-secure in the SKI–MU insider confidentiality in the FSO/FUO–IND–CCA2 sense, where $\varepsilon \leqslant t/2^{k+1} + t/2^{k+3}+ 4(q_{\mathsf{{H}}_2}+ 2 q_{\mathsf{{Usc}}} +2q_{{\mathsf{{N}}}}+1)/p+2t/|\textbf{K}|.$ As an $\mathcal {O}(\sqrt{p})$ algorithm is known for the discrete logarithm problem, ${\alpha \sqrt{p}\geqslant 2^{k+1}}$ for some “moderate” constant $\alpha$. As $q_{\mathsf{{H}}_2}+ 2 q_{\mathsf{{Usc}}} +2q_{{\mathsf{{N}}}}+1\leqslant 2t$ and $|\textbf{K}| \geqslant 2^{k+3}$, we obtain ${\varepsilon \leqslant t/2^k}.$ Hence, $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ has k-bits of security in the SKI–MU insider confidentiality in the FSO/FUO–IND–CCA2 sense. A similar analysis shows that under the same assumptions, $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ has k-bits of security with regard to (i) (ii) the MU insider strong unforgeability in the FSO/FUO–sUF–CMA sense, (iii) the soundness of non-repudiation, and (vi) the unforgeability of non-repudiation evidence.

5 Comparison with Other Schemes

The design of $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ integrates the randomness reuse idea suggested in [2, 20]. A $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ sender (resp. receiver) key pair generation requires one (resp. two) exponentiations. An execution of the ${\mathsf{{Sc}}}$ algorithm requires $\mathsf{{Exp}}(\mathcal {G}, 8)$. Four of the 8 exponentiations can be performed offline, before the receiver public key and the plain text are provided. If the receiver public key is provided before the plain text (this may occur in email systems where the recipient is often typed before email text) all the 8 exponentiations can be performed before the plain text is provided The $\mathsf{{Usc}}$ and ${\mathsf{{N}}}$ algorithms require $\mathsf{{Exp}}(\mathcal {G}, 4)$ (two pairs of exponentiations with the same exponent) and two multi-exponentiations. The public verification algorithm requires two multi-exponentiations. If the encryption scheme $\mathcal {E}$ is such that a clear text and a corresponding ciphertext have the same length, the communication overhead of $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$, compared to the CM signature scheme is one group element. Notice that we neglected the group membership tests, as they have a negligible cost in $\mathbb {Z}^*_q$ and elliptic curve groups.

In [19], Malone–Lee (ML) proposes a very efficient design with NINR. Unfortunately, the design, which is analyzed in the RO model under de $\mathsf{{cDH}}$ assumption, does not achieve insider security. Also the reduction uses the Forking Lemma [6, 22]. Assuming $q_{\mathsf{{H}}}=2^{32}$, for a security target of 128-bits, the underlying group $\mathcal {G}'$ must be chosen to offer 160-bits of security. In the case $\mathcal {G}'$ is a (sub)group of the rational points of an elliptic curve $\mathcal {G}'=E(\mathbb {F}_{q'})$, $q'$ has to be chosen such that $|q'|\approx 320$. An execution of the ML ${\mathsf{{Sc}}}$ or $\mathsf{{Usc}}$ algorithm requires two exponentiations. As a modular multiplication (performed with the Karatsuba–Ofman algorithm) in $\mathbb {F}_{q'}$ has complexity $\approx |q'|^{1.585}$. Given the tightness of our reduction, in ECC, we need $|q|=256$ to have 128 bits of security. As $\mathsf{{Mult}}(\mathbb {F}_{q'})\approx 1.42\cdot \mathsf{{Mult}}(\mathbb {F}_q)$, assuming that a group operation in $\mathcal {G}'$ requires $14\cdot \mathsf{{Mult}}(\mathbb {F}_{q'})$ (see¹ [16, p. 96]), $\mathsf{{Exp}}(\mathcal {G}')\approx 6720\cdot \mathsf{{Mult}}(\mathbb {F}_{q'})\approx 9570\cdot \mathsf{{Mult}}(\mathbb {F}_q)~\approx 1.78\cdot \mathsf{{Exp}}(\mathcal {G})$. The ML design is about (a) 2.25 times faster for signcryption, and (b) 1.25 times faster for unsigncryption than ours.

Bjørstad and Dent’s (BD) design [8] tightly achieves, in the RO model, insider unforgeability under the cDH assumption and outsider confidentiality under the gap DH assumption. The scheme does not achieve insider confidentiality. The ${\mathsf{{Sc}}}$ algorithm requires $\mathsf{{Exp}}(\mathcal {G}, 3)$ operations, the $\mathsf{{Usc}}$ algorithm requires two multi-exponentiations. The BD construction is about 2.5 times faster than $\mathcal{S}\mathcal{C}_{\mathsf{{edl}}}$ for signcrypted ciphertext generation and about 3 times faster for unsigncryption.

Some of the designs we consider hereunder assume the existence of groups $\mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T$ together with a bilinear pairing $e:\mathbb {G}_1\times \mathbb {G}_2\rightarrow \mathbb {G}_T$. Recall that for a choice of the groups $\mathcal {G}, \mathbb {G}_1, \mathbb {G}_2,$ and $\mathbb {G}_T$ (where $\mathcal {G}$ is a classical ECC group), with a target of 128-bits of security, the cost of a pairing evaluation is about $\approx \mathsf{{Exp}}(\mathcal {G}, 8)$, $\mathsf{{Exp}}(\mathbb {G}_1)\approx \mathsf{{Exp}}(\mathcal {G}, 3)$, and $\mathsf{{Exp}}(\mathbb {G}_2)\approx \mathsf{{Exp}}(\mathcal {G}, 6)$ [7, p. 126].

Arriaga et al.’s generic construction with NINR [2] is insider secure in the standard model. They propose an instantiation of their design which assumes the Decisional Bilinear and the q-Strong DH assumptions. Unfortunately, the unforgeability is achieved in the registered key model [20], wherein an attacker needs to register to the challenger the keys pairs it uses in its attack. The design assumes the existence of groups $\mathbb {G}, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T$ such that (i) $\mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T$ are of order q, (ii) there is a bilinear pairing $e:\mathbb {G}_1\times \mathbb {G}_2\rightarrow \mathbb {G}_T$ and (iii) a one to one and efficiently invertible mapping from $\mathbb {G}$ to $\mathbb {Z}_q$.

An evaluation of the ${\mathsf{{Sc}}}$ algorithm requires $\mathsf{{Exp}}(\mathbb {G}, 2)+\mathsf{{Exp}}(\mathbb {G}_1)$ and one multi-exponentiation in $\mathbb {G}$. The $\mathsf{{Usc}}$ algorithm requires two multi-exponentiations, one in $\mathbb {G}$ and one in $\mathbb {G}_2$, and a pairing evaluation. For a target of 128 bits of security, we expect $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ to be 1.5 times faster for signcryption and 2.8 times faster for unsigncryption.

Matsuda et al. [20]’s two generic constructions with NINR are insider secure in the FSO/FUO model. The security reduction is provided in the RO model. The most efficient among the instanciations that achieve insider security in the FSO/FUO model uses as base schemes, the DHIES encryption scheme [1] and the BLS signature scheme [9]. The construction assumes the existence of groups $\mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T$ together with a bilinear pairing $e:\mathbb {G}_1\times \mathbb {G}_2\rightarrow \mathbb {G}_T$. A ${\mathsf{{Sc}}}$ operation requires $\mathsf{{Exp}}(\mathbb {G}_1, 3)$, an $\mathsf{{Usc}}$ operation requires $\mathsf{{Exp}}(\mathbb {G}_2)$ and two pairing evaluations. Compared to $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$, for a target of 128 bits of security (given that $\mathsf{{Exp}}(\mathbb {G}_1)\approx \mathsf{{Exp}}(\mathcal {G}, 3)$, $\mathsf{{Exp}}(\mathbb {G}_2)\approx \mathsf{{Exp}}(\mathcal {G}, 6)$ and the cost of a pairing evaluation $\approx \mathsf{{Exp}}(\mathcal {G}, 8)$) we expect our design to be 1.12 times faster for signcryption, and about 3.6 times faster for unsigncryption.

For a comparison with Chiba et al.’s generic construction with NINR [13], we consider the most efficient among the instantiations they propose. It achieves insider security in the FSO/FUO model, under the Decisional Bilinear and the q-strong DH assumptions. Although the insider security is shown in the standard model, the unforgeability is achieved in the registered key model. Besides, the scheme assumes the existence of a pairing $e:\mathbb {G}_1\times \mathbb {G}_2\rightarrow \mathbb {G}_T$, with $\mathbb {G}_1=\mathbb {G}_2$. The ${\mathsf{{Sc}}}$ algorithm requires $\mathsf{{Exp}}(\mathbb {G}_1, 3)$ together with a multi-exponentiation. The $\mathsf{{Usc}}$ operation requires one exponentiation, one multi-exponentiation, and one pairing evaluation. We expect $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ to be about 1.5 times faster for signcryption, and about 2.3 times faster for unsigncryption.

Fan et al.’s design [14] assumes the existence of a bilinear map $e:\mathbb {G}\times \mathbb {G}\rightarrow \mathbb {G}_T$, where $\mathbb {G}$ and $\mathbb {G}_T$ are multiplicative cyclic groups. The ${\mathsf{{Sc}}}$ algorithm requires one pairing, $\mathsf{{Exp}}(\mathbb {G}, 4)+\mathsf{{Exp}}(\mathbb {G}_T)$, and $(n+1)/2$ group operations in $\mathbb {G}$, where n is the bit-length output of some collision resistant hash function $\mathsf{{H}}:\mathbb {G}\rightarrow \{0, 1\}^n$ used in the design. The unsigncryption algorithm requires 3 pairings, $\mathsf{{Exp}}(\mathbb {G}, 2)$, and $(n/2+1)$ group operations in $\mathbb {G}$. A signcrypted ciphertext is an element of $\mathbb {G}_T\times \mathbb {G}^3$. For a choice of the groups $\mathcal {G}$, $\mathbb {G}$, and $\mathbb {G}_T$, with target 128-bits of security, we expect our design to be about (a) (b) 2.5 times faster for signcryption, and (c) 7.5 times faster for unsigncryption than Fan et al.’s construction, in addition to having shorter signcrypted ciphertexts.

In the scheme from [23], defined over the (RSA based) group of signed quadratic residues $\mathbb {J}_N^+$, the ${\mathsf{{Sc}}}$ algorithm requires $\mathsf{{Exp}}(\mathbb {J}^+_N, 6)$ and the $\mathsf{{Usc}}$ algorithm requires $\mathsf{{Exp}}(\mathbb {Z}_N, 3)$ (we ignore the exponentiation with the RSA public exponent, which is often small and sparse). Unfortunately, the security reduction uses the Forking Lemma, which implies a $1/q_{\mathsf{{H}}}$ security degradation, where $q_{\mathsf{{H}}}$ is the number of digest queries the attacker issues. For $q_{\mathsf{{H}}}=2^{32}$, if the target security is 128-bits, the RSA modulus needs to have a bitlength $|N|\approx 7864$ [18]². Then, considering a square-and-multiply based exponentiation, $\mathsf{{Exp}}(\mathbb {J}^+_N)\approx 11796\cdot \mathsf{{Mult}}(\mathbb {Z}_N)$, where $\mathsf{{Mult}}(\mathbb {Z}_N)$ denotes the cost of a multiplication in $\mathbb {Z}_N$. In contrast $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ can be instantiated over an elliptic curve (sub)group $\mathcal {G}=E(\mathbb {F}_q)$ such that $|q|\approx 256$ and $\mathcal {G}$ has 128-bits of security. Assuming that a group operation in $\mathcal {G}$ requires $14\cdot \mathsf{{Mult}}(\mathbb {F}_q)$ [16, p. 96], $\mathsf{{Exp}}(\mathcal {G})\approx 5376\cdot \mathsf{{Mult}}(\mathbb {F}_q)$. As $\mathsf{{Mult}}(\mathbb {Z}_N)> 30\cdot \mathsf{{Mult}}(\mathbb {F}_q)$, for a 128-bits security target, we expect $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ over $\mathcal {G}$ to be at least 13 times faster (for key generation, signcryption, unsigncryption, etc.) than the design from [23].

Compared to the ML and BD schemes, which do not require any specificity of the underlying group and do not achieve insider security, $\mathcal{S}\mathcal{C}_{\mathsf{{edl}}}$ offers a stronger security, even if it is less efficient. And, compared to the schemes from [2, 13, 14, 20, 23], $\mathcal{S}\mathcal{C}_{{\mathsf{{edl}}}}$ offers a tight security reduction, a better efficiency and a comparable or a superior security. We summarize in Table 1 some elements of comparisons. The column Assumptions indicates the computational assumptions used in the security reductions; FL and IS stand respectively for Forking Lemma and Insider Security (in the FSO/FUO model). The letters ‘y’ and ‘n’ stand for “yes” and “no”, respectively; ‘p’ stands for “partial” (BD achieves insider unforgeability, but outsider confidentiality). In the column Computations $[a, b, c] [a', b', c']$ means that a ${\mathsf{{Sc}}}$ (resp. $\mathsf{{Usc}}$) operation requires a (resp. $a'$) exponentiations, b (resp. $b'$) multi-exponentiations, and c (resp. $c'$) pairing evaluations. We recall that the number of exponentiations has to be considered in conjunction with the underlying mathematical structure. For instance, as previously said, if a scheme requires a bilinear pairing $e:\mathbb {G}_1\times \mathbb {G}_2\rightarrow \mathbb {G}_T$, for a target of 128 bits of security, it holds $\mathsf{{Exp}}(\mathbb {G}_1)\approx \mathsf{{Exp}}(\mathcal {G}, 3)$ and $\mathsf{{Exp}}(\mathbb {G}_2)\approx \mathsf{{Exp}}(\mathcal {G}, 6)$. The column Overhead indicates the signcrypted ciphertext overhead compared to the cleartext.

Table 1 Comparison of the proposed signcryption schemes with some SCNINR schemes from the litterature