Recent years have witnessed the surge of academic researches and industrial implementations of succinct non-interactive arguments of knowledge (SNARKs). However, proving time remains a bottleneck for applying SNARKs to large-scale circuits. To accelerate the proof generation process, a promising way is to distribute the workload to several machines running in parallel, the SNARKs with which feature are called distributed SNARKs. Nevertheless, most existing works either require a trusted setup, or rely on quantum-insecure assumptions, or suffer from linear communication costs.

Abstract With increasing global demand for vaccines and the changing level of biotechnology, vaccines become an important force to promote the development of the global pharmaceutical market. Vaccine forms an important basis for human self-protection. At present, existing vaccine supply management is mostly established in a centralized manner with a central authority (CA) for assuring trust. This approach requires that a trusted CA be set up, and it incurs overhead costs in communications and storage in networks. At the same time, issues such as the authenticity, integrity, and privacy are still widespread in vaccine supply management. Therefore, it is crucial to study a vaccine supply management traceability scheme that can be supervised in a decentralized manner and whose data cannot be tampered with or forged. In view of the security and efficiency problems in the existing vaccine supply management traceability scheme, a practical blockchain-based vaccine supply management framework with verifiability and traceability is proposed in this paper. This architecture can solve the lack of centralization in the existing vaccine supply management and the problems of data falsification, tampering, and low work efficiency in the current vaccine supply supervision process. At the same time, aiming at the lack of efficiency and security of the existing signature schemes suitable for consortium chains, an improved SM2 digital signature algorithm based on key distribution authentication and modulo-free inverse operation is designed, which improves the signature efficiency and reliability in the signature verification process. Then, we design a new way to store vaccine production records, which can avoid the forgery and modification of production records by treating the production record of each production step as a separate piece of data. Based on the decentralized and traceable feature of the framework, it can well resolve the trust issue between consumers and the vaccine regulators. Consumers can be allowed to verify the authenticity of vaccine supply management process. In addition, the security analysis shows that the proposed framework meets all desired security requirements. Compared with similar solutions, the proposed scheme takes less computation and communication costs. Hence, our construction is more appropriate for practical vaccine supply management.

In resource-constrained environments such as IoT sensors and mobile devices, there is a strong demand for efficient conjunctive keyword search over privacy-sensitive data. However, existing schemes struggle to simultaneously suppress sterm equality leakage, the cross-query intersection pattern (IP), and the volume pattern without incurring prohibitive overhead. In this paper, we present XORCMM, a practical volume-hiding encrypted conjunctive multi-map (EMM) designed for robust leakage suppression. First, we shift the index construction from single keywords to global-ordering co-occurrence pairs, which ensures that search tokens are no longer tied to static keyword identities, thereby suppressing sterm equality leakage. Second, we integrate an incremental multiset hash aggregation mechanism directly into a fully padded Xor filter. This allows the server to aggregate multiple conjunctive results into a single, fixed length response, concealing both IP and volume patterns while eliminating the data redundancy of prior schemes. Third, we employ a prefix-constrained PRF to compactly encode keyword pairs, generating succinct query tokens whose size is independent of keyword volumes. Formal security analysis proves that XORCMM is adaptively secure with sterm equality, IP, and volume leakages hidden. Experimental results demonstrate that XORCMM achieves up to a 2.99× speedup in client setup, a 3.3× speedup in server query time, and reductions of 47% in response size and 84.61% in search token size, providing a stronger security guarantee with significantly higher efficiency.

Linkable Ring Signatures (LRS) allow users to anonymously sign messages on behalf of ad-hoc rings, while ensuring that multiple signatures from the same user can be linked. This feature makes LRS widely used in privacy-preserving applications like e-voting and e-cash. To scale to systems with large user groups, efficient schemes with short signatures and fast verification are essential. Recent works, such as DualDory (ESORICS'22) and LLRing (ESORICS'24), improve verification efficiency through offline precomputations but rely on static rings, limiting their applicability in ad-hoc ring scenarios. Similarly, constant-size ring signature schemes based on accumulators face the same limitation.

Recent advances in Vector Oblivious Linear Evaluation (VOLE) protocols have enabled constant-round, fast, and scalable (designated-verifier) zero-knowledge proofs, significantly reducing prover computational cost. Existing protocols, such as QuickSilver [CCS'21] and LPZKv2 [CCS'22], achieve efficiency with prover costs of 4 multiplications in the extension field per AND gate for Boolean circuits, with one multiplication requiring a O (k log k) -bit operation where k== 128 is the security parameter, and 3–4 field multiplications per multiplication gate for arithmetic circuits over a large field. We introduce JesseQ, a suite of two VOLE-based protocols: JQv1 and JQv2, which advance state of the art. JQv1 requires only 2 scalar multiplications in an extension field per AND gate for Boolean circuits, with one scalar needing a$O(\kappa)$bit operation, and 2 field multiplications per multiplication gate for arithmetic circuits over a large field. In terms of communication costs, JQv1 needs just 1 field element per gate. JQv2 further reduces communication costs by half at the cost of doubling the prover's computation. Experiments show that, compared to the current state of the art, both JQv1 and JQv2 achieve at least 3.9× improvement in the online phase for Boolean circuits. For large field circuits, JQv1 has a similar performance, while JQv2 offers a 1.3× improvement. Additionally, both JQv1 and JQv2 maintain the same communication cost as the current state of the art. No-tably, on the cheapest AWS instances, JQv1 can prove 9.2 tril-lion AND gates (or 5.8 trillion multiplication gates over a 61-bit field) for just one US dollar. JesseQ excels in applications like inner products, matrix multiplication, and lattice problems, delivering 40% – 200% performance improvements compared to QuickSilver. Additionally, JesseQ integrates seamlessly with the sublinear Batchman framework [CCS'23], enabling further efficiency gains for batched disjunctive statements.

With highly mobile and flexible-configurable, autonomous aerial vehicles (AAVs) are becoming crucial wireless communication infrastructures. To improve the reliability and throughput of data delivery for wireless networks, network coding, as a progressive technology, can be applied in AAV networks. However, network coding incurs a security problem called pollution attacks for AAV networks. Although homomorphic network coding signature can prevent pollution attacks, existing schemes are not suitable for AAV networks due to cumbersome certificate management, the key-escrow issue, or insecurity. In this article, we propose an efficient certificateless homomorphic network coding signature scheme for secure transmission of AAV networks, which can avoid certificate management and the key-escrow issue. Then our scheme is proven to be secure against adaptive chosen identity-and-subspace attacks in the random oracle model, thus our scheme can guarantee data integrity and authenticity to resist pollution attacks. We provide a performance evaluation for the proposed scheme and prior research, and experimental results illustrate the efficiency and feasibility of our scheme for practical application, reducing the verification overhead by 42.918% for a 72-dimensional data vector.

The smart environment is a crucial application of the Internet of Things(IoT). Due to its growing security and efficiency needs, recent years have seen the proposal of numerous authentication and key agreement (AKA) protocols. Unfortunately, most of existing AKA protocols only support one-to-one AKA and rely on the elliptic curve cryptosystem, resulting in huge overhead. In addition, these protocols fail to consider the resource-asymmetric characteristics of this scenario. That is, the resources on the gateway side are abundant, while the resources on user sides and device sides are limited. In order to achieve efficient and secure one-to-many AKA establishment in this scenario, where one-to-many means that users can realize key agreements with multiple smart devices at the same time. For the first time, this paper uses the one-to-many computing structure of the Chinese Remainder Theorem (CRT) to design an efficient one-to-many AKA establishment, which is perfectly adapted to resource-asymmetric allocation in smart environments. Compared with existing solutions, this solution has the following advantages. Firstly, our protocol is suitable for resource-asymmetric environments, where the gateway acts as an intermediate node and uses rich resources to integrate multiple AKA requests. Secondly, the solution supports users to negotiate session keys with multiple smart devices at the same time. Thirdly, we prove the protocol’s security under the Real-or-Random (ROR) model. In addition, we perform formal security verification of the protocol using the Automated Validation of Internet Security Protocols and Applications(AVISPA) tool. Finally, the security and efficiency of this solution are superior to similar solutions. Specifically, our solution can meet 18 security and functionality requirements. Compared with the latest similar scheme, assuming that the number of smart devices is 10, our scheme reduces the computational cost by 75.75%. At the same time, in terms of communication cost, our protocol reduces it by 37.78%.

Recently, Li et al. proposed an identity-based linearly homomorphic network coding signature (IB-HNCS) scheme for secure data delivery in Internet of Things (IoT) networks, and they claimed that the IB-HNCS scheme can resist pollution attacks. However, this paper shows that the IB-HNCS scheme is vulnerable to pollution attacks, as anyone who only has the public parameter can forge a new file identifier or a valid signature on a corrupted data packet to pollute legitimate sensor data. To enhance security and performance in network coding-based IoT networks, we propose a secure and efficient certificateless linearly homomorphic network coding signature scheme for IoT data delivery, which is free of burdensome certificate management and key escrow issue. In addition, our scheme is proved to be secure against adaptive chosen identity and adaptive chosen subspace attacks under two types of adversaries in the algebraic group model and random oracle model. Therefore, our scheme can verify the validity of data packets and allow data packets to be computed, so as to resist pollution attacks. The performance evaluation demonstrates that our scheme is more efficient and practical than existing secure schemes. Specifically, for a 73-dimensional data vector, the costs of signature generation and verification in our scheme are reduced by 38.588%-86.076% and 38.570%-85.664% respectively under the symmetric bilinear pairing setting, and the costs of signature generation and verification in our scheme are reduced by 17.740%-49.752% and 29.697%-58.645% respectively under the asymmetric bilinear pairing setting.

Ring Confidential Transaction (RingCT) protocols are widely used in cryptocurrencies to protect user privacy. Consequently, a corresponding digital signature scheme, such as a ring signature scheme that hides the signers’ identities, is required. Accordingly, the security of a RingCT protocol depends on the confidentiality of the secret signing keys of the underlying ring signature scheme. However, existing solutions like hardware wallets, Trusted Execution Environments (TEEs), and threshold signature schemes have limitations such as specified expensive hardware, targeting attacks at CPUs on insufficiently secure hardware, and overheads caused by multiple parties. On the contrary, program obfuscation for signature schemes offers advantages over these existing approaches. Concretely, we propose a novel obfuscator that secures the secret keys of the concise linkable spontaneous anonymous group (CLSAG) signature scheme, which is the latest ring signature scheme used in Monero’s RingCT protocol. To achieve enhanced security, the proposed obfuscator leverages Paillier homomorphic encryption to transform secret keys into an obfuscated form resistant to attacks. The security of the proposed obfuscator has been formally proved. Computational efficiency has been both theoretically analyzed and experimentally evaluated with positive results on various testing platforms.

IoT-based sharing economy is a win-win business model, where a transferor owns idle IoT devices and transfers the right to use a device to a user for a fee. Considering usage of multiple devices and privacy preservation, anonymous single-sign-on (ASSO) is a feasible solution for authentication. ASSO allows a user to access multiple devices with one token issued by the transferor and prevents the transferor from identifying the user. We also observe that in the scenario of IoT-based sharing economy, the token should (i) support attributes since a device should be available only to users with specific attributes (e.g., age) and (ii) avoid incurring significant communication/computation overhead as IoT devices are resource-constrained. In this paper, we proposed PILOT, a privacy-preserving single-sign-on with fine-grained access control for IoT devices. When a user attempts to access a device, he/she requests a token from the transferor. The token is actually a blind signature that cannot be tracked, and contains the user’s attributes which facilitate fine-grained access control on the device. Besides, the token consists of only four group elements and verification of the token involves only several exponentiation operations. This renders PILOT superior in terms of communication/computation overhead and suitable for IoT devices.

The Paillier cryptosystem is renowned for its applications in electronic voting, threshold ECDSA, multi-party computation, and more, largely due to its additive homomorphism. In these applications, range proofs for the Paillier cryptosystem are crucial for maintaining security, because of the mismatch between the message space in the Paillier system and the operation space in application scenarios.

Random numbers play a crucial role in decen-tralized applications (dApps) like decentralized finance (DeFi) and non-fungible tokens (NFTs). However, their generation faces challenges due to blolckchain's deterministic and decentralized nature, risking smart contract security and ecosystem stability. Prior solutions, including Oracles, employing commit-execute schemes, suffer from higher transaction fees, extended processing times, and increased on-chain storage, compromising efficiency. This paper proposes a novel random number provider (RNP) protocol for smart contracts, eliminating dependencies on traditional commit-execute approaches. Furthermore, we systematically identify potential random number-related attacks on smart contracts, particularly Post-reveal Undo Attacks (PUAs), where attackers may reverse contract operations when randomness is unfavorable, and discuss the security requirements. Our protocol addresses these attacks by (1) incorporating distributed random beacons (D RBs) with consensus processes, bridging the semantic gap between DRB and consensus, and (2) thoroughly analyzing and classifying four types of PUA and offering robust mitigations, alongside presenting a security proof. Our experiments show the protocol significantly enhances response times and security for random number queries in smart contracts, slashing request fees by at least 89 % and reducing on-chain data by 76.4% versus current methods. This work advances the integration of DRB protocols and consensus mechanisms, securing and optimizing random number applications in dApps, thus fostering the creation of more dependable, robust systems.

Network coding, as a routing technology to improve network throughput and robustness, is widely used in various scenarios. However, network coding is vulnerable to pollution attacks where nodes may maliciously modify transmitted data packets. Recently, certificateless linearly homomorphic signature schemes have been proposed to resist pollution attacks in network coding, which avoids burdensome certificate management and the key-escrow issue. In this paper, we show that Wu et al.’s certificateless homomorphic network coding signature (CHNCS) scheme, Chang et al.’s CHNCS scheme, and Li et al.’s CHNCS are not secure against pollution attacks in network coding. Then we present a secure and efficient CHNCS scheme and prove it is unforgeable against adaptive chosen identity-and-subspace attacks under two types of adversaries. Finally, performance analysis illustrates that our scheme is more efficient in practical application.

We present an efficient zero-knowledge argument of knowledge system customized for the Paillier cryptosystem. Our system enjoys sublinear proof size, low verification cost, and acceptable proof generation effort, while also supporting batch proof generation/verification. Existing works specialized for Paillier cryptosystem feature linear proof size and verification time. Using existing sublinear argument systems for generic statements (e.g., zk-SNARK) results in unaffordable proof generation cost since it involves translating the relations to be proven into an inhibitive large Boolean or arithmetic circuit over a prime order field. Our system does not suffer from these limitations.The core of our argument systems is a constraint system defined over the ring of residue classes modulo a composite number, together with novel techniques tailored for arguing binary values in this setting. We then adapt the approach from Bootle et al. (EUROCRYPT 2016) to compile the constraint system into a sublinear argument system. Our constraint system is generic and can be used to express typical relations in Paillier cryptosystems including range proof, correctness proof, relationships between bits of plaintext, relationships of plaintexts among multiple ciphertexts, and more. Our argument supports batch proof generation and verification, with the amortized cost outperforming state-of-the-art protocol specialized for Paillier when the number of Paillier ciphertext is in the order of hundreds.We report an end-to-end prototype and conduct comprehensive experiments across multiple scenarios. Scenario 1 is Paillier with packing. When we pack 25.6K bits into 400 ciphertexts, a proof that all these ciphertexts are correctly computed is 17 times smaller and is 3 times faster to verify compared with the naive implementation: using 25.6K OR-proofs without packing. Furthermore, we can prove additional statements almost for free, e.g., one can prove that the sum of a subset of the witness bits is less than a threshold t. Another scenario is range proof. To prove that each plaintext in 200 Paillier ciphertexts is of size 256 bits, our proof size is 10 times smaller than the state-of-the-art. Our analysis suggests that our system is asymptotically more efficient than existing protocols, and is highly suitable for scenarios involving a large number (more than 100) of Paillier ciphertexts, which is often the case for data analytics applications.

Single-sign-on authentication (SSO) enables a user to obtain a token from an identity server, and access multiple service providers with the token. In conventional SSO, the identity server can identify the user through the token, which compromises the user’s privacy. Anonymous SSO is proposed to solve this problem. However, the unconditional anonymity precludes identification of fraudulent users and leads to increase in illegitimate activities. In this paper, we propose SONAR, an anonymous single-sign-on authentication protocol that supports fraud detection. The identity server first accesses a user’s trustworthiness using fraud detection. We observe that directly refusing to issue tokens to an untrustworthy user allows the user to immediately realize that he have been detected, which poses security problems. Instead, we postpone the moment the user realizes he has been detected until he attempts to access a service provider. We also illustrate the benefits of this postponement using denial of service attacks as an example. In the proposed SONAR, the identity server issues the user (regardless of his trustworthiness) with a token that contains a covert channel, which is restricted to conveying only a 0/1 bit that is hidden from the user. The restriction of the channel prevents the identity server from tracking the user by embedding specific information in the channel, and meanwhile the 0/1 bit indicates whether the user is trustworthy or not. The token is actually a randomizable signature and can be randomized by the user, while the embedded bit remains unchanged. The user accesses a service provider with a randomized token, which protects the user from being identified as well as informs the service provider whether the user’s access should be permitted. We provide a formal security proof to demonstrate that SONAR is secure, and conduct a performance evaluation to show efficiency of SONAR.

Blockchain systems, such as Bitcoin and Ethereum, enable new applications, such as cryptocurrencies and smart contracts, using decentralized consensus without trusted authorities. Since the most widely used technique, proof-of-work, suffers from the costs of high latency and huge energy consumption, a number of blockchain systems based on proof-of-stake techniques have been proposed in recent years, many of which use verifiable random functions as fundamental building blocks, such as Ouroboros, Algorand, and Dfinity, etc. The secret key of a verifiable random function scheme, similar to that of a digital signature scheme, is critical to the security of a verifiable random function and the entire blockchain system built on it. To protect the secret keys of verifiable random functions and maintain the efficiency of the proof-of-stake protocol, we extend the objective of cryptographic program obfuscation to verifiable random functions and propose a novel obfuscatable verifiable random function scheme. In particular, we propose an obfuscator that can transform the implementation of the scheme's random string generation algorithm and the given secret key into an unintelligible form. Obfuscated implementations of the random string generation algorithm are deployed on peers of a blockchain for supporting normal routines of the proof-of-stake protocol. Even if a hacker has controlled a peer's host, the owner's secret key will not be compromised because the key has been hardwired into the obfuscated implementation in an “encrypted manner”. We formally prove the correctness and the security of the proposed verifiable random function and obfuscator. Since the proposed scheme supports the general semantics of verifiable random functions, it can be used as a building block for all blockchain systems that adopt proof-of-stake protocols based on Verifiable Random Functions (VRFs). The extensive experimental result indicated that the scheme performs well on various platforms, such as cloud servers, workstations, PCs, smartphones, and embedded devices.

A Verifiably Encrypted Signature (VES) scheme encrypts a digital signature in a way that allows the public to verify the validity of the encrypted signature. Recently, several practical VES schemes for ECDSA have been proposed to enable escrowed transactions with cryptocurrencies. However, these schemes are inefficient in terms of both communication and computation, or require a large lookup table. In this paper, we present two efficient VES schemes for ECDSA that improve upon previous work. The first scheme is based on Castagnos-Laguillaumie (CL) encryption, while the second is based on modified Joye-Libert (JL) encryption. Our benchmark shows that our schemes outperform existing constructions by a factor of at least 2 in both computation and communication. Additionally, our solution does not rely on any lookup table. We demonstrate that these schemes can also be generalized to design VES for Schnorr signature scheme and EdDSA. The main technical contribution of this paper, which is of independent interest, is a zero-knowledge proof for the equality of the discrete log of an elliptic-curve point and that of a JL ciphertext. Importantly, the security of our proof does not rely on any non-standard assumptions.

Threshold ECDSA receives interest lately due to its widespread adoption in blockchain applications. A common building block of all leading constructions involves a secure conversion of multiplicative shares into additive ones, which is called the multiplicative-to-additive (MtA) function. MtA dominates the overall complexity of all existing threshold ECDSA constructions. Specifically, O(n2) invocations of MtA are required in the case of n active signers. Hence, improvement of MtA leads directly to significant improvements for all state-of-the-art threshold ECDSA schemes.

Time series data have numerous applications in big data analytics. However, they often cause privacy issues when collected from individuals. To address this problem, most existing works perturb the values in the time series while retaining their temporal order, which may lead to significant distortion of the values. Recently, we propose TLDP model [45] that perturbs temporal perturbation to ensure privacy guarantee while retaining original values. It has shown great promise to achieve significantly higher utility than value perturbation mechanisms in many time series analysis. However, its practicability is still undermined by two factors, namely, utility cost of extra missing or empty values, and inflexibility of privacy budget settings. To address them, in this paper we propose switch as a new two-way operation for temporal perturbation, as opposed to the one-way dispatch operation in [45]. The former inherently eliminates the cost of missing, empty or repeated values. Optimizing switch operation in a stateful manner, we then propose StaSwitch mechanism for time series release under TLDP. Through both analytical and empirical studies, we show that StaSwitch has significantly higher utility for the published time series than any state-of-the-art temporal- or value-perturbation mechanism, while allowing any combination of privacy budget settings.

With the rapid growth and popularization of the Internet of Things (IoT), it has been applied to numerous fields such as smart industry, smart agriculture and smart home. Designing practical and robust authentication key agreement (AKA) schemes for smart environments has become a pressing problem to be solved. Due to differences in security requirements and resource allocation in smart environments, which we call security-asymmetry and resource-asymmetry, it is necessary to design specific AKA schemes for this environment. Since the design of remote AKA protocols does not fully consider security-asymmetry and resource-asymmetry, many existing schemes are not practical in smart environments. With regard to security-asymmetry, compared with traditional public-key techniques applied in AKA schemes, chaotic map is more effective than modular exponentiation and scalar multiplication, and it supplies many feasible attributes such as unpredictability, unrepeatability, uncertainty, which can be used to achieve communication security between users and gateways, while security operations based on hash function are sufficient to secure communications between gateways and smart devices. In view of resource-asymmetry, the complex operations in the authentication process can be completed by the gateway, so as to make full use of the rich resources on gateway side and reduce the use of resources on user side and device side. Based on such considerations, an efficient and secure authentication key agreement scheme based on chaotic map and physical unclonable function (PUF) for smart environments is proposed. We present a rigorous informal analysis of the proposed scheme. Moreover, the formal security verification is accomplished using the Automated Validation of Internet Security Protocols and Applications (AVISPA) tool. Finally, performance evaluations indicate the proposed protocol consumes less communication cost and computation cost while achieving more security functions compared to other four state-of-the-art related schemes.

Decentralized storage (DS) projects such as Filecoin are gaining traction. Their openness mandates effective auditing mechanisms to assure users that their data remains intact. A blockchain is typically employed here as an unbiased public auditor. While the case for static data is relatively easy to handle, on-chain auditing of dynamic data with practical performance guarantees is still an open problem. Dynamic Proof-of-Storage (PoS) schemes developed for conventional cloud storage are not applicable to DS, since they require large storage proofs and/or large auditor states that are unmanageable by a resource-constrained blockchain. To fill the gap, we propose a family of dynamic on-chain auditing protocols that can produce concretely small auditor states while retaining the compact proofs promised by static PoS schemes. Our design revolves around a set of succinct data structures and optimization techniques for index information management. With proper instantiation and realistic parameters, our protocols can achieve 0.25MB on-chain state and 1.2KB storage proof for the auditing of 1TB data, outperforming previous dynamic PoS schemes that are adaptable for DS by orders of magnitude. As another practical contribution, we introduce a data abstraction layer that allows one to deploy the auditing protocols on arbitrary storage systems hosting dynamic data.

Data availability is the major concern of outsourced data storage services. While reliability is promoted by many storage providers, it is infeasible for users to verify these claims. Proofs of Storage-Time are proposed to address this issue: they allow a prover to convince a verifier that the prover indeed stores the outsourced data continuously during the whole storage period. These protocols, however, either fail to guarantee the actual duration of data possession, or require the client to perform a computationally expensive storing process for each file, marking them far from being practical. We present$\mathsf {ePoSt}$, the first secure, stateless and efficient Proof of Storage-Time protocol with public verifiability. Not only does it ensure continuous data availability, but it also minimizes the cost of the client, which is crucial for real-world deployment. Specifically, processing a 1GB file for outsourcing, in anticipation for 3 proof/verify interactions, each attesting a period of 1 year at 25 minutes intervals requires only 66.34 minutes. In contrast, state-of-the-art solution requires 51 hours of processing to prepare a file for outsourcing. Proof size and verification remains at a reasonable cost: a proof is of size 48.82KB, and can be verified in 36.05 ms. Furthermore, our solution enjoys public verifiability and remains stateless. The former allows the data owner to outsource the verification process, and the latter allows unlimited number of proofs and verification to be conducted after the file has been stored. These properties make$\mathsf {ePoSt}$particularly suitable for new business models such as decentralised storage networks (e.g., Filecoin).

In a traffic monitoring system, users report their driving data (e.g., routes and timestamps) to a server, aggregating them to acquire the information of interest and provide services, e.g., traffic flow prediction. Such systems have considerable promise for improving the quality of life and decreasing environmental pollution and economic losses. However, the threat to individual privacy is a critical problem that hinders the further development of such systems; e.g., the server can abuse the spatio-temporal metadata in the reports to infer sensitive user information, such as the home address. In this paper, we propose a privacy-preserving aggregation framework called secure Publish Aggregate Subscribe Data ($s$PASD) for traffic monitoring that can protect spatio-temporal metadata during driving data aggregation. The framework is built upon a trusted execution environment and two cryptographic tools: additive homomorphic encryption and oblivious RAM. It takes a hierarchical structure that boosts batch processing efficiency, making it more appropriate for traffic monitoring scenarios. Furthermore, we provide a cost model to derive the optimal settings from the efficiency perspective. Security analysis demonstrates that$s$PASD can protect individual privacy by hiding spatio-temporal information during aggregation. Moreover, we implement the proposed framework in Python and evaluate it together with other competitive methods over a real-world dataset. The experiment results verify the accuracy of the proposed cost model and show that the proposed framework can gain a 51.39% saving on computation cost.

Mobile devices have become near-ubiquitous tools in our daily lives. Following this trend, mobile commence is developed rapidly which in turns stimulates interests in mobile payment. Some prominent examples include Google’s Wallet, WeChat Pay, and Apple Pay. Most of these technologies, however, are designed for users to be able to pay conveniently to the business. In other words, they are designed with the business to user model in mind. Besides, an active network connection with an external payment server is required either from payer or payee during transaction. Our work intends to supplement existing solutions, which allows payment to be made in an off-line and dual-anonymous manner. In doing so, a dual-anonymous off-line electronic cash scheme is proposed by utilizing BBS+ signature. The feature of our scheme is dual-anonymous payment, which means that both the payer and the payee in any transaction cannot be identified even all other users and the payment server collude. Through security proof and performance analysis, we also demonstrate that the security of the proposed scheme can be reduced to standard assumptions and it is suitable for applications in mobile commerce.

Payment channels have been a promising solution to blockchain scalability. While payment channels for script-empowered blockchains (such as Bitcoin and Ethereum) have been well studied, developing payment channels for scriptless blockchains (such as Monero) is considered challenging. In particular, nabling bidirectional payment on scriptless blockchains remains an open challenge.

As a promising alternative solution to cloud storage, decentralized storage networks (DSN) are widely anticipated to develop continuously and reshape the storage market share in the foreseeable future. In particular, one of the most important research problems is how to enforce the quality of service (QoS) in the context of storage solutions. Despite plenty of auditing-related works in the context of cloud storage, none of them can be directly applied to the decentralized storage paradigm. The challenges of designing a feasible storage auditing framework emanate from two aspects: 1) security problems unique to the decentralized settings and 2) performance overhead due to on-chain operations. In this article, we first put forward a basic storage auditing framework that satisfies the security and efficiency requirements, and outperforms the existing approaches. We also identify a critical and overlooked security problem that would compromise the integrity of storage auditing solutions in the blockchain paradigm. With our refined storage auditing design based on customized zero knowledge protocols, we propose a convenient mitigation solution in our revised security model. The evaluation results confirm that our solution would only incur a 10–15 percent increase in the overall auditing costs for common usage scenarios, compared to the basic design.

This article presents two dynamic symmetric searchable encryption schemes for geometric range search. Our constructions are the first to provide forward/backward security in the context of SSE-based schemes supporting geometric range search. Besides, we define a security notion called content privacy. This security notion captures the leakages that are critical in the context of geometric range search but not considered by forward/backward security. Content privacy eliminates the leakage on the updated points of the database during both search and update. Due to the inherent leakages associated with range queries, none of the existing related works can support content privacy, whereas the design of our constructions avoids such leakages. When compared to the state-of-the-art schemes, our constructions provide a higher level of security and practical efficiency supported by our experimental results.

Verifiably encrypted signature (VES) allows a signer to encrypt a signature under the public key of a trusted third party (aka adjudicator) in a verifiable manner. Recently, Yanget al.proposed a practical verifiably encrypted signature scheme for ECDSA and initiated the study of escrow protocol for Bitcoin via VES. This paper generalizes and improves the VES scheme of Yanget al., such that it covers a family of signatures with similar structures, including ECDSA, Schnorr and their variants. Our construction is very efficient: comparing with Yanget al.’s construction, the size of the resulting VES (for ECDSA) is reduced by more than 25 times. The only caveat is that the adjudicator is required to store a look-up table of size around 270MB. Our scheme naturally gives rise to escrow protocols for mainstream cryptocurrencies that employ ECDSA-like signatures to authorise transaction, including Bitcoin, Ethereum, Cardano, Chainlink, etc.

Local differential privacy (LDP) is an emerging technique for privacy-preserving data collection without a trusted collector. Despite its strong privacy guarantee, LDP cannot be easily applied to real-world graph analysis tasks such as community detection and centrality analysis due to its high implementation complexity and low data utility. In this paper, we address these two issues by presenting LF-GDPR, the first LDP-enabled graph metric estimation framework for graph analysis. It collects two atomic graph metrics—the adjacency bit vector and node degree—from each node locally. LF-GDPR simplifies the job of implementing LDP-related steps (e.g., local perturbation, aggregation and calibration) for a graph metric estimation task by providing either a complete or a parameterized algorithm for each step. To address low data utility of LDP, it optimally allocates privacy budget between the two atomic metrics during data collection. To demonstrate the usage of LF-GDPR, we show use cases on two common graph analysis tasks, namely, clustering coefficient estimation and community detection. The privacy and utility achieved by LF-GDPR are verified through theoretical analysis and extensive experimental results.

Two-party ECDSA signatures have received much attention due to their widespread deployment in cryptocurrencies. Depending on whether or not the message is required, we could divide two-party signing into two different phases, namely, offline and online. Ideally, the online phase should be made as lightweight as possible. At the same time, the cost of the offline phase should remain similar to that of a normal signature generation. However, the existing two-party protocols of ECDSA are not optimal: either their online phase requires decryption of a ciphertext, or their offline phase needs at least two executions of multiplicative-to-additive conversion which dominates the overall complexity. This paper proposes an online-friendly two-party ECDSA with a lightweight online phase and a single multiplicative-to-additive function in the offline phase. It is constructed by a novel design of a re-sharing of the secret key and a linear sharing of the nonce. Our scheme significantly improves previous protocols based on either oblivious transfer or homomorphic encryption. We implement our scheme and show that it outperforms prior online-friendly schemes (i.e., those have lightweight online cost) by a factor of roughly 2 to 9 in both communication and computation. Furthermore, our two-party scheme could be easily extended to the 2-out-of-n threshold ECDSA.

A permissioned blockchain framework typically runs an efficient Byzantine consensus protocol and is attractive to deploy fast trading applications among a large number of mutually untrusted participants (e.g., companies). Unfortunately, all existing permissioned blockchain frameworks adopt sequential workflows for invoking the consensus protocol and executing applications' transactions, making the performance of these applications much lower than deploying them in traditional systems (e.g., in-datacenter stock exchange).

Malware authors are abusing packers (or runtime-based obfuscators) to protect malicious apps from being analyzed. Although many unpacking tools have been proposed, they can be easily impeded by the anti-analysis methods adopted by the packers, and they fail to effectively collect the hidden Dex data due to the evolving protection strategies of packers. Consequently, many packing behaviors are unknown to analysts and packed malware can circumvent the inspection. To fill the gap, in this paper, we propose a novel hardware-assisted approach that first monitors the packing behaviors and then selects the proper approach to unpack the packed apps. Moreover, we develop a prototype named Happerwith a domain-specific language named behavior description language (BDL) for the ease of extending Happerafter tackling several technical challenges. We conduct extensive experiments with 12 commercial Android packers and more than 24k Android apps to evaluate Happer. The results show that Happerobserved 27 packing behaviors, 17 of which have not been elaborated by previous studies. Based on the observed packing behaviors, Happeradopted proper approaches to collect all the hidden Dex data and assembled them to valid Dex files.

Monero provides a high level of anonymity for both users and their transactions. However, many criminal activities might be committed with the protection of anonymity in cryptocurrency transactions. Thus, user accountability (or traceability) is also important in Monero transactions, which is unfortunately lacking in the current literature. In this paper, we fill this gap by introducing a new cryptocurrency named Traceable Monero to balance the user anonymity and accountability. Our framework relies on a tracing authority, but is optimistic, in that it is only involved when investigations in certain transactions are required. We formalize the system model and security model of Traceable Monero. We present a detailed construction of Traceable Monero by overlaying Monero with two types of tracing mechanisms, tracing the one-time addresses with money flows and tracing the long-term addresses. We prove the security of Traceable Monero and implement a prototype of the system, which demonstrates that Traceable Monero incurs merely a very small overhead in generating and verifying a transaction compared to Monero transactions.

A procurement protocol is a protocol for a buyer to purchase digital goods at their prices from a vendor. A procurement protocol with privacy preservation can be achieved by priced oblivious transfer (POT). POT allows the buyer to obliviously procure items one by one. An adaptive POT protocol only consumes O(1) communication cost in each transaction, where all items are committed and encrypted before transactions. However, we found that the state-of-the-art adaptive POT protocol proposed by Rial et al. is less practical and does not meet real-world needs. It has to restrict to the one-buyer setting where all items are encrypted associated with one buyer's public key. For multiple buyers, the vendor must respectively encrypt all the same items for each buyer. Besides, it has to employ computationally expensive primitives such as zero-knowledge proof which imply inefficient computation operations. It is therefore unscalable and unsuitable in large-scale applications. In this paper, we propose an efficient adaptive priced oblivious transfer protocol to address the aforementioned problems. The proposed adaptive POT is built on top of a new cryptographic primitive, namely, adaptive set membership encryption (ASME). In our proposed protocol, all items are encrypted without the use of buyers' public keys and hence they can be used for universal buyers. Our protocol significantly reduces the transaction cost compared to existing schemes. For example, the communication in each transaction costs only 6 group elements compared to at least 141 group elements in Rial et al.'s protocol. The implementation shows that our protocol is efficient in terms of bandwidth and computational cost.

Filtering refers to an operation to determine whether the concerned data should be accepted and transferred, or be blocked and marked as a malicious traffic flow. It mitigates the inter-domain bandwidth overhead, local computational cost and storage cost for data identification. In many sensitive applications, the identity of the data provider needs to be hidden. This creates challenges how to filter the transmitted data packet with an encrypted form. It is non-trivial to hide this data provider's identity while enabling filtering, as the policy used as a matching criteria will need to determine whether the data needs to be transferred or not without knowing the origin of that data. In this work, we designPPFilter, a privacy-aware encrypted filtering mechanism which allows the filtering to be conducted without the need to know the identity of the data provider. PPFilter achieves the integrity protection of the data packets and the provider privacy Level 3. PPFilter is built on top of a novel notion calledidentity-based encryption with sender search (IESS), which supports anonymous sender identity in an encrypted searching. We present a provably secure IESS instantiation, and apply it to achieve a PPFilter protocol. PPFilter allows the data provider's identity to be hidden from both the transferred data and policy while enabling the filtering capability, which solves the aforementioned problem. The analysis and evaluation show that PPFilter maintains cost-reasonable filtering while preserving provider privacy, and hence it guarantees its practicality.

How to audit outsourced data in centralized storage like cloud is well-studied, but it is largely under-explored for the rising decentralized storage network (DSN) that bodes well for a billion-dollar market. To realize DSN as a usable service in a fully decentralized manner, the blockchain comes in handy - to record and verify audit trails in forms of proof of storage, and based on that, to enforce fair payments with necessary dispute resolution. Leaving the audit trails on the blockchain offers transparency and fairness, yet it 1) sacrifices privacy, as they may leak information about the data under audit, and 2) overwhelms onchain resources, as they may be practically large in size and expensive to verify. Prior auditing designs in centralized settings are not directly applicable here. A handful of proposals targeting DSN cannot satisfactorily address these issues either. We present an auditing solution that addresses on-chain privacy and efficiency, from a synergy of homomorphic linear authenticators with polynomial commitments for succinct proofs, and the sigma protocol for provable privacy. The solution results in, per audit, 288-byte proof written to the blockchain, and constant verification cost. It can sustain long-term operation and easily scale to thousands of users on Ethereum.

Password-based authentication is essential to any online service. It is normally powered by a database of user credentials, for example a RADIUS server. However, even with various indexing techniques (e.g., B+-tree), password-based authentication can still be resource-consuming on large-scale systems (e.g., Internet and IoT), and is thus vulnerable to distributed denial-of-service (DDoS) attacks.In this paper, we propose a cloud-based firewall that uses Bloom filters to pre-screen and reject suspicious requests with wrong password before they reach the authentication server. The main challenge is the security of the firewall because it can be operated by a third party, so the Bloom filters might be accessed by adversaries to assist their brute-force password guessing.To ensure security, we start with the assumption of trusted cloud server and design a key-based semantic secure Bloom filter (KSSBF) for the best efficiency. We then design a generically secure Bloom filter (GSBF) for non-trusted cloud servers, which is key-independent and with strictly provable security. Through theoretical and empirical analysis, we show both of them can mitigate malicious requests without compromising the security of passwords.

Local differential privacy (LDP) is an emerging technique for privacy-preserving data collection without a trusted collector. Despite its strong privacy guarantee, LDP cannot be easily applied to real-world graph analysis tasks such as community detection and centrality analysis due to its high implementation complexity and low data utility. In this paper, we address these two issues by presenting LF-GDPR, the first LDP-enabled graph metric estimation framework for graph analysis. It collects two atomic graph metrics - the adjacency bit vector and node degree - from each node locally. LF-GDPR simplifies the job of implementing LDP-related steps (e.g., local perturbation, aggregation and calibration) for a graph metric estimation task by providing either a complete or a parameterized algorithm for each step.

An escrow protocol for Bitcoin allows fair trading using bitcoins. To ensure fairness, the existing proposals made various trade-offs between trust, privacy, and efficiency. In this work, we evaluate the existing escrow protocols for cryptocurrency and propose a practical escrow protocol for Bitcoin that is: (a) computationally efficient; (b) round efficient; and (c) privacy-preserving. The core component of our escrow protocol for Bitcoin is a new verifiably encrypted ECDSA scheme, which may be of independent interest. Furthermore, we implement the escrow protocol for Bitcoin in Bitcoin mainnet, demonstrating the feasibility of our protocol.

We develop new foundations on transaction untraceability for CryptoNote-style blockchain systems. In particular, we observe new attacks; develop theoretical foundations to model transaction untraceability; provide the least upper bound of transaction untraceability guarantee; provide ways to efficiently and automatically verify whether a given ledger achieves optimal transaction untraceability; and provide a general solution that achieves provably optimal transaction untraceability. Unlike previous cascade effect attacks (ESORICS' 17 and PETS' 18) on CryptoNote-style transaction untraceability, we consider not only a passive attacker but also an active adaptive attacker. Our observed attacks allow both types of attacker to trace blockchain transactions that cannot be traced by using the existing attacks. We develop a series of new games, which we call "The Sun-Tzu Survival Problem", to model CryptoNote-style blockchain transaction untraceability and our identified attacks. In addition, we obtain seven novel results, where three of them are negative and the rest are positive. In particular, thanks to our abstract game, we are able to build bipartite graphs to model transaction untraceability, and provide reductions to formally relate the hardness of calculating untraceability to the hardness of calculating the number of perfect matchings in all possible bipartite graphs. We prove that calculating transaction untraceability is a #P-complete problem, which is believed to be even more difficult to solve than NP problems. In addition, we provide the first result on the least upper bound of transaction untraceability. Moreover, through our theoretical results, we are able to provide ways to efficiently and automatically verify whether a given ledger achieves optimal transaction untraceability. Furthermore, we propose a simple strategy for CryptoNote-style blockchain systems to achieve optimal untraceability. We take Monero as a concrete example to demonstrate how to apply this strategy to optimise the untraceability guarantee provided by Monero.

Crowdsensing, driven by the proliferation of sensor-rich mobile devices, has emerged as a promising data sensing and aggregation paradigm. Despite useful, traditional crowdsensing systems typically rely on a centralized third-party platform for data collection and processing, which leads to concerns like single point of failure and lack of operation transparency. Such centralization hinders the wide adoption of crowdsensing by wary participants. We therefore explore an alternative design space of building crowdsensing systems atop the emerging decentralized blockchain technology. While enjoying the benefits brought by the public blockchain, we endeavor to achieve a consolidated set of desirable security properties with a proper choreography of latest techniques and our customized designs. We allow data providers to safely contribute data to the transparent blockchain with the confidentiality guarantee on individual data and differential privacy on the aggregation result. Meanwhile, we ensure the service correctness of data aggregation and sanitization by delicately employing hardware-assisted transparent enclave. Furthermore, we maintain the robustness of our system against faulty data providers that submit invalid data, with a customized zero-knowledge range proof scheme. The experiment results demonstrate the high efficiency of our designs on both mobile client and SGX-enabled server, as well as reasonable on-chain monetary cost of running our task contract on Ethereum.

Distributed embedded devices are widely used in sensor networks and the Internet of Things for gathering and sending data. Many of them are deployed in an unattended manner (e.g., sensor nodes and tag readers), while others may be easily lost (e.g., smart wristbands and watches). These distributed embedded devices could be potentially captured and accessed in an unauthorized manner due to their physical natures. From a security perspective, they are typically working in the white-box attack context, where adversaries have total visibility on the implementations of built-in cryptosystems and full control over their execution processes. It is undoubtedly a significant challenge to deal with white-box attacks on these devices. Existing encryption algorithms for white-box attack contexts require large memory footprint and thus are not suitable for resource- constrained embedded devices. To address this challenge, we propose a novel light-weight encryption scheme for protecting data confidentiality. The encryption is conducted with specialized secret components, and the encryption algorithm requires a small volume of static data for storing critical information. In addition, this scheme uniquely supports efficient key-updating at very small cost. The security and the cost of the proposed scheme have been theoretically analyzed with positive results, and the extensive experimental evaluations indicate that the new scheme satisfies the requirements of distributed embedded devices in terms of limited memory usage and low computational cost.

Intercloud seeks to facilitate resource sharing among clouds. To support Intercloud, a trust evaluation framework among clouds and users is required. For trust evaluation, conventional protocols are typically based on a centralized architecture focusing on a one-way relationship. For Intercloud, the environment is highly dynamic and distributed, and relationships can be one-way or two-way (i.e., clouds provide services to each other). This paper presents a distributed trust evaluation protocol with privacy protection for Intercloud. The new contributions and innovative features are summarized below. First, feedback is protected by homomorphic encryption with verifiable secret sharing. Second, to cater to the dynamic nature of Intercloud, trust evaluation can be conducted in a distributed manner and is functional even when some of the parties are offline. Third, to facilitate customized trust evaluation, an innovative mechanism is used to store feedback, such that it can be processed flexibly while protecting feedback privacy. The protocol has been proved based on a formal security model. Simulations have been performed to demonstrate the effectiveness of the protocol. The results show that even when half of the clouds are malicious or offline, by choosing suitable operational parameters the protocol can still support effective trust evaluation with privacy protection.

Outsourcing the decryption of attribute-based encryption (ABE) ciphertext is a promising way to tackle the question of how users can perform decryption efficiently. However, existing solutions require the type of the target ciphertext to be determined at the setup of the outsourcing scheme. As such, making the target cryptosystems (or the clients) to be versatile becomes an issue that warrants investigations. In this paper, the problem we wish to tackle is to transform an ABE ciphertext to any client who is using the same, or possibly different, public-key encryption (PKE) system with the sender. The problem is of practical interest since it is hard to require all clients to use the same PKE, especially in the case of remote and cross-system data sharing. In addition, we also consider whether robust client-side decryption scheme can be adopted. This feature is not supported in the existing ABE with outsourcing.

Query authentication has been extensively studied to ensure the integrity of query results for outsourced databases, which are often not fully trusted. However, access control, another important security concern, is largely ignored by existing works. Notably, recent breakthroughs in cryptography have enabled fine-grained access control over outsourced data. In this paper, we take the first step toward studying the problem of authenticating relational queries with fine-grained access control. The key challenge is how to protect information confidentiality during query authentication, which is essential to many critical applications. To address this challenge, we propose a novel access-policy-preserving (APP) signature as the primitive authenticated data structure. A useful property of the APP signature is that it can be used to derive customized signatures for unauthorized users to prove the inaccessibility while achieving the zero-knowledge confidentiality. We also propose a grid-index-based tree structure that can aggregate APP signatures for efficient range and join query authentication. In addition to this, a number of optimization techniques are proposed to further improve the authentication performance. Security analysis and performance evaluation show that the proposed solutions and techniques are robust and efficient under various system settings.

For cloud data storage, data privacy and security are two key concerns. Although sensitive data can be encrypted before they are stored in the cloud, the encrypted data can hardly be processed efficiently. Hence, a lightweight solution is required to satisfy both high security and high efficiency requirements. In this paper, we study the problem of range query over encrypted data. The main idea is to transform the range comparison to a privacy-preserving set intersection operation. To protect record privacy, our scheme builds searchable encrypted indexes for records that are secure against inference attack. To ensure the privacy of range queries, non-deterministic encryption, which has not been achieved in range query before, is proposed to hide the search pattern of queries. During range comparison, our scheme neither leaks the order relationship between the upper/lower bound of a range query and the encrypted index, nor produces false positives in the query results. We have implemented our scheme and evaluated its performance in comparison with other schemes. The comparison results indicate that our scheme has a shorter index size and search time than the order-revealing encryption (ORE) scheme when the processing unit is large. Meanwhile, our scheme only leaks the access pattern, and is proved to be more secure than existing schemes.

Proximity-based apps have been changing the way people interact with each other in the physical world. To help people extend their social networks, proximity-based nearby-stranger (NS) apps that encourage people to make friends with nearby strangers have gained popularity recently. As another typical type of proximity-based apps, some ridesharing (RS) apps allowing drivers to search nearby passengers and get their ridesharing requests also become popular due to their contribution to economy and emission reduction. In this paper, we concentrate on the location privacy of proximity-based mobile apps. By analyzing the communication mechanism, we find that many apps of this type are vulnerable to large-scale location spoofing attack (LLSA). We accordingly propose three approaches to performing LLSA. To evaluate the threat of LLSA posed to proximity-based mobile apps, we perform real-world case studies against an NS app named Weibo and an RS app called Didi. The results show that our approaches can effectively and automatically collect a huge volume of users’ locations or travel records, thereby demonstrating the severity of LLSA. We apply the LLSA approaches against nine popular proximity-based apps with millions of installations to evaluate the defense strength. We finally suggest possible countermeasures for the proposed attacks.

We introduce an efficient Key-Policy Attribute-Based Encryption (KP-ABE) scheme in prime order groups. Our scheme is semi-adaptively secure under the decisional linear assumption and supports a large universe of attributes and multi-use of attributes. Those properties are critical for real applications of KP-ABE schemes since they enable an efficient and flexible access control. Prior to our work, existing KP-ABE schemes with short ciphertexts were in composite order groups or utilized either Dual Pairing Vector Spaces (DPVS) or Dual System Groups (DSG) in prime order groups. However, those techniques brought an efficiency loss. In this work, we utilize a nested dual system encryption which is a variant of Waters' dual system encryption (Crypto' 09) to achieve semi-adaptively secure KP-ABE. As a result, we obtain a new scheme having better efficiency compared to existing schemes while it keeps a semi-adaptive security under the standard assumption. We implement our scheme and compare its efficiency with the previous best work.

Intrusion detection systems (IDSs) are one of the widely adopted security tools in protecting computer networks, whereas it is still a big challenge for a single IDS to identify various threats in practice. Collaborative intrusion detection networks (CIDNs) are then developed in order to enhance the detection capability of a single IDS. However, CIDNs are known to suffer from insider attacks, in which malicious nodes can perform adversary actions. To mitigate this issue, challenge-based trust mechanisms are one of the promising solutions in literature, which are robust against various common insider threats. With the popularity of mobile devices, medical smartphone networks (MSNs) have become an emerging network architecture for healthcare organizations to improve the quality of medical services. Due to the sensitivity, there is a great need to defend MSNs against insider attacks. In this work, we conduct an empirical study to investigate and evaluate the implementation of challenge-based mechanism in MSNs. Our work aims to complement current literature, through providing insights and learned lessens (i.e., whether it is suitable to deploy such a mechanism in MSNs).

Blockchain technology has attracted a lot of attention in recent years. Applications of blockchain are not only restricted to cybercurrencies, but have also been extended to other areas such as finance, e-health, music, and other business. One of the key components of blockchain is the design for miners who are responsible for adding new transactions (blocks) by solving a puzzle and receive some rewards in return. As a result, miners tend to join centralized mining pools to outsource their computing resources in order to gain more steady rewards, which may affect the security and fairness of the system. This motivates the researchers to propose nonoutsourceable puzzles. However, existing nonoutsourceable puzzles do not work well under the high-rate transaction processing protocol (GHOST). In this paper, we propose the first nonoutsourceable puzzle that can satisfy all security requirements of GHOST. Our experimental results show that our puzzle is practical.

By hiding messages inside existing network protocols, anti-censorship tools could empower censored users to visit blocked websites. However, existing solutions generally suffer from two limitations. First, they usually need the support of ISP or the deployment of many customized hosts to conceal the communication between censored users and blocked websites. Second, their manipulations of normal network traffic may result in detectable features, which could be captured by the censorship system. In this paper, to tackle these limitations, we propose a novel framework that exploits the publicly available automation services and the plenty of web services and contents to circumvent web censorship, and realize it in a practical tool named AutoFlowLeaker. Moreover, we conduct extensive experiments to evaluate AutoFlowLeaker, and the results show that it has promising performance and can effectively evade realworld web censorship.

Vehicular Ad Hoc Network (VANET) allows vehicles to exchange information about road and traffic conditions through wireless communications. Nevertheless, providing reliable and authenticated information without violating the user's privacy seems contradictory. In this paper, we propose an Anonymous Announcement System especially designed for Electric Vehicle (EV) in VANETs to achieve the aforementioned contradictory goals. We demonstrated the feasibility of the protocol with a prototype implementation on a suitable device and a network simulation with our protocol added on top of a normal VANET.

Remote data integrity checking (RDIC) enables a data storage server, say a cloud server, to prove to a verifier that it is actually storing a data owner's data honestly. To date, a number of RDIC protocols have been proposed in the literature, but most of the constructions suffer from the issue of a complex key management, that is, they rely on the expensive public key infrastructure (PKI), which might hinder the deployment of RDIC in practice. In this paper, we propose a new construction of identity-based (ID-based) RDIC protocol by making use of key-homomorphic cryptographic primitive to reduce the system complexity and the cost for establishing and managing the public key authentication framework in PKI-based RDIC schemes. We formalize ID-based RDIC and its security model, including security against a malicious cloud server and zero knowledge privacy against a third party verifier. The proposed ID-based RDIC protocol leaks no information of the stored data to the verifier during the RDIC process. The new construction is proven secure against the malicious server in the generic group model and achieves zero knowledge privacy against a verifier. Extensive security analysis and implementation results demonstrate that the proposed protocol is provably secure and practical in the real-world applications.

An anonymous identification scheme for ad hoc group allows a participant to identify himself as a member of a group of users in a way that his actual identity is not revealed. We propose a highly efficient construction of this cryptographic primitive in the symmetric key setting based on the idea of program obfuscation. The salient feature of our scheme is that only hash evaluations are needed. Consequently, our scheme outperforms all existing constructions for a reasonably large ad hoc group size (of around 50000 users) since no exponentiation nor pairing operation is involved. Technically, the participant only needs to evaluate one hash operation to identify himself. While the time complexity of the verifier is linearly in the size of the ad hoc group, the actual running time is rather insignificant since the constant factor of this linear dependence is the time of a single hash evaluation. To analyse the security of our proposal, we develop a security model to capture the security requirements of this primitive and prove that our construction satisfies these requirements in the random oracle model against unbounded attackers. Similar to other identification schemes secure in the random oracle model, our proposed protocol requires only two message flow.

We propose a generic construction that yields efficient identity-based encryption (IBE) schemes secure against chosen ciphertext attack (CCA) in the standard model. Our construction extends Kiltz et al.'s (Eurocrypt '09) method of constructing CCA-secure public-key encryption schemes via randomness extraction to the identity-based setting. The main idea of our construction is to transform ‘|$\epsilon _1$|-almost |$\kappa $|-entropic’ and valid/invalid ciphertext indistinguishable (VI-IND) identity-based hash proof system to the one that satisfies the stronger ‘|$\epsilon _2$|-universal’ and VI-IND property. This transformation is realized by a randomness extractor based on the 4-wise hash function. We demonstrate that our generic construction can produce CCA-secure IBE schemes whose efficiency is comparable with the most efficient but non-generic CCA-secure IBE schemes without random oracles in the literature.

In this paper, we propose a privacy-preserving reservation system for electric vehicles (EV) charging stations. Due to the short driving range of EV, frequent charging is necessary. A mechanism for charging station reservation for EV owners is desirable. Our proposed system allows the vehicle owner to reserve a number of charging stations along the intended route at different time-slots. Yet it is secure against misuse such that a user can only hold a limited number of reservations simultaneously. More importantly, our system can provide privacy for users. The charging station does not know the identity of the user who has reserved it. Thus location privacy can be protected. We demonstrate the practicality of our system with a prototype implementation on a smart phone. Finally, we also provide a security proof to show that our system is secure under well-known computational assumptions.

The goal of this special issue is to collate a selection of representative research articles that were primarily presented at the 8th International Conference on Network and System Security (NSS 2014). This annual conference brings together researchers and practitioners in the world from both academia and industry who are working on network and system security, in order to foster interaction between researchers and developers, promote an exchange of ideas, discuss future collaborations, and develop new research directions.

In this paper, we introduce a new fine-grained two-factor authentication (2FA) access control system for web-based cloud computing services. Specifically, in our proposed 2FA access control system, an attribute-based access control mechanism is implemented with the necessity of both a user secret key and a lightweight security device. As a user cannot access the system if they do not hold both, the mechanism can enhance the security of the system, especially in those scenarios where many users share the same computer for web-based cloud services. In addition, attribute-based control in the system also enables the cloud server to restrict the access to those users with the same set of attributes while preserving user privacy, i.e., the cloud server only knows that the user fulfills the required predicate, but has no idea on the exact identity of the user. Finally, we also carry out a simulation to demonstrate the practicability of our proposed 2FA system.

Electric Vehicle (EV) infrastructure is relatively new in many countries. Due to the recency of an EV infrastructure, it is important to carry out a series of testing programs. Furthermore, authenticity for collection of data is necessary for testing programs in order to provide accurate results. At the same time, user privacy should not cease since tracing one's daily logistic movements or behaviour from the EV testing programs means breaching one's privacy. In this paper, we propose a novel solution PEVTS for enabling both data authenticity and user privacy concurrently. Our proposed system provides great flexibility to the authority to choose any arbitrary set of authenticated users for testing in every time period. At the same time, it provides anonymity for all participating users. Yet it can trace any vehicle within a time period for statistical purpose. We give a detailed description of our system. We also implement the prototype of our system to show its practicality.

The problem to allow two parties (say Alice and Bob) to sign an electronic contract online fairly is an interesting problem and it has been studied for a long time. Optimistic fair exchange (OFE) is an efficient remedy to this problem, which incorporates a semi-trusted third party called arbitrator, who will be called in to resolve a dispute during an exchange between Alice and Bob. It should be noted that the arbitrator is not required to be fully trusted, or else such an entity may not be available in practice. To reduce the trust level of the arbitrator, the requirement that the arbitrator should not be able to produce a full signature without the signer's content has been proposed in literature. Nevertheless, we observe that the existing OFE models do not capture the realistic situation that the arbitrator itself should not be able to generate a partial signature on a new message. This requirement is essential since we only put a partial trust towards the arbitrator, but on the other hand, we also assume that the arbitrator will not do such a forgery. Therefore, to reflect this situation, we propose an enhanced model of OFE that explicitly captures this requirement. We demonstrate the difference between our enhanced model and the existing chosen-key model through a concrete OFE scheme that serves as a counterexample. Since our model is strictly stronger than the existing model, we investigate the security of the existing schemes in our enhanced model. Interestingly, we show that OFE schemes based on verifiably encrypted signature and those based on ring signature can remain secure in our enhanced model given slight modifications to the primitives.

Delegation of signing is a working way common in office automation work, and is also an important approach to establish trust. Proxy signature is an important cryptographic primitive for delegating signing powers and it has found many real-world applications. The existing proxy signature schemes from factorization assumption are either insecure or inefficient. In this paper, we propose a novel, efficient and provably secure proxy signature scheme from factorization. Our construction makes use of a factorization-based key exposure-free chameleon hash function in the delegation phase and the proxy signer needs only to find a collision to a chameleon hash value to generate a valid proxy signature. As a result, our scheme is highly efficient in terms of the computation of a proxy signature. We also provide a formal security proof by classifying the adversaries into three categories. Comparisons demonstrate that the new scheme outperforms the known ones in terms of security, computational efficiency and the length of the public key.

Modern technologies such as cloud computing, grid computing and software as a service all require data to be stored by the third parties. A specific problem encountered in this context is to convince a verifier that a user's data are kept intact at the storage servers. An important approach to achieve this goal is called proof of retrievability, by which a storage server can assure a verifier via a concise proof that a user's file is available. However, for most publicly verifiable systems, existing proof of retrievability solutions do not take physical attacks into consideration, where an adversary can observe the outcome of the computation with methods like fault injection techniques. In fact, the authors find that giving the adversary the ability to obtain the information about the relations between the private keys, those systems are not secure anymore. Motivated by the need of preventing this kind of attacks, they present the security model for related‐key attacks in publicly verifiable proofs of retrievability, where the adversary can subsequently observe the outcome of the publicly verifiable proof of retrievability under the modified key. After pointing out a linear related‐key attack on an existing proof of retrievability system with public verifiability, they present a secure and efficient proof of retrievability with public verifiability, against related‐key attacks.

In this paper, we propose a new notion called$k$-times attribute-based anonymous access control, which is particularly designed for supporting cloud computing environment. In this new notion, a user can authenticate himself/herself to the cloud computing server anonymously. The server only knows the user acquires some required attributes, yet it does not know the identity of this user. In addition, we provide a$k$-times limit for anonymous access control. That is, the server may limit a particular set of users (i.e., those users with the same set of attribute) to access the system for a maximum$k$-times within a period or an event. Further additional access will be denied. We also prove the security of our instantiation. Our implementation result shows that our scheme is practical.

To prevent illegal users accessing the database and protect users' privacy, oblivious transfer with access control (AC-OT) was proposed. In an AC-OT scheme, the database provider can encrypt the records and publish corresponding access control lists (ACLs). Prior to accessing the records, a user needs to obtain anonymous credentials from the issuer. Subsequently, an authorized user can obtain the intended records without the database provider knowing its choices. Although AC-OT schemes have shown a lot of merits, there are some practical issues: 1) one of the inherited problems in anonymous credentials is timely revocation and 2) how to prevent malicious users overusing the records. In this paper, we propose an accountable AC-OT scheme to address these issues. In our scheme, an authorized user can access the protected records without the database provider knowing his personal information and choices if: 1) he has obtained the required credentials listed in the ACLs and 2) the number of the access times for each record is no more than the specified bound. Notably, the database provider can trace and revoke the user who overused the records even in the lifetime of his credentials. To the best of our knowledge, it is the first AC-OT scheme where timely revocation and overuse detection are considered.

In previous privacy-preserving multiauthority attribute-based encryption (PPMA-ABE) schemes, a user can acquire secret keys from multiple authorities with them knowing his/her attributes and furthermore, a central authority is required. Notably, a user's identity information can be extracted from his/her some sensitive attributes. Hence, existing PPMA-ABE schemes cannot fully protect users' privacy as multiple authorities can collaborate to identify a user by collecting and analyzing his attributes. Moreover, ciphertext-policy ABE (CP-ABE) is a more efficient public-key encryption, where the encryptor can select flexible access structures to encrypt messages. Therefore, a challenging and important work is to construct a PPMA-ABE scheme where there is no necessity of having the central authority and furthermore, both the identifiers and the attributes can be protected to be known by the authorities. In this paper, a privacy-preserving decentralized CP-ABE (PPDCP-ABE) is proposed to reduce the trust on the central authority and protect users' privacy. In our PPDCP-ABE scheme, each authority can work independently without any collaboration to initial the system and issue secret keys to users. Furthermore, a user can obtain secret keys from multiple authorities without them knowing anything about his global identifier and attributes.

In this paper, we present an adaptively secure identity-based broadcast encryption system featuring constant sized ciphertext in the standard model. The size of the public key and the private keys of our system are both linear in the maximum number of receivers. In addition, our system is fully collusion-resistant and has stateless receivers. Compared with the state-of-the-art, our scheme is well optimized for the broadcast encryption. The computational complexity of decryption of our scheme depends only on the number of receivers, not the maximum number of receivers of the system. Technically, we employ dual system encryption technique and our proposal offers adaptive security under the general subgroup decisional assumption. Our scheme demonstrates that the adaptive security of the schemes utilizing a composite order group can be proven under the general subgroup decisional assumption, while many existing systems working in a composite order group are secure under multiple subgroup decision assumptions. We note that this finding is of an independent interest, which may be useful in other scenarios.

We propose an anonymous authentication protocol that supports time-bound credentials for an efficient revocation. It is especially suitable for large-scale network in roaming scenario. With our newly designed group signature scheme as a building block, a timestamp can be embedded to user secret key. No expired key can be used to authenticate, and hence naturally revoked users (e.g., due to contract expiration) are not required to be put into the revocation list. This makes our protocol much faster than previous roaming protocols in terms of revocation checking, which is a main part in verification.

Recently, a public auditing protocol for shared data called Panda (IEEE Transactions on Services Computing, doi: 10.1109/TSC.2013.2295611) was proposed to ensure the correctness of the outsourced data. A distinctive feature of Panda is the support of data sharing and user revocation. Unfortunately, in this letter, we show that Panda is insecure in the sense that a cloud server can hide data loss without being detected. Specifically, we show that even some stored file blocks have been lost, the server is able to generate a valid proof by replacing a pair of lost data block and its signature with another block and signature pair. We also provide a solution to the problem while preserving all the desirable features of the original protocol.

Wee (PKC'12) proposed a generic public-key encryption scheme in the setting of related-key attacks. Bellare, Paterson and Thomson (Asiacrypt'12) provided a framework enabling related-key attack (RKA) secure cryptographic primitives for a class of non-linear related-key derivation functions. However, in both of their constructions, the instantiations to achieve the full (not weak) RKA security are given under the scenario regarding the private key composed of single element. In other words, each element of the private key shares the same modification. However, this is impractical in real world. In this paper, we concentrate on the security of public-key encryption schemes under linear related-key attacks in the setting of multielement private keys (that is, the private key is composed of more than one element), where an adversary is allowed to tamper any part of this private key stored in a hardware device, and subsequently observes the outcome of a public key encryption system under this targeted modified private key. We define the security model for RKA secure public-key encryption schemes as chosen-cipher text and related-key attack (CC-RKA) security, which means that a public-key encryption scheme remains secure even when an adversary is allowed to issue the decryption oracle on linear shifts of any component of the private key. After that, we present a detailed public key encryption schemes with the private key formed of several elements, of which the CC-RKA security is under the decisional BDH assumption in the standard model.

A related-key attack (RKA) occurs when an adversary tampers the private key stored in a cryptographic hardware device, and observes the result of the cryptographic primitive under this modified private key. In this paper, we consider the security of signcryption schemes under linear RKAs, where an adversary is allowed to tamper the private keys of the receiver and the sender, and subsequently observe the outcome of a signcryption system under these modified private keys of both parties. We define two security notions for RKA-secure signcryption schemes: chosen ciphertext RKA and chosen message RKA. We require that a signcryption scheme remains secure even when an adversary is allowed to access the designcryption oracle and the signcryption oracle on linear shifts of the private keys of the receiver and the sender, respectively. After reviewing some basic definitions related to our construction, we give a specific signcryption scheme from bilinear Diffie-Hellman which is secure against RKAs. Furthermore, we extend the security model of signcryption with anonymity, where the ciphertext is anonymous to others except the real receiver given the honest sender and the honest receiver. Fortunately, with a trivial modification to the original signcryption scheme, our proposed signcryption scheme can protect the privacy of both the sender and the receiver.

SUMMARY Designated verifier signatures (DVS) allow a signer to create a signature whose validity can only be verified by a specific entity chosen by the signer. In addition, the chosen entity, known as the designated verifier, cannot convince any body that the signature is created by the signer. Multidesignated verifiers signatures (MDVS) are a natural extension of DVS in which the signer can choose multiple designated verifiers. DVS and MDVS are useful primitives in electronic voting and contract signing. In this paper, we investigate various aspects of MDVS and make two contributions. Firstly, we revisit the notion of unforgeability under rogue key attack on MDVS. In this attack scenario, a malicious designated verifier tries to forge a signature that passes through the verification of another honest designated verifier. A common counter‐measure involves making the knowledge of secret key assumption in which an adversary is required to produce a proof‐of‐knowledge of the secret key. We strengthened the existing security model to capture this attack and propose a new construction that does not rely on the knowledge of secret key assumption. Secondly, we propose a generic construction of strong MDVS. Copyright © 2013 John Wiley & Sons, Ltd.

In this paper, for the first time, we define a general notion for proxy re-encryption (PRE), which we call deterministic finite automata-based functional PRE (DFA-based FPRE). Meanwhile, we propose the first and concrete DFA-based FPRE system, which adapts to our new notion. In our scheme, a message is encrypted in a ciphertext associated with an arbitrary length index string, and a decryptor is legitimate if and only if a DFA associated with his/her secret key accepts the string. Furthermore, the above encryption is allowed to be transformed to another ciphertext associated with a new string by a semitrusted proxy to whom a re-encryption key is given. Nevertheless, the proxy cannot gain access to the underlying plaintext. This new primitive can increase the flexibility of users to delegate their decryption rights to others. We also prove it as fully chosen-ciphertext secure in the standard model.

Optimistic fair exchange (OFE) is a kind of protocol that solves the fair exchange problem with the help of a trusted third party, usually referred to as an arbitrator. Participation of the arbitrator is required only when there is a dispute among the exchanging parties. Thus, the majority of the executions of the exchange does not involve the arbitrator and hence the term optimistic. The passive nature of the arbitrator makes optimistic fair exchange a desirable tool in applications, such as contract signing and electronic commerce. The highest level of security of optimistic fair exchange in the literature is the multiuser security in the chosen-key model, proposed by Huang, Yang, Wong, and Susilo in CT-RSA 2008. They showed that an efficient optimistic fair exchange scheme secure in this sense can be constructed generically from a conventional digital signature and a two-party ring signature. In particular, the underlying ring signature is required to be unforgeable under an adaptive attack, against a static adversary in the 2-user setting. In this paper, we propose a new security model for two-party ring signatures called unforgeability against restricted adaptive attacks and demonstrate that our new model is strictly weaker than the model of unforgeable under an adaptive attack, against a static adversary in the 2-user setting. We make an observation that two-party ring signatures secure in this weaker model will suffice to guarantee the security of the resulting OFE scheme following the aforementioned generic construction. Based on this observation, more efficient OFE schemes secure in the standard model can be constructed. Specifically, we prove that the well-known Bender, Katz, and Morselli's 2-user ring signature is secure in our weakened model. Based on this two-party ring signature, we construct an OFE secure in the chosen-key model offering multiuser security in the standard model under the computational Diffie-Hellman assumption. The assumption is arguably weaker than those used in all existing constructions, which rely on the random oracle model, decisional assumptions, or the strong Diffie-Hellman assumptions. It is also worth noting that our scheme is the most efficient one in the standard model, and offers comparable efficiency against those secure under the random oracle model.

Optimistic fair exchange (OFE) is a type of cryptographic protocols aimed at solving the fair exchange problem over open networks with the help of a third party to settle disputes between exchanging parties. It is well known that a third party is necessary in the realization of a fair exchange protocol. However, a fully trusted third party may not be available over open networks. In this paper, the security of most of the proposed OFE protocols depends on the assumption that the third party is semitrusted in the sense that it may misbehave on its own but does not conspire with either of the main parties. The existing security models of OFE have not taken into account the case where the potentially dishonest third party may collude with a signer in the sense of sharing its secret key with the signer. In this paper, to reduce the trust level of the arbitrator and increase the security of OFE, we propose an enhanced security model that, for the first time, captures this scenario. We also show a separation between the existing model and our enhanced model with a concrete counter example. Finally, we revisit two popular approaches in the construction of OFE protocols, which are based on verifiably encrypted signature and conventional signature plus ring signature, respectively. Our result shows that the conventional signature plus ring signature approach approach remains valid in our enhanced model. However, for schemes based on verifiably encrypted signature, slight modifications are needed to guarantee the security.

In this paper, we construct a linkable ring signature scheme with unconditional anonymity. It has been regarded as an open problem in [22] since 2004 for the construction of an unconditional anonymous linkable ring signature scheme. We are the first to solve this open problem by giving a concrete instantiation, which is proven secure in the random oracle model. Our construction is even more efficient than other schemes that can only provide computational anonymity. Simultaneously, our scheme can act as an counterexample to show that [19, Theorem 1] is not always true, which stated that linkable ring signature scheme cannot provide strong anonymity. Yet we prove that our scheme can achieve strong anonymity (under one of the interpretations).

Linkable ring signatures have found many attractive applications. One of the recent important extensions is a linkable threshold ring signature (LTRS) scheme. Unfortunately, the existing LTRS schemes are only secure in the random oracle model (ROM). In this paper, we make the following contributions. First, we construct the first LTRS scheme that is secure without requiring the ROM. Further, we enhance the security of a threshold ring signature (for both linkable or non-linkable) by providing a stronger definition of anonymity. This strengthened notion makes threshold ring signature schemes more suitable in real life. Finally, we provide efficient schemes that outperform the existing schemes in the literature. Our scheme is particularly suitable for electronic commerce or electronic government where anonymity and accountability are the most concerned factors.

We describe a secure and unrestricted identity-based ring signature scheme in the standard model. Our construction is provably fully secure in the standard model under static assumptions and is motivated by an existing HIBE scheme. Our observation on the relationship between ID-based ring signatures and HIBE is of interest to researchers in other fields as well. Following the strongest anonymity definition in ring signatures, we define a new level of anonymity for ID-based ring signatures in which the attacker can specify the randomness used in the creation of the user secret key, in addition to the private key generators master key. Our scheme provides unconditional anonymity in this model.

Some users may misbehave under the cover of anonymity by, e.g., defacing webpages on Wikipedia or posting vulgar comments on YouTube. To prevent such abuse, a few anonymous credential schemes have been proposed that revoke access for misbehaving users while maintaining their anonymity such that no trusted third party (TTP) is involved in the revocation process. Recently we proposed BLACR, a TTP-free scheme that supports `reputation-based blacklisting' --- the service provider can score users' anonymous sessions (e.g., good vs. inappropriate comments) and users with insufficient reputation are denied access.

Wireless handheld devices which support e-mail and web browsing are increasingly popular. The authenticity of the information received is important, especially for business uses. In server-aided verification (SAV), a substantial part of the verification computation can be offloaded to a powerful but possibly untrusted server. This allows resource-constrained devices to enjoy the security guarantees provided by cryptographic schemes, such as pairing-based signatures, which may be too heavyweight to verify otherwise.

In this paper, we present the notion and construction of threshold ring signature without random oracles. This is the first scheme in the literature that is proven secure in the standard model. Our scheme extends the Shacham-Waters signature from PKC 2007 in a non-trivial way. We note that our technique is specifically designed to achieve a threshold ring signature in the standard model. Interestingly, we can still maintain the signature size to be the same as the Shacham-Waters signature, while only a tiny computation cost is added.

The problem of access control on outsourced data to "honest but curious" cloud servers has received considerable attention, especially in scenarios involving potentially huge sets of data files, where re-encryption and re-transmission by the data owner may not be acceptable. Considering the user privacy and data security in cloud environment, in this paper, we propose a solution to achieve flexible and fine-grained access control on outsourced data files. In particular, we look at the problem of defining and assigning keys to users based on different attribute sets, and hiding access policies as well as users information to the third-party cloud servers. Our proposed scheme is partially based on our observation that, in practical application scenarios each user can be associated with a set of attributes which are meaningful in the access policy and data file context. The access policy can thus be defined as a logical expression formula over different attribute sets to reflect the scope of data file that the kind of users is allowed to access. As any access policy can be represented as such a logical expression formula, fine-grained access control can be accomplished.

Several anonymous authentication schemes allow servers to revoke a misbehaving user's ability to make future accesses. Traditionally, these schemes have relied on powerful Trusted Third Parties (TTPs) capable of deanonymizing (or linking) users' connections. Such TTPs are undesirable because users' anonymity is not guaranteed, and users must trust them to judge misbehaviors fairly. Recent schemes such as Blacklistable Anonymous Credentials (BLAC) and Enhanced Privacy ID (EPID) support “privacy-enhanced revocation”— servers can revoke misbehaving users without a TTP's involvement, and without learning the revoked users' identities. In BLAC and EPID, however, the computation required for authentication at the server is linear in the size (L) of the revocation list , which is impractical as the size approaches thousands of entries. We propose PEREA, a new anonymous authentication scheme for which this bottleneck computation is independent of the size of the revocation list . Instead, the time complexity of authentication is linear in the size of a revocation window K ≪ L , the number of subsequent authentications before which a user's misbehavior must be recognized if the user is to be revoked. We extend PEREA to support more complex revocation policies that take the severity of misbehaviors into account. Users can authenticate anonymously if their naughtiness , i.e., the sum of the severities of their blacklisted misbehaviors, is below a certain naughtiness threshold. We call our extension PEREA-Naughtiness. We prove the security of our constructions, and validate their efficiency as compared to BLAC analytically and quantitatively.

In an attribute-based signature (ABS), users sign messages with any predicate of their attributes issued from an attribute authority. Under this notion, a signature attests not to the identity of the individual who signed a message, but a claim regarding the attributes the underlying signer possesses. In ABS, users cannot forge signatures with attributes they do not possess even through colluding. On the other hand, a legitimate signer remains anonymous without the fear of revocation and is indistinguishable among all the users whose attributes satisfying the predicate specified in the signature. ABS is useful in many important applications such as anonymous authentication and attribute-based messaging systems.

Several credential systems have been proposed in which users can authenticate to service providers anonymously. Since anonymity can give users the license to misbehave, some variants allow the selective deanonymization (or linking) of misbehaving users upon a complaint to a Trusted Third Party (TTP). The ability of the TTP to revoke a user’s privacy at any time, however, is too strong a punishment for misbehavior. To limit the scope of deanonymization, some systems have been proposed in which users can be deanonymized only if they authenticate “too many times,” such as “double spending” with electronic cash. While useful in some applications, such techniques cannot be generalized to more subjective definitions of misbehavior, for example, using such schemes it is not possible to block anonymous users who “deface too many Web pages” on a Web site. We present BLAC, the first anonymous credential system in which service providers can revoke the credentials of misbehaving users without relying on a TTP . Since revoked users remain anonymous, misbehaviors can be judged subjectively without users fearing arbitrary deanonymization by a TTP . Additionally, our construction supports a d-strikes-out revocation policy, whereby users who have been subjectively judged to have repeatedly misbehaved at least d times are revoked from the system. Thus, for the first time, it is indeed possible to block anonymous users who have “defaced too many Web pages” using our scheme.

Several anonymous authentication schemes allow servers to revoke a misbehaving user's ability to make future accesses. Traditionally, these schemes have relied on powerful TTPs capable of deanonymizing (or linking) users' connections. Recent schemes such as Blacklistable Anonymous Credentials (BLAC) and Enhanced Privacy ID (EPID) support privacy-enhanced -- servers can revoke misbehaving users without a TTP's involvement, and without learning the revoked users' identities.In BLAC and EPID, however, the computation required for authentication at the server is linear in the size (L) of the revocation list. We propose PEREA, a new anonymous authentication scheme for which this bottleneck computation is independent of the size of the revocation list. Instead, the time complexity of authentication is linear in the size (K

Several credential systems have been proposed in which users can authenticate to services anonymously. Since anonymity can give users the license to misbehave, some variants allow the selective deanonymization (or linking) of misbehaving users upon a complaint to a trusted third party (TTP). The ability of the TTP to revoke a user's privacy at any time, however, is too strong a punishment for misbehavior. To limit the scope of deanonymization, systems such as "e-cash" have been proposed in which users are deanonymized under only certain types of well-defined misbehavior such as "double spending." While useful in some applications, it is not possible to generalize such techniques to more subjective definitions of misbehavior.