Search

During the Coincheck incident, which recorded the largest damages in cryptocurrency history in 2018, it was demonstrated that using Mosaic token can have a certain effect. Although it seems attractive to employ tokens as countermeasures for cryptocurrency leakage, Mosaic is a specific token for the New Economy Movement (NEM) cryptocurrency and is not employed for other blockchain systems or cryptocurrencies. Moreover, although some volunteers tracked leaked NEM using Mosaic in the CoinCheck incident, it would be better to verify that the volunteers can be trusted. Simultaneously, if someone (e.g., who stole cryptocurrencies) can identify the volunteers, then that person or organization may be targets of them. In this paper, we propose an anonymous trust-marking scheme on blockchain systems that is universally applicable to any cryptocurrency. In our scheme, entities called token admitters are allowed to generate tokens adding trustworthiness or untrustworthiness to addresses. Anyone can anonymously verify whether these tokens were issued by a token admitter. Simultaneously, only the designated auditor and no one else, including nondesignated auditors, can identify the token admitters. Our scheme is based on accountable ring signatures and commitment, and is implemented on an elliptic curve called Curve25519, and we confirm that both cryptographic tools are efficient. Moreover, we also confirm that our scheme is applicable to Bitcoin, Ethereum, and NEM., An extended abstract appeared at the 3rd IEEE International Conference on Blockchain and Cryptocurrency, ICBC 2021. This is the full version

Chu et al. (ASIACCS 2012) proposed group signature with time-bound keys (GS-TBK), where each signing key is associated with expiry time $\tau$ τ . In addition, to prove membership of the group, a signer needs to prove that the expiry time has not passed, i.e., $t t τ , where $t$ t is the current time. A signer whose expiry time has passed is automatically revoked, and this revocation is called natural revocation. Signers can be revoked simultaneously before their expiry times if the credential is compromised. This revocation is called premature revocation. A nice property in the Chu et al. proposal is that the size of revocation lists can be reduced compared to those of Verifier-Local Revocation (VLR) group signature schemes by assuming that natural revocation accounts for most of the signer revocations in practice, and prematurely revoked signers are only a small fraction. In this paper, we point out that the definition of traceability of Chu et al. did not capture the unforgeability of expiry time for signing keys, which guarantees that no adversary who has a signing key associated with expiry time $\tau$ τ can compute a valid signature after $\tau$ τ has passed. This situation significantly reduces the dependability of the system since legitimate signing keys may be used for providing a forged signature. We introduce a security model that captures unforgeability, and propose a secure GS-TBK scheme in the new model. Our scheme also provides constant signing costs, whereas those of the previous schemes depended on the bit-length of the time representation. Finally, we provide the implementation results. We employ Barreto-Lynn-Scott (BLS) curves with 455-bit prime order and the RELIC library, and demonstrate that our scheme is feasible in practical settings.

Maintaining a balance between anonymity and traceability is a fundamental issue in privacy-preserving systems. Isshiki et al. proposed an identity management system based on group signatures in which a service provider anonymously determines whether or not users of the service are legitimate members, and only a bill collector can identify users for the purposes of sending them invoices. It is particularly worth noting that, under the Isshiki system, the service provider is not required to manage personal information such as user lists, which allows the system to outperform other in terms of preserving user privacy and managing personal information leakage risk. It is also noteworthy that the Isshiki system only considers cases in which the bill collector identifies users who have used the service and that, in fact, identified users who ignore invoices can use the service for free. In this paper, we extended the Isshiki system by adding a smart contract-enabled enforcement bill collection functionality. Under this functionality, deposits made by users who do not pay a service fee are automatically transferred to the bill collector. Because of their centralized structure, group signatures are not suitable to blockchain systems, therefore, the proposed system employs accountable ring signatures as building blocks. The privacy-preserving enforced bill collection system is implemented using the accountable ring signature scheme developed by Bootle et al. and Ethereum smart contracts. To reduce the gas costs associated with running smart contracts, the smart contract is not run unless the user ignores an invoice, and basic procedures are run via an off-chain channel. To avoid the use of heavy cryptographic algorithms in carrying out the accountable ring signature scheme for running smart contracts, we employed standard elliptic curve digital signature algorithm (ECDSA) signatures without especially changing the state to be verified in smart contracts.

This paper describes techniques that enable vehicles to collect local information (such as road conditions and traffic information) and report it via road-to-vehicle communications. To exclude malicious data, the collected information is signed by each vehicle. In this communication system, the location privacy of vehicles must be maintained. However, simultaneously linkable information (such as travel routes) is also important. That is, no such linkable information can be collected when full anonymity is guaranteed using cryptographic tools such as group signatures. Similarly, continuous linkability (via pseudonyms, for example) may also cause problem from the viewpoint of privacy. In this paper, we propose a road-to-vehicle communication system with relaxed anonymity via group signatures with time-token dependent linking (GS-TDL). Briefly, a vehicle is unlinkable unless it generates multiple signatures in the same time period. We provide our experimental results (using the RELIC library on a cheap and constrained computational power device, Raspberry Pi) and simulate our system by using a traffic simulator (PTV), a radio wave propagation analysis tool (RapLab), and a network simulator (QualNet). Though a similar functionality of time-token-dependent linking was proposed by Wu et al. (“Balanced trustworthiness, safety, and privacy in vehicle-to-vehicle communications,” IEEE Trans. Veh. Technol., vol. 59, 2010), we can show an attack against the scheme where anyone can forge a valid group signature without using a secret key. In contrast, our GS-TDL scheme is provably secure. In addition to the time-dependent linking property, our GS-TDL scheme supports verifier-local revocation, where a signer (vehicle) is not involved in the revocation procedure. It is particularly worth noting that no secret key or certificate of a signer (vehicle) must be updated, whereas the security credential management system must update certificates frequently for vehicle privacy. Moreover, our technique maintains constant signing and verification costs by using the linkable part of signatures. This might be of independent interest.

Several cryptographic tools provide anonymity in a cryptographic sense, but solely using such a tool does not guarantee anonymity; for example, even if the underlying cryptographic primitives enable anonymity in some sense, a communication system using these tools may reveal the senders’ IP address. Moreover, since a certificate of public key infrastructure contains information of a key holder, and that contradicts anonymity of the key holder, the certificate must be removed. Therefore, it seems difficult to check the validity of the public key in an anonymous environment. That is, constructing a secure and anonymous communication protocol, where end-to-end encryption and anonymous authentication are achieved simultaneously, is an important issue to be solved. In ACM SAC 2014 (and IEEE Trans. Emerging Topics Comput. 2016), such a protocol was proposed, where it applies identity-based encryption (IBE) for packet encryption without contradicting anonymity. However, this protocol is inefficient and approximately 20 times slower than that of SSL communications because IBE requires heavy cryptographic pairing computations. In this paper, we propose a more efficient, secure, and anonymous communication protocol, which achieves the same security level as the IBE-based protocol does. The protocol is exempted from pairing computation for establishing a secure channel by applying hybrid encryption instead of IBE. We implement the protocol and show that it is more efficient (overall approximately 1.2 times faster) than the IBE-based protocol. In particular, the decryption algorithm of our protocol is several hundred times faster than that of the IBE-based protocol. In our protocol, we employ the ElGamal KEM scheme and 128-bit AES as the underlying KEM and DEM schemes, respectively, and we have used the TEPLA library for the prototype implementation.

Let us consider a situation where a client (Alice) frequently buys a certain kind of product from a shop (Bob) (e.g., an online music service sells individual songs at the same price, and a client buys songs multiple times in a month). In this situation, Alice and Bob would like to aggregate the total transactions and pay once per month because individual payments are troublesome. Though optimistic fair exchange (OFE) has been considered in order to swap electronic items simultaneously, known OFE protocols cannot provide such aggregate function efficiently because various costs are bounded by the number of transactions in the period. In order to run this aggregation procedure efficiently, we introduce a new kind of OFE called accumulable OFE (AOFE) that allows clients to efficiently accumulate payments in each period. In AOFE, any memory costs, computational costs, and communication complexity of the payment round must be constant in terms of the number of transactions. Since a client usually has just a low power and poor memory device, these efficiencies are desirable in practice. Currently, known approaches (e.g., based on verifiably encrypted signature scheme) are not very successful for constructing AOFE. Thus, we consider a new approach based on a new cryptographic primitive called verifiably encrypted homomorphic signature scheme (VEHS). In this paper, we propose a generic construction of AOFE from VEHS and also present a concrete VEHS scheme over a composite-order bilinear group by using the dual-form signature techniques. This VEHS scheme is also of independent interest. Since we can prove the security of VEHS without random oracles, our AOFE protocol is also secure without random oracles. Finally, we implemented our AOFE protocol, and it is efficient enough for practical use.

To provide a search functionality for encrypted data, public key encryption with keyword search (PEKS) has been widely recognized. In actual usage, a PEKS scheme should be employed with a PKE scheme since PEKS itself does not support the decryption of data. Since a naive composition of a PEKS ciphertext and a PKE ciphertext does not provide CCA security, several attempts have been made to integrate PEKS and PKE in a joint CCA manner (PEKS/PKE for short). In this paper, we further extend these works by integrating secure-channel free PEKS (SCF-PEKS) and PKE, which we call SCF-PEKS/PKE, where no secure channel is required to send trapdoors. We give a formal security definition of SCF-PEKS/PKE in a joint CCA manner, and propose a generic construction of SCF-PEKS/PKE based on anonymous identity-based encryption, tag-based encryption, and one-time signature. We also strengthen the current consistency definition according to the secure-channel free property, and show that our construction is strongly consistent if the underlying IBE provides unrestricted strong collision-freeness which is defined in this paper. We also show that such an IBE scheme can be constructed by employing the Abdalla et al. transformations (TCC 2010/J. Cryptology 2018). Finally, as an application of SCF-PEKS/PKE, we strengthen the security of encrypted Electronic Medical Record (EMR) system proposed by Guo and Yau (J. Medical Sys. 2015).

The key escrow problem is one of the main barriers to the widespread real-world use of identity-based encryption (IBE). Specifically, a key generation center (KGC), which generates secret keys for a given identity, has the power to decrypt all ciphertexts. At PKC 2009, Chow defined a notion of security against the KGC, that relies on assuming that it cannot discover the underlying identities behind ciphertexts. However, this is not a realistic assumption since, in practice, the KGC manages an identity list and hence it can easily guess the identities corresponding to given ciphertexts. Chow later closed the gap between theory and practice by introducing a new entity called an identity-certifying authority (ICA) and proposed an anonymous key-issuing protocol. Essentially, this allows the users, KGC, and ICA to interactively generate secret keys without users ever having to reveal their identities to the KGC. Unfortunately, the proposed protocol did not include a concrete security definition, meaning that all of the subsequent works following Chow lack the formal proofs needed to determine whether or not it delivers a secure solution to the key escrow problem.

Group signatures are a class of digital signatures with enhanced privacy. By using this type of signature, a user can sign a message on behalf of a specic group without revealing his identity, but in the case of a dispute, an authority can expose the identity of the signer. However, in some situations it is only required to know whether a specic user is the signer of a given signature. In this case, the use of a standard group signature may be problematic since the specied user might not be the signer of the given signature, and hence, the identity of the actual signer will be exposed. Inspired by this problem, we propose the notion of a deniable group signature, where, with respect to a signature and a user, the authority can issue a proof showing that the specied user is NOT the signer of the signature, without revealing the actual signer. We also describe a fairly practical construction by extending the Groth group signature scheme (ASIACRYPT 2007). In particular, a denial proof in our scheme consists of 96 group elements, which is about twice the size of a signature in the Groth scheme. The proposed scheme is provably secure under the same assumptions as those of the Groth scheme.

Group signature with verifier-local revocation (VLR-GS) is a special type of revocable group signature which enables a user to sign messages without referring to information regarding revoked users. Although there have been several proposals of VLR-GS schemes since the first scheme proposed by Boneh and Shacham [CCS 2004], all of these schemes only achieve a security notion called selfless anonymity, which is strictly weaker than the de facto standard security notion, full anonymity where an adversary is allowed to corrupt all users. Thus, for more than a decade, it has been an open problem whether a fully anonymous VLR-GS scheme can be constructed. In this paper, we give an affirmative answer to this problem. Concretely, we show the construction of a fully anonymous VLR-GS scheme from a digital signature scheme, a key-private public key encryption scheme, and a non-interactive zero-knowledge proof system. Moreover, we give a fully anonymous VLR-GS scheme with backward unlinkability, which ensures that even after a user is revoked, signatures produced by the user before the revocation remain anonymous.

In this paper, we introduce the notion of secret key encryption with non-interactive opening (SKENO). With SKENO, one can make a non-interactive proof π to show that the decryption result of a ciphertext C under a shared secret key K is indeed plaintext M without revealing K itself. SKENO is the secret key analogue of public key encryption with non-interactive opening (PKENO). We give a generic construction of SKENO from verifiable random function (VRF) with certain stronger uniqueness, for example, the Hohenberger–Waters VRF and the Berbain–Gilbert I V-dependent stream cipher construction. Although the strong primitive VRF is used, by taking advantage of the features of the stream cipher, we can still achieve good performance without sacrificing much of the efficiency. Though our VRF-based SKENO construction does not require random oracles, we show that SKENO can be constructed from weak VRF (which is strictly weaker primitive than VRF) in the random oracle model.

Collecting and analyzing personal data is important in modern information applications. Though the privacy of data providers should be protected, some adversarial users may behave badly under circumstances where they are not identified. However, the privacy of honest users should not be infringed. Thus, detecting anomalies without revealing normal users-identities is quite important for operating information systems using personal data. Though various methods of statistics and machine learning have been developed for detecting anomalies, it is difficult to know in advance what anomaly will come up. Thus, it would be useful to provide a "general" framework that can employ any anomaly detection method regardless of the type of data and the nature of the abnormality. In this paper, we propose a privacy preserving anomaly detection framework that allows an authority to detect adversarial users while other honest users are kept anonymous. By using cryptographic techniques, group signatures with message-dependent opening (GS-MDO) and public key encryption with non-interactive opening (PKENO), we provide a correspondence table that links a user and data in a secure way, and we can employ any anonymization technique and any anomaly detection method. It is particularly worth noting that no big brother exists, meaning that no single entity can identify users, while bad behaviors are always traceable. We also show the result of implementing our framework. Briefly, the overhead of our framework is on the order of dozens of milliseconds.

Chu et al. (ASIACCS 2012) proposed group signature with time-bound keys (GS-TBK) where each signing key is associated to an expiry time τ. In addition to prove the membership of the group, a signer needs to prove that the expiry time has not passed, i.e., t

In public key encryption with keyword search (PEKS), a secure channel must be required in order to send trapdoors to the server, whereas in secure-channel free PEKS (SCF-PEKS), no such secure channel is required. As an extension of SCF-PEKS, Wang et al. (NSS 2016) proposed SCF-PEKS with multiple keywords (SCF-MPEKS). In this paper, we further extend the Wang et al. result by proposing the generic construction of SCF-MPEKS from hidden vector encryption (HVE), tag-based encryption, and a one-time signature. Our generic construction provides adaptive security, where the test queries are allowed in the security model, and does not require random oracles. On the other hand, the Wang et al. scheme did not consider adaptive security, and the scheme is secure in the random oracle model. We give an instantiation of our generic construction by employing the Park-Lee-Susilo-Lee HVE scheme (Information Sciences 2013). This is the first adaptive secure SCF-MPEKS scheme in the standard model.

Revoking corrupted users is a desirable functionality for cryptosystems. Since Boldyreva, Goyal, and Kumar (ACM CCS 2008) proposed a notable result for scalable revocation method in identity-based encryption (IBE), several works have improved either the security or the efficiency of revocable IBE (RIBE). Currently, all existing scalable RIBE schemes that achieve adaptively security against decryption key exposure resistance (DKER) can be categorized into two groups; either with long public parameters or over composite-order bilinear groups. From both practical and theoretical points of views, it would be interesting to construct adaptively secure RIBE scheme with DKER and short public parameters in prime-order bilinear groups.

Boneh and Franklin gave a naive revocation method in identity-based encryption (IBE) which imposes a huge overhead into the key generation center. Later, Boldyreva, Goyal, and Kumar proposed an elegant way of achieving an IBE with efficient revocation, called revocable IBE (RIBE). In this paper, we revisit RIBE from the viewpoint of both security models and constructions. First, we introduce a realistic threat, which we call decryption key exposure, and show that all prior RIBE constructions, except the Boneh-Franklin one, are vulnerable to decryption key exposure. Next, we propose the first scalable RIBE scheme with decryption key exposure resistance by combining the (adaptively secure) Waters IBE scheme and the (selectively secure) Boneh-Boyen IBE scheme, and show that our RIBE scheme is more efficient than all previous adaptively secure scalable RIBE schemes. In addition, we extend our interest into identity-based signatures; we introduce a new security definition of revocable identity-based signature (RIBS) with signing key exposure resistance, and propose the first scalable RIBS scheme based on the Paterson-Schuldt IBS. Finally, we provide implementation results of our schemes to adduce the feasibility of our schemes.

In practice, revocation functionality is indispensable to the public key cryptosystems since there are threats of leaking a secret key by hacking or legal situation of expiration of contract for using system. In the public key infrastructure setting, numerous solutions have been proposed, and in the Identity Based Encryption (IBE) setting, a recent series of papers proposed revocable IBE schemes. Delegation of key generation is also an important functionality in cryptography from a practical standpoint since it allows reduction of excessive workload for a single key generation authority. Although efficient solutions for either revocation or delegation of key generation in IBE systems have been proposed, an important open problem is efficiently delegating both the key generation and revocation functionalities in IBE systems. Even if the goal is very natural, there are some obstacles to achieve both functionalities at the same time. Libert and Vergnaud, for instance, left this as an open problem in their CT-RSA 2009 paper. In this paper, we propose the first efficient solution for this problem. We prove the selective-ID security of our proposal under the Decisional Bilinear Diffie-Hellman assumption in the standard model.

In this paper, we reevaluate leakage resilient cryptography from the viewpoint of game theory. We provide a general framework on leakage resilience in game theoretic setting and show that it is of each party's interest not to deviate from the protocol, i.e., their behavior is rational which assures them the highest incentive. We show that it is enough for a Public Key Encryption (PKE) scheme to be Computational Threat-Free Nash Equilibrium (CTFNE) for being leakage resilient. To be specific, CTFNE is not guaranteed if an internal state of a CCLA1 (Chosen Ciphertext with Leakage Attack)-secure Key Encapsulation Mechanism (KEM) of PKE is updated using a poor randomness with low-entropy. This work thus allows us for arguing about the strategic behavior of players in protocols where leakage is allowed.

Group signature is a central topic of cryptography with anonymity, and its several applications have been considered so far, e.g., privacy-preserving vehicle communications. Since anonymity a.k.a. unlinkability is quite strong in certain situations and it requires heavy cryptographic costs, group signatures with relaxed anonymity also have been proposed. For example, group signatures with controllable linkability was proposed by Hwang et al., LightSec 2011 where an authority called Linker can anonymously check whether two group signatures are made by the same signer or not by using a linking key. However, the linking algorithm requires a heavy computation, i.e., bilinear pairings. In this paper, we propose the notion group signatures with time-token dependent Linking GS-TDL, where a signer is unlinkable unless it generates multiple signatures at the same time period. It is particularly worth noting that our linking algorithm does not require cryptographic computations i.e., comparisons to determine two elements are the same. Moreover, the signature size is 25i??% shorter than that of the Hwang et al. scheme, and is 34i??% shorter than that of the Boneh-Boeyn-Shacham short group signature scheme. Our GS-TDL scheme supports verifier-local revocation VLR, which maintains constant signing and verification costs by using the linkable part of signatures. These appear to be related to independent interests. Finally, we provide our experimental results using the TEPLA library on a cheap and constrained computational power device, Raspberry Pi.

Public key infrastructure has been widely used, but its certificate must be removed when a corresponding public key is sent via an anonymous communication channel in order to maintain anonymity. It is because the certificate contains information of the key holder, and that contradicts anonymity. A secure and anonymous communication protocol was proposed to address this issue, where end-to-end encryption and anonymous authentication are achieved simultaneously. It applies identity-based encryption (IBE) for packet encryption. However, because IBE requires heavy pairing computations, this protocol is inefficient and approximately 20 times slower than that of SSL communications. In this paper, we propose a more efficient, secure, and anonymous communication protocol, which achieves the same security level as the IBE-based protocol does. The protocol is exempted from pairing computation for establishing a secure channel by applying hybrid encryption instead of IBE. We implement the protocol and show that it is more efficient (overall approximately 1.2 times faster) than the IBE-based protocol. In particular, the decryption algorithm of our protocol is several hundred times faster than that of the IBE-based protocol.

We propose the notion of disavowable public key encryption with non-interactive opening (disavowable PKENO) where, for a ciphertext and a message, the receiver of the ciphertext can issue a proof that the plaintext of the ciphertext is NOT the message, and give a fairly practical construction.

Let us consider a situation where a client (Alice) frequently buys a certain kind of product from a shop (Bob) (e.g., an online music service sells individual songs at the same price, and a client buys songs multiple times in a month). In this situation, Alice and Bob would like to aggregate the total transactions and pay once per month because individual payments are troublesome. Though optimistic fair exchange (OFE) has been considered in order to swap electronic items simultaneously, known OFE protocols cannot provide such aggregate function efficiently because various costs are bounded by the number of transactions in the period. In order to run this aggregation procedure efficiently, we introduce a new kind of OFE called Accumulable OFE (AOFE) that allows clients to efficiently accumulate payments in each period. In AOFE, any memory costs, computational costs, and communication complexity of the payment round must be constant in terms of the number of transactions. Since a client usually has just a low power and poor memory device, these efficiency are desirable in practice. Currently known approaches (e.g., based on verifiably encrypted signature scheme) are not very successful for constructing AOFE. Thus, we consider a new approach based on a new cryptographic primitive called verifiably encrypted homomorphic signature scheme (VEHS). In this paper, we propose a generic construction of AOFE from VEHS, and also present a concrete VEHS scheme over a composite-order bilinear group by using the dual-form signature techniques. This VEHS scheme is also of independent interest. Since we can prove the security of VEHS without random oracles, our AOFE protocol is also secure without random oracles. Finally, we implemented our AOFE protocol, and it is efficient enough for practical use.

Nowadays, sensitive data is treated for a constellation of purposes, e.g., establishing the presence or absence of causal association among certain diseases. Then, statistics of sensitive data needs to be computed, and a number of methods for computing such statistics with concerning privacy so far have been investigated, e.g., secure computation, differential privacy, k-anonymity, etc. On the contrary, it seems not clear how to collect sensitive data with concerning privacy in the first place. Moreover, the cost for data collection should be considered if the number of data suppliers is relatively large. In this paper, we propose an anonymous data collection system with mediators, where no mediator knows actual data, but simultaneously mediators can check a data format whether data belongs to a certain range. Then, data with the expected format can be collected in a "secure" and "efficient" way. For constructing this system, we employ public key encryption with an additional functionality which is called restrictive public key encryption RPKE. Finally, we estimate the performance of the proposed system in which existing concrete constructions are used and confirm it is sufficiently efficient for practical use.

Revocable Hierarchical Identity-Based Encryption (RHIBE) is a variant of Identity-Based Encryption (IBE), which enables the dynamic user management; a Key Generation Center (KGC) of a usual IBE has a key issuing ability. In contrast, in a RHIBE, a KGC can revoke compromised secret keys and even delegate both key issuing ability and revocation ability.

In online services, e.g., Online shopping, a service provider (SP) manages access logs containing customers' buying histories. Therefore, user's personal information, e.g., Their hobbies and diversions, is revealed from the exposed logs if each customer can be linked. In fact, such information exposure has occurred due to the popularization of online services. To cope with this problem, SPs may only have to delete access logs, but then no illegitimate users, who accessed the server illegally, will be traced from the logs. In this paper, we propose a log management mechanism where (1) no user information is revealed even if logs are exposed, but (2) illegitimate users can be traced when necessary. Specifically, we consider single sign on (SSO) systems, since plural access logs might be connected by one account, and this could trigger the above privacy infringement problem. We construct our privacy-enhanced access log management mechanism based on the Wang-Wang-Susilo SSO system (TrustCom 2013) which applies nominative signatures as its building block. Specifically, we realize the system by additionally applying the invisibility property of the Schuldt-Hanaoka nominative signature scheme (ACNS 2011). Finally, we estimate the efficiency of the proposed system by using Pairing-Based Cryptography (PBC) library and confirmed that for each algorithm, computation time is at most just over 80 milliseconds on a PC, which seems sufficiently practical.

Various techniques need to be combined to realize anonymously authenticated communication. Cryptographic tools enable anonymous user authentication while anonymous communication protocols hide users' IP addresses from service providers. One simple approach for realizing anonymously authenticated communication is their simple combination, but this gives rise to another issue; how to build a secure channel. The current public key infrastructure cannot be used since the user's public key identifies the user. To cope with this issue, we propose a protocol that uses identity-based encryption for packet encryption without sacrificing anonymity, and group signature for anonymous user authentication. Communications in the protocol take place through proxy entities that conceal users' IP addresses from service providers. The underlying group signature is customized to meet our objective and improve its efficiency. We also introduce a proof-of-concept implementation to demonstrate the protocol's feasibility. We compare its performance to SSL communication and demonstrate its practicality, and conclude that the protocol realizes secure, anonymous, and authenticated communication between users and service providers with practical performance., Comment: This is a preprint version of our paper presented in SAC'14, March 24-28, 2014, Gyeongju, Korea. ACMSAC 2014

If there are many displaced workers in a company, then a person who goes for job hunting might not select this company. That is, the number of members who quit is quite negative information. Similarly, in revocable group signature schemes, if one knows (or guesses) the number of revoked users (sayr), then one may guess the reason behind such circumstances, and it may lead to harmful rumors. However, no previous revocation procedure can achieve hidingr. In this paper, we propose the first revocable group signature scheme, whereris kept hidden, which we callr-hiding revocable group signature. To handle this property, we newly define the security notion called anonymity with respect to the revocation which guarantees the unlinkability of revoked users.

The number of computer security incidents is rising in unison with the development of cyber-society. One reason for this is a lack of users' security awareness. The widespread use of mobile devices further complicates this problem. An approach for raising the awareness level is introducing a system that visualizes and issues alerts of security risks end-users. This paper introduces the architecture of such a system. It analyzes information by monitoring the user's end-to-end communication and its related entities, looks up knowledge bases, and provides alerts by directly visualizing risks to the user. One characteristic of this system is its ability to enable customized visualization for each user, which boosts the user's risk awareness and understanding. This paper also introduces the system's proof-of-concept implementation, which demonstrates the architecture's feasibility. Based on the prototype, the paper discusses the direction of further technical development.

In ACM CCS 2008, Boldyreva et al. proposed an elegant way of achieving an Identity-based Encryption (IBE) with efficient revocation, which we call revocable IBE (RIBE). One of the significant benefit of their construction is scalability, where the overhead of the trusted authority is logarithmically increased in the number of users, whereas that in the Boneh-Franklin naive revocation way is linearly increased. All subsequent RIBE schemes follow the Boldyreva et al. security model and syntax. In this paper, we first revisit the Boldyreva et al. security model, and aim at capturing the exact notion for the security of the naive but non-scalable Boneh-Franklin RIBE scheme. To this end, we consider a realistic threat, which we call decryption key exposure. We also show that all prior RIBE constructions except for the Boneh-Franklin one are vulnerable to decryption key exposure. As the second contribution, we revisit approaches to achieve (efficient and adaptively secure) scalable RIBE schemes, and propose a simple RIBE scheme, which is the first scalable RIBE scheme with decryption key exposure resistance, and is more efficient than previous (adaptively secure) scalable RIBE schemes. In particular, our construction has the shortest ciphertext size and the fastest decryption algorithm even compared with all scalable RIBE schemes without decryption key exposure resistance.

This paper introduces a new capability of the group signature, called message-dependent opening. It is intended to weaken the higher trust put on an opener, that is, no anonymity against an opener is provided by ordinary group signature. In a group signature system with message-dependent opening (GS-MDO), in addition to the opener, we set up the admitter which is not able to open any user's identity but admits the opener to open signatures by specifying messages whose signatures should be opened. For any signature whose corresponding message is not specified by the admitter, the opener cannot extract the signer's identity from it. In this paper, we present formal definitions and constructions of GS-MDO. Furthermore, we also show that GS-MDO implies identity-based encryption, and thus for designing a GS-MDO scheme, identity-based encryption is crucial. Actually, we propose a generic construction of GS-MDO from identity-based encryption and adaptive NIZK proofs, and its specific instantiation from the Groth-Sahai proof system by constructing a new (k-resilient) identity-based encryption scheme which is compatible to the Groth-Sahai proof.

In the public key cryptosystems, revocation functionality is required when a secret key is corrupted by hacking or the period of a contract expires. In the public key infrastructure setting, numerous solutions have been proposed, and in the Identity Based Encryption (IBE) setting, a recent series of papers proposed revocable IBE schemes. Delegation of key generation is also an important functionality in cryptography from a practical standpoint since it allows reduction of excessive workload for a single key generation authority. Although efficient solutions for either revocation or delegation of key generation in IBE systems have been proposed, an important open problem is efficiently delegating both the key generation and revocation functionalities in IBE systems. Libert and Vergnaud, for instance, left this as an open problem in their CT-RSA 2009 paper. In this paper, we propose the first solution for this problem. We prove the selective-ID security of our proposal under the Decisional Bilinear Diffie-Hellman assumption in the standard model.

In homomorphic encryption schemes, anyone can perform homomorphic operations, and therefore, it is difficult to manage when, where and by whom they are performed. In addition, the property that anyone can ‘‘freely” perform the operation inevitably means that ciphertexts are malleable, and it is well-known that adaptive chosen ciphertext (CCA) security and the homomorphic property can never be achieved simultaneously. In this paper, we show that CCA security and the homomorphic property can be simultaneously handled in situations that the user(s) who can perform homomorphic operations on encrypted data should be controlled/limited, and propose a new concept of homomorphic public-key encryption, which we call keyed-homomorphic public-key encryption (KH-PKE). By introducing a secret key for homomorphic operations, we can control who is allowed to perform the homomorphic operation. To construct KH-PKE schemes, we introduce a new concept, a homomorphic transitional universal hash family, and present a number of KH-PKE schemes through hash proof systems. We also present a practical construction of KH-PKE from the DDH assumption. For l-bit security, our DDH-based scheme yields only l-bit longer ciphertext size than that of the Cramer-Shoup PKE scheme.

We identify a potential weakness in the standard security model for dynamic group signatures which appears to have been overlooked previously. More specifically, we highlight that even if a scheme provably meets the security requirements of the model, a malicious group member can potentially claim ownership of a group signature produced by an honest group member by forging a proof of ownership. This property leads to a number of vulnerabilities in scenarios in which dynamic group signatures are likely to be used. We furthermore show that the currently most efficient dynamic group signature scheme does not provide protection against this type of malicious behavior. To address this, we introduce the notion of opening soundness for group signatures which essentially requires that it is infeasible to produce a proof of ownership of a valid group signature for any user except the original signer. We then show a relatively simple modification of the scheme by Groth (ASIACRYPT 2007, full version) which allows us to prove opening soundness for the modified scheme without introducing any additional assumptions. We believe that opening soundness is an important and natural security requirement for group signatures, and hope that future schemes will adopt this type of security.

As well-known results, timed-release encryption (TRE) and public key encryption scheme with keyword search (PEKS) are very close to identity-based encryption (IBE), respectively. It seems natural that there is a close relationship between TRE and PEKS. However, no explicit bridge has been shown between TRE and PEKS so far. In this paper, we show that TRE can be generically constructed by PEKS with extended functionalities, called secure-channel free PEKS (SCF-PEKS) with adaptive security, and discuss the reason why PEKS and (nonadaptive) SCF-PEKS are not suitable for constructing TRE. In addition to this result, we also show that adaptive SCF-PEKS can be generically constructed by anonymous IBE only. That is, for constructing adaptive SCF-PEKS we do not have to require any additional cryptographic primitive compared to the Abdalla et al. PEKS construction (J. Cryptology 2008), even though adaptive SCF-PEKS requires additional functionalities. This result seems also independently interesting.

In this paper, we investigate a new concept, called share selectable secret sharing, where no unauthorized set can obtain information of the secret (in the information-theoretic sense) even if shares are selectable as arbitrary values which are independent of the secret. We propose two totally selectable (i.e., all users' shares are selectable) secret sharing schemes with unanimous structure. We also propose a quasiselectable (i.e., a part of each user's share is selectable) secret sharing scheme with certain hierarchical structures which contains special cases of the hierarchical threshold structures introduced by Tamir Tassa in TCC2004 (or its full version (J. Cryptology 2007)). If all selectable shares are randomly chosen, then our schemes are perfect. Finally, we discuss the effect of the leakage information of the secret if a weak secret is indicated as a selectable share.

Identity-Based Proxy Re-Encryption (IB-PRE) has been proposed by Green and Ateniese (ACNS2007), where the proxy transforms a source ciphertext encrypted by a delegator's identity into a destination ciphertext that can be decrypted using a delegatee's secret key corresponding to the delegatee's identity. By using IB-PRE, we expect that mailing-list systems can be constructed without public key certificates. However, in all previous IB-PRE, information about whether a source ciphertext (encrypted by a mailing-list address) is the source of a destination ciphertext (encrypted by an e-mail address) or not, is revealed from both the source ciphertext and the destination ciphertext. In this paper, for the first time we propose an IB-PRE scheme with source hiding property, where no information about source identity is revealed from the destination ciphertext. Our work is the valuable and important milestone for establishing the secure PRE-based mailing-list system without public key certificates.

In many distributed data mining settings, disclosure of the original data sets is not acceptable due to privacy concerns. To address such concerns, privacy-preserving data mining has been an active research area in recent years. While confidentiality is a key issue, scalability is also an important aspect to assess the performance of a privacypreserving data mining algorithms for practical applications. With this in mind, Kantarcioglu et al. proposed secure dot product and secure setintersection protocols for privacy-preserving data mining in malicious adversarial model using zero knowledge proofs, since the assumption of semi-honest adversary is unrealistic in some settings. Both the computation and communication complexities are linear with the number of data items in the protocols proposed by Kantarcioglu et al. In this paper, we build efficient and secure dot product and set-intersection protocols in malicious model. In our work, the complexity of computation and communication for proof of knowledge is always constant (independent of the number of data items), while the complexity of computation and communication for the encrypted messages remains the same as in Kantarcioglu et al.'s work (linear with the number of data items). Furthermore, we provide the security model in Universal Composability framework.

There are many cryptographic schemes with anonymity, such as group signatures. As one important property, anonymity revocation has been introduced. In such schemes, the fact of whether a signer's rights have been revoked or not is important additional information. For example, if a third party knows that there are many revoked members in a company, then the company's reputation may be damaged in many ways. People may think that there might be many problematic employees (who have bad behavior-s) in this company, there might be many people who have quit, i.e., the labor environment may not be good, and so on. To avoid such harmful rumors, in this paper, we propose an Anonymous Designated Verifier Signature (ADVS) scheme with revocation. In ADVS, a designated verifier can only verify a signature anonymously, and a third party cannot identify whether the rights of the signer have been revoked or not. We show two security-enhanced schemes as applications of our scheme: a biometric-based remote authentication scheme, and an identity management scheme.

Timed-Release Encryption (TRE) (proposed by May in 1993) prevents even a legitimate recipient decrypting a ciphertext before a semitrusted Time Server (TS) sends trapdoor sT assigned with a release time T of the encryptor's choice. Cathalo et al. (ICICS2005) and Chalkias et al. (ESORICS2007) have already considered encrypting a message intended to multiple recipients with the same release time. These schemes are efficient compared with previous TRE schemes with recipient-to-recipient encryption, since the most costly part (especially pairing computation) has only to be computed once, and this element is used commonly. One drawback of these schemes is the ciphertext size and computational complexity, which depend on the number of recipients N. In this paper, for the first time we propose Timed-Release Proxy Re-Encryption (TR-PRE) scheme. As in PRE, a semi-trusted proxy transforms a ciphertext under a particular public key (this can be regarded as a mailing list) into reencrypted ciphertexts under each recipient (who can be regarded as mailing list members). Even if the proxy transformation is applied to a TRE ciphertext, the release time is still effective. An encryptor can transfer N- dependent computation parts to the proxy. This function can be applied to multicast communication with a release time indication. For example, in an on-line examination, an examiner sends encrypted e-mails to each examinee, and each examination can be fairly opened at the same time. Our TR-PRE scheme is provably secure under both chosen-time period chosen-ciphertext attack (IND-CTCA) and replayable chosen-ciphertext attack (IND-RCCA) without random oracles.

In a k-Times Anonymous Authentication (k-TAA) scheme, Application Providers (APs) authenticates each group member in k times. A user can preserve his/her own privacy and an AP can restrict the number of used services to just k-times, since users are identified if they access an AP more than k times. In all previous schemes, each AP assumes the same k for all users. Added to this, total anonymity of unlinkability requires large computation amount such as pairing computations compared with non-anonymous schemes. In this paper, we propose a selectable k-TAA scheme with relaxed anonymity. Relaxed anonymity is an intermediate level of privacy required between total anonymity and linkability, where authentication executions for the same AP are linkable, but an authentication execution with an AP v 0 and an authentication execution with an AP v 1 (v 0 ? v 1) are unlinkable. Our authentication algorithm is efficient than existing ones thanks to this relaxed notion.

In this paper, we show that both Public Key Encryption (PKE) with non-interactive opening and threshold PKE can be constructed from an arbitrary group signature scheme which is secure in the dynamic group setting. This result implies that group signature (in dynamic groups) is a significantly strong cryptographic primitive, since the above PKEs with additional functionalities are already much stronger primitives than the standard chosen-ciphertext secure PKE, which is itself recognized as a very powerful cryptographic tool. We can interpret our result as meaning that designing secure group signatures is significantly harder than many other ordinary cryptographic primitives.

This paper investigates methods that allow a third-party authority to control contents transmitted using a public key infrastructure. Since public key encryption schemes are normally designed not to leak even partial information of plaintext, traditional public key encryption schemes do not allow such controlling by an authority. In the proposed schemes, an authority specifies some set of forbidden messages, and anyone can detect a ciphertext that encrypts one of the forbidden messages. The syntax of public key encryption with such a functionality (restrictive public key encryption), formal definitions of security requirement for restrictive public key encryption schemes, and an efficient construction of restrictive public key encryption are given. In principle, restrictive public key encryption schemes can be constructed by adding an NIZK proof that proves whether the encrypted messages are not prohibited. However if one uses the general NIZK technique to construct such a noninteractive proof, the scheme becomes extremely inefficient. In order to avoid such an inefficient construction, the construction given in this paper uses techniques of Teranishi et al., Boudot, and Nakanishi et al. One of the possible applications of restrictive public key encryption is protecting a public key infrastructure from abuse by terrorists by disallowing encryption of crime-related keywords. Another example is to perform format-check of a ballot in an electronic voting, by disallowing encryption of irregular format voting.

Any multi-user cryptographic primitives need revocation since a legitimate user may quit the organization, or may turn to be malicious, or the key may be leaked. In the group signature context, usually group manager publishes the revocation list that contains revocation tokens. Since signers/verifiers need to obtain the revocation list in each revocation epoch for generating/verifying a group signature, a small-size revocation list is really important in practice. However, all previous revocable group signatures require at least O(r)-size revocation list, where r is the number of revoked users. In this paper, we propose the first revocable group signature scheme with the constant size revocation list from identity-based revocation (IBR) techniques. We use an IBR scheme proposed by Attrapadung-Libert-Panafieu (PKC2011) as a building block. Although the maximum number of the revoked users needs to be fixed in the setup phase, however, the maximum number of group members is potentially unbounded (as in IBR). This property has not been achieved in the recent scalable revocable group signature schemes, and seems to be of independent interest.