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.

Private Set Intersection (PSI) allows two mutually untrusted parties to compute the intersection of their private sets without revealing additional information. In general, PSI operates in a static setting, where the computation is performed only once on the input sets of both parties. Badrinarayanan et al. initiated the study of Updatable PSI (UPSI), which extends this capability to dynamically updating sets, enabling both parties to securely compute the intersection as their sets are modified while incurring significantly less overhead than re-executing a conventional PSI. However, existing UPSI protocols either do not support arbitrary deletion of elements or incur high computational and communication overhead. This work combines asymmetric PSI with Private Set Union (PSU) to present a novel UPSI protocol, which supports arbitrary additions and deletions of elements, offering a flexible approach to update sets. Furthermore, we design a primitive called multi-round OPRF to satisfy the forward security (IEEE TIFS 2024). Our protocol enjoys efficient performance compared to previous work. Specifically, we implement our protocol and compare it against state-of-the-art conventional PSI and UPSI protocols. Experimental results demonstrate that our UPSI protocol achieves up to three orders of magnitude reduction in computational overhead and incurs 190 ∼ 707×less communication overhead than the state-of-the-art UPSI protocol (ASIACRYPT 2024) that supports arbitrary additions and deletions.

As applications increasingly rely on vector search to find semantically similar content in large-scale databases, preserving user query privacy is of paramount importance. Existing solutions based on advanced cryptography, such as Fully Homomorphic Encryption (FHE) or Private Information Retrieval (PIR), often incur prohibitive computational or communication overheads, limiting their practical deployment. This paper introduces PrivANN, a fully oblivious system for private approximate nearest neighbor (ANN) search that leverages Trusted Execution Environments (TEEs). PrivANN employs a read-optimized Oblivious RAM (ORAM) protocol to defend against side-channel leakage, introduces a novel shuffling mechanism that decouples costly offline preparation from fast online operations and incorporates a novel oblivious Top-k selection algorithm. We formally prove PrivANN’s security guarantees and demonstrate its real-world performance. Our evaluation shows that PrivANN improves throughput by 2.4x over state-of-the-art FHE-based systems while achieving superior search quality, and reduces client-side communication overhead from gigabytes to kilobytes compared to PIR-based approach.

Abstract Artificial intelligence (AI) is revolutionizing both industries and reshaping the global economy. However, the rapid advancement of AI technologies brings significant security and privacy challenges. Recent incidents highlight vulnerabilities in AI systems, such as data leakage and malicious code injection, leading to severe financial losses and privacy breaches. Although existing studies have discussed specific security threats, they often lack detailed granularity and cover a limited scope. In this survey, we fill this gap by systematically categorizing and analyzing the threats and countermeasures in AI systems, which span both the training and inference stages, encompass centralized and distributed settings, and address both conventional and foundation AI models. By reviewing existing literature, we aim to provide AI researchers and practitioners with a thorough understanding of system vulnerabilities and current countermeasures. We hope to inspire further research into robust solutions, ultimately contributing to the development of resilient AI technologies.

Recent developments in the field of Dynamic Searchable Symmetric Encryption (DSSE) with forward and backward privacy have attracted much attention from both research and industrial communities. However, most DSSE schemes with forward and backward privacy schemes only support single keyword queries, which impedes its prevalence in practice. Although some forward and backward private DSSE schemes with expressive queries (e.g., conjunctive queries) have been introduced, their backward privacy either essentially corresponds to single keyword queries or forward privacy is not comprehensive. In addition, the deletion of many DSSE schemes is achieved by addition paired with a deletion mark (i.e., lazy deletion). To address these problems, we present two novel DSSE schemes with conjunctive queries (termed SDSSE-CQ and SDSSE-CQ-S), which achieve both forward and backward privacy. To analyze their security, we present two new levels of backward privacy (named Type-O and Type-O-, more and more secure), which give a more comprehensive understanding of the leakages of conjunctive queries in the OXT framework. Eventually, the security analysis and experimental evaluations show that the proposed schemes achieve better security with reasonable computation and communication increase.

Private Set Intersection (PSI) enables us to compute the intersection of private sets without leaking additional data. The state-of-the-art PSI protocol$\mathsf {RR22}$(CCS 2022) is derived from an Oblivious Pseudo-Random Function (OPRF) protocol based on Oblivious Key-Value Stores (OKVS). However, the existing OKVS suffers either low computation efficiency or high encoding redundancy. In this work, we propose a new efficient bucket-based OKVS with only 1% redundancy. The encoding algorithm of our OKVS is 4 to 15 times faster than the recent state-of-the-art OKVS (USENIX Security 2023). Specifically, our OKVS can encode$2^{24}$key-value pairs in only 2.1 to 8.5 seconds, corresponding to 30% to 1% redundancy, while the latter takes about 30 seconds with at least 3%. We can then obtain a new ultra-fast PSI protocol with lower communication from our OKVS in both semi-honest and malicious settings. Furthermore, we implemented our PSI protocol and conducted an extensive evaluation, which shows that it outperforms the existing PSI protocols, such as$\mathsf {KKRT16}$(CCS 2016),$\mathsf {CM20}$(Crypto 2020),$\mathsf {RS21}$(EuroCrypt 2021),$\mathsf {RR22}$(CCS 2022), and$\mathsf {KBM23}$(NDSS 2023). Since our PSI features an ultra-low communication overhead, it has overall advantages for the network environment with a small bandwidth. For example, our PSI takes only about 468 and 476 seconds in semi-honest and malicious settings with the input size of$2^{24}$when the bandwidth is 10 Mbps, while the state-of-the-art$\mathsf {RR22}$requires about 541 and 625 seconds. Our implementation is available onhttps://github.com/ShallMate/fastpsi.

Private Set Intersection (PSI) enables each party with a private set to compute the intersection without disclosing other information. However, even in maliciously secure PSI, it does not guarantee input authenticity and output integrity, which becomes problematic in certain scenarios. For instance, in Web 3.0, one of the essential requirements is to find common certifiers among the parties. However, if certifier identities are meant to be protected, some parties may attempt to forge certifier identities or intentionally exclude a particular certifier during protocol execution. Recently, the Private Certifier Intersection (PCI), a variant of PSI, has been proposed to address this problem. Nevertheless, it incurs significantly high computational and communication overhead. This work proposes thePrivate Identity Intersection(PII), which takes private identifiers and corresponding anonymous signatures from mutually distrusting parties as input, verifies them, and delivers the intersection of the successfully verified identifiers to all parties while ensuring the integrity of the output. Furthermore, PII can naturally extend from two to multiple-party settings while resisting the collusion attack. To achieve the ideal functionality of PII, we implement a user-friendly MPC framework called$\mathsf {Oryx}$without third-party libraries. Based on$\mathsf {Oryx}$, we instantiate PII with two digital signature schemes, one proposed in this paper. Compared to existing work, our PII protocols reduce the computation overhead by up to$163\times$and the communication overhead by up to$190\times$, representing an improvement of two orders of magnitude. To demonstrate the practicality of our work, we evaluate its performance in WAN environments with bandwidths of 100 Mbps and 500 Mbps, under a fixed latency of 20 ms.

Volume-hiding encrypted multi-map (EMM) allows the client to efficiently search on encrypted data while concealing the real volume of values for the queried key, thereby mitigating privacy-compromising attacks that depend on volume knowledge. However, most of the volume-hiding EMMs focus on single keyword queries, leaving the design of a volume-hiding conjunctive-keyword EMM a significant challenge. In this paper, we first propose a performance-optimized volume-hiding single-keyword EMM by adopting binary fuse filter,$\mathsf {BF^{2}MM}$, which serves as the crucial component for volume-hiding conjunctive-keyword EMM. We then introduce a generic construction dubbed$\mathsf {vCMM}$for volume-hiding conjunctive query, relying on a novel index structure from merely symmetric-key cryptographic tools. We further instantiate it to a practical volume-hiding conjunctive-keyword EMM,$\mathsf {BF^{2}CMM}$, which features nearly optimal query communication complexity and storage overhead. In addition, we extend our proposals to non-interactive DP-variants$\mathsf {DP\textrm {-}BF^{2}MM}$and$\mathsf {DP\textrm {-}BF^{2}CMM}$to provide tunable trade-offs between performance and privacy. Finally, we provide a thorough comparison with the existing volume-hiding conjunctive-keyword EMM$\mathsf {OXTMM}$. Experimental results show a significant performance improvement of$\mathsf {BF^{2}CMM}$, with over a$2\times$storage saving, a$90\times$increase in setup efficiency, and roughly$180\times$speedup in search latency compared to$\mathsf {OXTMM}$, respectively.

Symmetric Searchable Encryption (SSE) enables querying over encrypted data stored on servers, protecting the privacy of both client queries and the data. However, the response results of the query can leak certain statistical information, allowing an active attacker to inject files and exploit these leakages to recover the queried keyword. Recently, Zhang et al. (USENIX Security 2023) proposed a volumetric injection attack, called BVMA, based on response volume patterns. This attack requires larger file injections and has a moderate recovery rate. In this work, we propose a powerful volumetric injection attack,$\mathsf {Violin}$, that utilizes response length and size patterns, achieving a higher recovery rate and smaller injection size. Specifically,$\mathsf {Violin}$requires$\mathcal {O}(\log n)$injection files with a total size of$\mathcal {O}(n\log n)$, where$n$is the number of keywords. Furthermore, we propose a file injection method with optimal injection amount (i.e., injected files number and size) based on Pascal’s triangle rule under threshold countermeasure. We implement$\mathsf {Violin}$and compare it with the existing injection attacks. Experimental results indicate that$\mathsf {Violin}$achieves a recovery rate approaching 100%, surpassing the state-of-the-art BVMA while requiring smaller file sizes. Under threshold countermeasure,$\mathsf {Violin}$achieves a saving of 22% in injection file size and a remarkable 95% decrease in injected file number compared to BVMA.

Secure join schemes, an important class of queries over encrypted databases, have attracted increasing attention. While efficient querying is paramount, data owners also emphasize the significance of privacy preservation. The state-of-the-art JXT (Jutla and Patranabis ASIACRYPT 2022) enables efficient join queries over encrypted tables with a symmetric-key solution. However, we observe that JXT inadvertently leaks undesirable query results as the number of queries increases. In this paper, we propose a novel equi-join scheme, One-Time Join Cross-Tags (OTJXT), which can avoid additional result leakage in multiple queries and extend to equi-join as opposed to natural join in JXT. Specifically, we design a new data encoding method using nonlinear transformations that reveals only the union of results for each query without extra leakage observed in JXT. Moreover, OTJXT addresses the linear search complexity issue (Shafieinejad et al. ICDE 2022) while preventing multiple query leakage. Finally, we implement OTJXT and compare its performance with JXT and Shafieinejad et al.'s scheme on the TPC-H dataset. The results show that OTJXT outperforms in search and storage efficiency, achieving a$\mathbf {98.5\times }$(resp.,$\mathbf {10^{6}\times }$) speedup in search latency and reducing storage cost by 62.5% (resp., 78.5%), compared to JXT (resp., Shafieinejad et al.'s scheme). Using OTJXT, a TPC-H query on a 40 MB database only takes 21 ms.

Mixing services provide unlinkability for blockchains by breaking the link between sender/receiver identities and are highly appreciated for their compatibility with the underlying blockchains. Many efforts have been made to provide mixing services for either non-confidential or confidential payments. For confidential payments, all the known mixing protocols are designed for confidential blockchains using homomorphic commitment. There is, however, no satisfactory solution for confidential blockchains using public key encryption (PKE), such as PGC and Zether.

Encrypted conjunctive search enables server to perform efficient conjunctive query over encrypted data while guaranteeing data and query privacy. The well-known Oblivious Cross-Tags (OXT) protocol (by Cash et al. in CRYPTO 2013) is the first to realize efficient conjunctive search with some well-defined leakage, such as the keyword pair result pattern (KPRP) leakage and the cross-query intersection result pattern (IP) leakage. To mitigate the potential threats brought by the leakage, much effort has been made to reduce the information leaked by OXT. However, it is still open to achieve encrypted conjunctive search without revealing both KPRP and IP, while preserving high-efficiency.

Order-revealing encryption (ORE) enables the untrusted server to perform greater-than-comparison over ciphertext without compromising data privacy, which allows anyone to evaluate the lexicographic ordering of two arbitrary ciphertexts with a public comparison algorithm. However, most ORE constructions merely support ciphertext comparison for single-user. Recently, a variant of ORE named delegatable ORE has been introduced, which achieves cross-user ciphertext comparison by employing token mutual authorization technique at the cost of weak security, i.e., reveals the most significant differing bit of underlying plaintexts. To tackle this problem, we first present a deterministic property-preserving hash called DPPH with short-size hash value, and then propose a novel multi-client ORE scheme (m-ORE) from DPPH that supports ciphertext comparison among multiple users while hiding the most significant differing bits. Furthermore, we present an enhanced construction dubbed m-H-ORE by introducing a two-phase comparison method, which can achieve supper-efficient comparison in some cases, i.e., two ciphertexts with different bit-length. Finally, we provide formal security proofs of the proposed schemes and run extensive experiments to evaluate their performance on real-world and synthetic datasets. The results demonstrate that both of the proposed schemes can achieve a speedup of 47× and 138× in comparison cost to that of parameter-hiding ORE, respectively.

Data deduplication is of vital importance for mobile cloud computing to cope with the explosive growth of outsourced mobile data. In order to ensure the privacy of sensitive mobile data against an untrusted cloud, Message-Locked Encryption (MLE) has been proposed to enable deduplication over ciphertext. However, MLE prohibits data access control since it uses deterministic content-derived encryption keys. Recently, a lightweight rekeying-aware encrypted deduplication system (REED) has been proposed to achieve dynamic access control for secure data deduplication. However, REED is vulnerable to key-retaining attack and stub-retaining attack, which leads to insecure access revocation, and thus cannot support secure dynamic access control. In response, we present AC-Dedup, an encrypted deduplication storage system that supportssecure dynamic access controlfor mobile cloud storage. At the core of AC-Dedup are two novel encryption techniques namedmixed message locked encryptionandrandom stub re-encryptionto resist the two types of attacks, respectively. To the best of our knowledge, AC-Dedup is the first practical system that achieves secure data deduplication and secure dynamic access control simultaneously. We conduct security analysis and experimental evaluation on mobile device and cloud platform with real-world IoT datasets. The results show that AC-Dedup enables secure and efficient dynamic access control while preserving deduplication effectiveness.

Abstract DualRing is a novel generic construction introduced by Yuen et al. (CRYPTO’21), which can transform a special kind of (Type-T*) canonical identification scheme to a ring signature scheme. Compared with the classical approaches, this method can get a shorter signature. In this paper, we construct a new middle-product learning with errors (MPLWE)-based ring signature scheme by using this framework. Specifically, we propose a new MPLWE-based identification scheme, which is compatible with the DualRing, then we obtain a ring signature scheme by using DualRing framework. We also show how to achieve linkability from this ring signature by using a collision resistant hash function. In the end, we provide available parameter options for our (linkable) ring signature scheme. Under these parameters, the signature size of our linkable ring signature is $2-40 \times $ shorter (depending on the ring size) than the previous MPLWE-based scheme by Das et al. (Africacrypt’19).

Face recognition has been extensively employed in practice, such as attendance system and public security. Linear discriminant analysis (LDA) algorithm is one of the most significant ones in the field of face recognition, but it is very difficult for many clients to employ it in their resource-constrained devices (e.g., smartphones and notebook computers). Outsourcing computation provides a promising method for clients to perform heavy tasks with limited computing power. In this paper, we design a protocol of outsourcing LDA-based face recognition to an untrusted cloud, which can help the client to complete the operations of matrix inversion (MI), matrix multiplication (MM) and eigenvalue decomposition (ED) simultaneously. The proposed outsourcing protocol can hide the private data of the client from the cloud. More importantly, the client can verify whether the outsourcing results are correct or not with probability one and so it is impossible for the server to deceive the client. In addition, the proposed protocol greatly decreases the computational complexity of the client thus enabling the client to complete LDA algorithm efficiently. Finally, we implement the protocol and give a comprehensive evaluation. The experimental results demonstrate that the client obtain great computing savings and the face recognition accuracy in the proposed protocol is almost identical to the original LDA algorithm.

Rotation invariant local binary pattern (RI-LBP) features have been applied in diverse scenarios with the advantages of gray-scale and rotation invariance. Secure fog computing has become an emerging paradigm for enterprises or individuals with a huge volume of private data, but limited computing power for feature extraction. Prior secure outsourcing protocols based on LBP and RI-LBP simply focus on local data privacy, which can only resist ciphertext-only attack, and also make extracted features exposed to the cloud. This work focuses on how to effectively ensure data confidentiality and feature integrity. We propose a verifiable privacy-enhanced protocol for RI-LBP feature extraction (VRLBP) based on the fog computing paradigm, which mitigates the aforementioned challenges by involving the proposed symmetric cryptographic scheme where local data and extracted features are proven secure against chosen plaintext attack. Meanwhile, the stage of verification can check the correctness of outsourced features with an overwhelming probability and constant computational complexity. The security analysis and computational costs demonstrate that VRLBP can reduce the computation overhead to around 30% of original feature extraction in a privacy-preserving manner. To exhibit the practical utility, VRLBP is implemented for deepfake detection on five public datasets. Extensive evaluations indicate that VRLBP achieves almost the same accuracy as the original RI-LBP algorithm and outperforms the state-of-the-art protocols.

Cloud storage systems have seen a growing number of clients due to the fact that more and more businesses and governments are shifting away from in-house data servers and seeking cost-effective and ease-of-access solutions. However, the security of cloud storage is underestimated in current practice, which resulted in many large-scale data breaches. To change the status quo, this paper presents the design of ShieldDB, an encrypted document database. ShieldDB adapts the searchable encryption technique to preserve the search functionality over encrypted documents without having much impact on its scalability. However, merely realising such a theoretical primitive suffers from real-world threats, where a knowledgeable adversary can exploit the leakage (aka access pattern to the database) to break the claimed protection on data confidentiality. To address this challenge in practical deployment, ShieldDB is designed with tailored padding countermeasures. Unlike prior works, we target a more realistic adversarial model, where the database gets updated continuously, and the adversary can monitor it at an (or multiple) arbitrary time interval(s). ShieldDB’s padding strategies ensure that the access pattern to the database is obfuscated all the time. We present a full-fledged implementation of ShieldDB and conduct intensive evaluations on Azure Cloud.

Encrypted multi-map (EMM), as a special case of structured encryption, has attracted extensive attention recently. However, most of EMM constructions reveal the real volumes of queried keys, which can be leveraged to launch leakage-abuse attacks, as demonstrated by Kellaris et al. in CCS 2016 and Kornaropoulos et al. in S&P 2021.

The design of zkSNARKs is increasingly complicated and requires familiarity with a broad class of cryptographic and algebraic tools. This complexity in zkSNARK design also increases the difficulty in zkSNARK implementation, analysis, and optimization. To address this complexity, we develop a new workflow for designing and implementing zkSNARKs, called VOProof. In VOProof, the designer only needs to construct a Vector Oracle (VO) protocol that is intuitive and straightforward to design, and then feeds this protocol to our VO compiler to transform it into a fully functional zkSNARK. This new workflow conceals most algebraic and cryptographic operations inside the compiler, so that the designer is no longer required to understand these cumbersome and error prone procedures. Moreover, our compiler can be fine-tuned to compile one VO protocol into multiple zkSNARKs with different tradeoffs.

Ring confidential transaction (RingCT) protocol is widely used in cryptocurrency to protect the privacy of both users’ identities and transaction amounts. Most recently, a new RingCT protocol (called RingCT 2.0) was proposed by leveraging cryptographic accumulators, which can achieve a constant-size output theoretically but still far from being practical due to the heavy zero-knowledge associated with the accumulator. In this article, we revisit the design of ring confidential transaction protocol and put forward a more efficient privacy-preserving payment protocol, which is built upon an extended version of one-out-of-many proof and a special multi-signature. Compared with previous works, the new protocol is not only more practical, but also does not suffer from a trusted setup. Besides, we show that the protocol satisfies the security requirements provided that the underlying cryptographic primitives are secure in the random oracle model. We implement our new payment protocol in Java, and the experimental results show that it is efficient enough to be used in practice.

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.

Network Function Virtualisation (NFV) advances the adoption of composable software middleboxes. Accordingly, cloud data centres become major NFV vendors for enterprise traffic processing. Due to the privacy concern of traffic redirection to the cloud, secure middlebox systems (e.g., BlindBox) draw much attention; they can process encrypted packets against encrypted rules directly. However, most of the existing systems supporting pattern matching based network functions require the enterprise gateway to tokenise packet payloads via sliding windows. Such tokenisation induces a considerable communication overhead, which can be over 100× to the packet size. To overcome this bottleneck, in this article, we propose the first bandwidth-efficient encrypted pattern matching protocol for secure middleboxes. We resort to a primitive called symmetric hidden vector encryption (SHVE), and propose a variant of it, aka SHVE+, to achieve constant and moderate communication cost. To speed up, we devise encrypted filters to reduce the number of accesses to SHVE+ during matching highly. We formalise the security of our proposed protocol and conduct comprehensive evaluations over real-world rulesets and traffic dumps. The results show that our design can inspect a packet over 20 k rules within 100$\mu$s. Compared to prior work, it brings a saving of 94 percent in bandwidth consumption.

In this article, we introduce a new mechanism for constructing multi-client searchable encryption (SE). By tactfully leveraging the RSA-function, we propose the first multi-client SE protocol that successfully avoids per-query interaction between data owner and client. Therefore, our approach significantly reduces the communication cost by eliminating the need for data owner to authorize client queries at all times. To be compatible with the RSA-based approach, we also present a deterministic and memory-efficient ‘keyword to prime’ hash function, which may be of independent interest. Further, to improve efficiency, we put forward a more generic construction from set-constrained PRFs. The construction not only inherits the merits of our first protocol, but also achieves an enhanced security (against untrusted clients), where colluding attack among clients is also taken into account. Both protocols are instantiated via the recent representative SE protocol by Cashet al.with the support of boolean queries. At last, we implement our proposed protocols and comprehensively evaluate their performance to demonstrate their practicability and scalability.

Due to its capabilities of searches and updates over the encrypted database, the dynamic searchable symmetric encryption (DSSE) has received considerable attention recently. To resist leakage abuse attacks, a secure DSSE scheme usually requires forward and backward privacy. However, the existing forward and backward private DSSE schemes either only support single keyword queries or require more interactions between the client and the server. In this article, we first give a new leakage function for range queries, which is more complicated than the one for single keyword queries. Furthermore, we propose a concrete forward and backward private DSSE scheme by using a refined binary tree data structure. Finally, the detailed security analysis and extensive experiments demonstrate that our proposal is secure and efficient, respectively.

Searchable Encryption (SE) enables a data owner to outsource encrypted data to an untrusted server while preserving the keyword search functionality. Typically, the server learns whether or not a query has been performed more than once, which is usually called the search pattern. However, such kind of information leakage might be leveraged to break query privacy. To further reduce such type of leakage and provide strong privacy guarantee, Wanget al.proposed a novel SE scheme based on the Paillier encryption scheme in INFOCOM’15. Unfortunately, their scheme cannot perform keyword search successfully, because the additive homomorphic property is not sufficient for their construction. In this article, we first show that why their scheme fails to return the correct search result, and then propose a new SE scheme by adopting a special additive homomorphic encryption scheme to achieve the multiplicative homomorphic property efficiently. Furthermore, we enhance the security on the user side. Specifically, we use random polynomials with an appropriate degree to guarantee that the user cannot learn anything other than the desired search result. Finally, we present a formal security analysis and implement our scheme on a real-world database, which demonstrates that our construction can achieve the desired security properties with good performance.

The immutability of blockchain is crucial to the security of many blockchain applications, while it is still desired or even legally obliged to allow for redacting the contents of blockchain for some scenarios. In this work, we revisit the conflict between the immutability and redaction of blockchain, and put forward a new fine-grained redactable blockchain with a semi-trusted regulator, who follows our protocol but has a tendency to abuse his power. To the best of our knowledge, it is the first blockchain that not only supports the supervision of blockchain content, but also allows users themselves to manage their own data. To this end, we introduce a new variant of chameleon-hash function, named stateful Chameleon Hash with Revocable Subkey, which is important for building our redactable blockchain and may be of independent interest. We also propose a black-box construction from standard chameleon-hash functions, and prove its security properties under our proposed security notions. At last, we provide a proof-of-concept implementation. The evaluation results demonstrate that our redactable blockchain is practical and can be adopted with small additional overhead compared to the immutable blockchain.

In this paper, we propose GraphSE\textsuperscript2, an encrypted graph database for online social network services to address massive data breaches. GraphSE\textsuperscript2 ~preserves the functionality of social search, a key enabler for quality social network services, where social search queries are conducted on a large-scale social graph and meanwhile perform set and computational operations on user-generated contents. To enable efficient privacy-preserving social search, GraphSE\textsuperscript2 ~provides an encrypted structural data model to facilitate parallel and encrypted graph data access. It is also designed to decompose complex social search queries into atomic operations and realise them via interchangeable protocols in a fast and scalable manner. We build GraphSE\textsuperscript2 ~with various queries supported in the Facebook graph search engine and implement a full-fledged prototype. Extensive evaluations on Azure Cloud demonstrate that GraphSE\textsuperscript2 ~is practical for querying a social graph with a million of users.

The recently proposed Oblivious Cross-Tags (OXT) protocol (CRYPTO 2013) has broken new ground in designing efficient searchable symmetric encryption (SSE) protocol with support for conjunctive keyword search in a single-writer single-reader framework. While the OXT protocol offers high performance by adopting a number of specialised data-structures, it also trades-off security by leaking 'partial' database information to the server. Recent attacks have exploited similar partial information leakage to breach database confidentiality. Consequently, it is an open problem to design SSE protocols that plug such leakages while retaining similar efficiency. In this paper, we propose a new SSE protocol, called Hidden Cross-Tags (HXT), that removes 'Keyword Pair Result Pattern' (KPRP) leakage for conjunctive keyword search. We avoid this leakage by adopting two additional cryptographic primitives - Hidden Vector Encryption (HVE) and probabilistic (Bloom filter) indexing into the HXT protocol. We propose a 'lightweight' HVE scheme that only uses efficient symmetric-key building blocks, and entirely avoids elliptic curve-based operations. At the same time, it affords selective simulation-security against an unbounded number of secret-key queries. Adopting this efficient HVE scheme, the overall practical storage and computational overheads of HXT over OXT are relatively small (no more than 10% for two keywords query, and 21% for six keywords query), while providing a higher level of security.

Symmetric Searchable Encryption (SSE) has received wide attention due to its practical application in searching on encrypted data. Beyond search, data addition and deletion are also supported in dynamic SSE schemes. Unfortunately, these update operations leak some information of updated data. To address this issue, forward-secure SSE is actively explored to protect the relations of newly updated data and previously searched keywords. On the contrary, little work has been done in backward security, which enforces that search should not reveal information of deleted data. In this paper, we propose the first practical and non-interactive backward-secure SSE scheme. In particular, we introduce a new form of symmetric encryption, named symmetric puncturable encryption (SPE), and construct a generic primitive from simple cryptographic tools. Based on this primitive, we then present a backward-secure SSE scheme that can revoke a server's searching ability on deleted data. We instantiate our scheme with a practical puncturable pseudorandom function and implement it on a large dataset. The experimental results demonstrate its efficiency and scalability. Compared to the state-of-the-art, our scheme achieves a speedup of almost 50x in search latency, and a saving of 62% in server storage consumption.

Non-malleability is an important and intensively studied security notion for many cryptographic primitives. In the context of public key encryption, this notion means it is infeasible for an adversary to transform an encryption of some message m into one of a related message m' under the given public key. Although it has provided a strong security property for many applications, it still does not suffice for some scenarios like the system where the users could issue keys on-the-fly. In such settings, the adversary may have the power to transform the given public key and the ciphertext. To withstand such attacks, Fischlin introduced a stronger notion, known as complete non-malleability, which requires that the non-malleability property be preserved even for the adversaries attempting to produce a ciphertext of some related message under the transformed public key. To date, many schemes satisfying this stronger security have been proposed, but they are either inefficient or proved secure in the random oracle model. In this work, we put forward a new encryption scheme in the common reference string model. Based on the standard DBDH assumption, the proposed scheme is proved completely non-malleable secure against adaptive chosen ciphertext attacks in the standard model. In our scheme, the well-formed public keys and ciphertexts could be publicly recognized without drawing support from unwieldy techniques like non-interactive zero knowledge proofs or one-time signatures, thus achieving a better performance.

Related-key attacks (RKAs) are a flavor of powerful physical attacks, which allow an adversary to modify the secret key stored in a cryptographic device and subsequently observe the effect of such modifications on the output of the device. Designing secure encryption schemes against such attacks is a challenging task, especially for a large class of such physical attacks which are usually captured by related-key derivation functions. In this work, we achieve the security of public key encryptions (PKEs) against a new and broad function class that consists of almost all efficiently invertible functions in two different ways. Specifically, we first give a generic construction of PKE which is proven secure against such a broad function class under the standard chosen-ciphertext security. Moreover, we present two practical concrete constructions, both of which are shown to be secure against such function class under standard assumptions in the standard model. At last, we give a detailed performance analysis, which shows that our constructions can not only resist to a large class of RKAs but also achieve a good efficiency.

The authors present a new general construction of public key encryption (PKE) based on the restricted subset membership (RSM) assumption, which can achieve the bounded‐memory leakage resilient security and the auxiliary‐input leakage resilient security simultaneously. The construction is BHHO‐type, as Brakerski et al . work, but the message space is much larger and the proof is more concise benefiting from the RSM assumption. Instantiating the construction with the QR assumption, the authors get the first QR‐based auxiliary‐input secure PKE with a larger message space than {0,1}. Moreover, the authors generalise the Goldreich–Levin theorem to large rings. This theorem helps to improve the construction to achieve the same security level with fewer public parameters and shorter ciphertexts compared with Brakerski et al . work. For the bounded‐memory leakage resilient security, the construction can achieve leakage rate of 1 − o (1) and avoid the dependence between the message length and the amount of leakage. Based on the general construction, the authors also can achieve both bounded‐memory leakage resilient chosen ciphertext attack (CCA) security and the auxiliary‐input leakage resilient CCA security via the well‐known Naor–Yung paradigm.

Abstract Due to the proliferation of side‐channel attacks, many efforts have been made to construct cryptographic systems that remain provably secure even if part of the secret information is leaked to the adversary. Recently, there have been many identity‐based encryption (IBE) schemes proposed in this context, almost all of which, however, can only achieve chosen plaintext attack (CPA) security. As far as we know, Alwenet al.'sIBE is the unique practical scheme secure against adaptive chosen ciphertext attacks (CCA2) in the standard model. Unfortunately, this scheme suffers from an undesirable shortcoming that the leakage parameterλand the message lengthmare subject toλ+m≤ logp−ω(logκ), whereκandpdenote the security parameter and the prime order of the underlying group, respectively. Beyond that, the leakage ratio in this scheme is very low, which can just reach 1/6. In this work, we put forward two new IBE schemes, both of which areλ‐leakage‐resilient CCA2 secure in the standard model. Specifically, the first construction is proposed based on Gentry's IBE, which is quite practical and almost as efficient as the original scheme. Moreover, its leakage parameter,λ≤ logp−ω(logκ), is independent of the size of the message space. To the best of our knowledge, it is the first practical leakage‐resilient fully CCA2 secure IBE scheme in the standard model, tolerating up to (logp−ω(logκ))‐bit leakage of the private key and its leakage parameter being independent of the message length. As to the second construction, it is proposed based on the scheme of Alwenet al., which has the same leakage parameter as Alwenet al., but has a better efficiency performance and a higher leakage ratio. As far as we know, it is the first practical and fully CCA2 secure leakage‐resilient IBE scheme with leakage ratio up to 1/4. Copyright © 2016 John Wiley & Sons, Ltd.

With the purpose of taking physical attacks into account in security proofs, leakage-resilient cryptography has been initiated. Recently, many leakage-resilient cryptographic primitives have been proposed. In this paper, we put forward the first leakage-resilient wicked identity-based encryption (wicked IBE) scheme. To achieve this goal, we first present a new wicked IBE scheme in the composite order groups. The security proof of this scheme is achieved via the dual system encryption technique. In contrast with existing wicked IBE schemes, the new proposal can be proved fully secure in the standard model, even when the maximum hierarchy depth is a polynomial in the security parameter. Moreover, its security is based on some standard assumptions in the composite groups, which are independent of the hierarchy depth of the scheme. Based on this newly proposed scheme, we then put forward a fully secure leakage-resilient wicked IBE scheme in the bounded memory-leakage model. The leakage here is not only allowed on the user's secret key, but also on the master secret key. Its security is proved in the standard model by a hybrid argument in a sequence of computationally indistinguishable games. To the best of our knowledge, this is the first wicked IBE scheme in the context of leakage resilience.

Vehicular Ad Hoc Networks (VANETs) enable vehicle-to-vehicle communication to enhance road safety and improve driving experience. To secure periodic single-hop beacon messages for VANET applications, digital signature is one of the fundamental security approaches. However, it is vulnerable as excessive signatures would exhaust the computational resources of vehicles. In this paper, we propose a novel authentication mechanism VSPT, VANET authentication with Signatures and Prediction-based TESLA, which combines the advantages of both Elliptic Curve Digital Signature Algorithm (ECDSA) and Prediction-based TESLA. Although ECDSA is computationally expensive, it provides authentication and non-repudiation. Prediction-based TESLA enables fast and efficient verification by exploiting the sender's ability to predict its own future beacons. Both theoretical analysis and simulation results show that VSPT outperforms either the signature or TESLA in not only lossless situations but also lossy environments.