As a multi-receiver variant of public key encryption with keyword search (PEKS), broadcast encryption with keyword search (BEKS) has been proposed (Attrapadung et al. at ASIACRYPT 2006/Chatterjee-Mukherjee at INDOCRYPT 2018). Unlike broadcast encryption, no receiver anonymity is considered because the test algorithm takes a set of receivers as input and thus a set of receivers needs to be contained in a ciphertext. In this paper, we propose a generic construction of BEKS from anonymous and weakly robust 3-level hierarchical identity-based encryption (HIBE). The proposed generic construction provides outsider anonymity, where an adversary is allowed to obtain secret keys of outsiders who do not belong to the challenge sets, and provides sublinear-size ciphertext in terms of the number of receivers. Moreover, the proposed construction considers security against chosen-ciphertext attack (CCA) where an adversary is allowed to access a test oracle in the searchable encryption context. The proposed generic construction can be seen as an extension to the Fazio-Perera generic construction of anonymous broadcast encryption (PKC 2012) from anonymous and weakly robust identity-based encryption (IBE) and the Boneh et al. generic construction of PEKS (EUROCRYPT 2004) from anonymous IBE. We run the Fazio-Perera construction employs on the first-level identity and run the Boneh et al. generic construction on the second-level identity, i.e., a keyword is regarded as a second-level identity. The third-level identity is used for providing CCA security by employing one-time signatures. We also introduce weak robustness in the HIBE setting, and demonstrate that the Abdalla et al. generic transformation (TCC 2010/JoC 2018) for providing weak robustness to IBE works for HIBE with an appropriate parameter setting. We also explicitly introduce attractive concrete instantiations of the proposed generic construction from pairings and lattices, respectively.

This paper considers the problem of balancing traceability and anonymity in designated verifier signatures (DVS), which are a kind of group-oriented signatures. That is, we propose claimable designated verifier signatures (CDVS), where a signer is able to claim that he/she indeed created a signature later. Ordinal DVS does not provide any traceability, which could indicate too strong anonymity. Thus, adding claimability, which can be seen as a sort of traceability, moderates anonymity. We demonstrate two generic constructions of CDVS from (i) ring signatures, (non-ring) signatures, pseudorandom function, and commitment scheme, and (ii) claimable ring signatures (by Park and Sealfon, CRYPTO'19).

Authenticated Key Exchange (AKE) is a cryptographic protocol to share a common session key among multiple parties. Usually, PKI-based AKE schemes are designed to guarantee secrecy of the session key and mutual authentication. However, in practice, there are many cases where mutual authentication is undesirable such as in anonymous networks like Tor and Riffle, or difficult to achieve due to the certificate management at the user level such as the Internet. Goldberg et al. formulated a model of anonymous one-sided AKE which guarantees the anonymity of the client by allowing only the client to authenticate the server, and proposed a concrete scheme. However, existing anonymous one-sided AKE schemes are only known to be secure in the random oracle model. In this paper, we propose generic constructions of anonymous one-sided AKE in the random oracle model and in the standard model, respectively. Our constructions allow us to construct the first post-quantum anonymous one-sided AKE scheme from isogenies in the standard model.

The prosperous Internet communication technologies have led to e-commerce in mobile computing and made Web of Things become popular. Electronic payment is the most important part of e-commerce, so many electronic payment schemes have been proposed. However, most of proposed schemes cannot give change. Based on proxy blind signatures, an e-cash payment system is proposed in this paper to solve this problem. This system can not only provide change divisibility through Web of Things, but also provide anonymity, verifiability, unforgeability and double-spending owner track.

Existing cyber deception technologies (e.g., operating system obfuscation) can effectively disturb attackers' network reconnaissance and hide fingerprint information of valuable cyber assets (e.g., containers). However, they exhibit ineffectiveness against skilled attackers. In this study, a proactive fingerprint deception method is proposed, termed as Continuously Anonymizing Containers' Fingerprints (CACF), which modifies the container's fingerprint in the cloud resource pool to satisfy the anonymization standard. As demonstrated by experimental results, the CACF can effectively increase the difficulty for attackers.

Group signatures are signatures providing signer anonymity where signers can produce signatures on behalf of the group that they belong to. Although such anonymity is quite attractive considering privacy issues, it is not trivial to check whether a signer has been revoked or not. Thus, how to revoke the rights of signers is one of the major topics in the research on group signatures. In particular, scalability, where the signing and verification costs and the signature size are constant in terms of the number of signers N, and other costs regarding signers are at most logarithmic in N, is quite important. In this paper, we propose a revocable group signature scheme which is currently more efficient compared to previous all scalable schemes. Moreover, our revocable group signature scheme is secure under simple assumptions (in the random oracle model), whereas all scalable schemes are secure under q-type assumptions. We implemented our scheme by employing a Barreto-Lynn-Scott curve of embedding degree 12 over a 455-bit prime field (BLS-12-455), and a Barreto-Naehrig curve of embedding degree 12 over a 382-bit prime field (BN-12-382), respectively, by using the RELIC library. We showed that the online running times of our signing algorithm were approximately 14msec (BLS-12-455) and 11msec (BN-12-382), and those of our verification algorithm were approximately 20msec (BLS-12-455) and 16msec (BN-12-382), respectively. Finally, we showed that our scheme (with a slight extension) is applied to an identity management system proposed by Isshiki et al.

In conventional ID-based user authentications, privacy issues may occur, since users' behavior histories are collected in Service Providers (SPs). Although anonymous authentications such as group signatures have been proposed, these schemes rely on a Trusted Third Party (TTP) capable of tracing misbehaving users. Thus, the privacy is not high, because the TTP of tracing authority can always trace users. Therefore, the anonymous credential system using a blacklist without the TTP of tracing authority has been proposed, where blacklisted anonymous users can be blocked. Recently, an RSA-based blacklistable anonymous credential system with efficiency improvement has been proposed. However, this system still has an efficiency problem: The data size in the authentication is O(K'), where K' is the maximum number of sessions in which the user can conduct. Furthermore, the O(K')-size data causes the user the computational cost of O(K') exponentiations. In this paper, a blacklistable anonymous credential system using a pairing-based accumulator is proposed. In the proposed system, the data size in the authentication is constant for parameters. Although the user's computational cost depends on parameters, the dependent cost is O(δBL·K) multiplications, instead of exponentiations, where δBL is the number of sessions added to the blacklist after the last authentication of the user, and K is the number of past sessions of the user. The demerit of the proposed system is O(n)-size public key, where n corresponds to the total number of all sessions of all users in the system. But, the user only has to download the public key once.

In ID-based user authentications, a privacy problem can occur, since the service provider (SP) can accumulate the user's access history from the user ID. As a solution to that problem, group signatures have been researched. One of important issues in the group signatures is the user revocation. Previously, an efficient revocable scheme with signing/verification of constant complexity was proposed by Libert et al. In this scheme, users are managed by a binary tree, and a list of data for revoked users, called a revocation list (RL), is used for revocation. However, the scheme suffers from the large RL. Recently, an extended scheme has been proposed by Sadiah and Nakanishi, where the RL size is reduced by compressing RL. On the other hand, there is a problem that some overhead occurs in the authentication as a price for reducing the size of RL. In this paper, we propose an extended scheme where the authentication is speeded up by reducing the number of Groth-Sahai (GS) proofs. Furthermore, we implemented it on a PC to show the effectiveness. The verification time is about 30% shorter than that of the previous scheme by Sadiah and Nakanishi.

A purpose of password-based anonymous authentication schemes is to provide not only password-based authentication but also user anonymity. In [19], Yang et al., proposed a password-based anonymous authentication scheme (we call it YZWB10 scheme) using the password-protected credentials. In this paper, we discuss user anonymity of the YZWB10 scheme [19] against a third-party attacker, who is much weaker than a malicious server. First, we show that a third-party attacker in the YZWB10 scheme can specify which user actually sent the login request to the server. This attack also indicates that the attacker can link different login requests to be sent later by the same user. Second, we give an effective countermeasure to this attack which does not require any security for storing users' password-protected credentials.

Group signature (GS) schemes guarantee anonymity of the actual signer among group members. Previous GS schemes assume that randomness in signing is never exposed. However, in the real world, full randomness exposure can be caused by implementation problems (e.g., using a bad random number generator). In this paper, we study (im)possibility of achieving anonymity against full randomness exposure. First, we formulate a new security model for GS schemes capturing full randomness exposure. Next, we clarify that it is impossible to achieve full-anonymity against full randomness exposure without any secure component (e.g., a tamper-proof module or a trusted outside storage). Finally, we show a possibility result that selfless-anonymity can be achieved against full randomness exposure. While selfless-anonymity is weaker than full-anonymity, it is strong enough in practice. Our transformation is quite simple; and thus, previous GS schemes used in real-world systems can be easily replaced by a slight modification to strengthen the security.

PPDP (Privacy-Preserving Data Publishing) is technology that discloses personal information while protecting individual privacy. k-anonymity is a privacy model that should be achieved in PPDP. However, k-anonymity does not guarantee privacy against adversaries who have knowledge of even a few uncommon individuals in a population. In this paper, we propose a new model, called k-presence-secrecy, that prevents such adversaries from inferring whether an arbitrary individual is included in a personal data table. We also propose an algorithm that satisfies the model. k-presence-secrecy is a practical model because an algorithm that satisfies it requires only a PPDP target table as personal information, whereas previous models require a PPDP target table and almost all the background knowledge of adversaries. Our experiments show that, whereas an algorithm satisfying only k-anonymity cannot protect privacy, even against adversaries who have knowledge for one uncommon individual in a population, our algorithm can do so with less information loss and shorter execution time.

Anonymous password-based authentication protocols are designed to provide not only password-based authentication but also client anonymity. In [22], Qian et al. proposed a simple anonymous password-based authentication protocol (SAPAKE). In this paper, we reconsider the SAPAKE protocol [22] by first showing that an (third party) active attacker can impersonate the server and compute a session key with probability 1. After giving a formal model that captures such attacks, we propose a simple and secure anonymous password-based authentication (for short, S2APA) protocol that provides security against modification attacks on protocol-specific values and is more efficient than YZWB09/10 [32], [33] and SAPAKE [22]. Also, we prove that the S2APA protocol is AKE-secure against active attacks as well as modification attacks under the computational Diffie-Hellman problem in the random oracle model, and provides unconditional client anonymity against a semi-honest server, who honestly follows the protocol.

In data sharing privacy has become one of the main concerns particularly when sharing datasets involving individuals contain private sensitive information. A model that is widely used to protect the privacy of individuals in publishing micro-data is k-anonymity. It reduces the linking confidence between private sensitive information and specific individual by generalizing the identifier attributes of each individual into at least k-1 others in dataset. K-anonymity can also be defined as clustering with constrain of minimum k tuples in each group. However, the accuracy of the data in k-anonymous dataset decreases due to huge information loss through generalization and suppression. Also most of the current approaches are designed for numerical continuous attributes and for categorical attributes they do not perform efficiently and depend on attributes hierarchical taxonomies, which often do not exist. In this paper we propose a new model for k-anonymization, which is called Similarity-Based Clustering (SBC). It is based on clustering and it measures similarity and calculates distances between tuples containing numerical and categorical attributes without hierarchical taxonomies. Based on this model a bottom up greedy algorithm is proposed. Our extensive study on two real datasets shows that the proposed algorithm in comparison with existing well-known algorithms offers much higher data utility and reduces the information loss significantly. Data utility is maintained above 80% in a wide range of k values.

Tor is the most popular and well-researched low-latency anonymous communication network provides sender privacy to Internet users. It also provides recipient privacy by making TCP services available through “hidden service”, which allowing users not only to access information anonymously but also to publish information anonymously. However, based on our analysis of the hidden service protocol, we found a special combination of cells, which is the basic transmission unit over Tor, transmitted during the circuit creation procedure that could be used to degrade the anonymity. In this paper, we investigate a novel protocol-feature based attack against Tor's hidden service. The main idea resides in fact that an attacker could monitor traffic and manipulate cells at the client side entry router, and an adversary at the hidden server side could cooperate to reveal the communication relationship. Compared with other existing attacks, our attack reveals the client of a hidden service and does not rely on traffic analysis or watermarking techniques. We manipulate Tor cells at the entry router to generate the protocol-feature. Once our controlled entry onion routers detect such a feature, we can confirm the IP address of the client. We implemented this attack against hidden service and conducted extensive theoretical analysis and experiments over Tor network. The experiment results validate that our attack can achieve high rate of detection rate with low false positive rate.

To overcome the privacy limitations of conventional PKI (Public Key Infrastructure) systems, combinatorial certificate schemes assign each certificate to multiple users so that users can perform anonymous authentication. From a certificate pool of N certificates, each user is given n certificates. If a misbehaving user revokes a certificate, all the other users who share the revoked certificate will also not be able to use it. When an honest user shares a certificate with a misbehaving user and the certificate is revoked by the misbehaving user, the certificate of the honest user is said to be covered. To date, only the analysis for the worst scenario has been conducted; the probability that all n certificates of an honest user are covered when m misbehaving users revoke their certificates is known. The subject of this article is the following question: how many certificates (among n certificates) of an honest user are covered on average when m misbehaving users revoke their certificates? We present the first average-case analysis of the cover probability in combinatorial certificate schemes.

To accomplish secure communication in vehicular networks, public key infrastructure (PKI) can be employed. However, traditional PKI systems are not suitable because a unique certificate is assigned to each vehicle and thus no anonymity is guaranteed. In the combinatorial certificate schemes, each vehicle is assigned multiple certificates from a shared certificate pool and each certificate in the pool is assigned to multiple vehicles to achieve a level of anonymity. When a certificate assigned to a misbehaving vehicle is revoked, a certificate replacement procedure is executed to all vehicles sharing the certificate. To replace the revoked certificate, a randomized certificate replacement scheme probabilistically assigns different certificates to different vehicles, which can reduce collateral damage caused by repeatedly misusing a certificate and its replacement certificates. Unfortunately, previous randomized certificate replacement schemes allow unbounded collateral damage; a finite number of certificate replacements cannot detect the misbehaving vehicle with certainty. To address this problem, we propose a new randomized certificate replacement scheme with bounded collateral damage.

Password-based anonymous authentication schemes provide not only password-based authentication but also user anonymity. In [15], Yang et al., proposed a password-based anonymous authentication scheme (we call it YZWB10 scheme) using the password-protected credentials. This scheme has being standardized in ISO/IEC 20009-4 that was approved to proceed to the CD stage in the 49th ISO/IEC JTC 1/SC 27 Mexico meeting. In this paper, we analyze unlinkability of the YZWB10 scheme [15]. In particular, we show that a (malicious) server in the YZWB10 scheme can specify which user actually sent the login request to the server. Unlike Yang et al.,'s claim, the YZWB10 scheme [15] does not provide unlinkability against server.

To enhance the privacy of vehicle owners, combinatorial certificate management schemes assign each certificate to a large enough group of vehicles so that it will be difficult to link a certificate to any particular vehicle. When an innocent vehicle shares a certificate with a misbehaving vehicle and the certificate on the misbehaving vehicle has been revoked, the certificate on the innocent vehicle also becomes invalid and is said to be covered. When a group of misbehaving vehicles collectively share all the certificates assigned to an innocent vehicle and these certificates are revoked, the innocent vehicle is said to be covered. We point out that the previous analysis of the vehicle cover probability is not correct and then provide a new and exact analysis of the vehicle cover probability.

Secure authentication of low cost Radio Frequency Identification (RFID) tag with limited resources is a big challenge, especially when we simultaneously consider anonymity, un-traceability, and forward secrecy. The popularity of Internet of Things (IoT) further amplifies this challenge, as we should authenticate these mobile tags in the partial-distributed-server environments. In this paper, we propose an RFID authentication scheme in the partial-distributed-server environments. The proposed scheme owns excellent performance in terms of computational complexity and scalability as well as security properties.

A group signature scheme allows a group member to anonymously sign a message on behalf of the group. One of the important issues is the member revocation, and lots of revocable schemes have been proposed so far. A scheme recently proposed by Libert et al. achieves that O(1) or O(log N) efficiency of communication and computation except for the revocation list size (also the revocation cost), for the total number of members N and the number of revoked members R. However, since a signature is required for each subset separated from the set of non-revoked members, the size is about 900R Bytes in the 128-bit security. In the case of R=100,000, it amounts to about 80MB. In this paper, we extend the scheme to reduce the revocation list (also the revocation cost), by accumulating T subsets, which is signed for the revocation list. The revocation list size is reduced by 1/T. Unfortunately, the public key size, membership certificate size and the cost of a witness computation needed for signing increase related to T.