# Group Signatures with Message-Dependent Opening: Formal Definitions and Constructions

Authors: Keita Emura; Goichiro Hanaoka; Yutaka Kawai; Takahiro Matsuda; Kazuma Ohara; Kazumasa Omote; Yusuke Sakai
Journal: Security and Communication Networks
 (2019)

---

## Abstract

This paper introduces a new capability for group signatures calledmessage-dependent opening. It is intended to weaken the high trust placed on the opener; i.e., no anonymity against the opener is provided by an ordinary group signature scheme. In a group signature scheme with message-dependent opening (GS-MDO), in addition to the opener, we set up anadmitter that is not able to extract any user’s identity butadmits the opener to open signatures by specifying messages where signatures on the specified messages will be opened by the opener. The opener cannot extract the signer’s identity from any signature whose corresponding message is not specified by the admitter. This paper presents formal definitions of GS-MDO and proposes a generic construction of it from identity-based encryption and adaptive non-interactive zero-knowledge proofs. Moreover, we propose two specific constructions, one in the standard model and one in the random oracle model. Our scheme in the standard model is an instantiation of our generic construction but the message-dependent opening property is bounded. In contrast, our scheme in the random oracle model is not a direct instantiation of our generic construction but is optimized to increase efficiency and achieves the unbounded message-dependent opening property. Furthermore, we also demonstrate that GS-MDO implies identity-based encryption, thus implying that identity-based encryption is essential for designing GS-MDO schemes.


---

## Body

## 1. Introduction

Group signatures [1] are anonymous signatures that allow members of a group to anonymously sign messages on behalf of the group. Signatures are verified with a single group public key, and the verification process does not reveal the identity of the signer. A designated authority, called the opener, identifies the actual signer in various exceptional cases. However, ordinary group signatures provide the opener with an extreme privilege; i.e., the opener can freely identify the originator of any signature that he chooses. In other words, ordinary group signature schemes provide absolutely no assurance of privacy against the opener. For example, in an anonymous auction the opener can extract all bidders’ identities, which will be explained later in more detail.This paper investigates a way of “decentralizing” this strong authority of the opener. Towards this end, we propose a new kind of group signatures involvingthe message-dependent opening (MDO) property. It divides (or decentralizes) the strong authority of the opener by introducing another authority called theadmitter. In exceptional cases that a signature on a problematic message is found, the admitter issues atoken that corresponds to the message (as opposed to all signed messages). The opener extracts the signer’s identity from the signature using this token, whereas without it, he is not able to do so. For instance, in an anonymous bulletin board system using our group signature scheme, if the admitter decides that the message “Mr. XXX is a fool!” should not be publicized as a signed message by an anonymous group member, he issues a token for this message. Then, by using it, the opener can immediately identify the signer’s identity of any signature if it corresponds to this message.At first glance, one may think that the popular thresholding technique (i.e., thresholding the opener into multiple less-trusted openers) [2] would already be sufficient to achieve the above property. However, this is not true. Namely, in our context, the token is generated onthe message that the admitter chooses but not the signature for such messages. Therefore, once a token for a message (which is chosen by the admitter) is issued, the signers’ identities for all signatures on this message can immediately be extracted by the opener without him having to interact with any other party. Consequently, the opener can noninteractively identify the signer’s identity for a message that has already been specified as problematic. Furthermore if the admitter considers that there is no longer any need to specify further messages that should be opened, then he can erase his memory to avoid having his secret leaked. Note that even when the admitter has erased his secret, the opener can still open the signer’s identity of any signature provided that its corresponding message was previously specified by the admitter.


### 1.1. Contributions

This paper proposes group signatures with a new additional capability, calledgroup signatures with message-dependent opening (GS-MDO). We introduce anadmitter in GS-MDO, as previously mentioned, that issues tokens for specific messages, and by using these tokens, the opener can extract signers’ identities from signatures only if their corresponding messages have been specified. We can flexibly restrict the capabilities of the opener utilizing this property without implementing any complicated interactive procedures (e.g., threshold decryption).The main contributions of this paper are threefold. First, we provide a formal model and a security definition for GS-MDO. Our model and security definition are extensions of the Bellare-Micciancio-Warinschi (BMW) model [3], which is considered to be the basic security definition for group signatures in the static setting. More specifically, our security model is a natural modification of this model extended according to the difference between a standard group signature scheme and ours which introduces the MDO property. In addition, we demonstrate thatit is possible to derive identity-based encryption (IBE) from any GS-MDO scheme in a black-box manner if the underlying GS-MDO is secure in the above sense.Secondly, we present a generic construction of GS-MDO from a public key encryption (PKE) scheme, an IBE scheme, and an adaptive noninteractive zero-knowledge (NIZK) proof system. (Technically, we use a tag-based KEM (key encapsulation mechanism) and an identity-based KEM instead of a PKE scheme and an IBE scheme). Given the above result that GS-MDO implies IBE, it is expected to be quite hard to construct GS-MDO without using IBE or similar primitives as a building block. We note that simulation-soundness [4] is not required for NIZK in our generic construction, while the generic construction of the (ordinary) group signature [3] requires this strong property.Finally, we propose two efficient instantiations of GS-MDO, one in the standard model and one in the random oracle model. Our scheme in the standard model uses the Groth-Sahai proof system [5] as an NIZK proof system in our generic construction. To utilize the Groth-Sahai proof system in our generic construction, we note that an IBE scheme that is compatible with the Groth-Sahai proof (such as structure-preserving signatures [6]) is necessary since our generic construction requires IBE. To be compatible with the Groth-Sahai proof system, an IBE scheme needs to be able to encrypt a base-group element and to have its ciphertext consist of only base-group elements. Although Libert and Joye [7] proposed an IBE scheme whose plaintext space is a base group, and the IBE scheme is compatible with the Groth-Sahai proof, the size of the group signature of the resulting GS-MDO scheme depends on the number of group members. In order to construct a GS-MDO scheme with constant-size signature, we also construct a new IBE scheme that has only k-resilient security [8]. Therefore, the resulting GS-MDO scheme inherits this restriction (i.e., the admitter can issue at most k tokens). The size of a signature is approximately 10 kilobytes when a 170-bit prime-order group is used. (We adopt the estimates of bit sizes for group elements used in [9]). Our scheme in the random oracle model, on the other hand, is based on the Boneh-Boyen-Shacham (BBS) group signature [10] and uses the Boneh-Franklin (BF) IBE scheme [11] and a variant of the Cramer-Shoup encryption scheme [12, 13]. As we can use IBE (which is not k-resilient) in the random oracle model, GS-MDO with an unbounded MDO property (i.e., the number of tokens issued by the admitter is unlimited) can thus be constructed. The idea behind this construction is based on our generic construction, but the instantiation is not straightforward since the PKE scheme and the IBE scheme cannot directly be combined. Hence, we modify the building blocks and the construction to combine them. To be more precise, we design a dedicated extension of the linear encryption scheme [10] with chosen-ciphertext security and public verifiability to enable our efficient construction. The size of the signature of the scheme is 3636 bits in 80-bit security, which is 20 times smaller than that of our standard model scheme.Note that our security notions and proposed schemes assume that the system setup is carried out honestly. This setup includes the generation of a common reference string, the opener’s and the admitter’s secret keys, and the group members’ signing keys. However, the goal of the current paper is to provide a feasibility study of the MDO property in group signatures. Namely, we study the possibility of constructing a GS-MDO scheme in a simple setting where several parameters and secret keys are generated honestly. We defer to future work a more comprehensive study on the possibility of constructing a scheme with a more complicated and realistic scenario such as that allowing maliciously generated parameters and on providing a hedge against this types of attack.


### 1.2. Applications

As previously mentioned, a straightforward application of GS-MDO schemes is in detecting the originators of inappropriate messages in anonymous bulletin board systems. We further discuss more potential applications of GS-MDO schemes in what follows.The first application we discuss isanonymous auctions, where bidders form a group of anonymous signers. Each bidder produces a group signature on his bidding price. The admitter issues a token for opening signatures on the highest price to detect the winner(s). The opener is then only able to open the signatures on the highest price.The main advantage (of the MDO approach) over the threshold approach becomes clear in this application. Suppose that there aremany winners who all have bid the highest price resulting in a tie. As an interaction will be needed for each winner in the threshold approach, the total communication cost will be proportional to the number of winners. In contrast, if one takes the MDO approach, only a small communication bandwidth from the admitter to the opener is needed. The communication cost does not depend on the number of winners.Another application in which the MDO property is useful isidentity escrow. Although our primitive is a rather general purpose primitive for identity escrow scenarios, for the ease of understanding, let us discuss this with a concrete example. Consider a customer who enters an automated parking garage [14], where he generates a group signature on a message that encodes the date when he enters the car park (say, the string “2012-02-20”). Let us assume a felony has been committed (e.g., a person is murdered) in the garage. The opener in this case will open the signatures on the date when the murder occurred to identify who was there on that day.The opener in this application needs to openmany signatures on thesame message. If one adopts the threshold technique to decentralize the authority, many interactions are required to open all the signatures. The MDO property removes interactions between authorities, i.e., the admitter issues a token for the day, and the opener opens all the signatures without interactions.As an application of GS-MDO, Arai et al. [15] proposed a privacy-preserving anomaly detection framework. In their framework, the admitter plays the role of analyzing data, and the opener plays the role of detecting adversarial users. Briefly, a user generates a group signature on data, and sends it to the admitter. Then, the admitter can detect anomaly data without identifying users. For detecting adversarial users who generate anomaly data, the admitter generates tokens that correspond to the anomaly data, and sends them to the opener. This framework allows the admitter to detect adversarial users, while other honest users are kept anonymous.


### 1.3. Related Work

Since group signatures were first proposed by Chaum and van Heyst [1], many efficient constructions have been proposed, most of which depend on a random oracle [10, 16–23]. Many earlier schemes were based on the strong RSA assumption [24, 25]. Group signature schemes based on assumptions related to the discrete-logarithm type were achieved, to name a few, by Camenisch and Lysyanskaya [17] and by Boneh, Boyen, and Shacham [10]. The former scheme is based on the LRSW assumption [26], while the latter is based on the q-strong Diffie-Hellman (q-SDH) assumption [27].Group signature schemes without random oracles were also achieved. Ateniese et al. [28] first proposed a group signature scheme from interactive assumptions avoiding random oracles. Following this scheme, Groth proposed a group signature scheme that avoids random oracles and interactive assumptions [29], but his scheme has a very large signature size. Boyen and Waters [30, 31] proposed highly efficient constructions, although the security guarantees of their schemes are not very strong, i.e., they only achieve so-called CPA-anonymity. Groth [32] proposed another group signature scheme, which is almost as efficient as the Boyen-Waters schemes and satisfies higher security guarantee of the Bellare-Shi-Zhang (BSZ) model [33]. Libert et al. [34] proposed a group signature scheme secure in the standard model from standard assumptions.Regarding decentralizing and distributing the power of the group manager, the separability of a cryptographic protocol was introduced by Kilian and Petrank [14] in the context of identity escrow. Later, this notion was refined and adopted to the context of group signature by Camenisch and Michels [35]. The separability notion requires that keys of several entities involved in a cryptographic primitive be generated independently of each other. In their setting, the power of a group manager is separated into two authorities. The first authority is able to allow a new member to join the group but is not able to identify the originator of a group signature, and the other authority is able to identify the originator of a group signature but is not able to allow a new member to join the group. More formal modeling of these separated authorities has been proposed by Bellare et al. [33] and Kiayias and Yung [36]. Sakai et al. [37] further extended the BSZ model by considering signature hijacking attacks.Libert et al. [38, 39] proposed scalable group signature schemes with revocation, and Attrapadung et al. [40] and Nakanishi et al. [41] also proposed revocable group signature schemes with a compact revocation list.Traceable signatures are an extended notion of group signatures and were introduced by Kiayias, Tsiounis, and Yung [42]. This primitive allows the group manager to specify a group member as “misbehaving”. Once a member is specified by the manager, anyone becomes able to detect the signatures of the specified user without interacting with the manager. In this case, signatures of other group members continue to be anonymous. In our terminology, this primitive achieves a somewhat “signer-dependent opening” property, but the MDO property is not achieved. A contractual anonymity system [43] based on group signatures with verifier-local revocation [44] has been proposed. In this system, when a user breaks a contract, an accountability server revokes the anonymity of the user and notifies the identity of the user to the service provider. (In this system, a user is said tobreak a contract when the user sends a message breaking the contract policy of the service provider). Since this scheme uses a conventional open algorithm, this system also differs from MDO.As follow-up works to our results [45, 46], Libert and Joye [7] proposed an unbounded GS-MDO scheme in the standard model with logarithmic signature size. They proposed a partially structure-preserving IBE scheme and used it as a building block of GS-MDO. The signature of their scheme consists of 53log⁡N+35 group elements, where N is the number of group members, whereas our GS-MDO schemes achieve constant-size signatures, though our standard model scheme does not achieve the unbounded MDO property. Constructing an unbounded GS-MDO scheme secure in the standard model with constant-size signatures is an interesting open problem. Libert, Mouhartem, and Nguyen [47] proposed a lattice-based (unbounded) GS-MDO scheme in the random oracle model. Their scheme was proved secure from the short integer solution (SIS) assumption and the learning with errors (LWE) assumption. The signature size of this scheme is still logarithmic in the number of signers, whereas our two constructions have constant-size signatures.Preliminary versions of this paper were presented at the 5th International Conference on Pairing-Based Cryptography (Pairing 2012) [45] and at the 8th ACM Symposium on Information, Computer and Communications Security (ASIACCS 2013) [46]. This is the merged full version. In this version, we give security proofs omitted in the proceedings versions.


### 1.4. Paper Organization

The rest of this paper is structured as follows. Section2 briefly describes definitions and security notions of several building blocks. Section 3 presents the notion of GS-MDO, its syntax and security definitions. Section 4 discusses difficulties behind constructing efficient GS-MDO schemes. Specifically, we argue the use of IBE in a construction of GS-MDO is essential by showing a generic construction of IBE from GS-MDO. In Section 5, we propose a generic construction of GS-MDO, and Sections 6 and 7 show reasonably efficient instantiations in the standard model and the random oracle model, respectively. In Section 8, we compare the efficiency of our GS-MDO schemes with previous group signatures. In Section 9, we conclude the paper and list open problems.


## 1.1. Contributions

This paper proposes group signatures with a new additional capability, calledgroup signatures with message-dependent opening (GS-MDO). We introduce anadmitter in GS-MDO, as previously mentioned, that issues tokens for specific messages, and by using these tokens, the opener can extract signers’ identities from signatures only if their corresponding messages have been specified. We can flexibly restrict the capabilities of the opener utilizing this property without implementing any complicated interactive procedures (e.g., threshold decryption).The main contributions of this paper are threefold. First, we provide a formal model and a security definition for GS-MDO. Our model and security definition are extensions of the Bellare-Micciancio-Warinschi (BMW) model [3], which is considered to be the basic security definition for group signatures in the static setting. More specifically, our security model is a natural modification of this model extended according to the difference between a standard group signature scheme and ours which introduces the MDO property. In addition, we demonstrate thatit is possible to derive identity-based encryption (IBE) from any GS-MDO scheme in a black-box manner if the underlying GS-MDO is secure in the above sense.Secondly, we present a generic construction of GS-MDO from a public key encryption (PKE) scheme, an IBE scheme, and an adaptive noninteractive zero-knowledge (NIZK) proof system. (Technically, we use a tag-based KEM (key encapsulation mechanism) and an identity-based KEM instead of a PKE scheme and an IBE scheme). Given the above result that GS-MDO implies IBE, it is expected to be quite hard to construct GS-MDO without using IBE or similar primitives as a building block. We note that simulation-soundness [4] is not required for NIZK in our generic construction, while the generic construction of the (ordinary) group signature [3] requires this strong property.Finally, we propose two efficient instantiations of GS-MDO, one in the standard model and one in the random oracle model. Our scheme in the standard model uses the Groth-Sahai proof system [5] as an NIZK proof system in our generic construction. To utilize the Groth-Sahai proof system in our generic construction, we note that an IBE scheme that is compatible with the Groth-Sahai proof (such as structure-preserving signatures [6]) is necessary since our generic construction requires IBE. To be compatible with the Groth-Sahai proof system, an IBE scheme needs to be able to encrypt a base-group element and to have its ciphertext consist of only base-group elements. Although Libert and Joye [7] proposed an IBE scheme whose plaintext space is a base group, and the IBE scheme is compatible with the Groth-Sahai proof, the size of the group signature of the resulting GS-MDO scheme depends on the number of group members. In order to construct a GS-MDO scheme with constant-size signature, we also construct a new IBE scheme that has only k-resilient security [8]. Therefore, the resulting GS-MDO scheme inherits this restriction (i.e., the admitter can issue at most k tokens). The size of a signature is approximately 10 kilobytes when a 170-bit prime-order group is used. (We adopt the estimates of bit sizes for group elements used in [9]). Our scheme in the random oracle model, on the other hand, is based on the Boneh-Boyen-Shacham (BBS) group signature [10] and uses the Boneh-Franklin (BF) IBE scheme [11] and a variant of the Cramer-Shoup encryption scheme [12, 13]. As we can use IBE (which is not k-resilient) in the random oracle model, GS-MDO with an unbounded MDO property (i.e., the number of tokens issued by the admitter is unlimited) can thus be constructed. The idea behind this construction is based on our generic construction, but the instantiation is not straightforward since the PKE scheme and the IBE scheme cannot directly be combined. Hence, we modify the building blocks and the construction to combine them. To be more precise, we design a dedicated extension of the linear encryption scheme [10] with chosen-ciphertext security and public verifiability to enable our efficient construction. The size of the signature of the scheme is 3636 bits in 80-bit security, which is 20 times smaller than that of our standard model scheme.Note that our security notions and proposed schemes assume that the system setup is carried out honestly. This setup includes the generation of a common reference string, the opener’s and the admitter’s secret keys, and the group members’ signing keys. However, the goal of the current paper is to provide a feasibility study of the MDO property in group signatures. Namely, we study the possibility of constructing a GS-MDO scheme in a simple setting where several parameters and secret keys are generated honestly. We defer to future work a more comprehensive study on the possibility of constructing a scheme with a more complicated and realistic scenario such as that allowing maliciously generated parameters and on providing a hedge against this types of attack.


## 1.2. Applications

As previously mentioned, a straightforward application of GS-MDO schemes is in detecting the originators of inappropriate messages in anonymous bulletin board systems. We further discuss more potential applications of GS-MDO schemes in what follows.The first application we discuss isanonymous auctions, where bidders form a group of anonymous signers. Each bidder produces a group signature on his bidding price. The admitter issues a token for opening signatures on the highest price to detect the winner(s). The opener is then only able to open the signatures on the highest price.The main advantage (of the MDO approach) over the threshold approach becomes clear in this application. Suppose that there aremany winners who all have bid the highest price resulting in a tie. As an interaction will be needed for each winner in the threshold approach, the total communication cost will be proportional to the number of winners. In contrast, if one takes the MDO approach, only a small communication bandwidth from the admitter to the opener is needed. The communication cost does not depend on the number of winners.Another application in which the MDO property is useful isidentity escrow. Although our primitive is a rather general purpose primitive for identity escrow scenarios, for the ease of understanding, let us discuss this with a concrete example. Consider a customer who enters an automated parking garage [14], where he generates a group signature on a message that encodes the date when he enters the car park (say, the string “2012-02-20”). Let us assume a felony has been committed (e.g., a person is murdered) in the garage. The opener in this case will open the signatures on the date when the murder occurred to identify who was there on that day.The opener in this application needs to openmany signatures on thesame message. If one adopts the threshold technique to decentralize the authority, many interactions are required to open all the signatures. The MDO property removes interactions between authorities, i.e., the admitter issues a token for the day, and the opener opens all the signatures without interactions.As an application of GS-MDO, Arai et al. [15] proposed a privacy-preserving anomaly detection framework. In their framework, the admitter plays the role of analyzing data, and the opener plays the role of detecting adversarial users. Briefly, a user generates a group signature on data, and sends it to the admitter. Then, the admitter can detect anomaly data without identifying users. For detecting adversarial users who generate anomaly data, the admitter generates tokens that correspond to the anomaly data, and sends them to the opener. This framework allows the admitter to detect adversarial users, while other honest users are kept anonymous.


## 1.3. Related Work

Since group signatures were first proposed by Chaum and van Heyst [1], many efficient constructions have been proposed, most of which depend on a random oracle [10, 16–23]. Many earlier schemes were based on the strong RSA assumption [24, 25]. Group signature schemes based on assumptions related to the discrete-logarithm type were achieved, to name a few, by Camenisch and Lysyanskaya [17] and by Boneh, Boyen, and Shacham [10]. The former scheme is based on the LRSW assumption [26], while the latter is based on the q-strong Diffie-Hellman (q-SDH) assumption [27].Group signature schemes without random oracles were also achieved. Ateniese et al. [28] first proposed a group signature scheme from interactive assumptions avoiding random oracles. Following this scheme, Groth proposed a group signature scheme that avoids random oracles and interactive assumptions [29], but his scheme has a very large signature size. Boyen and Waters [30, 31] proposed highly efficient constructions, although the security guarantees of their schemes are not very strong, i.e., they only achieve so-called CPA-anonymity. Groth [32] proposed another group signature scheme, which is almost as efficient as the Boyen-Waters schemes and satisfies higher security guarantee of the Bellare-Shi-Zhang (BSZ) model [33]. Libert et al. [34] proposed a group signature scheme secure in the standard model from standard assumptions.Regarding decentralizing and distributing the power of the group manager, the separability of a cryptographic protocol was introduced by Kilian and Petrank [14] in the context of identity escrow. Later, this notion was refined and adopted to the context of group signature by Camenisch and Michels [35]. The separability notion requires that keys of several entities involved in a cryptographic primitive be generated independently of each other. In their setting, the power of a group manager is separated into two authorities. The first authority is able to allow a new member to join the group but is not able to identify the originator of a group signature, and the other authority is able to identify the originator of a group signature but is not able to allow a new member to join the group. More formal modeling of these separated authorities has been proposed by Bellare et al. [33] and Kiayias and Yung [36]. Sakai et al. [37] further extended the BSZ model by considering signature hijacking attacks.Libert et al. [38, 39] proposed scalable group signature schemes with revocation, and Attrapadung et al. [40] and Nakanishi et al. [41] also proposed revocable group signature schemes with a compact revocation list.Traceable signatures are an extended notion of group signatures and were introduced by Kiayias, Tsiounis, and Yung [42]. This primitive allows the group manager to specify a group member as “misbehaving”. Once a member is specified by the manager, anyone becomes able to detect the signatures of the specified user without interacting with the manager. In this case, signatures of other group members continue to be anonymous. In our terminology, this primitive achieves a somewhat “signer-dependent opening” property, but the MDO property is not achieved. A contractual anonymity system [43] based on group signatures with verifier-local revocation [44] has been proposed. In this system, when a user breaks a contract, an accountability server revokes the anonymity of the user and notifies the identity of the user to the service provider. (In this system, a user is said tobreak a contract when the user sends a message breaking the contract policy of the service provider). Since this scheme uses a conventional open algorithm, this system also differs from MDO.As follow-up works to our results [45, 46], Libert and Joye [7] proposed an unbounded GS-MDO scheme in the standard model with logarithmic signature size. They proposed a partially structure-preserving IBE scheme and used it as a building block of GS-MDO. The signature of their scheme consists of 53log⁡N+35 group elements, where N is the number of group members, whereas our GS-MDO schemes achieve constant-size signatures, though our standard model scheme does not achieve the unbounded MDO property. Constructing an unbounded GS-MDO scheme secure in the standard model with constant-size signatures is an interesting open problem. Libert, Mouhartem, and Nguyen [47] proposed a lattice-based (unbounded) GS-MDO scheme in the random oracle model. Their scheme was proved secure from the short integer solution (SIS) assumption and the learning with errors (LWE) assumption. The signature size of this scheme is still logarithmic in the number of signers, whereas our two constructions have constant-size signatures.Preliminary versions of this paper were presented at the 5th International Conference on Pairing-Based Cryptography (Pairing 2012) [45] and at the 8th ACM Symposium on Information, Computer and Communications Security (ASIACCS 2013) [46]. This is the merged full version. In this version, we give security proofs omitted in the proceedings versions.


## 1.4. Paper Organization

The rest of this paper is structured as follows. Section2 briefly describes definitions and security notions of several building blocks. Section 3 presents the notion of GS-MDO, its syntax and security definitions. Section 4 discusses difficulties behind constructing efficient GS-MDO schemes. Specifically, we argue the use of IBE in a construction of GS-MDO is essential by showing a generic construction of IBE from GS-MDO. In Section 5, we propose a generic construction of GS-MDO, and Sections 6 and 7 show reasonably efficient instantiations in the standard model and the random oracle model, respectively. In Section 8, we compare the efficiency of our GS-MDO schemes with previous group signatures. In Section 9, we conclude the paper and list open problems.


## 2. Preliminaries

In this section, we describe the syntax of building blocks and some computational assumptions we use for constructing GS-MDO. Throughout the paper, we use the following notations:x←X denotes that x is uniformly and independently sampled from the set X. For an algorithm A, an input x, and a randomness r we denote y←A(x;r) to run A with an input x and a randomness r and let y be the output. When the randomness is implicit, we denote y←A(x). For an integer n∈N, let [n]=1,…,n.


### 2.1. Signatures

A signature scheme consists of the following three algorithms:(i)
SigKg: this is the key generation algorithm that takes as an input a security parameter 1λ and outputs a pair (vk,sk) of a verification key and a signing key.(ii)
Sign: this is the signing algorithm that takes as inputs a signing key sk and a message M and outputs a signature s on the message M.(iii)
Verify: this is the verification algorithm that takes as inputs a verification key vk, a message M, and a signature s and outputs ⊤ or ⊥, which, respectively, indicate “accept” or “reject.”For correctness, we require that for allλ∈N, all pairs (vk,sk)←SigKg(1λ), and all messages M, it is satisfied thatVerify(vk,M,Sign(sk,M)) = ⊤.A signature scheme is said to beexistentially unforgeable under chosen-message attacks (EUF-CMA), if for any probabilistic polynomial-time adversary the advantage in the following game is negligible:(i)
Setup: the challenger runs (vk,sk)←SigKg(1λ) and gives the adversary vk.(ii)
Query: the adversary adaptively issues signing queries M in an arbitrary order. For each signing query M, the challenger runs s←Sign(sk,M) and returns s to the adversary.(iii)
Forge: finally the adversary outputs a forgery (M∗,s∗). The adversary wins the game if M∗ is not queried as a signing query, andVerify(vk,M∗,s∗) = ⊤.The advantage of the adversaryA is defined as the probability that the adversary wins and is denoted by AdvAEUF-CMA(λ).A signature scheme is said to bea strongly unforgeable one-time signature scheme, if for any probabilistic polynomial-time adversary the advantage in the following game is negligible:(i)
Setup: the challenger runs (vk,sk)←SigKg(1λ) and gives the adversary vk.(ii)
Query: the adversary issues a signing query Monly once. The challenger runs s←Sign(sk,M) and returns s to the adversary.(iii)
Forge: finally the adversary outputs a forgery (M∗,s∗). The adversary wins the game if (M∗,s∗)≠(M,s) andVerify(vk,M∗,s∗) = ⊤.The advantage of the adversaryA is defined as the probability that the adversary wins and is denoted by AdvAOT-CMA(λ).


### 2.2. Tag-Based Key Encapsulation Mechanism

A tag-based key encapsulation mechanism (tag-based KEM) (Tag-based encryption, an encryption analogue of tag-based KEM, is originally introduced as “encryption with labels” by Shoup and Gennaro [49]. Tag-based KEM is different from “tag-KEM”, introduced by Abe, Gennaro, Kurosawa, and Shoup [50]. However, any chosen-ciphertext secure tag-KEM can be immediately converted to a tag-based KEM satisfying security that is sufficient for our purpose) [51, 52] scheme consists of the following three algorithms:(i)
TKg: this is the key generation algorithm that takes as an input a security parameter 1λ and outputs a pair (pk,dk) of a public key and a secret key.(ii)
TEnc: this is the encapsulation algorithm that takes as inputs a public key pk and a tag t and outputs (C,K) where a ciphertext C for a tag t encapsulates a session key K∈KPKE and KPKE is the session key space associated with the scheme.(iii)
TDec: this is the deterministic decapsulation algorithm that takes as inputs a secret key dk, a tag t, and a ciphertext C and outputs a decapsulated session key K or a special symbol ⊥ indicating an invalid ciphertext.For correctness, we require that for allλ∈N, all (pk,dk)←TKg(1λ), all tags t∈0,1∗, and all (C,K)←TEnc(pk,t), it holds thatTDec(dk,t,C) = K.A tag-based KEM is said to beselective-tag weakly chosen-ciphertext secure if for any probabilistic polynomial-time adversary the advantage in the following game is negligible:(i)
Setup: the adversary is given a security parameter 1λ and outputs a challenge tag t∗. The challenger runs (pk,dk)←TKg(1λ), then the challenger gives the adversary the public key pk.(ii)
Query (Phase I): the adversary issues decryption queries (t,C) in an arbitrary order. The challenger runs K←TDec(dk,t,C) and returns K to the adversary. Here the adversary is not allowed to issue queries with t=t∗.(iii)
Challenge: at some point the adversary requests a challenge. The challenger chooses a random bit b←0,1, runs (K0,C∗)←TEnc(pk,t∗), chooses K1←KPKE, and sends (C∗,Kb).(iv)
Query (Phase II): after receiving the challenge the adversary is again allowed to issue decryption queries. The same restriction for queries is applied as before.(v)
Guess: finally the adversary outputs a bit b′. The adversary wins the game if b=b′.The advantage of the adversaryA is defined by Pr[b=b′]-1/2 and is denoted by AdvAtb-KEM(λ).


### 2.3. Identity-Based KEM and Itsk-Resilient Variant

An identity-based KEM [8] consists of the following four algorithms:(i)
ISetup: this is the setup algorithm that takes as inputs a security parameter 1λ and a collusion threshold 1k and outputs a pair (par,mk) of a public parameter and a master secret key.(ii)
IExt: this is the key extraction algorithm that takes as inputs a master secret key mk and an identity ID and outputs a user decapsulation key dkID.(iii)
IEnc: this is the encapsulation algorithm that takes as inputs a public parameter par and an identity ID and outputs (C,K) where a ciphertext C for an identity ID encapsulates a session key K∈KIBE and KIBE is the session key space associated with the scheme.(iv)
IDec: this is the deterministic decapsulation algorithm that takes as inputs dkID, ID, and C and outputs a decapsulated session key K or a special symbol ⊥ indicating an invalid ciphertext.For correctness, we require that for allλ∈N, all k∈N, all (par,mk)←ISetup(1λ,1k), all identities ID∈{0,1}∗, all dkID←IExt(mk,ID), and all (C,K)←IEnc(par,ID), it holds thatIDec(dkID,ID,C) = K.An identity-based KEM is said to bek-resilient if for any probabilistic polynomial-time adversary the advantage in the following game is negligible:(i)
Setup: the challenger runs (par,mk)←ISetup(1λ), then the challenger gives the adversary the public parameter par.(ii)
Query (Phase I): the adversary issues extraction queries ID in an arbitrary order. The challenger runs dkID←IExt(mk,ID) and returns dkID to the adversary. The total number (the summation of those in Phase I and Phase II) of extraction queries during the game is restricted to be smaller than or equal to k.(iii)
Challenge: at some point the adversary requests a challenge with an identity ID∗. The challenger chooses a random bit b←0,1, runs (C∗,K0)←IEnc(par,ID∗), chooses K1←KIBE, and sends (C∗,Kb). The adversary is not allowed to request a challenge with an identity whose user decapsulation key is queried before.(iv)
Query (Phase II): after receiving the challenge the adversary is again allowed to issue extraction queries. This time querying a user decapsulation key for ID∗ is disallowed.(v)
Guess: finally the adversary outputs a bit b′. The adversary wins the game if b=b′.The advantage of the adversaryA is defined by Prb=b′-1/2 and is denoted by AdvAib-KEM(λ).Afully secure IBE scheme is defined analogously with the difference that the setup algorithm does not take 1k as an input and in the game the number of extraction queries is unbounded.


### 2.4. Adaptive Noninteractive Zero-Knowledge Proofs

A noninteractive proof system for a polynomial-time computable relationR consists of the following three algorithms:(i)
K: this is the common reference string generation algorithm that takes as an input a security parameter 1λ and outputs a common reference string Σ.(ii)
P: this is the proof algorithm that takes as inputs a common reference string Σ, a statement x, and a witness w, where R(x,w)=⊤ and outputs a proof π.(iii)
V: this is the verification algorithm that takes as inputs a common reference string Σ, a statement x, and a proof π and outputs either ⊤ or ⊥.We say that a noninteractive proof system(K,P,V) has perfect completeness, if for all λ∈N, for all (x,w) such that R(x,w)=⊤, for all Σ←K(1λ), for all π←P(Σ,x,w) it holds that V(Σ,x,π)=⊤.A noninteractive proof system is said to have adaptive perfect soundness, if for any probabilistic polynomial-time adversary the advantage in the following game is equal to zero:(i)
Setup: the challenger runs Σ←K(1λ) and gives the adversary the common reference string Σ.(ii)
Forge: the adversary outputs a pair (x,π) of a statement and a proof. The adversary wins if V(Σ,x,π)=⊤ and R(x,w)=⊥ for any w.The advantage of the adversaryA is defined by the probability that the adversary wins and is denoted by AdvAsound(λ).We say that a noninteractive proof system(K,P,V) is adaptively zero-knowledge if there is a pair of algorithms (S1,S2) such that for any probabilistic polynomial-time adversary the advantage in the following game is negligible:(i)
Setup: the challenger generates a bit b←0,1. If b=0 the challenger runs Σ←K(1λ). If b=1 the challenger runs (Σ,τ)←S1(1λ). Then the challenger gives the adversary the common reference string Σ.(ii)
Query: the adversary is allowed to issue a query (x,w) such that R(x,w)=⊤only once. If b=0 the challenger runs π←P(Σ,x,w). If b=1 the challenger runs π←S2(Σ,τ,x). The challenger gives the adversary π.(iii)
Guess: finally the adversary outputs a bit b′.The advantage of the adversaryA is defined by Prb=b′-1/2 and is denoted by AdvAzk(λ).


### 2.5. Computational Assumptions

LetG be a probabilistic polynomial-time algorithm that takes a security parameter 1λ as an input and generates a parameter (p,G,GT,e,g) ofbilinear groups, where p is a λ-bit prime, G and GT are groups of order p, e is a bilinear map from G×G to GT, and g is a generator of G. We then describe several computational assumptions on which the proposed schemes are based.The q -Strong Diffie-Hellman Assumption [27]. Let q∈N and let (p,G,GT,e,g)←G(1λ), γ←Zp and Ai←gγi for i∈[q]. The q-strong Diffie-Hellman problem in G is stated as follows: given (g,(Ai)i∈[q]), output (c,g1/(γ+c)) where c∈Zp. The advantage of an algorithm A in solving the q-strong Diffie-Hellman problem is defined as (1)AdvAq-SDHλ=PrAg,Aii∈q=c,g1/γ+c∧c∈Zp.We say that the q-strong Diffie-Hellman (q-SDH) assumption holds if AdvAq-SDH(λ) is negligible in λ for any probabilistic polynomial-time algorithm A.For some fixed baseg∈G and a fixed group element w=gγ∈G we say that a pair (x,A)∈Zp×G is anSDH pair if A is equal to g1/(γ+x).The Decision Linear Assumption [10]. Let (p,G,GT,e,g)←G(1λ), u, v, h←G∖1, α, β←Zp, and γ←Zp∖α+β. The decision linear problem in G is stated as follows: distinguish the distribution (u,v,h,uα,vβ,hα+β) from the distribution (u,v,h,uα,vβ,hγ). The advantage of an algorithm A in solving the decision linear problem is defined as (2)AdvADLINλ=PrAu,v,h,uα,vβ,hα+β=1-PrAu,v,h,uα,vβ,hγ=1.We say that the decision linear (DLIN) assumption holds if AdvADLIN(λ) is negligible in λ for any probabilistic polynomial-time algorithm A.For some fixed basesu, v, h∈G, we say that a tuple (T1,T2,T3) is alinear tuple if there exist exponents α, β∈Zp that satisfy (T1,T2,T3)=(uα,vβ,hα+β).The Decision Bilinear Diffie-Hellman Assumption [53]. Let (p,G,GT,e,g)←G(1λ) and a, b, c, d←Zp. The decision bilinear Diffie-Hellman problem in (G,GT) is stated as follows: distinguish the distribution (g,ga,gb,gc,e(g,g)abc) from the distribution (g,ga,gb,gc,e(g,g)d). The advantage of an algorithm A in solving the decision bilinear Diffie-Hellman problem is defined as (3)AdvADBDHλ=PrAg,ga,gb,gc,eg,gabc=1-PrAg,ga,gb,gc,eg,gd=1.We say that the decision bilinear Diffie-Hellman (DBDH) assumption holds if AdvADBDH(λ) is negligible in λ for any probabilistic polynomial-time algorithm A.The Simultaneous Flexible Pairing Assumption [54]. Let (p,G,GT,e,g)←G(1λ), gz, gr, hz, hu←G are generators of G and (a,a~), (b,b~)←G×G. For i∈[q], let Ri=(zi,ri,si,ti,ui,vi,wi)∈G7 which satisfies e(a,a~)=e(gz,zi)e(gr,ri)e(si,ti) and e(b,b~)=e(hz,zi)e(hu,ui)e(vi,wi). The simultaneous flexible pairing problem is stated as follows: given (gz,gr,hz,hu,a,a~,b,b~) and R1,…,Rq, output R∗=(z∗,r∗,s∗,t∗,u∗,v∗,w∗) where e(a,a~)=e(gz,z∗)e(gr,r∗)e(s∗,t∗) and e(b,b~)=e(hz,z∗)e(hu,u∗)e(v∗,w∗) satisfying z∗≠1 and z∗≠zi for every i. The advantage of an algorithm A in solving the simultaneous flexible pairing problem is defined as(4)AdvASFPλ=PrAgz,gr,hz,hu,a,a~,b,b~,Rii∈q=z∗,r∗,s∗,t∗,u∗,v∗,w∗∧ea,a~=egz,z∗egr,r∗es∗,t∗∧eb,b~=ehz,z∗ehu,u∗ev∗,w∗∧z∗≠1∧z∗≠zi∀i.We say that the simultaneous flexible pairing (SFP) assumption holds if AdvASFP(λ) is negligible in λ for any probabilistic polynomial-time algorithm A.


## 2.1. Signatures

A signature scheme consists of the following three algorithms:(i)
SigKg: this is the key generation algorithm that takes as an input a security parameter 1λ and outputs a pair (vk,sk) of a verification key and a signing key.(ii)
Sign: this is the signing algorithm that takes as inputs a signing key sk and a message M and outputs a signature s on the message M.(iii)
Verify: this is the verification algorithm that takes as inputs a verification key vk, a message M, and a signature s and outputs ⊤ or ⊥, which, respectively, indicate “accept” or “reject.”For correctness, we require that for allλ∈N, all pairs (vk,sk)←SigKg(1λ), and all messages M, it is satisfied thatVerify(vk,M,Sign(sk,M)) = ⊤.A signature scheme is said to beexistentially unforgeable under chosen-message attacks (EUF-CMA), if for any probabilistic polynomial-time adversary the advantage in the following game is negligible:(i)
Setup: the challenger runs (vk,sk)←SigKg(1λ) and gives the adversary vk.(ii)
Query: the adversary adaptively issues signing queries M in an arbitrary order. For each signing query M, the challenger runs s←Sign(sk,M) and returns s to the adversary.(iii)
Forge: finally the adversary outputs a forgery (M∗,s∗). The adversary wins the game if M∗ is not queried as a signing query, andVerify(vk,M∗,s∗) = ⊤.The advantage of the adversaryA is defined as the probability that the adversary wins and is denoted by AdvAEUF-CMA(λ).A signature scheme is said to bea strongly unforgeable one-time signature scheme, if for any probabilistic polynomial-time adversary the advantage in the following game is negligible:(i)
Setup: the challenger runs (vk,sk)←SigKg(1λ) and gives the adversary vk.(ii)
Query: the adversary issues a signing query Monly once. The challenger runs s←Sign(sk,M) and returns s to the adversary.(iii)
Forge: finally the adversary outputs a forgery (M∗,s∗). The adversary wins the game if (M∗,s∗)≠(M,s) andVerify(vk,M∗,s∗) = ⊤.The advantage of the adversaryA is defined as the probability that the adversary wins and is denoted by AdvAOT-CMA(λ).


## 2.2. Tag-Based Key Encapsulation Mechanism

A tag-based key encapsulation mechanism (tag-based KEM) (Tag-based encryption, an encryption analogue of tag-based KEM, is originally introduced as “encryption with labels” by Shoup and Gennaro [49]. Tag-based KEM is different from “tag-KEM”, introduced by Abe, Gennaro, Kurosawa, and Shoup [50]. However, any chosen-ciphertext secure tag-KEM can be immediately converted to a tag-based KEM satisfying security that is sufficient for our purpose) [51, 52] scheme consists of the following three algorithms:(i)
TKg: this is the key generation algorithm that takes as an input a security parameter 1λ and outputs a pair (pk,dk) of a public key and a secret key.(ii)
TEnc: this is the encapsulation algorithm that takes as inputs a public key pk and a tag t and outputs (C,K) where a ciphertext C for a tag t encapsulates a session key K∈KPKE and KPKE is the session key space associated with the scheme.(iii)
TDec: this is the deterministic decapsulation algorithm that takes as inputs a secret key dk, a tag t, and a ciphertext C and outputs a decapsulated session key K or a special symbol ⊥ indicating an invalid ciphertext.For correctness, we require that for allλ∈N, all (pk,dk)←TKg(1λ), all tags t∈0,1∗, and all (C,K)←TEnc(pk,t), it holds thatTDec(dk,t,C) = K.A tag-based KEM is said to beselective-tag weakly chosen-ciphertext secure if for any probabilistic polynomial-time adversary the advantage in the following game is negligible:(i)
Setup: the adversary is given a security parameter 1λ and outputs a challenge tag t∗. The challenger runs (pk,dk)←TKg(1λ), then the challenger gives the adversary the public key pk.(ii)
Query (Phase I): the adversary issues decryption queries (t,C) in an arbitrary order. The challenger runs K←TDec(dk,t,C) and returns K to the adversary. Here the adversary is not allowed to issue queries with t=t∗.(iii)
Challenge: at some point the adversary requests a challenge. The challenger chooses a random bit b←0,1, runs (K0,C∗)←TEnc(pk,t∗), chooses K1←KPKE, and sends (C∗,Kb).(iv)
Query (Phase II): after receiving the challenge the adversary is again allowed to issue decryption queries. The same restriction for queries is applied as before.(v)
Guess: finally the adversary outputs a bit b′. The adversary wins the game if b=b′.The advantage of the adversaryA is defined by Pr[b=b′]-1/2 and is denoted by AdvAtb-KEM(λ).


## 2.3. Identity-Based KEM and Itsk-Resilient Variant

An identity-based KEM [8] consists of the following four algorithms:(i)
ISetup: this is the setup algorithm that takes as inputs a security parameter 1λ and a collusion threshold 1k and outputs a pair (par,mk) of a public parameter and a master secret key.(ii)
IExt: this is the key extraction algorithm that takes as inputs a master secret key mk and an identity ID and outputs a user decapsulation key dkID.(iii)
IEnc: this is the encapsulation algorithm that takes as inputs a public parameter par and an identity ID and outputs (C,K) where a ciphertext C for an identity ID encapsulates a session key K∈KIBE and KIBE is the session key space associated with the scheme.(iv)
IDec: this is the deterministic decapsulation algorithm that takes as inputs dkID, ID, and C and outputs a decapsulated session key K or a special symbol ⊥ indicating an invalid ciphertext.For correctness, we require that for allλ∈N, all k∈N, all (par,mk)←ISetup(1λ,1k), all identities ID∈{0,1}∗, all dkID←IExt(mk,ID), and all (C,K)←IEnc(par,ID), it holds thatIDec(dkID,ID,C) = K.An identity-based KEM is said to bek-resilient if for any probabilistic polynomial-time adversary the advantage in the following game is negligible:(i)
Setup: the challenger runs (par,mk)←ISetup(1λ), then the challenger gives the adversary the public parameter par.(ii)
Query (Phase I): the adversary issues extraction queries ID in an arbitrary order. The challenger runs dkID←IExt(mk,ID) and returns dkID to the adversary. The total number (the summation of those in Phase I and Phase II) of extraction queries during the game is restricted to be smaller than or equal to k.(iii)
Challenge: at some point the adversary requests a challenge with an identity ID∗. The challenger chooses a random bit b←0,1, runs (C∗,K0)←IEnc(par,ID∗), chooses K1←KIBE, and sends (C∗,Kb). The adversary is not allowed to request a challenge with an identity whose user decapsulation key is queried before.(iv)
Query (Phase II): after receiving the challenge the adversary is again allowed to issue extraction queries. This time querying a user decapsulation key for ID∗ is disallowed.(v)
Guess: finally the adversary outputs a bit b′. The adversary wins the game if b=b′.The advantage of the adversaryA is defined by Prb=b′-1/2 and is denoted by AdvAib-KEM(λ).Afully secure IBE scheme is defined analogously with the difference that the setup algorithm does not take 1k as an input and in the game the number of extraction queries is unbounded.


## 2.4. Adaptive Noninteractive Zero-Knowledge Proofs

A noninteractive proof system for a polynomial-time computable relationR consists of the following three algorithms:(i)
K: this is the common reference string generation algorithm that takes as an input a security parameter 1λ and outputs a common reference string Σ.(ii)
P: this is the proof algorithm that takes as inputs a common reference string Σ, a statement x, and a witness w, where R(x,w)=⊤ and outputs a proof π.(iii)
V: this is the verification algorithm that takes as inputs a common reference string Σ, a statement x, and a proof π and outputs either ⊤ or ⊥.We say that a noninteractive proof system(K,P,V) has perfect completeness, if for all λ∈N, for all (x,w) such that R(x,w)=⊤, for all Σ←K(1λ), for all π←P(Σ,x,w) it holds that V(Σ,x,π)=⊤.A noninteractive proof system is said to have adaptive perfect soundness, if for any probabilistic polynomial-time adversary the advantage in the following game is equal to zero:(i)
Setup: the challenger runs Σ←K(1λ) and gives the adversary the common reference string Σ.(ii)
Forge: the adversary outputs a pair (x,π) of a statement and a proof. The adversary wins if V(Σ,x,π)=⊤ and R(x,w)=⊥ for any w.The advantage of the adversaryA is defined by the probability that the adversary wins and is denoted by AdvAsound(λ).We say that a noninteractive proof system(K,P,V) is adaptively zero-knowledge if there is a pair of algorithms (S1,S2) such that for any probabilistic polynomial-time adversary the advantage in the following game is negligible:(i)
Setup: the challenger generates a bit b←0,1. If b=0 the challenger runs Σ←K(1λ). If b=1 the challenger runs (Σ,τ)←S1(1λ). Then the challenger gives the adversary the common reference string Σ.(ii)
Query: the adversary is allowed to issue a query (x,w) such that R(x,w)=⊤only once. If b=0 the challenger runs π←P(Σ,x,w). If b=1 the challenger runs π←S2(Σ,τ,x). The challenger gives the adversary π.(iii)
Guess: finally the adversary outputs a bit b′.The advantage of the adversaryA is defined by Prb=b′-1/2 and is denoted by AdvAzk(λ).


## 2.5. Computational Assumptions

LetG be a probabilistic polynomial-time algorithm that takes a security parameter 1λ as an input and generates a parameter (p,G,GT,e,g) ofbilinear groups, where p is a λ-bit prime, G and GT are groups of order p, e is a bilinear map from G×G to GT, and g is a generator of G. We then describe several computational assumptions on which the proposed schemes are based.The q -Strong Diffie-Hellman Assumption [27]. Let q∈N and let (p,G,GT,e,g)←G(1λ), γ←Zp and Ai←gγi for i∈[q]. The q-strong Diffie-Hellman problem in G is stated as follows: given (g,(Ai)i∈[q]), output (c,g1/(γ+c)) where c∈Zp. The advantage of an algorithm A in solving the q-strong Diffie-Hellman problem is defined as (1)AdvAq-SDHλ=PrAg,Aii∈q=c,g1/γ+c∧c∈Zp.We say that the q-strong Diffie-Hellman (q-SDH) assumption holds if AdvAq-SDH(λ) is negligible in λ for any probabilistic polynomial-time algorithm A.For some fixed baseg∈G and a fixed group element w=gγ∈G we say that a pair (x,A)∈Zp×G is anSDH pair if A is equal to g1/(γ+x).The Decision Linear Assumption [10]. Let (p,G,GT,e,g)←G(1λ), u, v, h←G∖1, α, β←Zp, and γ←Zp∖α+β. The decision linear problem in G is stated as follows: distinguish the distribution (u,v,h,uα,vβ,hα+β) from the distribution (u,v,h,uα,vβ,hγ). The advantage of an algorithm A in solving the decision linear problem is defined as (2)AdvADLINλ=PrAu,v,h,uα,vβ,hα+β=1-PrAu,v,h,uα,vβ,hγ=1.We say that the decision linear (DLIN) assumption holds if AdvADLIN(λ) is negligible in λ for any probabilistic polynomial-time algorithm A.For some fixed basesu, v, h∈G, we say that a tuple (T1,T2,T3) is alinear tuple if there exist exponents α, β∈Zp that satisfy (T1,T2,T3)=(uα,vβ,hα+β).The Decision Bilinear Diffie-Hellman Assumption [53]. Let (p,G,GT,e,g)←G(1λ) and a, b, c, d←Zp. The decision bilinear Diffie-Hellman problem in (G,GT) is stated as follows: distinguish the distribution (g,ga,gb,gc,e(g,g)abc) from the distribution (g,ga,gb,gc,e(g,g)d). The advantage of an algorithm A in solving the decision bilinear Diffie-Hellman problem is defined as (3)AdvADBDHλ=PrAg,ga,gb,gc,eg,gabc=1-PrAg,ga,gb,gc,eg,gd=1.We say that the decision bilinear Diffie-Hellman (DBDH) assumption holds if AdvADBDH(λ) is negligible in λ for any probabilistic polynomial-time algorithm A.The Simultaneous Flexible Pairing Assumption [54]. Let (p,G,GT,e,g)←G(1λ), gz, gr, hz, hu←G are generators of G and (a,a~), (b,b~)←G×G. For i∈[q], let Ri=(zi,ri,si,ti,ui,vi,wi)∈G7 which satisfies e(a,a~)=e(gz,zi)e(gr,ri)e(si,ti) and e(b,b~)=e(hz,zi)e(hu,ui)e(vi,wi). The simultaneous flexible pairing problem is stated as follows: given (gz,gr,hz,hu,a,a~,b,b~) and R1,…,Rq, output R∗=(z∗,r∗,s∗,t∗,u∗,v∗,w∗) where e(a,a~)=e(gz,z∗)e(gr,r∗)e(s∗,t∗) and e(b,b~)=e(hz,z∗)e(hu,u∗)e(v∗,w∗) satisfying z∗≠1 and z∗≠zi for every i. The advantage of an algorithm A in solving the simultaneous flexible pairing problem is defined as(4)AdvASFPλ=PrAgz,gr,hz,hu,a,a~,b,b~,Rii∈q=z∗,r∗,s∗,t∗,u∗,v∗,w∗∧ea,a~=egz,z∗egr,r∗es∗,t∗∧eb,b~=ehz,z∗ehu,u∗ev∗,w∗∧z∗≠1∧z∗≠zi∀i.We say that the simultaneous flexible pairing (SFP) assumption holds if AdvASFP(λ) is negligible in λ for any probabilistic polynomial-time algorithm A.


## 3. Group Signatures with Message-Dependent Opening

In this section we introduce the syntax and security definitions for GS-MDO. As an ordinary group signature scheme, a GS-MDO scheme allows group members to sign a message anonymously, that is, without revealing their identities but only showing that one of the group members actually signed. In exceptional cases, a designated third party, called the opener, can “open” exceptional signatures to identify the originator of the signatures. In contrast to ordinary group signature schemes, a GS-MDO scheme requires the opener to cooperate with another authority, called the admitter, to open signatures. The admitter issues a message-specific token, and the opener is able to open a signature on the messageonly when a token for the message is issued from the admitter.In this section, we define the formal model and the security requirements of GS-MDO.


### 3.1. The Model of GS-MDO

Formally, a GS-MDO scheme consists of the following five probabilistic polynomial-time algorithms:(i)
GKg: this is the key generation algorithm that takes as inputs a security parameter 1λ, the number of group members 1n, and the maximum number 1k of message-specific tokens that can be issued and outputs a group public key gpk, an admitting key ak, an opening key ok, and n group signing keys (gski)i∈[n]. We note that the input 1k is omitted when the number of message-specific tokens that can be issued is unbounded.(ii)
GSig: this is the signing algorithm that takes as inputs a group public key gpk, a group signing key gski, and a message M and outputs a group signature σ.(iii)
Td: this is the message-specific token generation algorithm that takes as inputs a group public key gpk, an admitting key ak, and a message M and outputs a token tM for M.(iv)
GVf: this is the verification algorithm that takes as inputs a group public key gpk, a message M, and a group signature σ and outputs ⊤ (that means accept) or ⊥ (that means reject).(v)
Open: this is the opening algorithm that takes as inputs a group public key gpk, an opening key ok, a message M, a group signature σ, and a message-specific token tM and outputs a user index i∈N or ⊥.For correctness, we require that for allλ, n, k∈N, for all (gpk,ak,ok,gskii∈[n])←GKg(1λ,1n,1k), for all messages M∈0,1∗ and all user i∈[n], it holds thatGVf(gpk, M,GSig(gpk,gski,M)) = ⊤ andOpen(gpk, ok, M,GSig(gpk,gski,M),Td(gpk,ak,M)) = i.In the above scenario, the signing keysgskii∈[n], the opening key ok, and the admitting key ak are generated by theGKg algorithm in the setup phase. Then, ok is given to the opener and ak is given to the admitter. A signer can make a group signature σ by using theGSig algorithm, and all entities can verify the group signature by theGVf algorithm and public key gpk. This setting is the same as ordinary group signatures, except the group manager’s key is divided into ok and ak. In exceptional cases, the admitter issues a message-specific token tM by using theTd algorithm. Moreover, the opener can identify the signer of a group signature by using theOpen algorithm only when the opener received tM from the admitter.


### 3.2. Security Requirements

We introduce the security notion for GS-MDO. In contract to ordinary group signatures, we need to take care of the MDO property.Ordinary group signatures are required to ensure two security notions, anonymity and traceability, whereas we have to further ensure two types of anonymity in the case of GS-MDO that are related to the original motivation for the introduction of the admitter. The introduction of the admitter is intended to strengthen signers’ anonymity against the authorities as much as possible. To capture this intention, we define the indistinguishability of the originator of a signature in the strong setting where the opening key is given to the adversary (opener anonymity). As a counterpart of this, we also define indistinguishability in the setting where the admitting key is given to the adversary (admitter anonymity). Note that we do not consider the situation in which the adversary obtains both the opening key and the admitting key because in this situation the adversary can open any signature by itself.For traceability, we use the same definition as for the ordinary group signatures, in which the authorities are entirely corrupted by the adversary, since even ordinary group signature schemes ensure this level of traceability against entirely corrupted openers.


#### 3.2.1. Opener Anonymity

Here we give the formal definition of anonymity against the opener, which we callopener anonymity. It is formalized as the indistinguishability of signatures of two different signers of the adversary’s choice. Opener anonymity is defined by requiring that no adversary has nonnegligible advantage in distinguishing signatures. We again remark that contrary to ordinary group signatures, the adversary is allowed to have the opening key. This is intended for modeling “anonymity against the opener.”Definition 1.
A GS-MDO scheme is said to haveopener anonymity if for any probabilistic polynomial-time adversary A the advantage in the following game is negligible: (i)
Setup: the challenger runsGKg(1λ,1n,1k) to obtain (gpk,ok,ak,(gski)i∈[n]). The challenger sends (gpk,ok,(gski)i∈[n]) to A.(ii)
Token Query (Phase I): A adaptively issues token queries M in an arbitrary order. The challenger runs tM←Td(gpk,ak,M) and returns tM to A.(iii)
Challenge: at some point A requests a challenge for i0, i1∈[n], and a message M∗. The challenger chooses a random bit b, runs σ∗←GSig(gpk,gskib,M∗), and sends σ∗ to A. A is not allowed to request a challenge with a message M∗ whose token is previously queried.(iv)
Token Query (Phase II): after receiving the challenge A is again allowed to issue token queries. This time querying a token for M∗ is disallowed.(v)
Guess: finally A outputs a bit b′. A wins the game if b=b′. A wins the game if b=b′.The advantage ofA is defined by Prb=b′-1/2 and is denoted by AdvAopener-anony(λ). We also say that a GS-MDO scheme hasopener anonymity withk-bounded tokens if any probabilistic polynomial-time adversary A which issues at most k token queries in total has negligible advantage.


#### 3.2.2. Admitter Anonymity

We next give the definition of anonymity against the admitter, which we calladmitter anonymity. It is formalized in a similar manner to opener anonymity. That is, admitter anonymity requires signatures of two different signers to be indistinguishable even when the adversary is given the admitting key. We emphasize that our definition of opener anonymity is categorized as so-calledCCA-anonymity. This means that the adversary in the security game is allowed to access the opening oracle. The formal definition is as follows:Definition 2.
A GS-MDO scheme is said to haveadmitter anonymity if for any probabilistic polynomial-time adversary A the advantage in the following game is negligible: (i)
Setup: the challenger runsGKg(1λ,1n,1k) to obtain (gpk,ok,ak,(gski)i∈[n]). The challenger sends (gpk,ak,(gski)i∈[n]) to A.(ii)
Open Query (Phase I): A adaptively issues open queries (M,σ) in an arbitrary order. The challenger finds a recorded tM which is a token for M, and if not found, runs tM←Td(gpk,ak,M), and stores tM. The challenger runs i←GSig(gpk,ok,M,σ,tM) and returns i to A.(iii)
Challenge: at some point A requests a challenge for i0, i1∈[n] and a message M∗. The challenger chooses a random bit b, runs σ∗←GSig(gpk,gskib,M∗) and sends σ∗ to A.(iv)
Open Query (Phase II): after receiving the challenge A is again allowed to issue open queries. This time querying an opening of (M∗,σ∗) is disallowed.(v)
Guess: finally A outputs a bit b′. A wins the game if b=b′.The advantage ofA is defined by Prb=b′-1/2 and is denoted by AdvAadmitter-anony(λ).Notice that the number of opening queries the adversary issues is unbounded (but of course polynomially many).


#### 3.2.3. Traceability

The last notion istraceability, which requires that even if the opener and the admitter collude and they further adaptively corrupt some group members, the corrupted parties can produce neither forged signatures nor untraceable signatures. We stress that in contrast to the case of the anonymity notions, this case considers the collusion of two authorities.Definition 3.
A GS-MDO scheme is said to havetraceability if for any probabilistic polynomial-time adversary A the advantage in the following game is negligible: (i)
Setup: the challenger runsGKg(1λ,1n,1k) to obtain (gpk,ok,ak,gskii∈[n]). The challenger sends (gpk,ok,ak) to A.(ii)
Query: A adaptively issues the following two types of queries:
(1)
A issues akey revealing queryi. The challenger returns gski to A.(2)
A issues asigning query(i,M). The challenger runs σ←GSig(gpk,gski,M) and returns σ.(iii)
Forge: finally A outputs a forgery (M∗,σ∗). A wins ifGVf(gpk,M∗,σ∗) = ⊤ and one of the following two conditions holds:
(a)
Open(gpk,ok,M∗,σ∗,Td(gpk,ak,M∗)) = ⊥, or(b)
all the following conditions hold,
∗Open(gpk,ok,M∗,σ∗,Td(gpk,ak,M∗)) = i∗≠⊥, and∗ neither a key revealing query for the user i∗ nor a signing query for (i∗,M∗) is submitted.The advantage ofA is defined by Pr[Awins] and denoted by AdvAtrace(λ).


## 3.1. The Model of GS-MDO

Formally, a GS-MDO scheme consists of the following five probabilistic polynomial-time algorithms:(i)
GKg: this is the key generation algorithm that takes as inputs a security parameter 1λ, the number of group members 1n, and the maximum number 1k of message-specific tokens that can be issued and outputs a group public key gpk, an admitting key ak, an opening key ok, and n group signing keys (gski)i∈[n]. We note that the input 1k is omitted when the number of message-specific tokens that can be issued is unbounded.(ii)
GSig: this is the signing algorithm that takes as inputs a group public key gpk, a group signing key gski, and a message M and outputs a group signature σ.(iii)
Td: this is the message-specific token generation algorithm that takes as inputs a group public key gpk, an admitting key ak, and a message M and outputs a token tM for M.(iv)
GVf: this is the verification algorithm that takes as inputs a group public key gpk, a message M, and a group signature σ and outputs ⊤ (that means accept) or ⊥ (that means reject).(v)
Open: this is the opening algorithm that takes as inputs a group public key gpk, an opening key ok, a message M, a group signature σ, and a message-specific token tM and outputs a user index i∈N or ⊥.For correctness, we require that for allλ, n, k∈N, for all (gpk,ak,ok,gskii∈[n])←GKg(1λ,1n,1k), for all messages M∈0,1∗ and all user i∈[n], it holds thatGVf(gpk, M,GSig(gpk,gski,M)) = ⊤ andOpen(gpk, ok, M,GSig(gpk,gski,M),Td(gpk,ak,M)) = i.In the above scenario, the signing keysgskii∈[n], the opening key ok, and the admitting key ak are generated by theGKg algorithm in the setup phase. Then, ok is given to the opener and ak is given to the admitter. A signer can make a group signature σ by using theGSig algorithm, and all entities can verify the group signature by theGVf algorithm and public key gpk. This setting is the same as ordinary group signatures, except the group manager’s key is divided into ok and ak. In exceptional cases, the admitter issues a message-specific token tM by using theTd algorithm. Moreover, the opener can identify the signer of a group signature by using theOpen algorithm only when the opener received tM from the admitter.


## 3.2. Security Requirements

We introduce the security notion for GS-MDO. In contract to ordinary group signatures, we need to take care of the MDO property.Ordinary group signatures are required to ensure two security notions, anonymity and traceability, whereas we have to further ensure two types of anonymity in the case of GS-MDO that are related to the original motivation for the introduction of the admitter. The introduction of the admitter is intended to strengthen signers’ anonymity against the authorities as much as possible. To capture this intention, we define the indistinguishability of the originator of a signature in the strong setting where the opening key is given to the adversary (opener anonymity). As a counterpart of this, we also define indistinguishability in the setting where the admitting key is given to the adversary (admitter anonymity). Note that we do not consider the situation in which the adversary obtains both the opening key and the admitting key because in this situation the adversary can open any signature by itself.For traceability, we use the same definition as for the ordinary group signatures, in which the authorities are entirely corrupted by the adversary, since even ordinary group signature schemes ensure this level of traceability against entirely corrupted openers.


### 3.2.1. Opener Anonymity

Here we give the formal definition of anonymity against the opener, which we callopener anonymity. It is formalized as the indistinguishability of signatures of two different signers of the adversary’s choice. Opener anonymity is defined by requiring that no adversary has nonnegligible advantage in distinguishing signatures. We again remark that contrary to ordinary group signatures, the adversary is allowed to have the opening key. This is intended for modeling “anonymity against the opener.”Definition 1.
A GS-MDO scheme is said to haveopener anonymity if for any probabilistic polynomial-time adversary A the advantage in the following game is negligible: (i)
Setup: the challenger runsGKg(1λ,1n,1k) to obtain (gpk,ok,ak,(gski)i∈[n]). The challenger sends (gpk,ok,(gski)i∈[n]) to A.(ii)
Token Query (Phase I): A adaptively issues token queries M in an arbitrary order. The challenger runs tM←Td(gpk,ak,M) and returns tM to A.(iii)
Challenge: at some point A requests a challenge for i0, i1∈[n], and a message M∗. The challenger chooses a random bit b, runs σ∗←GSig(gpk,gskib,M∗), and sends σ∗ to A. A is not allowed to request a challenge with a message M∗ whose token is previously queried.(iv)
Token Query (Phase II): after receiving the challenge A is again allowed to issue token queries. This time querying a token for M∗ is disallowed.(v)
Guess: finally A outputs a bit b′. A wins the game if b=b′. A wins the game if b=b′.The advantage ofA is defined by Prb=b′-1/2 and is denoted by AdvAopener-anony(λ). We also say that a GS-MDO scheme hasopener anonymity withk-bounded tokens if any probabilistic polynomial-time adversary A which issues at most k token queries in total has negligible advantage.


### 3.2.2. Admitter Anonymity

We next give the definition of anonymity against the admitter, which we calladmitter anonymity. It is formalized in a similar manner to opener anonymity. That is, admitter anonymity requires signatures of two different signers to be indistinguishable even when the adversary is given the admitting key. We emphasize that our definition of opener anonymity is categorized as so-calledCCA-anonymity. This means that the adversary in the security game is allowed to access the opening oracle. The formal definition is as follows:Definition 2.
A GS-MDO scheme is said to haveadmitter anonymity if for any probabilistic polynomial-time adversary A the advantage in the following game is negligible: (i)
Setup: the challenger runsGKg(1λ,1n,1k) to obtain (gpk,ok,ak,(gski)i∈[n]). The challenger sends (gpk,ak,(gski)i∈[n]) to A.(ii)
Open Query (Phase I): A adaptively issues open queries (M,σ) in an arbitrary order. The challenger finds a recorded tM which is a token for M, and if not found, runs tM←Td(gpk,ak,M), and stores tM. The challenger runs i←GSig(gpk,ok,M,σ,tM) and returns i to A.(iii)
Challenge: at some point A requests a challenge for i0, i1∈[n] and a message M∗. The challenger chooses a random bit b, runs σ∗←GSig(gpk,gskib,M∗) and sends σ∗ to A.(iv)
Open Query (Phase II): after receiving the challenge A is again allowed to issue open queries. This time querying an opening of (M∗,σ∗) is disallowed.(v)
Guess: finally A outputs a bit b′. A wins the game if b=b′.The advantage ofA is defined by Prb=b′-1/2 and is denoted by AdvAadmitter-anony(λ).Notice that the number of opening queries the adversary issues is unbounded (but of course polynomially many).


### 3.2.3. Traceability

The last notion istraceability, which requires that even if the opener and the admitter collude and they further adaptively corrupt some group members, the corrupted parties can produce neither forged signatures nor untraceable signatures. We stress that in contrast to the case of the anonymity notions, this case considers the collusion of two authorities.Definition 3.
A GS-MDO scheme is said to havetraceability if for any probabilistic polynomial-time adversary A the advantage in the following game is negligible: (i)
Setup: the challenger runsGKg(1λ,1n,1k) to obtain (gpk,ok,ak,gskii∈[n]). The challenger sends (gpk,ok,ak) to A.(ii)
Query: A adaptively issues the following two types of queries:
(1)
A issues akey revealing queryi. The challenger returns gski to A.(2)
A issues asigning query(i,M). The challenger runs σ←GSig(gpk,gski,M) and returns σ.(iii)
Forge: finally A outputs a forgery (M∗,σ∗). A wins ifGVf(gpk,M∗,σ∗) = ⊤ and one of the following two conditions holds:
(a)
Open(gpk,ok,M∗,σ∗,Td(gpk,ak,M∗)) = ⊥, or(b)
all the following conditions hold,
∗Open(gpk,ok,M∗,σ∗,Td(gpk,ak,M∗)) = i∗≠⊥, and∗ neither a key revealing query for the user i∗ nor a signing query for (i∗,M∗) is submitted.The advantage ofA is defined by Pr[Awins] and denoted by AdvAtrace(λ).


## 3.2.1. Opener Anonymity

Here we give the formal definition of anonymity against the opener, which we callopener anonymity. It is formalized as the indistinguishability of signatures of two different signers of the adversary’s choice. Opener anonymity is defined by requiring that no adversary has nonnegligible advantage in distinguishing signatures. We again remark that contrary to ordinary group signatures, the adversary is allowed to have the opening key. This is intended for modeling “anonymity against the opener.”Definition 1.
A GS-MDO scheme is said to haveopener anonymity if for any probabilistic polynomial-time adversary A the advantage in the following game is negligible: (i)
Setup: the challenger runsGKg(1λ,1n,1k) to obtain (gpk,ok,ak,(gski)i∈[n]). The challenger sends (gpk,ok,(gski)i∈[n]) to A.(ii)
Token Query (Phase I): A adaptively issues token queries M in an arbitrary order. The challenger runs tM←Td(gpk,ak,M) and returns tM to A.(iii)
Challenge: at some point A requests a challenge for i0, i1∈[n], and a message M∗. The challenger chooses a random bit b, runs σ∗←GSig(gpk,gskib,M∗), and sends σ∗ to A. A is not allowed to request a challenge with a message M∗ whose token is previously queried.(iv)
Token Query (Phase II): after receiving the challenge A is again allowed to issue token queries. This time querying a token for M∗ is disallowed.(v)
Guess: finally A outputs a bit b′. A wins the game if b=b′. A wins the game if b=b′.The advantage ofA is defined by Prb=b′-1/2 and is denoted by AdvAopener-anony(λ). We also say that a GS-MDO scheme hasopener anonymity withk-bounded tokens if any probabilistic polynomial-time adversary A which issues at most k token queries in total has negligible advantage.


## 3.2.2. Admitter Anonymity

We next give the definition of anonymity against the admitter, which we calladmitter anonymity. It is formalized in a similar manner to opener anonymity. That is, admitter anonymity requires signatures of two different signers to be indistinguishable even when the adversary is given the admitting key. We emphasize that our definition of opener anonymity is categorized as so-calledCCA-anonymity. This means that the adversary in the security game is allowed to access the opening oracle. The formal definition is as follows:Definition 2.
A GS-MDO scheme is said to haveadmitter anonymity if for any probabilistic polynomial-time adversary A the advantage in the following game is negligible: (i)
Setup: the challenger runsGKg(1λ,1n,1k) to obtain (gpk,ok,ak,(gski)i∈[n]). The challenger sends (gpk,ak,(gski)i∈[n]) to A.(ii)
Open Query (Phase I): A adaptively issues open queries (M,σ) in an arbitrary order. The challenger finds a recorded tM which is a token for M, and if not found, runs tM←Td(gpk,ak,M), and stores tM. The challenger runs i←GSig(gpk,ok,M,σ,tM) and returns i to A.(iii)
Challenge: at some point A requests a challenge for i0, i1∈[n] and a message M∗. The challenger chooses a random bit b, runs σ∗←GSig(gpk,gskib,M∗) and sends σ∗ to A.(iv)
Open Query (Phase II): after receiving the challenge A is again allowed to issue open queries. This time querying an opening of (M∗,σ∗) is disallowed.(v)
Guess: finally A outputs a bit b′. A wins the game if b=b′.The advantage ofA is defined by Prb=b′-1/2 and is denoted by AdvAadmitter-anony(λ).Notice that the number of opening queries the adversary issues is unbounded (but of course polynomially many).


## 3.2.3. Traceability

The last notion istraceability, which requires that even if the opener and the admitter collude and they further adaptively corrupt some group members, the corrupted parties can produce neither forged signatures nor untraceable signatures. We stress that in contrast to the case of the anonymity notions, this case considers the collusion of two authorities.Definition 3.
A GS-MDO scheme is said to havetraceability if for any probabilistic polynomial-time adversary A the advantage in the following game is negligible: (i)
Setup: the challenger runsGKg(1λ,1n,1k) to obtain (gpk,ok,ak,gskii∈[n]). The challenger sends (gpk,ok,ak) to A.(ii)
Query: A adaptively issues the following two types of queries:
(1)
A issues akey revealing queryi. The challenger returns gski to A.(2)
A issues asigning query(i,M). The challenger runs σ←GSig(gpk,gski,M) and returns σ.(iii)
Forge: finally A outputs a forgery (M∗,σ∗). A wins ifGVf(gpk,M∗,σ∗) = ⊤ and one of the following two conditions holds:
(a)
Open(gpk,ok,M∗,σ∗,Td(gpk,ak,M∗)) = ⊥, or(b)
all the following conditions hold,
∗Open(gpk,ok,M∗,σ∗,Td(gpk,ak,M∗)) = i∗≠⊥, and∗ neither a key revealing query for the user i∗ nor a signing query for (i∗,M∗) is submitted.The advantage ofA is defined by Pr[Awins] and denoted by AdvAtrace(λ).


## 4. Difficulty in Designing Efficient Constructions

In this section we discuss several difficulties in designing efficient GS-MDO schemes. We first observe the relationships between GS-MDO and other cryptographic primitives, and then we discuss the difficulty that lies in designing efficient constructions.Regarding the relationship with other primitives, we show that the existence of a GS-MDO scheme implies that of an IBE scheme. In other words, we will present a black-box construction of IBE from any GS-MDO scheme. The same holds for thek-resilient versions.This fact means that constructing a GS-MDO scheme is harder than IBE. Moreover, IBE is well known as a strong primitive. For example, there is no black-box construction of IBE from a trapdoor permutation or chosen-ciphertext secure PKE [55]. Therefore, GS-MDO is also strong and difficult to construct.We note that Box1 only shows a construction of an identity-basedkey encapsulation mechanism rather than identity-basedencryption. However, it suffices since we can obtain a secure encryption scheme by combining the construction with an appropriate data encapsulation mechanism.Box 1:The black-box construction of an identity-based KEM from GS-MDO.
I S e t u p ( 1 λ ): gpk,ok,ak,gsk1,gsk2←GKg(1λ,12): par←gpk,ok,gsk1,gsk2;mk←ak Output (par,mk). IEnc(par,ID): Fori∈[λ]: K i ← 0,1 σ i ← G S i g ( g p k , g s k K i + 1 , I D ) C←(σ1,…,σλ) K←K1⋯Kλ Output(C,K). I E x t m k ( I D ): dkID←Td(gpk,mk,ID) OutputdkID. IDec(dkID,ID,C): ParseC as (σ1,…,σλ) Fori∈[λ]: j i ← O p e n ( g p k , o k , I D , σ i , d k I D ) K i ← j i - 1 Ifji∉1,2 for some i then Output ⊥ Else OutputK1⋯Kλ.The formal theorems are as follows:Theorem 4.
If the underlying GS-MDO scheme satisfies opener anonymity, the identity-based KEM in Box1 is fully secure.Theorem 5.
If the underlying GS-MDO scheme satisfies opener anonymity withk-bounded tokens, the identity-based KEM in Box 1 is k-resilient.The intuition behind the construction in Box1 is as follows. In theIEnc algorithm, each σi is a group signature of either gsk0 or gsk1. Therefore, by the opener anonymity of the GS-MDO scheme, the entity who does not have mk (corresponding to the admitter’s key) cannot identify which signing key is used to make σi. The receiver can get dkID (corresponding to the message-dependent token), and only the receiver can open the group signature and get Ki by using the dkID. Formal proofs can be given by a straightforward modification of the proof by Abdalla and Warinschi [56] or the similar technique to that used by Ohtake, Fujii, Hanaoka, and Ogawa [57], hence we omit detailed proofs.From Theorems4 and 5, we make the following observation about the difficulty in constructing GS-MDO.(i)
Inevitability of using IBE:these theorems suggest that using IBE is essential for constructing a GS-MDO scheme. Considering the fact that a black-box construction of IBE from a trapdoor permutation is impossible [55], we can conclude that it is almost unavoidable for a GS-MDO scheme to rely on an IBE scheme or its equivalence, not only on a trapdoor permutation and an NIZK proof system. Otherwise one could construct an IBE scheme from surprisingly weaker primitives.(ii)
Difficulty in constructing efficient GS-MDO in the standard model:another important aspect of establishing anefficient GS-MDO scheme in the standard model is the necessity of realizing a “Groth-Sahai compatible” IBE scheme. This is because the only known construction of NIZK proof systems with reasonable efficiency in the standard model is limited to the Groth-Sahai proof system. Also note that an NIZK proof system has been an important building block for almost all group signature schemes ever.We show a generic construction of GS-MDO using a NIZK proof system and IBE in Section5. However, currently no known IBE scheme is Groth-Sahai compatible in the sense that the Groth-Sahai proof system cannot prove a kind of the well-formedness of an IBE ciphertext in zero-knowledge. (Libert and Joye [7] proposed an IBE scheme where we are able to prove the well-formedness of a ciphertext using the Groth-Sahai proof system. However, at the time of the publication of the conference version, there were no known IBE scheme with this property). This is because an IBE scheme in a bilinear group is typically able to encrypt a target-group element. In addition, the ciphertext of such a scheme includes a target-group element. Unfortunately, the Groth-Sahai proof system is not always able to prove a statement involving target-group elementsin zero-knowledge.Here we provide two methods of overcoming this gap. The first one is to adoptk-resilient IBE instead of fully secure IBE. In particular, we design a k-resilient IBE scheme from the DLIN assumption by modifying the Heng-Kurosawa scheme [8] for this purpose. (We also note that a similar construction can be obtained from the key-insulated encryption scheme proposed by Dodis, Katz, Xu, and Yung [58]). The construction of GS-MDO using k-resilient IBE is shown in Section 6.The second method is to apply random oracles. We construct a GS-MDO scheme based on the BBS group signature scheme [10], which is one of the most efficient group signature schemes in the random oracle model. The opening procedure is implemented by the linear encryption scheme [10, 13], and a user’s certificate is implemented by the Boneh-Boyen short signature scheme [27]. The MDO property is realized by adopting the BF IBE scheme [11]. In order to combine the short group signature scheme and the BF IBE scheme, we replace the linear encryption scheme with a certain type of 2-out-of-2 multiple encryption. This construction is shown in Section 7.


## 5. Generic Construction

In this section, we give a generic construction of a GS-MDO scheme. The construction is built on an EUF-CMA secure signature scheme, a strongly unforgeable one-time signature scheme, a selective-tag weakly chosen-ciphertext secure tag-based KEM, ak-resilient identity-based KEM, and an adaptive NIZK proof system.At a first glance, there are various building blocks. However, our generic construction only relies on the existence of an IBE scheme and that of an NIZK proof system. Indeed, signature schemes and a chosen-ciphertext secure tag-based encryption scheme can be constructed from a fully secure IBE scheme.


### 5.1. Underlying Ideas

The proposed construction shares an underlying idea with the generic construction of Bellare, Micciancio, and Warinschi (the BMW construction) [3] except that we do not need “simulation-soundness” for the underlying NIZK proof system. Instead of this strong security requirement, we combine (ordinary) NIZK proofs with a strongly unforgeable one-time signature scheme. We remark that essentially the same techniques have been used in a variety of contexts. To name a few, Groth [32] used this technique for an efficient group signature scheme in a very similar manner. Camenisch, Chandran, and Shoup [59] used it to construct simulation-sound NIZK proofs, improving the result of Groth [29].


### 5.2. Construction

In this section, we present our generic construction of GS-MDO. Our construction uses an identity-based KEM (ISetup,IExt,IEnc,IDec), tag-based KEM (TKg,TEnc,TDec), an EUF-CMA secure signature scheme (SigKg,Sign,Verify), a one-time signature scheme (SigKgOT, SignOT, VerifyOT), and an NIZK proof system (KNIZK,PNIZK,VNIZK). In addition, we require that the session key spaces KPKE and KIBE be the same set, and be associated with a group operation ⊙.In our construction, a group member has a key pair(vki,ski) of the signature scheme, in which vki is authorized by another verification key vkissue at the setup time. When a member generates a group signature, the member simply signs a message by ski. To be anonymous, the member further encrypts the signature together with the certificate (of the member), which authorizes the verification key vki, and attaches a noninteractive proof that demonstrates that a signature of an authorized member has been encrypted. To encrypt a signature, the member uses a multiple encryption technique to ensure that neither the opener nor the admitter can reveal the identity as long as the admitter has not issued a token to the opener. We need two requirements on the session key spaces of the tag-based KEM and the (k-resilient) IBE scheme. We require that KPKE be equal to KIBE as a set, and that they form a finite group with group operation ⊙. These requirements are needed because we use a one-time pad to encrypt a signature of the group member. This group operation also needs to fall into the class of relations that can be represented by the used noninteractive proof system.Let us explain the noninteractive proof that appears in the construction. The signature of the proposed scheme is of the form(vkOT,CPKE,CIBE,χ,π,σOT), and, as mentioned above, the proof π demonstrates that a valid signature of an authorized group member has been encrypted into (CPKE,CIBE,χ) in a kind of a “multiple encryption” manner. More specifically, the proof π proves that there exist a randomness r (for tag-based KEM), another randomness ρ (for identity-based KEM), a user index i, and the verification key vki, a certificate certi, and a signature s on a message M, such that(5)CPKE,KPKE=TEncpk,vkOT;r,CIBE,KIBE=IEncpar,M;ρ,χ=i,vki,certi,s⊙KPKE⊙KIBE,Verifyvkissue,i,vki,certi=⊤,Verifyvki,M,s=⊤.Finally, two encoding functions are needed to complete the description of the generic construction. The first is used to encode the user index of a group member and his verification key into the message space of the signature scheme when generating certificates of group members. The second one is used to encode(i,vki,certi,s) into KPKE, where i is the user index of a group member and vki, certi, and s are his verification key, certificate, and signature, respectively. It is used when issuing a group signature, especially when encrypting his signature in order to hide his identity.The complete description of the scheme is shown in Box2.Box 2:The description of the proposed generic construction. In the concrete instantiation, ⋅ denotes a tuple consisting of all group elements that appear in the bracket, and the operator ⊙ is the component-wise group multiplication. The noninteractive proof system (KNIZK,PNIZK,VNIZK) is for demonstrating the existence of a satisfying assignment of (5).
G K g ( 1 λ , 1 n , 1 k ): vkissue,skissue←SigKg(1λ) (pk,dk)←TKg(1λ) (par,mk)←ISetup(1λ,1k) Σ←KNIZK(1λ) gpk←(vkissue,pk,par,Σ) ok←dk ak←mk For alli∈[n]: ( v k i , s k i ) ← S i g K g ( 1 λ ) c e r t i ← S i g n ( s k i s s u e , 〈 i , v k i 〉 ) g s k i ← ( i , v k i , c e r t i , s k i ) Output(gpk,ok,ak,(gski)i). GSig(gpk,gski,M): Parsegpk as vkissue,pk,par,Σ Parsegski as (i,vki,certi,ski) s←Sign(ski,M) (vkOT,skOT)←SigKgOT(1λ) r←0,1k ρ←0,1k (CPKE,KPKE)←TEnc(pk,vkOT) (CIBE,KIBE)←IEnc(par,M) χ←〈i,vki,certi,s〉⊙KPKE⊙KIBE st←(vkissue,pk,par,CPKE,CIBE,χ) wt←(r,ρ,i,vki,certi,s) π←PNIZK(Σ,st,wt) σOT←SignOT(skOT,〈CPKE,CIBE,χ,π〉) σ←(vkOT,CPKE,CIBE,χ,π,σOT) Outputσ. GVf(gpk,M,σ): Parsegpk as (vkissue,pk,par,Σ) Parseσ as (vkOT,CPKE,CIBE,χ,π,σOT) st←(vkissue,pk,par,CPKE,CIBE,χ) IfVerifyOT(vkOT,〈CPKE,CIBE,χ,π〉,σOT)=⊤ andVNIZK(Σ,st,π)=⊤ then Output ⊤ Else Output⊥. Td(gpk,ak,M): Parsegpk as (vkissue,pk,par,Σ) tM←IExt(par,ak,M) OutputtM. Open(gpk,ok,M,σ,tM): Parsegpk as (vkissue,pk,par,Σ) Parseσ as (vkOT,CPKE,CIBE,χ,π,σOT) KPKE←TDec(ok,vkOT,CPKE) KIBE←IDec(tM,M,CIBE) IfKPKE=⊥ or KIBE=⊥ then Output ⊥ 〈i,vki,certi,s〉←χ⊙KIBE-1⊙KPKE-1 st←(vkissue,pk,par,CPKE,CIBE,χ) IfVerifyOT(vkOT,〈CPKE,CIBE,χ,π〉,σOT)=⊤ andVNIZK(Σ,st,π)=⊤ and i∈[n] then Output i Else Output⊥.As stated in the following theorem, our generic construction has desirable security properties when all building blocks satisfy appropriate security properties.Theorem 6.
The proposed scheme has opener anonymity withk-bounded tokens if the identity-based KEM is k-resilient and the noninteractive proof system is adaptively zero-knowledge. The proposed scheme satisfies opener anonymity if the identity-based KEM is fully secure and the noninteractive proof system is adaptively zero-knowledge.Theorem 7.
The proposed scheme has admitter anonymity when the a tag-based KEM is selective-tag weakly chosen-ciphertext secure, the noninteractive proof system is adaptively zero-knowledge, and the one-time signature scheme is strongly unforgeable.Theorem 8.
The proposed scheme has traceability when the noninteractive proof system is adaptively sound and the signature scheme is EUF-CMA secure.All the proofs of the theorems will appear in AppendixB.


## 5.1. Underlying Ideas

The proposed construction shares an underlying idea with the generic construction of Bellare, Micciancio, and Warinschi (the BMW construction) [3] except that we do not need “simulation-soundness” for the underlying NIZK proof system. Instead of this strong security requirement, we combine (ordinary) NIZK proofs with a strongly unforgeable one-time signature scheme. We remark that essentially the same techniques have been used in a variety of contexts. To name a few, Groth [32] used this technique for an efficient group signature scheme in a very similar manner. Camenisch, Chandran, and Shoup [59] used it to construct simulation-sound NIZK proofs, improving the result of Groth [29].


## 5.2. Construction

In this section, we present our generic construction of GS-MDO. Our construction uses an identity-based KEM (ISetup,IExt,IEnc,IDec), tag-based KEM (TKg,TEnc,TDec), an EUF-CMA secure signature scheme (SigKg,Sign,Verify), a one-time signature scheme (SigKgOT, SignOT, VerifyOT), and an NIZK proof system (KNIZK,PNIZK,VNIZK). In addition, we require that the session key spaces KPKE and KIBE be the same set, and be associated with a group operation ⊙.In our construction, a group member has a key pair(vki,ski) of the signature scheme, in which vki is authorized by another verification key vkissue at the setup time. When a member generates a group signature, the member simply signs a message by ski. To be anonymous, the member further encrypts the signature together with the certificate (of the member), which authorizes the verification key vki, and attaches a noninteractive proof that demonstrates that a signature of an authorized member has been encrypted. To encrypt a signature, the member uses a multiple encryption technique to ensure that neither the opener nor the admitter can reveal the identity as long as the admitter has not issued a token to the opener. We need two requirements on the session key spaces of the tag-based KEM and the (k-resilient) IBE scheme. We require that KPKE be equal to KIBE as a set, and that they form a finite group with group operation ⊙. These requirements are needed because we use a one-time pad to encrypt a signature of the group member. This group operation also needs to fall into the class of relations that can be represented by the used noninteractive proof system.Let us explain the noninteractive proof that appears in the construction. The signature of the proposed scheme is of the form(vkOT,CPKE,CIBE,χ,π,σOT), and, as mentioned above, the proof π demonstrates that a valid signature of an authorized group member has been encrypted into (CPKE,CIBE,χ) in a kind of a “multiple encryption” manner. More specifically, the proof π proves that there exist a randomness r (for tag-based KEM), another randomness ρ (for identity-based KEM), a user index i, and the verification key vki, a certificate certi, and a signature s on a message M, such that(5)CPKE,KPKE=TEncpk,vkOT;r,CIBE,KIBE=IEncpar,M;ρ,χ=i,vki,certi,s⊙KPKE⊙KIBE,Verifyvkissue,i,vki,certi=⊤,Verifyvki,M,s=⊤.Finally, two encoding functions are needed to complete the description of the generic construction. The first is used to encode the user index of a group member and his verification key into the message space of the signature scheme when generating certificates of group members. The second one is used to encode(i,vki,certi,s) into KPKE, where i is the user index of a group member and vki, certi, and s are his verification key, certificate, and signature, respectively. It is used when issuing a group signature, especially when encrypting his signature in order to hide his identity.The complete description of the scheme is shown in Box2.Box 2:The description of the proposed generic construction. In the concrete instantiation, ⋅ denotes a tuple consisting of all group elements that appear in the bracket, and the operator ⊙ is the component-wise group multiplication. The noninteractive proof system (KNIZK,PNIZK,VNIZK) is for demonstrating the existence of a satisfying assignment of (5).
G K g ( 1 λ , 1 n , 1 k ): vkissue,skissue←SigKg(1λ) (pk,dk)←TKg(1λ) (par,mk)←ISetup(1λ,1k) Σ←KNIZK(1λ) gpk←(vkissue,pk,par,Σ) ok←dk ak←mk For alli∈[n]: ( v k i , s k i ) ← S i g K g ( 1 λ ) c e r t i ← S i g n ( s k i s s u e , 〈 i , v k i 〉 ) g s k i ← ( i , v k i , c e r t i , s k i ) Output(gpk,ok,ak,(gski)i). GSig(gpk,gski,M): Parsegpk as vkissue,pk,par,Σ Parsegski as (i,vki,certi,ski) s←Sign(ski,M) (vkOT,skOT)←SigKgOT(1λ) r←0,1k ρ←0,1k (CPKE,KPKE)←TEnc(pk,vkOT) (CIBE,KIBE)←IEnc(par,M) χ←〈i,vki,certi,s〉⊙KPKE⊙KIBE st←(vkissue,pk,par,CPKE,CIBE,χ) wt←(r,ρ,i,vki,certi,s) π←PNIZK(Σ,st,wt) σOT←SignOT(skOT,〈CPKE,CIBE,χ,π〉) σ←(vkOT,CPKE,CIBE,χ,π,σOT) Outputσ. GVf(gpk,M,σ): Parsegpk as (vkissue,pk,par,Σ) Parseσ as (vkOT,CPKE,CIBE,χ,π,σOT) st←(vkissue,pk,par,CPKE,CIBE,χ) IfVerifyOT(vkOT,〈CPKE,CIBE,χ,π〉,σOT)=⊤ andVNIZK(Σ,st,π)=⊤ then Output ⊤ Else Output⊥. Td(gpk,ak,M): Parsegpk as (vkissue,pk,par,Σ) tM←IExt(par,ak,M) OutputtM. Open(gpk,ok,M,σ,tM): Parsegpk as (vkissue,pk,par,Σ) Parseσ as (vkOT,CPKE,CIBE,χ,π,σOT) KPKE←TDec(ok,vkOT,CPKE) KIBE←IDec(tM,M,CIBE) IfKPKE=⊥ or KIBE=⊥ then Output ⊥ 〈i,vki,certi,s〉←χ⊙KIBE-1⊙KPKE-1 st←(vkissue,pk,par,CPKE,CIBE,χ) IfVerifyOT(vkOT,〈CPKE,CIBE,χ,π〉,σOT)=⊤ andVNIZK(Σ,st,π)=⊤ and i∈[n] then Output i Else Output⊥.As stated in the following theorem, our generic construction has desirable security properties when all building blocks satisfy appropriate security properties.Theorem 6.
The proposed scheme has opener anonymity withk-bounded tokens if the identity-based KEM is k-resilient and the noninteractive proof system is adaptively zero-knowledge. The proposed scheme satisfies opener anonymity if the identity-based KEM is fully secure and the noninteractive proof system is adaptively zero-knowledge.Theorem 7.
The proposed scheme has admitter anonymity when the a tag-based KEM is selective-tag weakly chosen-ciphertext secure, the noninteractive proof system is adaptively zero-knowledge, and the one-time signature scheme is strongly unforgeable.Theorem 8.
The proposed scheme has traceability when the noninteractive proof system is adaptively sound and the signature scheme is EUF-CMA secure.All the proofs of the theorems will appear in AppendixB.


## 6. Construction in the Standard Model

In this section, we show an instantiation of GS-MDO in the standard model. Our scheme in this section satisfies the requirements of Section3.2 under the DLIN assumption and the SFP assumption. Because of the incompatibility between the Groth-Sahai NIZK proof system and known (pairing-based) IBE schemes, we use k-resilient IBE and thus the MDO property is bounded to be k. Note that the instantiation is not straightforward even though we have the generic construction in Section 5, since it is not obvious whether there exist building blocks which fit the generic construction. Of course, if we use a general NIZK proof system, we obtain an instantiation, but it is far from an efficient construction.


### 6.1. Underlying Ideas

Towards an efficient scheme, we discuss how to instantiate the building blocks used in our generic construction in the previous section.Regarding the noninteractive proof system, an obvious choice is the Groth-Sahai proof system, since there is no known practical construction of an NIZK proof system except the Groth-Sahai proof system. However, upon adopting the Groth-Sahai proof system, due to the limitation of the type of theorems that the Groth-Sahai proof system can prove, other building blocks are subjected to restrictions. More specifically, other building blocks need to bestructure preserving [60], and in particular, a statement to be proven should not involve elements of GT, where GT is the target group of the underlying bilinear groups. Hence, we have to choose an IBE scheme which fulfills this requirement as a building block, but unfortunately, no such scheme is known (except for the Libert-Joye scheme). This means thatit is not straightforward to construct an efficient instantiation of our generic construction from the Groth-Sahai proof system.In this section, we give an efficient instantiation by constructing astructure-preserving IBE scheme and choosing other appropriate building blocks. However, we must also honestly mention that our IBE does not provide full security but only k-resilience [8].Our structure-preservingk-resilient IBE scheme is obtained by means of modifying the Heng-Kurosawa scheme [8] which is secure in the sense of k-resilient security under the decision Diffie-Hellman (DDH) assumption. Since the DDH assumption does not hold in (symmetric) bilinear groups, it is not possible to utilize it as it is, and thus, we construct a modified version of this scheme which is secure under the DLIN assumption.


### 6.2. Construction

As described above, an efficient instantiation is not straightforward even from our generic construction in Section5, since it is not obvious whether there exist schemes which can be plugged into the generic construction. Therefore, we select concrete building blocks for the instantiation:(i)
Groth-Sahai Proofs [5, 61]. This is an efficient noninteractive proof system for groups with a bilinear map. This proof system can demonstrate the validity of a broad range of algebraic equations in a zero-knowledge manner and is useful for avoiding an expensive blowup from general NIZK techniques. We choose the DLIN-based instantiation of the Groth-Sahai proof system, which was proved to be perfectly sound with adaptive zero-knowledge from the DLIN assumption.(ii)
Abe-Haralambiev-Ohkubo Signature [6, 60]. This is a structure-preserving signature scheme, in the sense that the signing and verification procedures have no use of nonalgebraic operations. This property is essential when the scheme is used together with the Groth-Sahai proof system that has the restriction that it is unable to treat nonalgebraic relations such as a verification equation of a signature scheme which involves hashing. This signature scheme was proven secure from the SFP assumption.(iii)
DLIN Variant of Cramer-Shoup scheme [13]. The Groth-Sahai proof system is highly reliant on its use of pairing operations, and thus we need to choose the type of pairing on which we base our scheme. Type III or II may allow an efficient instantiation. However, in this setting a signature of the Abe-Haralambiev-Ohkubo scheme is bilateral, namely, it contains elements of both source groups. To encrypt such a bilateral message, we need to set up the encryption scheme in both source groups, which makes the scheme inefficient. Hence, we choose all the building blocks to be instantiated in Type I curves. For this reason, we choose a modification of Shacham’s DLIN variant [13] of the Cramer-Shoup encryption scheme as the tag-based KEM. We modify this scheme to be tag-based KEM to fit into our generic construction. (A possible alternative choice here is Kiltz’ tag-based encryption [52], which could reduce the size of NIZK proofs owning to its public verifiability. One drawback of this scheme is that, to the best of our knowledge, it does not allow the encryption of multiple group elements with a constant ciphertext overhead. On the other hand, the Cramer-Shoup scheme (and its DLIN variant by Shacham) allow such a modification. See Section C.3 for the details of this modification).We then show a more concrete description of our generic construction when being instantiated with the above building blocks. Notice that a signature of our concrete instantiation based on the above building blocks, is of the following form:(6)σ=vkOT,CPKE,CIBE,χ,π,σOT.As explained above, χ is represented by 29 group elements, which we denote by χ=(χ1,…,χ29). A more detailed description of each element is as follows:(7)vkOT=gs0,gs1,gxCPKE=ur,vr~,hrhr~,XYtrX~Y~tr~CIBE=uρ,vρ~,hρhρ~χ1=Z1r·Z~1r~·∏j=0kD1,jMjρ·∏j=0kD~1,jMjρ~·m1⋮χ29=Z29r·Z~29r~·∏j=0kD29,jMjρ·∏j=0kD~29,jMjρ~·m29σOT=x+e·s0+CRCPKE,CIBE,χ1,…,χ29,π+e·s1where CR is a collision resistant hash function and π is a Groth-Sahai proof.In (7), (m1,…,m29) is the encoding of (i,vki,certi,s), Zir·Z~ir~ corresponds to the session key KPKE of the tag-based KEM based on a DLIN variant of the Cramer-Shoup PKE scheme, and ∏j=0kDi,jMjρ·∏j=0kD~i,jMjρ~ corresponds to the session key KIBE of the k-resilient identity-based KEM based on the Heng-Kurosawa IBE scheme. CPKE and CIBE are ciphertexts of the tag-based KEM and the identity-based KEM, respectively. σOT is Wee’s one-time signature on (CPKE,CIBE,χ1,…,χ29,π).The signature size of the construction in Section6 is described in Table 1. The column “Cost” is the number of group elements of a statement to be proven, and the number of group elements of the Groth-Sahai NIZK proof per a statement. The abbreviations “var(s).”, “lin. eq.”, “mult”, and “pair. prod.” mean “variable(s)”, “linear equation”, “multiplication” and “pairing product”, respectively. The total number of group elements is shown in the column “G”. As shown in Table 1, the standard model scheme achieves reasonably efficient performance.Table 1
The number of group elements of GS-MDO in the standard model.
Cost G Z p verification keyvksots  3 TB-KEM CTCPKE  4 IB-KEM CTCIBE  3 DEM CTχ  29 NIZK proof commitments for r, r~∈Zp 2 vars.×3G per var. 6 ρ, ρ~∈Zp 2 vars.×3G per var. 6 gi∈G 1 var.×3G per var. 3 vki∈G14 14 vars.×3G per var. 42 certi∈G7 7 vars.×3G per var. 21 s∈G7 7 vars.×3G per var. 21 equations for well-formedness ofCPKE 4Zp-var. lin. eqs. ×2G per eq. 8 well-formedness ofCIBE 3Zp-var. lin. eqs. × ×2G per eq. 6 well-formedness ofχ 29 multi-scalar mult. eqs.×9G per eq. 261 validity ofcerti 2 pair. prod. eqs.×9G per eq. 18 validity ofs 2 pair. prod. eqs.×9G per eq. 18 one-time signatureσOT   2  Total  449 2From Theorems6, 7, and 8, the following theorems hold.Theorem 9.
When instantiating the identity-based KEM and the NIZK proof system in Box2 with our DLIN variant of the Heng-Kurosawa k-resilient IBE scheme and the Groth-Sahai proof system, the resulting scheme satisfies opener anonymity with k-bounded tokens under the DLIN assumption.Theorem 10.
When instantiating the tag-based KEM, the NIZK proof system and the one-time signature scheme in Box2 with the DLIN variant of the Cramer-Shoup PKE, the Groth-Sahai proof system and the Wee one-time signature scheme, the resulting scheme satisfies admitter anonymity under the DLIN assumption.Theorem 11.
When instantiating the signature scheme in Box2 with the Abe-Haralambiev-Ohkubo signature scheme, the resulting scheme satisfies traceability under the SFP assumption.


## 6.1. Underlying Ideas

Towards an efficient scheme, we discuss how to instantiate the building blocks used in our generic construction in the previous section.Regarding the noninteractive proof system, an obvious choice is the Groth-Sahai proof system, since there is no known practical construction of an NIZK proof system except the Groth-Sahai proof system. However, upon adopting the Groth-Sahai proof system, due to the limitation of the type of theorems that the Groth-Sahai proof system can prove, other building blocks are subjected to restrictions. More specifically, other building blocks need to bestructure preserving [60], and in particular, a statement to be proven should not involve elements of GT, where GT is the target group of the underlying bilinear groups. Hence, we have to choose an IBE scheme which fulfills this requirement as a building block, but unfortunately, no such scheme is known (except for the Libert-Joye scheme). This means thatit is not straightforward to construct an efficient instantiation of our generic construction from the Groth-Sahai proof system.In this section, we give an efficient instantiation by constructing astructure-preserving IBE scheme and choosing other appropriate building blocks. However, we must also honestly mention that our IBE does not provide full security but only k-resilience [8].Our structure-preservingk-resilient IBE scheme is obtained by means of modifying the Heng-Kurosawa scheme [8] which is secure in the sense of k-resilient security under the decision Diffie-Hellman (DDH) assumption. Since the DDH assumption does not hold in (symmetric) bilinear groups, it is not possible to utilize it as it is, and thus, we construct a modified version of this scheme which is secure under the DLIN assumption.


## 6.2. Construction

As described above, an efficient instantiation is not straightforward even from our generic construction in Section5, since it is not obvious whether there exist schemes which can be plugged into the generic construction. Therefore, we select concrete building blocks for the instantiation:(i)
Groth-Sahai Proofs [5, 61]. This is an efficient noninteractive proof system for groups with a bilinear map. This proof system can demonstrate the validity of a broad range of algebraic equations in a zero-knowledge manner and is useful for avoiding an expensive blowup from general NIZK techniques. We choose the DLIN-based instantiation of the Groth-Sahai proof system, which was proved to be perfectly sound with adaptive zero-knowledge from the DLIN assumption.(ii)
Abe-Haralambiev-Ohkubo Signature [6, 60]. This is a structure-preserving signature scheme, in the sense that the signing and verification procedures have no use of nonalgebraic operations. This property is essential when the scheme is used together with the Groth-Sahai proof system that has the restriction that it is unable to treat nonalgebraic relations such as a verification equation of a signature scheme which involves hashing. This signature scheme was proven secure from the SFP assumption.(iii)
DLIN Variant of Cramer-Shoup scheme [13]. The Groth-Sahai proof system is highly reliant on its use of pairing operations, and thus we need to choose the type of pairing on which we base our scheme. Type III or II may allow an efficient instantiation. However, in this setting a signature of the Abe-Haralambiev-Ohkubo scheme is bilateral, namely, it contains elements of both source groups. To encrypt such a bilateral message, we need to set up the encryption scheme in both source groups, which makes the scheme inefficient. Hence, we choose all the building blocks to be instantiated in Type I curves. For this reason, we choose a modification of Shacham’s DLIN variant [13] of the Cramer-Shoup encryption scheme as the tag-based KEM. We modify this scheme to be tag-based KEM to fit into our generic construction. (A possible alternative choice here is Kiltz’ tag-based encryption [52], which could reduce the size of NIZK proofs owning to its public verifiability. One drawback of this scheme is that, to the best of our knowledge, it does not allow the encryption of multiple group elements with a constant ciphertext overhead. On the other hand, the Cramer-Shoup scheme (and its DLIN variant by Shacham) allow such a modification. See Section C.3 for the details of this modification).We then show a more concrete description of our generic construction when being instantiated with the above building blocks. Notice that a signature of our concrete instantiation based on the above building blocks, is of the following form:(6)σ=vkOT,CPKE,CIBE,χ,π,σOT.As explained above, χ is represented by 29 group elements, which we denote by χ=(χ1,…,χ29). A more detailed description of each element is as follows:(7)vkOT=gs0,gs1,gxCPKE=ur,vr~,hrhr~,XYtrX~Y~tr~CIBE=uρ,vρ~,hρhρ~χ1=Z1r·Z~1r~·∏j=0kD1,jMjρ·∏j=0kD~1,jMjρ~·m1⋮χ29=Z29r·Z~29r~·∏j=0kD29,jMjρ·∏j=0kD~29,jMjρ~·m29σOT=x+e·s0+CRCPKE,CIBE,χ1,…,χ29,π+e·s1where CR is a collision resistant hash function and π is a Groth-Sahai proof.In (7), (m1,…,m29) is the encoding of (i,vki,certi,s), Zir·Z~ir~ corresponds to the session key KPKE of the tag-based KEM based on a DLIN variant of the Cramer-Shoup PKE scheme, and ∏j=0kDi,jMjρ·∏j=0kD~i,jMjρ~ corresponds to the session key KIBE of the k-resilient identity-based KEM based on the Heng-Kurosawa IBE scheme. CPKE and CIBE are ciphertexts of the tag-based KEM and the identity-based KEM, respectively. σOT is Wee’s one-time signature on (CPKE,CIBE,χ1,…,χ29,π).The signature size of the construction in Section6 is described in Table 1. The column “Cost” is the number of group elements of a statement to be proven, and the number of group elements of the Groth-Sahai NIZK proof per a statement. The abbreviations “var(s).”, “lin. eq.”, “mult”, and “pair. prod.” mean “variable(s)”, “linear equation”, “multiplication” and “pairing product”, respectively. The total number of group elements is shown in the column “G”. As shown in Table 1, the standard model scheme achieves reasonably efficient performance.Table 1
The number of group elements of GS-MDO in the standard model.
Cost G Z p verification keyvksots  3 TB-KEM CTCPKE  4 IB-KEM CTCIBE  3 DEM CTχ  29 NIZK proof commitments for r, r~∈Zp 2 vars.×3G per var. 6 ρ, ρ~∈Zp 2 vars.×3G per var. 6 gi∈G 1 var.×3G per var. 3 vki∈G14 14 vars.×3G per var. 42 certi∈G7 7 vars.×3G per var. 21 s∈G7 7 vars.×3G per var. 21 equations for well-formedness ofCPKE 4Zp-var. lin. eqs. ×2G per eq. 8 well-formedness ofCIBE 3Zp-var. lin. eqs. × ×2G per eq. 6 well-formedness ofχ 29 multi-scalar mult. eqs.×9G per eq. 261 validity ofcerti 2 pair. prod. eqs.×9G per eq. 18 validity ofs 2 pair. prod. eqs.×9G per eq. 18 one-time signatureσOT   2  Total  449 2From Theorems6, 7, and 8, the following theorems hold.Theorem 9.
When instantiating the identity-based KEM and the NIZK proof system in Box2 with our DLIN variant of the Heng-Kurosawa k-resilient IBE scheme and the Groth-Sahai proof system, the resulting scheme satisfies opener anonymity with k-bounded tokens under the DLIN assumption.Theorem 10.
When instantiating the tag-based KEM, the NIZK proof system and the one-time signature scheme in Box2 with the DLIN variant of the Cramer-Shoup PKE, the Groth-Sahai proof system and the Wee one-time signature scheme, the resulting scheme satisfies admitter anonymity under the DLIN assumption.Theorem 11.
When instantiating the signature scheme in Box2 with the Abe-Haralambiev-Ohkubo signature scheme, the resulting scheme satisfies traceability under the SFP assumption.


## 7. Construction in the Random Oracle Model

The previous section explained a GS-MDO scheme in the standard model, but it only allows at mostk tokens to be issued. In this section, we remove this restriction by using random oracles, and present a concrete GS-MDO scheme that allows an unbounded number of tokens. Moreover, its signature size is 1/20 times smaller than that of the scheme in Section 6, and it is also secure under the DLIN, DBDH, and q-SDH assumptions. We give the description of the proposed scheme in Box 3.Box 3:The proposed construction in the random oracle model. The functions H1 and H2 are cryptographic hash functions H1:{0,1}∗→G and H2:{0,1}∗→Zp, which are modeled as random oracles in the security proof. G is the parameter generation algorithm, which is defined in Section 2.5.
GKg ( 1 λ , 1 n ): (p,G,GT,e,g)←G(1λ) u, v, h←G∖1 ξ1, ξ2, ξ3, ζ, γ←Zp g1←uξ1hξ3; g2←vξ2hξ3; y←gζ; w←gγ Fori∈[n]: x i ← Z p A i ← g 1 / ( γ + x i ) gpk←(p,G,GT,e,g,u,v,h,g1,g2,y,w,H1,H2) ok←(ξ1,ξ2,ξ3,(e(Ai,g))i∈[n]) ak←ζ Fori∈[n]: g s k i ← ( A i , x i ) Output(gpk,ok,ak,(gski)i∈[n]). GSig ( g p k , i , g s k i , M ): (p,G,GT,e,g,u,v,h,g1,g2,y,w,H1,H2)←gpk (Ai,xi)←gski α, β, ρ, η←Zp (T1,T2,T3,T4)←(uα,vβ,hα+β,g1αg2βAigη) (T5,T6)←(gρ,ey,H1Mρeg,g-η) rα, rβ, rρ, rη, rx, rαx, rβx, rρx, rηx←Zp R1←urα R2←vrβ R3←hrα+rβ R4←e(T4,g)rxeg1,w-rαeg1,g-rαx ⋅ e ( g 2 , w ) - r β e ( g 2 , g ) - r β x ⋅ e ( g , w ) - r η e ( g , g ) - r η x R5←grρ R6←e(y,H1(M))rρe(g,g)-rη R7←T1rxu-rαx R8←T2rxv-rβx R9←T5rxg-rρx R10←T6rxe(y,H1(M))-rρxe(g,g)rηx c←H2(M,T1,…,T6,R1,…,R10) sα←rα+cα; sβ←rβ+cβ sρ←rρ+cρ; sη←rη+cη sx←rx+cxi; sαx←rαx+cαxi sβx←rβx+cβxi; sρx←rρx+cρxi sηx←rηx+cηxi σ←(T1,…,T6,c,sα,sβ,sρ,sη,sx,sαx,sβx,sρx,sηx) Outputσ. GVf ( g p k , M , σ ): (p,G,GT,e,g,u,v,h,g1,g2,y,w,H1,H2)←gpk (T1,…,T6,c,sα,sβ,sρ,sη,sx,sαx,sβx,sρx,sηx)←σ R1′←usαT1-c R2′←vsβT2-c R3′←hsα+sβT3-c R4′←e(T4,g)sxe(g1,w)-sαe(g1,g)-sαx ⋅ e ( g 2 , w ) - s β e ( g 2 , g ) - s β x ⋅ e ( g , w ) - s η e ( g , g ) - s η x ⋅ ( e ( g , g ) / e ( T 4 , w ) ) - c R5′←gsρT5-c R6′←e(y,H1(M))sρe(g,g)-sηT6-c R7′←T1sxu-sαx R8′←T2sxv-sβx R9′←T5sxg-sρx R10′←T6sxe(y,H1(M))-sρxe(g,g)sηx Ifc=H2(M,T1,…,T6,R1′,…,R10′) Output ⊤ Else output⊥. Td ( g p k , a k , M ): (p,G,GT,e,g,u,v,h,g1,g2,y,w,H1,H2)←gpk ζ←ak OutputtM←H1(M)ζ. Open ( g p k , o k , M , σ , t M ): (p,G,GT,e,g,u,v,h,g1,g2,y,w,H1,H2)←gpk (ξ1,ξ2,ξ3,(e(Ai,g))i∈[n])←ok (T1,…,T6,c,sα,sβ,sρ,sη,sx,sαx,sβx,sρx,sηx)←σ IfGVf(gpk,M,σ)=⊥ Output ⊥ If∃i∈[n]: e(T4/T1ξ1T2ξ2T3ξ3,g)⋅T6/e(T5,tM)=e(Ai,g) Outputi; Else output⊥.


### 7.1. Underlying Ideas

Our standard model instantiation uses the Groth-Sahai proof system as the NIZK proof system, and therefore the building block identity-based KEM needs to be compatible with the Groth-Sahai proof system (see Section6.1). Unfortunately, the only IBE scheme with this property is Libert et al.’s [7], however, this scheme has a ciphertext containing a linear number of group elements in the security parameter. We overcome this weakness by avoiding the use of the Groth-Sahai proof system. More specifically, we construct an NIZK proof system in the random oracle model based on the Fiat-Shamir heuristics, and choose the building block IBE scheme that is fully secure (i.e., fully collusion resilient).We start with the Boneh-Boyen-Shacham (BBS) group signature scheme [10], which is one of the most popular (standard) group signature schemes, to achieve the above idea. Each group member in this scheme is provided with an (ordinary) signature [27] of the Boneh-Boyen signature scheme, which certifies that the owner is a group member. A group signature of this scheme consists of two parts. The first part involves the linear encryption scheme of the certificate, whereas the second part involves the “signature of knowledge” [62] of the encrypted certificate. The decryption key for the linear encryption scheme is held by the opener, with which he can revoke the anonymity of any group signature.We extend the BBS group signature scheme by replacing the linear encryption scheme with a certain type of2-out-of-2 multiple encryption of ordinary PKE and IBE schemes. The multiple encryption is designed to ensure that one can decrypt an entire ciphertext only when he is able to decrypt ciphertexts ofboth the PKE scheme and the IBE scheme. Such multiple encryption can be accomplished by simple 2-out-of-2 secret sharing.This feature enables us to achieve the MDO property as follows. In our construction, the opener only possesses a decryption key for the PKE scheme, and the admitter holds the master secret of the IBE scheme. To anonymously sign a messageM, a signer encrypts his certificate using M as the identity of the IBE encryption. A decryption key (of the IBE scheme) under a message M can serve as a message-specific token for M.


### 7.2. Construction

In this subsection, we describe the proposed GS-MDO scheme in the random oracle model in detail. The complete description of the proposed scheme is shown in Box3. As described above, our scheme is constructed by modifying the BBS group signature scheme in such a way that the linear encryption scheme in the BBS group signature scheme is replaced with 2-out-of-2 multiple encryption by PKE and IBE, which are instantiated with the linear encryption scheme and the BF IBE scheme [11], respectively. Specifically, the values (T1,T2,T3,T4,T5,T6) generated in the signing algorithm are of the following form (8)T1=uα,T2=vβ,T3=hα+β,T4=g1αg2βAgη,T5=gρ,T6=ey,H1Mρeg,g-η,where the first four components constitute (a chosen-ciphertext secure variant of) the linear encryption of a 2-out-of-2 secret sharing of A. Here α and β are the randomness for the linear encryption scheme and η is the randomness for the 2-out-of-2 secret sharing. The other components, T5 and T6, constitute an encryption by the BF IBE scheme of the other share of the 2-out-of-2 secret sharing.As mentioned above, our linear encryption scheme is not identical to that used in the BBS group signature scheme and is modified to achieve CCA-anonymity. It is obtained by modifying the linear encryption scheme (in the BBS scheme) to a linear analogue of the “double encryption” [20, 63, 64] scheme and proving the “well-formedness” by a Schnorr-type proof. This can be seen as a variant of (the DLIN variant [13] of) the Cramer-Shoup encryption scheme [12, 65] in which the validity-check property is realized by a Schnorr-type proof.Note that the BF IBE scheme is also slightly modified in such a way that the scheme does not use a hash function for deriving the DEM key that masks a plaintext. Instead of using a hash function, we employ the slightly stronger assumption of the DBDH assumption (rather than the computational variant, on which the original BF scheme is based). This is due to the incompatibility of the use of a hash function of this type and Schnorr-type proofs. We also remark that our anonymity notion does not require the IBE scheme to be chosen-ciphertext secure, and hence we use a chosen-plaintext secure version of the BF scheme.We further remark thatR1,…,R10, c, sα, sβ, sρ, sη, sx, sαx, sβx, sρx, and sηx in Box 3 come from a Schnorr-type protocol that proves the knowledge of α, β, ρ, η, and x satisfying the equations(9)T1=uα,T2=vβ,T3=hα+β,eg,g=eT4g1-αg2-βg-η,wgx,T5=gρ,T6=ey,H1Mρeg,g-η.The first three equations prove the knowledge of α and β that are used for the linear encryption part, and furthermore prove the “well-formedness” of the ciphertext (in other words, they prove that (T1,T2,T3) constitutes a linear tuple). We note that the latter (proving the “well-formedness”) is crucial for achieving CCA-anonymity. The last two equations prove the knowledge of ρ and η that are used for the BF IBE scheme. Here ρ is the randomness for the BF IBE scheme, and η is the randomness for the 2-out-of-2 secret sharing. The fourth equation proves that the group element encrypted in T4 satisfies the verification equation of the Boneh-Boyen signature scheme. Recall that T4=g1αg2βAigη, where Ai is a Boneh-Boyen signature which certifies the membership of the signer. In other words, this equation proves that when the randomness that hides Ai is removed from T4, T4 is verified as valid by the verification equation of the Boneh-Boyen signature scheme.More concretely, introducing four intermediate variablesδ1, δ2, δ3, and δ4 (which are intended to be δ1=αx, δ2=βx, δ3=ρx, and δ4=ηx), the underlying protocol proves the knowledge of α, β, ρ, η, x, δ1, δ2, δ3, and δ4 satisfying the equations(10a)T1=uα,(10b)T2=vβ,(10c)T3=hα+β,(10d)eg,geT4,w=eT4,gxeg1,w-αeg1,g-δ1eg2,w-βeg2,g-δ2eg,w-ηeg,g-δ4,(10e)T5=gρ,(10f)T6=ey,H1Mρeg,g-η,(10g)1=T1xu-δ1,(10h)1=T2xv-δ2,(10i)1=T5xg-δ3,(10j)1=T6xey,H1M-δ3eg,gδ4.We explain these ten equations one by one. The first three equations are exactly the same as those of (9). Equation (10d) comes from expanding the equation (11)eg,g=eT4g1-αg2-βg-η,wgxto obtain (12)eg,g=eT4,weT4,gxeg1-α,weg1α,gxeg2-β,weg2-β,gxeg-η,weg-η,gx,=eT4,weT4,gxeg1,w-αeg1,g-αxeg2,w-βeg2,g-βxeg,w-ηeg,g-ηx,replacing αx with δ1, βx with δ2, and ηx with δ4 to obtain (13)eg,g=eT4,weT4,gxeg1,w-αeg1,g-δ1eg2,w-βeg2,g-δ2eg,w-ηeg,g-δ4,and rearranging them to obtain (14)eg,geT4,w=eT4,gxeg1,w-αeg1,g-δ1eg2,w-βeg2,g-δ2eg,w-ηeg,g-δ4,which is identical to (10d). We then need to prove that the intermediate variables surely have appropriate values, namely, that δ1=αx, δ2=βx, and δ4=ηx. Equations (10g)–(10j) are for this purpose. To prove δ1=αx, we introduce (10g). This equation, together with (10a), proves that δ1=αx. Specifically, (10a) ensures that T1 is equal to uα, and then (10g) in turn ensures that (15)1=uαxu-δ1. Since u is a generator, we have that (16)αx-δ1=0,which is what we want to prove. Similarly, (10h) together with (10b) proves that βx=δ2. To prove ηx=δ4, we need to introduce another intermediate variable δ3 which is intended to be equal to ρx. Towards this end, (10e) and (10i) prove that ρx=δ3. Using this, (10f) and (10j) prove that δ4=ηx. Specifically, (10f) ensures that T6=e(y,H1(M))ρe(g,g)-η, and then (10j) in turn ensures that (17)1=ey,H1Mρeg,g-ηxey,H1M-δ3eg,gδ4.Since (10e) and (10i) ensure that δ3=ρx, canceling out e(y,H1(M))ρx and e(y,H1(M))-δ3, (10j) further ensures that (18)1=eg,g-ηxeg,gδ4,since e(g,g) is a generator, this equation ensures that (19)-ηx+δ4=0,which is what we want to prove.The security of our proposed scheme is proved as follows.Theorem 12.
If the DBDH assumption holds, the proposed construction has opener anonymity in the random oracle model.Theorem 13.
If the DLIN assumption holds, the proposed construction has admitter anonymity in the random oracle model.Theorem 14.
If theq-SDH assumption holds, the proposed construction has traceability in the random oracle model.The proofs of Theorems12, 13, and 14 are given in Appendix D.


## 7.1. Underlying Ideas

Our standard model instantiation uses the Groth-Sahai proof system as the NIZK proof system, and therefore the building block identity-based KEM needs to be compatible with the Groth-Sahai proof system (see Section6.1). Unfortunately, the only IBE scheme with this property is Libert et al.’s [7], however, this scheme has a ciphertext containing a linear number of group elements in the security parameter. We overcome this weakness by avoiding the use of the Groth-Sahai proof system. More specifically, we construct an NIZK proof system in the random oracle model based on the Fiat-Shamir heuristics, and choose the building block IBE scheme that is fully secure (i.e., fully collusion resilient).We start with the Boneh-Boyen-Shacham (BBS) group signature scheme [10], which is one of the most popular (standard) group signature schemes, to achieve the above idea. Each group member in this scheme is provided with an (ordinary) signature [27] of the Boneh-Boyen signature scheme, which certifies that the owner is a group member. A group signature of this scheme consists of two parts. The first part involves the linear encryption scheme of the certificate, whereas the second part involves the “signature of knowledge” [62] of the encrypted certificate. The decryption key for the linear encryption scheme is held by the opener, with which he can revoke the anonymity of any group signature.We extend the BBS group signature scheme by replacing the linear encryption scheme with a certain type of2-out-of-2 multiple encryption of ordinary PKE and IBE schemes. The multiple encryption is designed to ensure that one can decrypt an entire ciphertext only when he is able to decrypt ciphertexts ofboth the PKE scheme and the IBE scheme. Such multiple encryption can be accomplished by simple 2-out-of-2 secret sharing.This feature enables us to achieve the MDO property as follows. In our construction, the opener only possesses a decryption key for the PKE scheme, and the admitter holds the master secret of the IBE scheme. To anonymously sign a messageM, a signer encrypts his certificate using M as the identity of the IBE encryption. A decryption key (of the IBE scheme) under a message M can serve as a message-specific token for M.


## 7.2. Construction

In this subsection, we describe the proposed GS-MDO scheme in the random oracle model in detail. The complete description of the proposed scheme is shown in Box3. As described above, our scheme is constructed by modifying the BBS group signature scheme in such a way that the linear encryption scheme in the BBS group signature scheme is replaced with 2-out-of-2 multiple encryption by PKE and IBE, which are instantiated with the linear encryption scheme and the BF IBE scheme [11], respectively. Specifically, the values (T1,T2,T3,T4,T5,T6) generated in the signing algorithm are of the following form (8)T1=uα,T2=vβ,T3=hα+β,T4=g1αg2βAgη,T5=gρ,T6=ey,H1Mρeg,g-η,where the first four components constitute (a chosen-ciphertext secure variant of) the linear encryption of a 2-out-of-2 secret sharing of A. Here α and β are the randomness for the linear encryption scheme and η is the randomness for the 2-out-of-2 secret sharing. The other components, T5 and T6, constitute an encryption by the BF IBE scheme of the other share of the 2-out-of-2 secret sharing.As mentioned above, our linear encryption scheme is not identical to that used in the BBS group signature scheme and is modified to achieve CCA-anonymity. It is obtained by modifying the linear encryption scheme (in the BBS scheme) to a linear analogue of the “double encryption” [20, 63, 64] scheme and proving the “well-formedness” by a Schnorr-type proof. This can be seen as a variant of (the DLIN variant [13] of) the Cramer-Shoup encryption scheme [12, 65] in which the validity-check property is realized by a Schnorr-type proof.Note that the BF IBE scheme is also slightly modified in such a way that the scheme does not use a hash function for deriving the DEM key that masks a plaintext. Instead of using a hash function, we employ the slightly stronger assumption of the DBDH assumption (rather than the computational variant, on which the original BF scheme is based). This is due to the incompatibility of the use of a hash function of this type and Schnorr-type proofs. We also remark that our anonymity notion does not require the IBE scheme to be chosen-ciphertext secure, and hence we use a chosen-plaintext secure version of the BF scheme.We further remark thatR1,…,R10, c, sα, sβ, sρ, sη, sx, sαx, sβx, sρx, and sηx in Box 3 come from a Schnorr-type protocol that proves the knowledge of α, β, ρ, η, and x satisfying the equations(9)T1=uα,T2=vβ,T3=hα+β,eg,g=eT4g1-αg2-βg-η,wgx,T5=gρ,T6=ey,H1Mρeg,g-η.The first three equations prove the knowledge of α and β that are used for the linear encryption part, and furthermore prove the “well-formedness” of the ciphertext (in other words, they prove that (T1,T2,T3) constitutes a linear tuple). We note that the latter (proving the “well-formedness”) is crucial for achieving CCA-anonymity. The last two equations prove the knowledge of ρ and η that are used for the BF IBE scheme. Here ρ is the randomness for the BF IBE scheme, and η is the randomness for the 2-out-of-2 secret sharing. The fourth equation proves that the group element encrypted in T4 satisfies the verification equation of the Boneh-Boyen signature scheme. Recall that T4=g1αg2βAigη, where Ai is a Boneh-Boyen signature which certifies the membership of the signer. In other words, this equation proves that when the randomness that hides Ai is removed from T4, T4 is verified as valid by the verification equation of the Boneh-Boyen signature scheme.More concretely, introducing four intermediate variablesδ1, δ2, δ3, and δ4 (which are intended to be δ1=αx, δ2=βx, δ3=ρx, and δ4=ηx), the underlying protocol proves the knowledge of α, β, ρ, η, x, δ1, δ2, δ3, and δ4 satisfying the equations(10a)T1=uα,(10b)T2=vβ,(10c)T3=hα+β,(10d)eg,geT4,w=eT4,gxeg1,w-αeg1,g-δ1eg2,w-βeg2,g-δ2eg,w-ηeg,g-δ4,(10e)T5=gρ,(10f)T6=ey,H1Mρeg,g-η,(10g)1=T1xu-δ1,(10h)1=T2xv-δ2,(10i)1=T5xg-δ3,(10j)1=T6xey,H1M-δ3eg,gδ4.We explain these ten equations one by one. The first three equations are exactly the same as those of (9). Equation (10d) comes from expanding the equation (11)eg,g=eT4g1-αg2-βg-η,wgxto obtain (12)eg,g=eT4,weT4,gxeg1-α,weg1α,gxeg2-β,weg2-β,gxeg-η,weg-η,gx,=eT4,weT4,gxeg1,w-αeg1,g-αxeg2,w-βeg2,g-βxeg,w-ηeg,g-ηx,replacing αx with δ1, βx with δ2, and ηx with δ4 to obtain (13)eg,g=eT4,weT4,gxeg1,w-αeg1,g-δ1eg2,w-βeg2,g-δ2eg,w-ηeg,g-δ4,and rearranging them to obtain (14)eg,geT4,w=eT4,gxeg1,w-αeg1,g-δ1eg2,w-βeg2,g-δ2eg,w-ηeg,g-δ4,which is identical to (10d). We then need to prove that the intermediate variables surely have appropriate values, namely, that δ1=αx, δ2=βx, and δ4=ηx. Equations (10g)–(10j) are for this purpose. To prove δ1=αx, we introduce (10g). This equation, together with (10a), proves that δ1=αx. Specifically, (10a) ensures that T1 is equal to uα, and then (10g) in turn ensures that (15)1=uαxu-δ1. Since u is a generator, we have that (16)αx-δ1=0,which is what we want to prove. Similarly, (10h) together with (10b) proves that βx=δ2. To prove ηx=δ4, we need to introduce another intermediate variable δ3 which is intended to be equal to ρx. Towards this end, (10e) and (10i) prove that ρx=δ3. Using this, (10f) and (10j) prove that δ4=ηx. Specifically, (10f) ensures that T6=e(y,H1(M))ρe(g,g)-η, and then (10j) in turn ensures that (17)1=ey,H1Mρeg,g-ηxey,H1M-δ3eg,gδ4.Since (10e) and (10i) ensure that δ3=ρx, canceling out e(y,H1(M))ρx and e(y,H1(M))-δ3, (10j) further ensures that (18)1=eg,g-ηxeg,gδ4,since e(g,g) is a generator, this equation ensures that (19)-ηx+δ4=0,which is what we want to prove.The security of our proposed scheme is proved as follows.Theorem 12.
If the DBDH assumption holds, the proposed construction has opener anonymity in the random oracle model.Theorem 13.
If the DLIN assumption holds, the proposed construction has admitter anonymity in the random oracle model.Theorem 14.
If theq-SDH assumption holds, the proposed construction has traceability in the random oracle model.The proofs of Theorems12, 13, and 14 are given in Appendix D.


## 8. Efficiency Comparison with Pairing-Based Group Signatures

Finally, we give a brief efficiency comparison between the proposed schemes and existing pairing-based group signature schemes (with and without the MDO property). Table2 shows a detailed comparison among such schemes.Table 2
Performance comparison among pairing-based GS-MDO and GS schemes.
Signature size # of [G,Zp,GT]-elements bits MDO Assumptions Without RO Ours (Section6) [ 449,2 , 0 ] 79364 k-bounded DLIN, SFP Yes Ours (Section7) [ 5,10,1 ] 3636 unbounded DLIN, DBDH,q-SDH No Libert-Joye [7] [53log⁡n+33,2,0] 9328 log ⁡ N + 6148 unbounded DLIN, D3DH Yes BBS [10] [ 3,6 , 0 ] 1548 - DLIN,q-SDH No Groth [32] [ 50,0 , 0 ] 8800 - DLIN,q-SDH, q-U Yes Signature Size. The signature size in terms of the number of group elements and the bit sizes for 80-bit security. We adopt the estimates of the bit sizes of group elements used in [9] (the sizes of the elements of G, Zp, and GT are 176 bits, 170 bits, and 1056 bits, respectively.) n is the number of group members. We assume that the Wee one-time signature scheme [48] is used for the instantiation of the one-time signature scheme. MDO. The security level of the message-dependent functionality, where “k-bounded” denotes that one needs, at the setup, to fix the number of tokens that will be issued, and “unbounded” denotes that one needs not fix the upper bound. Assumptions. The hardness assumption on which the scheme is based. D3DH stands for the decision 3-party Diffie-Hellman assumption [11]. The q-U assumption is defined in [32]. Without RO. Whether or not the scheme requires the random oracle model.The signature size of our standard model scheme is 10 times larger than that of Groth scheme [32]. We believe that this is a reasonably practical performance and can be implemented in practice.Compared with our scheme in the standard model, our scheme in the random oracle model is improved in two aspects: the first is the removal of the a priori upper bound on the number of tokens the admitter can issue, and the second is the substantial reduction of the signature size. When a 170-bit prime-order group is used, the signature size of our GS-MDO scheme in the standard model is 79364 bits, and that of our GS-MDO scheme in the random oracle model is 3636 bits, while that of the BBS scheme [10] is 1548 bits. (We adopt the estimates of bit sizes for group elements used in [9]). We also include more details of the performance of these schemes in Table 2. These two improvements are achieved at the cost of using random oracles, as indicated in the “Without RO” column in the table.In the Libert-Joye scheme, a signature containsO(log⁡N) group elements, whereas our schemes contain a constant number of group elements. However, our standard model scheme does not achieve the unbounded MDO property. Constructing an unbounded GS-MDO scheme secure in the standard model with a constant-signature size is an interesting open problem.Compared with the BBS scheme, we believe that the proposed scheme in the random oracle model achieves the MDO property at a reasonable cost given the increase in the signature size. As shown in Table2, the signature size of the proposed scheme is almost twice that of the BBS scheme. We also note that our random oracle model scheme achieves CCA-anonymity, which guarantees a markedly higher level of security than CPA-anonymity, which is achieved by the BBS scheme.


## 9. Conclusion and Open Problems

In this paper we proposed a new anonymous authentication primitive called group signatures with message-dependent opening. This primitive is an extension of ordinary group signatures, which relaxes the strong assumption that the opener, who is able to trace the identity of the signer of a signature, does not misuse his strong capability of breaking anonymity. The primitive does this by introducing another authority called the admitter, who is able to admit the opening of signatures on some specific messages to the opener.We formalized this new primitive by providing the syntax and security requirements of the primitive. Furthermore, we discussed the difficulties in constructing an efficient instantiation of the primitive, in particular, showed that IBE is inevitable for an instantiation. We provided one generic construction and two specific constructions. The first specific construction was proven to be secure in the standard model, while the other was proven to be secure in the random oracle model. Finally, we compared two specific constructions and known group signature schemes (with and without the message-dependent opening property).We list some open problems. We assumed that the setup of the scheme is executed honestly and that the entity who runs the setup does not collude with an adversary. An open problem is to provide a formal security requirement that does not require this assumption and an instantiation for it. Our schemes do not provide security against an adversary which may maliciously generate the opener’s or the admitter’s keys. Achieving this security is another open problem.



---

*Source: 4872403-2019-08-26.xml*