# Multidivisible Online/Offline Cryptography and Its Application to Signcryptions

Authors: Dan Yamamoto; Wakaha Ogata
Journal: Security and Communication Networks
 (2019)

---

## Abstract

We introduce a general concept ofmultidivisible online/offline (MDO) cryptography, which covers the previous works including online/offline cryptographic schemes, divisible online/offline signatures, incrementally executable signcryptions, and multidivisible online/offline encryptions. We then present the notion of multidivisible online/offline signcryptions (MDOSCs) as novel application of MDO cryptography. We define several security notions for MDOSCs and show implications and separations between these security notions. We also present a generic construction of MDOSC that achieves the strongest security notions with regard to confidentiality and unforgeability. Using MDOSC schemes, the computationally restricted and/or bandwidth-restricted devices can transmit messages in both confidential and authenticated way with low computational overhead and/or low-bandwidth network.


---

## Body

## 1. Introduction

In the emerging network environment, e.g., Internet of Things (IoT), more and more computationally restricted devices as well as bandwidth-restricted devices are connected to each other at any time in any place. Securing their communication is urgently required to make these environments sustainable and scalable. We can use cryptographic schemes as building blocks to achieve security for them, only if it is taken into account that the devices here have restricted resources.Online/offline cryptography, a fundamental concept for many cryptographic systems (e.g., signatures [1–4], encryptions [5–8], signcryptions [9–13], and so forth), is a key to reduce computational costs of the devices sending their messages in confidential and/or authenticated way.The history of online/offline cryptography began with online/offline signatures proposed by Even et al. [2, 3]. The signing procedure of online/offline signature scheme is split into the offline phase and the online phase. The signer can perform all the computationally expensive operations in the offline phase, i.e., in any idle time before the sender decides the message to be signed. Then, in the online phase, i.e., after the message is determined, only lightweight operations are required to sign the message so that even low-power devices can handle the signing process.As an extension of online/offline signature scheme in the context of signcryption, the notion of incrementally executable signcryptions (IESCs) was proposed in [12]. Here, a signcryption process is split into three subprocesses, where the sender can activate each subprocess incrementally by its given sequential input: the sender’s own key pair, a recipient’s public key, and a plaintext message to be sent to the recipient. We can utilize significant intervals between these three subprocesses to perform as much precomputation as possible.To save the transmission bandwidth as well as computational cost, Gao et al. [4] proposed the notion of divisible online/offline signatures (DOSs). Using DOS, intermediate outputs can be securely sent to the receiver in the offline phase so that the senders can save not only computational resources but also transmission bandwidths in the online phase.Applying the above attractive features of DOS as well as IESC to public-key encryption schemes, the notion of multidivisible online/offline encryptions (MDOEs) was proposed in [14]. In MDOEs, encryption process can be executed in at most three steps and at most three partial ciphertexts can be transmitted one-by-one.Our contributions: in this paper, we propose a general concept of multidivisible online/offline cryptography (MDO cryptography, for short), which covers the online/offline cryptography, divisible online/offline signatures, incrementally executable signcryptions, and multidivisible online/offline encryptions.In general, MDO cryptographic schemes have the following features:Incremental processing: a sender’s process can be divided into two or more subprocessesIncremental sending: outputs of intermediate subprocesses can be sent prior to all the subsequent subprocessesThese features enable us to save both computational overhead and transmission bandwidth, on which we can construct secure communication platform for IoT-like environment.As instances taking full advantage of these two features of MDO cryptography, we introduce notions of multidivisible online/offline signcryptions (MDOSCs) and divisible online/offline tag-based KEMs.We define parameterized security notions of MDOSCs, denoted ask,n,q‐dM‐IND‐iCCA for confidentiality and k,n‐dM‐UF‐iCMA for unforgeability, with regard to three parameters: the level of divisibility k, the number of users n, and the number of queries per user q. Then, we analyze all the relationships, i.e., the implications and separations, among these security notions.We also present a generic construction of MDOSC that achieves the strongest security notions of both confidentiality and unforgeability.Expected application scenario: Figure 1 shows a usage example of our MDOSCs, where a signcryption algorithm is split into three subalgorithms, i.e., sc1, sc2, and sc3, each of which can be processed incrementally and can send outputs to recipient incrementally. The sender in our example system consists of the following three components: a computationally powerful cloud with sc1, an energy-restricted mobile device with sc2, and the most computationally restricted as well as bandwidth-restricted IoT device such as a sensor node with sc3. Both the sender and the receiver in our system can access a shared storage. We assume the receiver has enough computational resource to decrypt signcrypted messages received from the sender. Firstly, the sender uses cloud computing to execute the most computationally expensive algorithm sc1 with the sender’s own key pair skS,pkS to generate partial ciphertext Σ1, store it into the shared storage, and also store state information φ1 to the storage of the mobile device. These procedures can be repeatedly executed depending on the storage capacity of the mobile device and the costs for using cloud computing as well as shared storage. Next, when the sender recognizes the target recipient to whom she might send some messages and obtains the receiver’s public key pkR, the sender’s mobile device executes less-expensive algorithm sc2 with φ1 and pkR to generate partial ciphertext Σ2, transmit it to the receiver, and store state information φ2 to the storage of the IoT device. These procedures can also be repeatedly executed depending on the storage capacities of the IoT device and the receiver. After that, when the IoT device is ready to send a message m (e.g., typically very short numeric value sensed by sensor), it executes the least expensive algorithm sc3 with φ2 and m to generate partial ciphertext Σ3, transmit it to the receiver. Note that Σ3 is reasonably short since the cryptographic information for decryption (unsigncryption) has been already transmitted as Σ1 and Σ2. Finally, the receiver securely obtains the message m by unsigncrypting Σ2 and Σ3 with separately downloaded Σ1 from the shared storage as well as pkS and skR using the unsc algorithm.Figure 1
Usage example of our proposed signcryption constructionMDOSC.Organization of this paper: this paper is organized as follows. Section 2 introduces basic notations used in this paper. In Section 3, we introduce the concept of MDO cryptography and discuss its instances including MDO signatures, MDO encryptions, and MDO signcryptions. Section 4 formally defines the notion of MDO signcryptions and its security notions. The relations between the security notions of MDOSC are discussed in Section 5. Section 6 shows a generic construction of MDOSC and comparison with previous signcryption schemes as well as usage example of our MDOSC construction. Concluding remarks are given in Section 7.


## 2. Notations

Forn∈ℕ, n denotes the set 1,2,…,n. We write x⟵y or y⟶x to indicate that x is the output from a function or an algorithm y, or the assignment of the value y to x. x⟵$X denotes the operation of selecting a random element x from a set X. We write A.x to indicate explicitly that the algorithm x belongs to the scheme A. We write z⟵Ax,y,…;oracle1,oracle2,… to indicate the operation of a turing machine A with inputs x,y,… and access to oracles oracle1,oracle2,…, and letting z be the output. Unless otherwise indicated, algorithms are randomized, i.e., it takes a source of randomness to make random choices during execution. In all the experiments (games), every number, set, and bit string is implicitly initialized by 0, empty set ∅, and empty string ε, respectively. We write PrGXYA=b to indicate the probability of the event that adversary A outputs b in attack game GXY.


## 3. Multidivisible Online/Offline Cryptography

In this section, we propose a concept of (multi)-divisible online/offline (MDO) cryptography as a generalization of online/offline cryptography. This concept can be applied to various cryptographic primitives, such as encryption schemes and signature schemes. MDO cryptographic schemes have the two features: incremental processing and incremental sending.Incremental Processing. In a cryptographic primitive, a list of several inputs x1,x2,…,xk is processed by an algorithm ALG to compute y=ALGx1,x2,…,xk, which is sent via a (insecure) channel.In contrast,ALG in MDO cryptography is split into k≥1 subalgorithms ALG1,…,ALGk, and(1)φ1,y1⟵ALG1x1φ2,y2⟵ALG2x2,φ1⋮yk⟵ALGkxk,φk‐1,are computed instead of y=ALGx1,x2,…,xk. y=y1,…,yk is treated as the output of ALG. φii=1,…,k‐1, state information, is assumed to be secretly stored and will be consumed only once by subalgorithm ALGi+1.For a more general model,k inputs are grouped into k′≤k input groups, x1′,…,xk′′. In this case, ALG is split into k′ subalgorithms. By this definition, our concept enables us to model wide variety of systems in a unified way. For example, an online/offline scheme is a special case where inputs are divided into two groups, a message and the others. Moreover, an ordinary cryptographic scheme can be treated as a special case where all inputs are grouped into only one input group, i.e., k′=1.Grouping of inputs should depend on the timing when each input is given to the sender.Incremental Sending. To save transmission bandwidth, it is desired to send each partial output yi one-by-one. However, it is known that a scheme could be insecure if each yi is allowed to be sent one-by-one, even when the scheme is secure if all the yi’s are sent at the same time [14]. Therefore, we need extended security notions that capture new types of adversary exploiting partial output yi’s for attacks.In the following, we show several MDO cryptographic primitives including: signatures, public-key encryptions, key encapsulation mechanisms (KEMs), tag-based key encapsulation mechanisms (TBKEMs), and signcryptions.


### 3.1. Signatures

We recall the notion ofdivisible online/offline signatures (DOSs) [4]. A divisible online/offline signature scheme DOS consists of the following algorithms:init⟶λ (the public parameter generation algorithm): it outputs public parameters λ to be used by all partiesgenλ⟶sk,pk (the key generation algorithm): it generates a key pair sk,pk for signing and verificationsign1λ,sk⟶φ,σ1 (the offline signing algorithm): given public parameters λ and a secret key sk, it outputs state information φ and an offline signature token σ1. We require that σ1≠εsign2φ,m⟶σ2 (the online signing algorithm): given state information φ and a message m, it outputs online signature token σ2verλ,pk,m,σ1,σ2⟶v (the deterministic verification algorithm): given a public key pk, a message m, and signature tokens C1,C2, it outputs 1 (accept) or 0 (reject)We require the correctness for DOS, namely, for anyλ⟵DOS.init, any sk,pk⟵DOS.genλ, any m∈0,1∗, any φ,σ1⟵DOS.sign1λ,sk, and any σ2⟵DOS.sign2φ,m, we have DOS.verλ,pk,m,σ1,σ2=1.As an attempt, we might try to extend DOS to MDOS,multidivisible online/offline signatures, based on our framework. More specifically, we could further split sign1λ,sk into sign1‐λ and sign1+sk. While this splitting is possible theoretically, it does not provide significant benefits to senders in practical. This is because public parameters λ and secret key sk are obtained by senders almost at the same time in most applications so that senders cannot take advantage of the precomputation of sign1−. We therefore do not try to formalize the syntax of multidivisible online/offline signatures in this paper. Nevertheless, we can provide the security notions for it based on multidivisible online/offline style to capture the unforgeability notion for ordinary signatures [15] as well as the notion for divisible online/offline signatures [4] in a unified way.We define the security notion of (strong) unforgeability against adaptive chosen message attacks (k,n‐UF‐CMA and k,n‐sUF‐CMA) as follows.Definition 1.
Letk∈1,2 and n∈ℕ. Let X∈UF,sUF. Let DOS be a DOS scheme, and let A be an adversary. The k,n‐X‐CMA-advantage of A against DOS is defined as(2)AdvDOSk,n‐X‐CMAA=PrGDOSk,n‐X‐CMAA=1,where the attack game GDOSk,n‐X‐CMA is defined in Figure 2.
We say thatDOS is t,q,ϵ‐k,n‐X‐CMA‐secure if AdvDOSk,n‐X‐CMAA≤ϵ holds for any adversary A that runs in time t and makes at most q queries to oracle sign.
Note that the notion of1,1‐UF‐CMA is equivalent to the standard unforgeability notion for ordinary signatures [15], whereas 2,1‐UF‐CMA is identical to the notion for divisible online/offline signatures [4].
We also define the notion ofsmooth divisible online/offline signature scheme in a similar fashion with a smooth KEM [16].Figure 2
Attack game definingk,n‐X‐CMA security. Boxed parts are evaluated only in sUF game.Definition 2.
SmoothnessSmthDOS for DOS is defined as follows:(3)SmthDOS=Emaxσ1∈0,1∗Prφ,σ1′⟵DOS.sign1λ,skσ1′=σ1,where the expected value is taken over λ⟵DOS.init;sk,pk⟵DOS.genλ. We say DOS is ϵ-smooth if SmthDOS≤ϵ holds.


### 3.2. Public-Key Encryptions and KEMs

The notion of multidivisible online/offline encryptions (MDOEs) was proposed in [14]. It captures both the desirable features of identity-based online/offline encryptions [5–8] and divisible online/offline signatures [4], that is, a part of encryption can be executed even when the public key to the receiver is unknown and partial ciphertexts can be sent to the receiver even when the sender’s inputs (e.g., a public key or a plaintext) are not fully determined. Concrete constructions are also proposed in [14], which allow the computationally restricted and/or bandwidth-restricted devices to transmit ciphertexts with low computational overhead and/or low-bandwidth network.Their concrete constructions are built onpartitioned KEM, which can be regarded as an instance of divisible online/offline KEM. As with DOS and MDOE, partitioned KEMs have divided encapsulation algorithms, enc1λ and enc2pk, both of which output partial encapsulations C1 and C2.


### 3.3. Tag-Based Key Encapsulation Mechanism

We introduce the notion ofdivisible online/offline tag-based KEM (DOTK), which is a tag-based analogue of divisible online/offline KEM, i.e., partitioned KEM.A divisible online/offline tag-based key encapsulation mechanismDOTK consists of the following algorithms:init⟶λ (the public parameter generation algorithm): it outputs public parameters λ to be used by all parties. Public parameters λ contains a description of the session key space, DOTK.K.genλ⟶sk,pk (the key generation algorithm): it generates a key pair sk,pk for decapsulation and encapsulation.enc1λ,τ⟶φ,C1 (the first key encapsulation algorithm): given public parameters λ and a tag τ∈0,1∗, it outputs state information φ and a partial encapsulation C1. We require that C1≠ε.enc2φ,pk⟶K,C2 (the second key encapsulation algorithm): given state information φ and a public key pk, it outputs a pair K,C2, where K∈DOTK.K is a generated session key and C2 is a partial encapsulation of K.decλ,sk,τ,C1,C2⟶K (the deterministic decapsulation algorithm): given a secret key sk, a tag τ, and encapsulations C1,C2, it outputs either a session key K or an error symbol ⊥.We require the correctness for DOTK, namely, for anyλ⟵DOTK.init, any sk,pk⟵DOTK.genλ, any τ∈0,1∗, any φ,C1⟵DOTK.enc1λ,τ, and any K,C2⟵DOTK.enc2φ,pk, we have DOTK.decλ,sk,τ,C1,C2=K.We define the security notion of indistinguishability against adaptive tag and adaptive chosen ciphertext attacksk,n,q‐IND‐tag‐CCA.Definition 3.
Letk∈1,2 and n,q∈ℕ. Let DOTK be a DOTK scheme, and let A be an adversary. The k,n,q‐IND‐tag‐CCA-advantage of A against DOTK is defined as(4)AdvDOTKk,n,q‐IND‐tag‐CCAA=2PrGDOTKk,n,q‐IND‐tag‐CCAA=1−1,where the attack game GDOTKk,n,q‐IND‐tag‐CCA is defined in Figure 3.
We say thatDOTK is t,qd,ϵ‐k,n,q‐IND‐tag‐CCA‐secure if AdvDOTKk,n,q‐IND‐tag‐CCAA≤ϵ holds for any adversary A that runs in time t and makes at most qd queries to the oracle dec.Figure 3
Attack game definingk,n,q‐IND‐tag‐CCA security.Construction.
Here, we give a concrete example of1,1‐IND‐tag‐CCA‐secure divisible online/offline tag-based KEM scheme with lightweight enc2 algorithm that requires only one regular exponentiation in GT of bilinear groups. The construction of our tag-based KEM is similar to the one of partitioned KEM [14] that is based on the IBE-based KEM from Boyen et al. [17, 18]. The concrete scheme DOTKBMW is described in Figure 4, where G,G^,GT is a bilinear group, i.e., G, G^, and GT are cyclic groups of prime order p, equipped with a bilinear map e:G×G^⟶GT (a bilinear map e:G×G^⟶GT satisfies the following properties: (1) bilinearity: ega,hb=eg,hab for any g∈G, any h∈G^, and any a,b∈ℤ; (2) efficient computability for any input pair; (3) nondegeneracy: eg,h≠1GT for any g∈G/1G and any h∈G^/1G^), H:G⟶ℤp is a target collision resistant hash function, and CH is a secure chameleon hash function. As with the partitioned KEM in [14], our scheme has no second partial ciphertext, i.e., C2=ε, which is desirable when algorithm enc2 is executed in the bandwidth-restricted environment. We can verify that the scheme is 1,1‐IND‐tag‐CCA‐secure if the DBDH (Decisional Bilinear Diffie–Hellman) assumption on G,G^,GT holds. The proof is similar with the original proof in [17].Figure 4
Construction ofDOTKBMW.


### 3.4. Signcryptions

The two features of MDO cryptography, i.e., incremental processing and sending, can show their full advantages when applying to signcryptions, where the sender-side algorithm has multiple input arguments that can be given incrementally in most cases. Therefore, in the rest of this paper, we focus on the notion ofmultidivisible online/offline signcryption (MDOSC).In MDOSC schemes, a signcryption algorithm is split into three subalgorithms, each of which can be processed incrementally, and their output can be transmitted incrementally. A formal definition, security notions, and a generic construction of MDOSC are described in the following sections.


## 3.1. Signatures

We recall the notion ofdivisible online/offline signatures (DOSs) [4]. A divisible online/offline signature scheme DOS consists of the following algorithms:init⟶λ (the public parameter generation algorithm): it outputs public parameters λ to be used by all partiesgenλ⟶sk,pk (the key generation algorithm): it generates a key pair sk,pk for signing and verificationsign1λ,sk⟶φ,σ1 (the offline signing algorithm): given public parameters λ and a secret key sk, it outputs state information φ and an offline signature token σ1. We require that σ1≠εsign2φ,m⟶σ2 (the online signing algorithm): given state information φ and a message m, it outputs online signature token σ2verλ,pk,m,σ1,σ2⟶v (the deterministic verification algorithm): given a public key pk, a message m, and signature tokens C1,C2, it outputs 1 (accept) or 0 (reject)We require the correctness for DOS, namely, for anyλ⟵DOS.init, any sk,pk⟵DOS.genλ, any m∈0,1∗, any φ,σ1⟵DOS.sign1λ,sk, and any σ2⟵DOS.sign2φ,m, we have DOS.verλ,pk,m,σ1,σ2=1.As an attempt, we might try to extend DOS to MDOS,multidivisible online/offline signatures, based on our framework. More specifically, we could further split sign1λ,sk into sign1‐λ and sign1+sk. While this splitting is possible theoretically, it does not provide significant benefits to senders in practical. This is because public parameters λ and secret key sk are obtained by senders almost at the same time in most applications so that senders cannot take advantage of the precomputation of sign1−. We therefore do not try to formalize the syntax of multidivisible online/offline signatures in this paper. Nevertheless, we can provide the security notions for it based on multidivisible online/offline style to capture the unforgeability notion for ordinary signatures [15] as well as the notion for divisible online/offline signatures [4] in a unified way.We define the security notion of (strong) unforgeability against adaptive chosen message attacks (k,n‐UF‐CMA and k,n‐sUF‐CMA) as follows.Definition 1.
Letk∈1,2 and n∈ℕ. Let X∈UF,sUF. Let DOS be a DOS scheme, and let A be an adversary. The k,n‐X‐CMA-advantage of A against DOS is defined as(2)AdvDOSk,n‐X‐CMAA=PrGDOSk,n‐X‐CMAA=1,where the attack game GDOSk,n‐X‐CMA is defined in Figure 2.
We say thatDOS is t,q,ϵ‐k,n‐X‐CMA‐secure if AdvDOSk,n‐X‐CMAA≤ϵ holds for any adversary A that runs in time t and makes at most q queries to oracle sign.
Note that the notion of1,1‐UF‐CMA is equivalent to the standard unforgeability notion for ordinary signatures [15], whereas 2,1‐UF‐CMA is identical to the notion for divisible online/offline signatures [4].
We also define the notion ofsmooth divisible online/offline signature scheme in a similar fashion with a smooth KEM [16].Figure 2
Attack game definingk,n‐X‐CMA security. Boxed parts are evaluated only in sUF game.Definition 2.
SmoothnessSmthDOS for DOS is defined as follows:(3)SmthDOS=Emaxσ1∈0,1∗Prφ,σ1′⟵DOS.sign1λ,skσ1′=σ1,where the expected value is taken over λ⟵DOS.init;sk,pk⟵DOS.genλ. We say DOS is ϵ-smooth if SmthDOS≤ϵ holds.


## 3.2. Public-Key Encryptions and KEMs

The notion of multidivisible online/offline encryptions (MDOEs) was proposed in [14]. It captures both the desirable features of identity-based online/offline encryptions [5–8] and divisible online/offline signatures [4], that is, a part of encryption can be executed even when the public key to the receiver is unknown and partial ciphertexts can be sent to the receiver even when the sender’s inputs (e.g., a public key or a plaintext) are not fully determined. Concrete constructions are also proposed in [14], which allow the computationally restricted and/or bandwidth-restricted devices to transmit ciphertexts with low computational overhead and/or low-bandwidth network.Their concrete constructions are built onpartitioned KEM, which can be regarded as an instance of divisible online/offline KEM. As with DOS and MDOE, partitioned KEMs have divided encapsulation algorithms, enc1λ and enc2pk, both of which output partial encapsulations C1 and C2.


## 3.3. Tag-Based Key Encapsulation Mechanism

We introduce the notion ofdivisible online/offline tag-based KEM (DOTK), which is a tag-based analogue of divisible online/offline KEM, i.e., partitioned KEM.A divisible online/offline tag-based key encapsulation mechanismDOTK consists of the following algorithms:init⟶λ (the public parameter generation algorithm): it outputs public parameters λ to be used by all parties. Public parameters λ contains a description of the session key space, DOTK.K.genλ⟶sk,pk (the key generation algorithm): it generates a key pair sk,pk for decapsulation and encapsulation.enc1λ,τ⟶φ,C1 (the first key encapsulation algorithm): given public parameters λ and a tag τ∈0,1∗, it outputs state information φ and a partial encapsulation C1. We require that C1≠ε.enc2φ,pk⟶K,C2 (the second key encapsulation algorithm): given state information φ and a public key pk, it outputs a pair K,C2, where K∈DOTK.K is a generated session key and C2 is a partial encapsulation of K.decλ,sk,τ,C1,C2⟶K (the deterministic decapsulation algorithm): given a secret key sk, a tag τ, and encapsulations C1,C2, it outputs either a session key K or an error symbol ⊥.We require the correctness for DOTK, namely, for anyλ⟵DOTK.init, any sk,pk⟵DOTK.genλ, any τ∈0,1∗, any φ,C1⟵DOTK.enc1λ,τ, and any K,C2⟵DOTK.enc2φ,pk, we have DOTK.decλ,sk,τ,C1,C2=K.We define the security notion of indistinguishability against adaptive tag and adaptive chosen ciphertext attacksk,n,q‐IND‐tag‐CCA.Definition 3.
Letk∈1,2 and n,q∈ℕ. Let DOTK be a DOTK scheme, and let A be an adversary. The k,n,q‐IND‐tag‐CCA-advantage of A against DOTK is defined as(4)AdvDOTKk,n,q‐IND‐tag‐CCAA=2PrGDOTKk,n,q‐IND‐tag‐CCAA=1−1,where the attack game GDOTKk,n,q‐IND‐tag‐CCA is defined in Figure 3.
We say thatDOTK is t,qd,ϵ‐k,n,q‐IND‐tag‐CCA‐secure if AdvDOTKk,n,q‐IND‐tag‐CCAA≤ϵ holds for any adversary A that runs in time t and makes at most qd queries to the oracle dec.Figure 3
Attack game definingk,n,q‐IND‐tag‐CCA security.Construction.
Here, we give a concrete example of1,1‐IND‐tag‐CCA‐secure divisible online/offline tag-based KEM scheme with lightweight enc2 algorithm that requires only one regular exponentiation in GT of bilinear groups. The construction of our tag-based KEM is similar to the one of partitioned KEM [14] that is based on the IBE-based KEM from Boyen et al. [17, 18]. The concrete scheme DOTKBMW is described in Figure 4, where G,G^,GT is a bilinear group, i.e., G, G^, and GT are cyclic groups of prime order p, equipped with a bilinear map e:G×G^⟶GT (a bilinear map e:G×G^⟶GT satisfies the following properties: (1) bilinearity: ega,hb=eg,hab for any g∈G, any h∈G^, and any a,b∈ℤ; (2) efficient computability for any input pair; (3) nondegeneracy: eg,h≠1GT for any g∈G/1G and any h∈G^/1G^), H:G⟶ℤp is a target collision resistant hash function, and CH is a secure chameleon hash function. As with the partitioned KEM in [14], our scheme has no second partial ciphertext, i.e., C2=ε, which is desirable when algorithm enc2 is executed in the bandwidth-restricted environment. We can verify that the scheme is 1,1‐IND‐tag‐CCA‐secure if the DBDH (Decisional Bilinear Diffie–Hellman) assumption on G,G^,GT holds. The proof is similar with the original proof in [17].Figure 4
Construction ofDOTKBMW.


## 3.4. Signcryptions

The two features of MDO cryptography, i.e., incremental processing and sending, can show their full advantages when applying to signcryptions, where the sender-side algorithm has multiple input arguments that can be given incrementally in most cases. Therefore, in the rest of this paper, we focus on the notion ofmultidivisible online/offline signcryption (MDOSC).In MDOSC schemes, a signcryption algorithm is split into three subalgorithms, each of which can be processed incrementally, and their output can be transmitted incrementally. A formal definition, security notions, and a generic construction of MDOSC are described in the following sections.


## 4. Multidivisible Online/Offline Signcryptions

We first introduce multidivisible online/offline signcryption (MDOSC). Then, we formally define its security models in terms of confidentiality and unforgeability.


### 4.1. Syntax

Definition 4.
A multidivisible online/offline signcryption scheme,MDOSC, consists of the following algorithms:init⟶λ (the public parameter generation algorithm): it outputs public parameters λ to be used by all partiesgenSλ⟶skS,pkS (the sender key generation algorithm): it generates a private/public key pair skS,pkS for a sendergenRλ⟶skR,pkR (the receiver key generation algorithm): it generates a private/public key pair skR,pkR for a receiversc1λ,skS,pkS⟶φ1,Σ1 (the first signcryption algorithm): given public parameter λ and sender’s key pair skS,pkS, it outputs state information φ1 and partial ciphertext Σ1sc2φ1,pkR⟶φ2,Σ2 (the second signcryption algorithm): given state information φ1 and recipient’s public key pkR, it outputs new state information φ2 and partial ciphertext Σ2sc3φ2,m⟶Σ3 (the third signcryption algorithm): given state information φ2 and plaintext m, it outputs partial ciphertext Σ3unscλ,skR,pkR,pkS,Σ1,Σ2,Σ3⟶m (the deterministic unsigncryption algorithm): given public parameters λ, recipient’s key pair skR,pkR, sender’s public key pkS, and partial ciphertexts Σ1, Σ2, and Σ3, it outputs either plaintext m or error symbol ⊥
We require the correctness for MDOSC, namely, for anyλ⟵init, any skS,pkS⟵genSλ, any skR,pkR⟵genRλ, any m, any φ1,Σ1⟵sc1λ,skS,pkS, and any φ2,Σ2⟵sc2φ1,pkR, we have unscλ,skR,pkR,pkS,Σ1,Σ2,sc3φ2,m=m.
We say that a MDOSC scheme is a 2-divisible online/offline signcryption (2-DOSC, for short) scheme ifΣ2 is not null. Similarly, if Σ1 is not null, we call it as 3-DOSC scheme.


### 4.2. Confidentiality

As for confidentiality, we define the indistinguishability against insider-chosen ciphertext attacks (or insider-chosen plaintext attacks) in the dynamic multiuser model, based on the same notion for standard (i.e., nondivisible) signcryption [19]. As with the indistinguishability of MDO encryption [14], we introduce the level of ciphertext divisibility, k, to express the following three distinct situations: (k=1) all the ciphertext Σ1, Σ2, and Σ3 are made public at the same time; (k=2) Σ1 and Σ2 are made public at the same time, then Σ3 is published; (k=3) Σ1, Σ2, and Σ3 are made public one by one. Notice that the case of k=1 is covered by the standard dM‐IND‐iCCA notion for signcryptions [19], whereas the case of k=2,3 corresponds to the incremental sending situation of MDO cryptography. Adversaries in the latter situations have more capabilities; for example, the adversary in the case of k=3 can choose the target recipient after observing Σ1 and can choose challenge messages m0,m1 after knowing Σ2 as well as Σ1. Our definition captures these types of adversaries using three signcryption oracles.Definition 5.
Letk∈1,2,3 and n,q∈ℕ. Let DOSC be a MDOSC scheme, and let A be an adversary. The k,n,q‐dM‐IND‐iCCA-advantage of A against DOSC is defined as(5)AdvDOSCk,n,q‐dM‐IND‐iCCAA=2PrGDOSCk,n,q‐dM‐IND‐iCCAA=1−1,where attack game GDOSCk,n,q‐dM‐IND‐iCCA is defined in Figure 5.
We say thatDOSC is t,qd,ϵ‐k,n,q‐dM‐IND‐iCCA‐secure if AdvDOSCk,n,q‐dM‐IND‐iCCAA≤ϵ holds for any adversary A that runs in time t and makes at most qd queries to the oracle unsc.
In addition, thek,n,q‐dM‐IND‐iCPA-advantage of A against DOSC is defined in a similar fashion with k,n,q‐dM‐IND‐iCCA-advantage, except that the adversary has no access to oracle unsc, i.e., qd=0, in game GDOSCk,n,q‐dM‐IND‐iCPA.Figure 5
Attack game definingk,n,q‐dM‐IND‐iCCA security.


### 4.3. Unforgeability

As for unforgeability, we define the (strong) unforgeability against insider chosen-message attacks in the dynamic multiuser model. Similar to the confidentiality notion, we use the levelk of divisibility to express the three distinct situations. Note that the case of k=1 is equivalent to the standard dM‐sUF‐iCMA for signcryptions [19]. The adversary in the case of k=3 can take more flexible strategy: it can decide the target recipient key pkR after observing Σ1 and can query the signcryption oracle with a message m after knowing Σ2 as well as Σ1.Definition 6.
Letk∈1,2,3 and n,q∈ℕ. Let X∈UF,sUF. Let DOSC be a MDOSC scheme, and let A be an adversary. The k,n‐dM‐X‐iCMA-advantage of A against DOSC is defined as(6)AdvDOSCk,n‐dM‐X‐iCMAA=PrGDOSCk,n‐dM‐X‐iCMAA=1,where the attack game GDOSCk,n‐dM‐X‐iCMA is defined in Figure 6.
We say thatDOSC is t,qs,ϵ‐k,n‐dM‐X‐iCMA‐secure if AdvDOSCk,n‐dM‐X‐iCMAA≤ϵ holds for any adversary A that runs in time t.Figure 6
Attack game definingk,n‐dM‐X‐iCMA security. Boxed parts are evaluated only in sUF game.


## 4.1. Syntax

Definition 4.
A multidivisible online/offline signcryption scheme,MDOSC, consists of the following algorithms:init⟶λ (the public parameter generation algorithm): it outputs public parameters λ to be used by all partiesgenSλ⟶skS,pkS (the sender key generation algorithm): it generates a private/public key pair skS,pkS for a sendergenRλ⟶skR,pkR (the receiver key generation algorithm): it generates a private/public key pair skR,pkR for a receiversc1λ,skS,pkS⟶φ1,Σ1 (the first signcryption algorithm): given public parameter λ and sender’s key pair skS,pkS, it outputs state information φ1 and partial ciphertext Σ1sc2φ1,pkR⟶φ2,Σ2 (the second signcryption algorithm): given state information φ1 and recipient’s public key pkR, it outputs new state information φ2 and partial ciphertext Σ2sc3φ2,m⟶Σ3 (the third signcryption algorithm): given state information φ2 and plaintext m, it outputs partial ciphertext Σ3unscλ,skR,pkR,pkS,Σ1,Σ2,Σ3⟶m (the deterministic unsigncryption algorithm): given public parameters λ, recipient’s key pair skR,pkR, sender’s public key pkS, and partial ciphertexts Σ1, Σ2, and Σ3, it outputs either plaintext m or error symbol ⊥
We require the correctness for MDOSC, namely, for anyλ⟵init, any skS,pkS⟵genSλ, any skR,pkR⟵genRλ, any m, any φ1,Σ1⟵sc1λ,skS,pkS, and any φ2,Σ2⟵sc2φ1,pkR, we have unscλ,skR,pkR,pkS,Σ1,Σ2,sc3φ2,m=m.
We say that a MDOSC scheme is a 2-divisible online/offline signcryption (2-DOSC, for short) scheme ifΣ2 is not null. Similarly, if Σ1 is not null, we call it as 3-DOSC scheme.


## 4.2. Confidentiality

As for confidentiality, we define the indistinguishability against insider-chosen ciphertext attacks (or insider-chosen plaintext attacks) in the dynamic multiuser model, based on the same notion for standard (i.e., nondivisible) signcryption [19]. As with the indistinguishability of MDO encryption [14], we introduce the level of ciphertext divisibility, k, to express the following three distinct situations: (k=1) all the ciphertext Σ1, Σ2, and Σ3 are made public at the same time; (k=2) Σ1 and Σ2 are made public at the same time, then Σ3 is published; (k=3) Σ1, Σ2, and Σ3 are made public one by one. Notice that the case of k=1 is covered by the standard dM‐IND‐iCCA notion for signcryptions [19], whereas the case of k=2,3 corresponds to the incremental sending situation of MDO cryptography. Adversaries in the latter situations have more capabilities; for example, the adversary in the case of k=3 can choose the target recipient after observing Σ1 and can choose challenge messages m0,m1 after knowing Σ2 as well as Σ1. Our definition captures these types of adversaries using three signcryption oracles.Definition 5.
Letk∈1,2,3 and n,q∈ℕ. Let DOSC be a MDOSC scheme, and let A be an adversary. The k,n,q‐dM‐IND‐iCCA-advantage of A against DOSC is defined as(5)AdvDOSCk,n,q‐dM‐IND‐iCCAA=2PrGDOSCk,n,q‐dM‐IND‐iCCAA=1−1,where attack game GDOSCk,n,q‐dM‐IND‐iCCA is defined in Figure 5.
We say thatDOSC is t,qd,ϵ‐k,n,q‐dM‐IND‐iCCA‐secure if AdvDOSCk,n,q‐dM‐IND‐iCCAA≤ϵ holds for any adversary A that runs in time t and makes at most qd queries to the oracle unsc.
In addition, thek,n,q‐dM‐IND‐iCPA-advantage of A against DOSC is defined in a similar fashion with k,n,q‐dM‐IND‐iCCA-advantage, except that the adversary has no access to oracle unsc, i.e., qd=0, in game GDOSCk,n,q‐dM‐IND‐iCPA.Figure 5
Attack game definingk,n,q‐dM‐IND‐iCCA security.


## 4.3. Unforgeability

As for unforgeability, we define the (strong) unforgeability against insider chosen-message attacks in the dynamic multiuser model. Similar to the confidentiality notion, we use the levelk of divisibility to express the three distinct situations. Note that the case of k=1 is equivalent to the standard dM‐sUF‐iCMA for signcryptions [19]. The adversary in the case of k=3 can take more flexible strategy: it can decide the target recipient key pkR after observing Σ1 and can query the signcryption oracle with a message m after knowing Σ2 as well as Σ1.Definition 6.
Letk∈1,2,3 and n,q∈ℕ. Let X∈UF,sUF. Let DOSC be a MDOSC scheme, and let A be an adversary. The k,n‐dM‐X‐iCMA-advantage of A against DOSC is defined as(6)AdvDOSCk,n‐dM‐X‐iCMAA=PrGDOSCk,n‐dM‐X‐iCMAA=1,where the attack game GDOSCk,n‐dM‐X‐iCMA is defined in Figure 6.
We say thatDOSC is t,qs,ϵ‐k,n‐dM‐X‐iCMA‐secure if AdvDOSCk,n‐dM‐X‐iCMAA≤ϵ holds for any adversary A that runs in time t.Figure 6
Attack game definingk,n‐dM‐X‐iCMA security. Boxed parts are evaluated only in sUF game.


## 5. Relations between Security Notions for MDOSCs

In this section, we clarify the relations between the security notions defined in the previous section in terms of confidentiality and unforgeability. The result is summarized in Figure7, where k,n,q denotes the notion of k,n,q‐dM‐IND‐iCCA‐security in the left-hand side, whereas k,n denotes the notion of k,n‐dM‐sUF‐iCMA‐security in the right-hand side. Note that for any k,k′∈1,2,3, n,n′∈ℕ, and q,q′∈ℕ such that k≥k′, n≥n′, and q≥q′, our k,n,q‐dM‐IND‐iCCA trivially implies k′,n′,q′‐dM‐IND‐iCCA and k,n,q‐dM‐IND‐iCPA. Similarly, k,n‐dM‐sUF‐iCMA trivially implies k′,n′‐dM‐sUF‐iCMA and k,n‐dM‐UF‐iCMA.Figure 7
Implications and separations between the security notions for MDOSCs. In the left-hand side, “k,n,q⟶k′,3n′,q′” with overlapped X denotes that k,n,q‐dM‐IND‐iCCA‐security implies k′,n′,q′‐dM‐IND‐iCCA‐security with reduction’s loss X, while the dotted arrow denotes that k,n,q‐dM‐IND‐iCCA‐security does not necessarily imply k′,n′,q′‐dM‐IND‐iCCA‐security. The ones for k,n‐dM‐sUF‐iCMA are similarly represented in the right-hand side.


### 5.1. Confidentiality

The following two theorems say that for anyk∈1,2,3, k,1,1‐dM‐IND‐iCCA‐security implies k,n,q‐dM‐IND‐iCCA‐security with reduction loss polynomial in the number n of receivers as well as the number q of challenge queries.Theorem 1.
(1,2,1,1‐iCCA⟶1,2,n,q‐iCCA). For k∈1,2, assume a k-DOSC scheme DOSC is t′,qd,ϵ‐k,1,1‐dM‐IND‐iCCA‐secure. Then, DOSC is also t,qd,nqϵ‐k,n,q‐dM‐IND‐iCCA‐secure, where t=t′−Onq.Using the hybrid argument in a similar fashion with [20], we can easily obtain the proof of Theorem 1.As for the case ofk=3, the hybrid argument cannot be trivially applied due to the difficulty of the simulation of oracle sc1 in 3,n,q‐dM‐IND‐iCCA, which is called nq times, using oracle sc1∗ in 3,1,1‐dM‐IND‐iCCA, which can be called only once. Responding to the adversary’s query to sc1 with Σ1j, the simulator for 3,n,q‐dM‐IND‐iCCA first chooses i∗,q∗∈n×q and uses its given single public key pk∗ as a key pki∗ of the user i∗. Then, the simulator uses its given oracle access to sc1∗ in 3,1,1‐dM‐IND‐iCCA if Σ1j will be used for the q∗-th query related to the target user i∗, whereas it computes Σ1j by the simulator itself otherwise. Here, the simulator has to guess whether Σ1j will be used for the q∗-th challenge query to i∗ before a subsequent invocation of sc2. To overcome this issue, we use a naive guessing approach and obtain the following reduction:Theorem 2.
(3,1,1‐iCCA⟶3,n,q‐iCCA). Assume a 3-DOSC scheme DOSC is t′,qd,ϵ‐3,1,1‐dM‐IND‐iCCA‐secure. Then, DOSC is also t,qd,n2q2ϵ‐3,n,q‐dM‐IND‐iCCA‐secure, where t=t′−Onq.The proof is given in AppendixB.1.Remark 1.
We can apply the above argument to the multidivisible online/offline encryptions (MDOEs) to get a same polynomial reduction from3,1,1‐CCA to 3,n,q‐CCA for MDOEs. The obtained reduction is significantly tighter than the previous one shown in [14] where only superpolynomial one was provided.
Next, we show that2,1,1‐dM‐IND‐iCCA‐security implies 3,1,1‐dM‐IND‐iCCA‐security as follows:Theorem 3.
(2,1,1‐iCCA⟹3,1,1‐iCCA). Assume a 3-DOSC scheme DOSC is t,qd,ϵ‐2,1,1‐dM‐IND‐iCCA‐secure. Then DOSC is also t,qd,ϵ‐3,1,1‐dM‐IND‐iCCA‐secure.Proof.
In the single-user setting, i.e.,n=1, the adversary has no choice of the recipient i when it invokes oracle sc2j,i. Hence, the successive invocations of sc1skS,pkS and sc2j,i in 3,1,1‐dM‐IND‐iCCA game is essentially equivalent to the invocation of the oracle sc12skS,pkS,i in 2,1,1‐dM‐IND‐iCCA.
Finally, we show the separation between1,⋅,⋅‐dM‐IND‐iCCA and 2,⋅,⋅‐dM‐IND‐iCCA. Specifically, we provide a 1,1,1‐dM‐IND‐iCCA‐secure but not 2,1,1‐dM‐IND‐iCCA‐secure 3-DOSC scheme, 3DOSCR, as an evidence of the separation. Scheme 3DOSCR is described in Figure 8.Figure 8
Constructions of3DOSCR, 3DOSCS1, and 3DOSCS2 used to prove Theorem 4 and Theorem 6. Boxed parts with superscript X are evaluated only in 3DOSCX.Theorem 4.
(1,1,1‐iCCA↛2,1,1‐iCPA). Assume there exists a (divisible) online/offline tag-based KEM DOTK that is 1,1,1‐IND‐tag‐CCA‐secure, a smooth divisible online/offline signature scheme DOS, and a IND‐OTCCA‐secure DEM DEM, where KEM.K=DEM.K. Then, there exists a 3-DOSC scheme 3DOSCR which is secure in the sense of 1,1,1‐dM‐IND‐iCCA but which is not secure in the sense of 2,1,1‐dM‐IND‐iCCA.The proof is given in AppendixB.2.


### 5.2. Unforgeability

First, we show the following implications with regard to the number of senders.Theorem 5.
(1,2,3,1‐sUF⟶1,2,3,n‐sUF). For k∈1,2,3, if a k-DOSC scheme DOSC is t′,q,ϵ‐k,1‐dM‐sUF‐iCMA‐secure, then DOSC is also t,q,nϵ‐k,n‐dM‐sUF‐iCMA‐secure, where t=t′−Onq.Proof.
The adversary attackingk,1‐dM‐sUF‐iCMA can simulate signcryption oracles for the adversary attacking k,n‐dM‐sUF‐iCMA, using its given oracles (for the single target sender) as well as its generating n‐1 sender key pairs. Contrary to the confidentiality notions, note that the first signcryption oracle, sc1, has the sender index i as its input so that its simulation can be done without any guessing.
Next, we show separations amongk,⋅‐dM‐sUF‐iCMA for k∈1,2,3.Theorem 6.
(1,1‐sUF↛2,1‐sUF⟶3,1‐sUF). Assume there exists a 2,1‐sUF‐CMA‐secure and smooth DOS. Then, there exists 3-DOSC schemes 3DOSCS1 and 3DOSCS2 such that the former is secure in the sense of 1,1‐dM‐sUF‐iCMA but which is not secure in the sense of 2,1‐dM‐UF‐iCMA, whereas the latter is secure in the sense of 2,1‐dM‐sUF‐iCMA but which is not secure in the sense of 3,1‐dM‐UF‐iCMA.Proof .
(sketch).3DOSCS1 and 3DOSCS2 are described in Figure 8. In order to show that 3DOSCS1 (or 3DOSCS2) is not 2,1‐dM‐UF‐iCMA‐secure (or 3,1‐dM‐UF‐iCMA‐secure), we construct adversary A1 (or A2) shown in Figure 9. Note that oracle sc3 (or sc2) always generates dS∗=skS as an answer to the query m=σ1∗ so that A can output any forgery using skS.
On the other hand, we can show that3DOSCS1 (or 3DOSCS2) is 1,1‐dM‐sUF‐iCMA‐secure (or 2,1‐dM‐sUF‐iCMA‐secure) in a similar fashion with the proof of Theorem 8 shown later.Figure 9
Description of adversaryA1 (or A2) attacking 2,1‐dM‐sUF‐iCMA (or 3,1‐dM‐sUF‐iCMA) security of 3DOSCS1 (or 3DOSCS2).


## 5.1. Confidentiality

The following two theorems say that for anyk∈1,2,3, k,1,1‐dM‐IND‐iCCA‐security implies k,n,q‐dM‐IND‐iCCA‐security with reduction loss polynomial in the number n of receivers as well as the number q of challenge queries.Theorem 1.
(1,2,1,1‐iCCA⟶1,2,n,q‐iCCA). For k∈1,2, assume a k-DOSC scheme DOSC is t′,qd,ϵ‐k,1,1‐dM‐IND‐iCCA‐secure. Then, DOSC is also t,qd,nqϵ‐k,n,q‐dM‐IND‐iCCA‐secure, where t=t′−Onq.Using the hybrid argument in a similar fashion with [20], we can easily obtain the proof of Theorem 1.As for the case ofk=3, the hybrid argument cannot be trivially applied due to the difficulty of the simulation of oracle sc1 in 3,n,q‐dM‐IND‐iCCA, which is called nq times, using oracle sc1∗ in 3,1,1‐dM‐IND‐iCCA, which can be called only once. Responding to the adversary’s query to sc1 with Σ1j, the simulator for 3,n,q‐dM‐IND‐iCCA first chooses i∗,q∗∈n×q and uses its given single public key pk∗ as a key pki∗ of the user i∗. Then, the simulator uses its given oracle access to sc1∗ in 3,1,1‐dM‐IND‐iCCA if Σ1j will be used for the q∗-th query related to the target user i∗, whereas it computes Σ1j by the simulator itself otherwise. Here, the simulator has to guess whether Σ1j will be used for the q∗-th challenge query to i∗ before a subsequent invocation of sc2. To overcome this issue, we use a naive guessing approach and obtain the following reduction:Theorem 2.
(3,1,1‐iCCA⟶3,n,q‐iCCA). Assume a 3-DOSC scheme DOSC is t′,qd,ϵ‐3,1,1‐dM‐IND‐iCCA‐secure. Then, DOSC is also t,qd,n2q2ϵ‐3,n,q‐dM‐IND‐iCCA‐secure, where t=t′−Onq.The proof is given in AppendixB.1.Remark 1.
We can apply the above argument to the multidivisible online/offline encryptions (MDOEs) to get a same polynomial reduction from3,1,1‐CCA to 3,n,q‐CCA for MDOEs. The obtained reduction is significantly tighter than the previous one shown in [14] where only superpolynomial one was provided.
Next, we show that2,1,1‐dM‐IND‐iCCA‐security implies 3,1,1‐dM‐IND‐iCCA‐security as follows:Theorem 3.
(2,1,1‐iCCA⟹3,1,1‐iCCA). Assume a 3-DOSC scheme DOSC is t,qd,ϵ‐2,1,1‐dM‐IND‐iCCA‐secure. Then DOSC is also t,qd,ϵ‐3,1,1‐dM‐IND‐iCCA‐secure.Proof.
In the single-user setting, i.e.,n=1, the adversary has no choice of the recipient i when it invokes oracle sc2j,i. Hence, the successive invocations of sc1skS,pkS and sc2j,i in 3,1,1‐dM‐IND‐iCCA game is essentially equivalent to the invocation of the oracle sc12skS,pkS,i in 2,1,1‐dM‐IND‐iCCA.
Finally, we show the separation between1,⋅,⋅‐dM‐IND‐iCCA and 2,⋅,⋅‐dM‐IND‐iCCA. Specifically, we provide a 1,1,1‐dM‐IND‐iCCA‐secure but not 2,1,1‐dM‐IND‐iCCA‐secure 3-DOSC scheme, 3DOSCR, as an evidence of the separation. Scheme 3DOSCR is described in Figure 8.Figure 8
Constructions of3DOSCR, 3DOSCS1, and 3DOSCS2 used to prove Theorem 4 and Theorem 6. Boxed parts with superscript X are evaluated only in 3DOSCX.Theorem 4.
(1,1,1‐iCCA↛2,1,1‐iCPA). Assume there exists a (divisible) online/offline tag-based KEM DOTK that is 1,1,1‐IND‐tag‐CCA‐secure, a smooth divisible online/offline signature scheme DOS, and a IND‐OTCCA‐secure DEM DEM, where KEM.K=DEM.K. Then, there exists a 3-DOSC scheme 3DOSCR which is secure in the sense of 1,1,1‐dM‐IND‐iCCA but which is not secure in the sense of 2,1,1‐dM‐IND‐iCCA.The proof is given in AppendixB.2.


## 5.2. Unforgeability

First, we show the following implications with regard to the number of senders.Theorem 5.
(1,2,3,1‐sUF⟶1,2,3,n‐sUF). For k∈1,2,3, if a k-DOSC scheme DOSC is t′,q,ϵ‐k,1‐dM‐sUF‐iCMA‐secure, then DOSC is also t,q,nϵ‐k,n‐dM‐sUF‐iCMA‐secure, where t=t′−Onq.Proof.
The adversary attackingk,1‐dM‐sUF‐iCMA can simulate signcryption oracles for the adversary attacking k,n‐dM‐sUF‐iCMA, using its given oracles (for the single target sender) as well as its generating n‐1 sender key pairs. Contrary to the confidentiality notions, note that the first signcryption oracle, sc1, has the sender index i as its input so that its simulation can be done without any guessing.
Next, we show separations amongk,⋅‐dM‐sUF‐iCMA for k∈1,2,3.Theorem 6.
(1,1‐sUF↛2,1‐sUF⟶3,1‐sUF). Assume there exists a 2,1‐sUF‐CMA‐secure and smooth DOS. Then, there exists 3-DOSC schemes 3DOSCS1 and 3DOSCS2 such that the former is secure in the sense of 1,1‐dM‐sUF‐iCMA but which is not secure in the sense of 2,1‐dM‐UF‐iCMA, whereas the latter is secure in the sense of 2,1‐dM‐sUF‐iCMA but which is not secure in the sense of 3,1‐dM‐UF‐iCMA.Proof .
(sketch).3DOSCS1 and 3DOSCS2 are described in Figure 8. In order to show that 3DOSCS1 (or 3DOSCS2) is not 2,1‐dM‐UF‐iCMA‐secure (or 3,1‐dM‐UF‐iCMA‐secure), we construct adversary A1 (or A2) shown in Figure 9. Note that oracle sc3 (or sc2) always generates dS∗=skS as an answer to the query m=σ1∗ so that A can output any forgery using skS.
On the other hand, we can show that3DOSCS1 (or 3DOSCS2) is 1,1‐dM‐sUF‐iCMA‐secure (or 2,1‐dM‐sUF‐iCMA‐secure) in a similar fashion with the proof of Theorem 8 shown later.Figure 9
Description of adversaryA1 (or A2) attacking 2,1‐dM‐sUF‐iCMA (or 3,1‐dM‐sUF‐iCMA) security of 3DOSCS1 (or 3DOSCS2).


## 6. MDOSC Construction

In this section, we provide a generic construction of MDOSC with security proofs and compare it with previous signcryption schemes.Using a (divisible) online/offline tag-based KEM, a divisible online/offline signature scheme, and a DEM as building blocks, we can derive 3-DOSC scheme3DOSC. 3DOSC is described in Figure 8 without all boxed parts.


### 6.1. Security

The following theorems guarantee the security of our construction.Theorem 7.
(3DOSC is 2,1,1‐iCCA‐secure). If DOTK is t′,qd′,ϵDOTK‐1,1,1‐IND‐tag‐CCA‐secure and DEM is t′,qd′,ϵDEM‐IND‐P0‐C2‐secure then 3DOSC is t,qd,ϵ‐2,1,1‐dM‐IND‐iCCA‐secure, where t=t′−Oqd, qd=qd′, and ϵ=2ϵDOTK+ϵDEM.We can prove this theorem in a similar fashion with the proof of Lemma B.2 described in AppendixB.2.Theorem 8.
(3DOSC is 3,1‐sUF‐secure). If DOS is t′,q′,ϵ′‐2,1‐sUF‐CMA‐secure and DEM is one-to-one then 3DOSC is t,q,ϵ‐3,1‐dM‐sUF‐iCMA‐secure, where t=t′−Oq, q=q′, and ϵ=ϵ′.Proof.
Assume we have at-time adversary A that makes at most q queries to oracles sc1, sc2, and sc3 in order to break 3,1‐dM‐sUF‐iCMA security of 3DOSC. We will construct adversary ℬ exploiting A as a black box to attack 2,1‐sUF‐CMA security of DOS. For any A, we will show the following relation holds:(7)Adv3DOSC3,1‐dM‐sUF‐iCMAA≤AdvDOS2,1‐sUF‐CMAℬ.
In order to prove equation (1), we use G0 and G1 described in Figure 10. As with the proof of Lemma B.2, we simplify the game description by omitting or modifying the statements and the variables that play no role when n=1.
GameG0 is equivalent to the original attack game played by A against 3DOSC. Hence, we have(8)PrG3DOSC3,1‐dM‐sUF‐iCMAA=1=PrG0A=1.
GameG1 is identical to G0 except the following: computations of DOS.sign1 and DOS.sign2 are replaced by oracle invocations of sign1 and sign2, respectively; one of the winning condition v2 is replaced by v2′. Note that sign1, sign2, and v2′ are exactly the ones in GDOS2,1‐sUF‐CMA described in Figure 2.
Oraclessign1 and sign2 here can be used to simulate the original behavior of G0 so that A’s views in these two games are equivalent.
In addition, we claim thatv2=1 implies v2′=1. Let us assume v2′=0, i.e., there exists some j∗ such that pkRj∗,C1j∗,C2j∗,mj∗,σ1j∗,σ2j∗ equals to pkR∗,C1∗,C2∗,m∗,σ1∗,σ2∗. Then, Kj∗=K∗ also holds because of the correctness property of DOTK. Furthermore, C3j∗=C3∗ also holds because(9)C3j∗=DEM.encλD,Kj∗,σ2j∗,mj∗=DEM.encλD,K∗,σ2∗,m∗=C3∗,where the second equality follows from one-to-one property of DEM. Hence, v2=0 holds since we now have j′ such that pkRj∗,mj∗,C1j∗,σ1j∗,C2j∗,C3j∗ equals to pkR∗,m∗,C1∗,σ1∗,C2∗,C3∗.
Therefore, it follows that(10)PrG0A=1≤PrG1A=1.
We now construct adversaryℬ satisfies the following relation:(11)PrG1A=1=AdvDOS2,1‐sUF‐CMAℬ.
The description of adversaryℬ is shown in Figure 11. We can see adversary ℬ makes at most q queries to sign1 as well as sign2, and its running time t′=t+Oq. It is easy to verify that A’s view in GDOS2,1‐sUF‐CMAℬ is equivalent to the one in G1 so that the above relation holds.
In summary, we now have equation (1). Combining it with the assumptions that DOS is t′,q′,ϵ′‐2,1‐sUF‐CMA‐secure, we have Adv3DOSC3,1‐dM‐sUF‐iCMAA≤ϵ′, which implies that 3DOSC is t,q,ϵ‐3,1‐dM‐sUF‐iCMA‐secure for ϵ=ϵ′, as desired.
From Theorems 2, 3, and 5, it follows that3DOSC has the strongest security in the sense of both confidentiality and unforgeability:Figure 10
GamesG0 and G1 for proving 3,1‐dM‐sUF‐iCMA security of 3DOSC. Codes in boxes with superscript X are evaluated only in game GX.Figure 11
Description of adversaryℬ attacking 2,1‐sUF‐CMA security of DOS.Corollary 1.
(3DOSC is 3,n,q‐iCCA‐secure). Suppose DOTK is t′,qd′,ϵDOTK1,1,1‐IND‐tag‐CCA‐secure and DEM is t′,qd′,ϵDEM‐IND‐P0‐C2‐secure. Then, 3DOSC is t,qd,ϵ‐3,n,q‐dM‐IND‐iCCA‐secure, where t=t′−Oqd, qd=qd′, and ϵ=2n2q2ϵDOTK+n2q2ϵDEM.Corollary 2.
(3DOSC is 3,n‐sUF‐secure). Suppose DOS is t′,q′,ϵ′2,1‐sUF‐CMA‐secure and DEM is one-to-one. Then, 3DOSC is t,q,ϵ3,n‐dM‐sUF‐iCMA‐secure, where t=t′−Oq, q=q′, and ϵ=nϵ′.


### 6.2. Comparison

In Tables1 and 2, we present a comparison of our 3DOSC construction with previous signcryption constructions in various viewpoints. Here, we consider the following three signcryption schemes (including ours) that satisfy the strongest notions of insider security in the multiuser setting without relying on random oracles:CMSM: the standard (i.e., not online/offline) signcryption scheme proposed by Chiba et al. [21] that consists of TBKEM, digital signature, and DEM. Here, we instantiate it with TBKEMtBMW1, TBKEM obtained from the PKE scheme by Boyen et al. [18] and Boneh-Boyen signature scheme DSBB [22].GIESC: the incrementally executable signcryption scheme [12] that consists of TBKEM, digital signature, one-time signature, and DEM. Here, we instantiate it with TBKEMtBMW1, DSBB, and the specific DL-based one-time signature scheme OTSM [23].3DOSC: our proposed MDOSC described in Figure 8 without all boxed parts, which consists of DOTK, DOS, and DEM. Here, we instantiate it with DOTKBMW, a concrete 1,1‐IND‐tag‐CCA‐secure DOTK described in Section 3.3, and the concrete DOS DOSGWXT proposed by Gao et al [4].Table 1
Comparison regarding computational cost.
CMSM [21]
GIESC [12]
Ours:3DOSC
Phase 1: sc1 with skS and pkS
Operation
—
DS
BB
.
sign
DOS
GWXT
.
sign
1
OTS
M
.
gen
DOTK
BMW
.
enc
1
Computational cost
—
3,2
;
0
2,2
;
0
Phase 2: sc2 with pkR
Operation
—
TBKEM
tBMW
1
.
enc
DOTK
BMW
.
enc
2
Computational cost
—
3,0
;
0
+
W
1,0
;
0
Phase 3: sc3 with m
Operation
TBKEM
tBMW
1
.
enc
OTS
M
.
sign
DOS
GWXT
.
sign
2
DS
BB
.
sign
DEM
.
enc
DEM
.
enc
DEM
.
enc
Computational cost
4,0
;
0
+
W
0,0
;
0
0,0
;
0Table 2
Comparison regarding storage and ciphertext size.
CMSM [21]
GIESC [12]
Ours:3DOSC
Phase 1: sc1 with skS and pkS
Ciphertext sizeΣ1
—
—
3
G
+
ℤ
p; 640
Phase 2: sc2 with pkR
Storage sizeφ1
—
4
G
+
5
ℤ
p
+
2
H; 1760
2
ℤ
p; 320
Ciphertext sizeΣ2
—
—
—
Phase 3: sc3 with m
Storage sizeφ2
—
6
G
+
5
ℤ
p
+
2
H
+
G
T; 3104
G
T
+
ℤ
p; 1184
Ciphertext sizeΣ3
3
G
+
ℤ
p
+
m; 720
6
G
+
3
ℤ
p
+
H
+
m; 1680
2
ℤ
p
+
m; 400Note that we do not specify any instance of DEM since the selection of DEM does not cause the efficiency difference in the comparison.Computational costs are measured in the same way as [21], that is, a,b;c denotes a exponentiations, b multiexponentiations, and c pairing computations, and W denotes computation of the Waters hash [24]. Other computational overhead caused by multiplications, hash functions, and symmetric key primitives are ignored.In terms of storage and ciphertext size,G and GT denote the size of a bilinear group element from G and GT, respectively. Similarly, ℤp denotes the size of a group element of ℤp, whereas H denotes the output length of target-collision resistant hash function. The appended numerical values are instance bit-length of storage and ciphertext when we assume G=ℤp=H=160 bits and GT=1024 bits to achieve 80-bit security. We also assume m=80 to capture typical IoT use cases where messages sent by IoT devices are significantly shorter than other cases.Our construction exploits the multidivisible feature effectively to achieve both the shortest ciphertext size and the least computational cost in the phase 3 (i.e., online phase). With ourDOSC, the expensive encryption process DOTK.enc1 can also be performed in the phase 1 (i.e., before being given the recipient’s public key), whereas it can be only in the phase 2 (i.e., after being given the recipient’s public key) with GIESC. All the advantages enable lightweight IoT devices to transmit confidential as well as authenticated messages to the recipient devices in IoT application scenarios as described in Section 1.


## 6.1. Security

The following theorems guarantee the security of our construction.Theorem 7.
(3DOSC is 2,1,1‐iCCA‐secure). If DOTK is t′,qd′,ϵDOTK‐1,1,1‐IND‐tag‐CCA‐secure and DEM is t′,qd′,ϵDEM‐IND‐P0‐C2‐secure then 3DOSC is t,qd,ϵ‐2,1,1‐dM‐IND‐iCCA‐secure, where t=t′−Oqd, qd=qd′, and ϵ=2ϵDOTK+ϵDEM.We can prove this theorem in a similar fashion with the proof of Lemma B.2 described in AppendixB.2.Theorem 8.
(3DOSC is 3,1‐sUF‐secure). If DOS is t′,q′,ϵ′‐2,1‐sUF‐CMA‐secure and DEM is one-to-one then 3DOSC is t,q,ϵ‐3,1‐dM‐sUF‐iCMA‐secure, where t=t′−Oq, q=q′, and ϵ=ϵ′.Proof.
Assume we have at-time adversary A that makes at most q queries to oracles sc1, sc2, and sc3 in order to break 3,1‐dM‐sUF‐iCMA security of 3DOSC. We will construct adversary ℬ exploiting A as a black box to attack 2,1‐sUF‐CMA security of DOS. For any A, we will show the following relation holds:(7)Adv3DOSC3,1‐dM‐sUF‐iCMAA≤AdvDOS2,1‐sUF‐CMAℬ.
In order to prove equation (1), we use G0 and G1 described in Figure 10. As with the proof of Lemma B.2, we simplify the game description by omitting or modifying the statements and the variables that play no role when n=1.
GameG0 is equivalent to the original attack game played by A against 3DOSC. Hence, we have(8)PrG3DOSC3,1‐dM‐sUF‐iCMAA=1=PrG0A=1.
GameG1 is identical to G0 except the following: computations of DOS.sign1 and DOS.sign2 are replaced by oracle invocations of sign1 and sign2, respectively; one of the winning condition v2 is replaced by v2′. Note that sign1, sign2, and v2′ are exactly the ones in GDOS2,1‐sUF‐CMA described in Figure 2.
Oraclessign1 and sign2 here can be used to simulate the original behavior of G0 so that A’s views in these two games are equivalent.
In addition, we claim thatv2=1 implies v2′=1. Let us assume v2′=0, i.e., there exists some j∗ such that pkRj∗,C1j∗,C2j∗,mj∗,σ1j∗,σ2j∗ equals to pkR∗,C1∗,C2∗,m∗,σ1∗,σ2∗. Then, Kj∗=K∗ also holds because of the correctness property of DOTK. Furthermore, C3j∗=C3∗ also holds because(9)C3j∗=DEM.encλD,Kj∗,σ2j∗,mj∗=DEM.encλD,K∗,σ2∗,m∗=C3∗,where the second equality follows from one-to-one property of DEM. Hence, v2=0 holds since we now have j′ such that pkRj∗,mj∗,C1j∗,σ1j∗,C2j∗,C3j∗ equals to pkR∗,m∗,C1∗,σ1∗,C2∗,C3∗.
Therefore, it follows that(10)PrG0A=1≤PrG1A=1.
We now construct adversaryℬ satisfies the following relation:(11)PrG1A=1=AdvDOS2,1‐sUF‐CMAℬ.
The description of adversaryℬ is shown in Figure 11. We can see adversary ℬ makes at most q queries to sign1 as well as sign2, and its running time t′=t+Oq. It is easy to verify that A’s view in GDOS2,1‐sUF‐CMAℬ is equivalent to the one in G1 so that the above relation holds.
In summary, we now have equation (1). Combining it with the assumptions that DOS is t′,q′,ϵ′‐2,1‐sUF‐CMA‐secure, we have Adv3DOSC3,1‐dM‐sUF‐iCMAA≤ϵ′, which implies that 3DOSC is t,q,ϵ‐3,1‐dM‐sUF‐iCMA‐secure for ϵ=ϵ′, as desired.
From Theorems 2, 3, and 5, it follows that3DOSC has the strongest security in the sense of both confidentiality and unforgeability:Figure 10
GamesG0 and G1 for proving 3,1‐dM‐sUF‐iCMA security of 3DOSC. Codes in boxes with superscript X are evaluated only in game GX.Figure 11
Description of adversaryℬ attacking 2,1‐sUF‐CMA security of DOS.Corollary 1.
(3DOSC is 3,n,q‐iCCA‐secure). Suppose DOTK is t′,qd′,ϵDOTK1,1,1‐IND‐tag‐CCA‐secure and DEM is t′,qd′,ϵDEM‐IND‐P0‐C2‐secure. Then, 3DOSC is t,qd,ϵ‐3,n,q‐dM‐IND‐iCCA‐secure, where t=t′−Oqd, qd=qd′, and ϵ=2n2q2ϵDOTK+n2q2ϵDEM.Corollary 2.
(3DOSC is 3,n‐sUF‐secure). Suppose DOS is t′,q′,ϵ′2,1‐sUF‐CMA‐secure and DEM is one-to-one. Then, 3DOSC is t,q,ϵ3,n‐dM‐sUF‐iCMA‐secure, where t=t′−Oq, q=q′, and ϵ=nϵ′.


## 6.2. Comparison

In Tables1 and 2, we present a comparison of our 3DOSC construction with previous signcryption constructions in various viewpoints. Here, we consider the following three signcryption schemes (including ours) that satisfy the strongest notions of insider security in the multiuser setting without relying on random oracles:CMSM: the standard (i.e., not online/offline) signcryption scheme proposed by Chiba et al. [21] that consists of TBKEM, digital signature, and DEM. Here, we instantiate it with TBKEMtBMW1, TBKEM obtained from the PKE scheme by Boyen et al. [18] and Boneh-Boyen signature scheme DSBB [22].GIESC: the incrementally executable signcryption scheme [12] that consists of TBKEM, digital signature, one-time signature, and DEM. Here, we instantiate it with TBKEMtBMW1, DSBB, and the specific DL-based one-time signature scheme OTSM [23].3DOSC: our proposed MDOSC described in Figure 8 without all boxed parts, which consists of DOTK, DOS, and DEM. Here, we instantiate it with DOTKBMW, a concrete 1,1‐IND‐tag‐CCA‐secure DOTK described in Section 3.3, and the concrete DOS DOSGWXT proposed by Gao et al [4].Table 1
Comparison regarding computational cost.
CMSM [21]
GIESC [12]
Ours:3DOSC
Phase 1: sc1 with skS and pkS
Operation
—
DS
BB
.
sign
DOS
GWXT
.
sign
1
OTS
M
.
gen
DOTK
BMW
.
enc
1
Computational cost
—
3,2
;
0
2,2
;
0
Phase 2: sc2 with pkR
Operation
—
TBKEM
tBMW
1
.
enc
DOTK
BMW
.
enc
2
Computational cost
—
3,0
;
0
+
W
1,0
;
0
Phase 3: sc3 with m
Operation
TBKEM
tBMW
1
.
enc
OTS
M
.
sign
DOS
GWXT
.
sign
2
DS
BB
.
sign
DEM
.
enc
DEM
.
enc
DEM
.
enc
Computational cost
4,0
;
0
+
W
0,0
;
0
0,0
;
0Table 2
Comparison regarding storage and ciphertext size.
CMSM [21]
GIESC [12]
Ours:3DOSC
Phase 1: sc1 with skS and pkS
Ciphertext sizeΣ1
—
—
3
G
+
ℤ
p; 640
Phase 2: sc2 with pkR
Storage sizeφ1
—
4
G
+
5
ℤ
p
+
2
H; 1760
2
ℤ
p; 320
Ciphertext sizeΣ2
—
—
—
Phase 3: sc3 with m
Storage sizeφ2
—
6
G
+
5
ℤ
p
+
2
H
+
G
T; 3104
G
T
+
ℤ
p; 1184
Ciphertext sizeΣ3
3
G
+
ℤ
p
+
m; 720
6
G
+
3
ℤ
p
+
H
+
m; 1680
2
ℤ
p
+
m; 400Note that we do not specify any instance of DEM since the selection of DEM does not cause the efficiency difference in the comparison.Computational costs are measured in the same way as [21], that is, a,b;c denotes a exponentiations, b multiexponentiations, and c pairing computations, and W denotes computation of the Waters hash [24]. Other computational overhead caused by multiplications, hash functions, and symmetric key primitives are ignored.In terms of storage and ciphertext size,G and GT denote the size of a bilinear group element from G and GT, respectively. Similarly, ℤp denotes the size of a group element of ℤp, whereas H denotes the output length of target-collision resistant hash function. The appended numerical values are instance bit-length of storage and ciphertext when we assume G=ℤp=H=160 bits and GT=1024 bits to achieve 80-bit security. We also assume m=80 to capture typical IoT use cases where messages sent by IoT devices are significantly shorter than other cases.Our construction exploits the multidivisible feature effectively to achieve both the shortest ciphertext size and the least computational cost in the phase 3 (i.e., online phase). With ourDOSC, the expensive encryption process DOTK.enc1 can also be performed in the phase 1 (i.e., before being given the recipient’s public key), whereas it can be only in the phase 2 (i.e., after being given the recipient’s public key) with GIESC. All the advantages enable lightweight IoT devices to transmit confidential as well as authenticated messages to the recipient devices in IoT application scenarios as described in Section 1.


## 7. Conclusions

We presented a general concept of multidivisible online/offline cryptography (MDO cryptography), which covers the previous works including online/offline cryptographic schemes, divisible online/offline signatures, incrementally executable signcryptions, and multidivisible online/offline encryptions. We then presented the notion of multidivisible online/offline signcryptions (MDOSCs) as novel application of MDO cryptography. We defined several security notions for MDOSCs and show implications and separations between these security notions. We also presented a generic construction of MDOSC that achieves the strongest security notions with regard to confidentiality and unforgeability. MDOSC schemes allow the computationally restricted and/or bandwidth-restricted devices to transmit signed ciphertexts with low computational overhead and/or low-bandwidth network.



---

*Source: 1042649-2019-10-08.xml*