Publications

Function secret sharing (FSS) has become a core primitive in privacy‑preserving computation. However, each FSS invocation requires a fresh pair of function keys, typically produced by a trusted dealer—a dependency that expands the system's trust boundary and hinders practical deployment. Existing dealerless protocols eliminate this dependency, but incur substantial communication and a number of interaction rounds that grows linearly with the input bit‑width, making key generation a major bottleneck. This paper presents KORD, a protocol–hardware co‑design that dramatically reduces the cost of dealerless FSS key generation. At its core is a pair of chips that establish a common root of trust through mutual attestation and, within it, reconstruct FSS keys—eliminating the need for a dealer. This root of trust further forms a security boundary within which KORD restructures the generation protocol, collapsing the interaction of prior dealerless protocols into a single round, independent of GGM depth. A cross‑key scheduling scheme then interleaves independent GGM‑tree traversals, sustaining high computational throughput. KORD reduces key‑generation communication per operation by $7{,}633$–$70{,}274\times$ over the state‑of‑the‑art distributed FSS protocol. On a ZCU102 FPGA, cross‑key interleaving lifts AES lane utilization from $8.3\%$ to a board‑measured $99.0\%$, for $11.60$ million $32$-bit DPF keys per second at $187.5\,\text{MHz}$ on a $21.5\,\text{K}$ LUT engine ($12.38\,\text{M}$ at the separately validated $200\,\text{MHz}$ operating point). On private ResNet‑18 inference, key generation's share of end‑to‑end time falls to $10.1\%$, from $82.6\%$ under a trusted dealer and over $96\%$ under the dealerless baseline.

TLS 1.3 is at the heart of secure modern internet communications. With the rise of quantum attacks, post-quantum TLS 1.3, built on post-quantum key encapsulation mechanisms (KEMs), has naturally become a major research focus. At Eurocrypt 2022, Huguenin-Dumittan and Vaudenay demonstrated that KEMs secure against chosen-plaintext attacks (CPA) are sufficient to construct a secure TLS 1.3 handshake in the random oracle model (ROM), but their security reduction incurs an $\mathcal{O}(q^6)$ loss, where $q$ is the number of random oracle queries. Improving their security bounds was left as an open problem. To address this problem, Zhou et al. took the first step at Asiacrypt 2024, improving the loss factor to $\mathcal{O}(q^2)$ in the ROM and $\mathcal{O}(q^4)$ in the quantum ROM (QROM) for OW-CPA secure KEMs, and to $\mathcal{O}(q)$ (ROM) and $\mathcal{O}(q^2)$ (QROM) for IND-CPA secure KEMs. In this work, we advance the state-of-the-art by providing tighter security reductions for TLS 1.3 handshake based on CPA-secure KEMs. We introduce a new security notion, IND-1CCA-1MAC, and show that with a slight ciphertext expansion, the reduction losses can be significantly improved to $\mathcal{O}(q)$ (ROM) and $\mathcal{O}(q^2)$ (QROM) for OW-CPA secure KEMs, and to only $\mathcal{O}(1)$ in both models for IND-CPA secure KEMs. Moreover, we prove that without additional modifications such as ciphertext expansion, the loss of $\mathcal{O}(q)$ (ROM) and $\mathcal{O}(q^2)$ (QROM) is unavoidable. Finally, we analyze the security of TLS 1.3 from CPA-secure KEMs in the hybrid key exchange setting, and provide experimental evidence that ciphertext expansion is a practical trade-off for mitigating reduction losses.

Information set decoding (ISD) algorithm is the main tool to estimate the concrete bit security of code-based cryptographic schemes including Classic McEliece, HQC and BIKE. Inspired by sieving methods in lattice-based cryptoanalysis, a new type of ISD algorithm (called sieving-ISD) based on locality sensitive filter (LSF) was recently proposed by Guo, Johansson, and Nguyen [GJN24, TIT], which has been shown to achieve comparable complexity with the BJMM/MMT algorithm when attacking Classic McEliece. At EUROCRYPT 2024, Ducas, Esser, Etinski and Kirshanova extended [GJN24, TIT]'s deterministic LSF to probabilistic LSFs and provided an asymptotic worst-case complexity analysis for sieving-ISD with different LSFs in the full-distance setting, which indicates that the sieving-ISD with probabilistic LSFs can achieve better time complexity than the ones with [GJN24, TIT]'s deterministic LSF. In this paper, we first propose a generalized sieving-ISD framework (called progressive sieving-ISD), which allows for more freedom in parameter configuration. In particular, we present a concrete complexity analysis for both our progressive sieving-ISD and its ``decoding one out of many'' (DOOM) variant under a binary sieve heuristic, whose validity can be verified via experiments. Then, by searching the optimal parameter configuration, we show that our progressive sieving-ISD can achieve attack time complexity improvements over the previous non-progressive version by 5-12 bits. In particular, for all the three categories of HQC to be standardized by NIST, we show that the state-of-the-art complexity results can be reduced by 7-9 bits using our progressive sieving-ISD, making their security levels 5.1/2.1/5.7 bits below the NIST requirements (143/207/272 bits). Interestingly, our results show that when considering the concrete security of Classic McEliece/HQC/BIKE, the progressive sieving-ISD with [GJN24, TIT]'s deterministic LSF can achieve a better performance than the ones with probabilistic LSFs in [DEEK24, EC]. Finally, we show the connection between progressive sieving-ISD and BJMM, and hence explain why progressive sieving-ISD can achieve a better time complexity than BJMM.

The Rank Decoding (RD) problem lies at the core of rank-based cryptography. To enable efficient constructions, several variants have been introduced, notably the Non-Homogeneous RD (NHRD) problem and the Blockwise RD (BRD) problem. The quantum security of these systems is currently considered to be determined by the complexity of combinatorial attacks such as AGHT, PRR, and Ourivski--Johansson (OJ) attacks. However, for the OJ attack, the modeling, soundness, and relative complexities remain poorly understood, particularly for the NHRD and BRD variants, thereby limiting confidence in security claims and hindering the design of compact schemes. In this work, we refine the modelings for the OJ attack (PIT, 2002) and the Improved OJ (IOJ, IEEE TIT 2025) attack, and obtain general and tight complexities on the RD, NHRD, and BRD problems. We show that the IOJ attack rests on optimistic assumptions that do not hold in practical random decoding scenarios, and thus its advantage over OJ should be disregarded in security assessments. For the RD problem, the OJ attack remains a strong candidate for the most powerful combinatorial attack in certain parameter regions, particularly when the code dimension $k$ is small and the extension degree $m$ is large. For the NHRD problem, we show that the OJ attack is the most powerful combinatorial attack for the parameters of NH-Multi-UR-AG, yielding up to a 100-bit improvement over the adapted AGHT attack (IEEE TIT 2024), while still preserving the claimed security level. For the BRD problem, we derive complexity formulas for general block structures, resolving questions posed in prior works (Asiacrypt 2023, IEEE TIT 2025, PQC 2024). Our analysis also reveals that the OJ attack is previously underestimated by about $\gamma^2$ bits, where $\gamma$ denotes the minimum block weight. We further show that the OJ attack outperforms AGHT and PRR attacks in certain parameter regions, achieving up to a 136-bit advantage over PRR (IEEE TIT 2025). Our work advances the understanding of decoding problems in the rank metrics and reinforces the security of related cryptosystems.

Skyline optimization is a powerful tool for filtering prominent data to support analysis and decision-making. However, traditional centralized skyline predicates are inadequate for contemporary data islands, and shallow data federation poses a threat to privacy with sensitive data. In existing distributed environments, achieving both efficiency and security in skyline computation remains a critical challenge. This paper addresses the challenge of performing secure skyline predicates on encrypted data federation while safeguarding both the dataset and skyline from unauthorized access. We propose a novel asynchronous structured skyline predicate based on vertical dominance and truth-value conversion, taking full advantage of distributed computing. Furthermore, we introduce a secure optimization that balances security and efficiency, thereby facilitating a distributed skyline predicate. We evaluate the efficiency and scalability across various parameters, demonstrating improvements in traversal overhead and expensive ciphertext operations.

Secure TransFormer Inference (STFI) for LLMs aims to protect both user inputs and model parameters. Fully Homomorphic Encryption (FHE) offers a promising approach for STFI due to its non-interactivity, which eliminates communication overhead. However, FHE-based STFI incurs significant computational costs compared to plaintext inference. Recent advancements have accelerated inference by optimizing packing strategies and reducing the number of rotations. Despite these improvements, several challenges persist, including excessive rotations in ciphertext-ciphertext matrix multiplications (CCMMs), low input/output projection throughput, and expensive maximum/inverse operations, as well as wasted storage slots and inflated ciphertext counts due to sparse packing. To address these issues, we propose STIP, an efficient and secure non-interactive transformer inference framework that incorporates three novel packing strategies: (1) Real-Imaginary Hybrid Packing (RIHP) halves the rotation costs of CCMMs by enabling the simultaneous computation of two output results within the real and imaginary components; (2) Dual-Head Packing (DHP) maps adjacent heads to the real and imaginary components, doubling the throughput of attention projections; and (3) Adaptive Multi-Column Packing (AMCP) packs multiple heads into a single ciphertext, maximizing slot occupancy to reduce the total ciphertext count and thereby enhance computational parallelism. Moreover, for non-linear layers, we employ the Gaussian Kernel instead of Softmax, eliminating the need for maximum value searches and inverse operations, supported by a column-packed RIHP-based L2-norm algorithm. We reformulate LayerNorm into an inverse-free form by exploiting scale-invariance. Experimental results on a GPU show that STIP achieves approximately 1.6× speedup over the SOTA scheme Euston (S&P '26) on BERT-base, LLAMA-3-8B, and GPT-2-1.5B.

In the NIST post-quantum standardization process, Fujisaki-Okamoto-like (FO-like) transformation has become the de facto paradigm for constructing IND-CCA secure key encapsulation mechanisms (KEMs) from public-key encryption (PKE). However, most post-quantum PKE schemes exhibit decryption error, which poses significant challenges for the security proofs of FO-like PKE-to-KEM transformations, particularly in the quantum-accessible random oracle model (QROM). Hofheinz, Hövelmanns, and Kiltz (TCC 2017) gave the first QROM security proofs for PKE-to-KEM transformations under worst-case decryption error. To relax this to the more designer-friendly one of average-case decryption error, Duman et al. (PKC 2023) presented two transformations, $\mathsf{FOAC}_0$ and $\mathsf{FOAC}$, which are under average-case decryption error but introduce substantial loss in QROM reduction tightness ($\mathcal{O}(q^8)$ for $\mathsf{FOAC}_0$ and $\mathcal{O}(q^6)$ for $\mathsf{FOAC}$) and the need for the $\gamma$-spread assumption on the underlying PKEs. Very recently, Ge et al. (ePrint 2025) removed the $\gamma$-spread assumption for $\mathsf{FOAC}_0$ and improved the QROM reduction tightness to $\mathcal{O}(q^4)$ for both $\mathsf{FOAC}_0$ and $\mathsf{FOAC}$. In this work, we make further advances by introducing two refined variants: $\mathsf{FOAC}'_0$ and $\mathsf{FOAC'}$. We provide new security analyses in both the ROM and the QROM, and present the following key contributions: (1) Compared with previous transformations under average-case decryption error, $\mathsf{FOAC}'_0$ and $\mathsf{FOAC'}$ exhibit tighter security proofs with QROM reduction loss of only $\mathcal{O}(q^2)$ for $\mathsf{FOAC}'_0$ and $\mathcal{O}(q^3)$ for $\mathsf{FOAC'}$ when the underlying PKE is OW‑CPA secure, and just $\mathcal{O}(q)$ when it is deterministic or IND‑CPA security; (2) Both $\mathsf{FOAC}'_0$ and $\mathsf{FOAC'}$ eliminate the $\gamma$-spread assumption entirely, further relaxing the requirements on the underlying PKE. To support our QROM proofs, we provide three new QROM proof techniques that build on Zhandry's compressed oracle technique (CRYPTO 2019). These techniques may be of independent interest and could have broader applicability in post-quantum cryptography.

In this paper, we investigate the Extended Gabidulin (EG) codes and the Interleaved EG (IEG) codes, conduct more analysis on the Blockwise Rank Decoding (BRD) problem, and obtain efficient rank-based cryptosystems. First, we develop a general decoding algorithm for the (I)EG codes by solving the Linear Reconstruction (LR) problem. We find that the (I)EG codes can be probabilistically decoded by Welch-Berlekamp like algorithm, can achieve an arbitrarily small decoding failure rate, and can decode up to the rank Gilbert-Varshamov bound (even close to the minimal distance). Our conclusion intrinsically shows that it is not necessary to require that the generator be linearly independent as Gabidulin codes for designing decodable codes from $q$-polynomials. An interesting and important byproduct is that we demonstrate that decoding interleaved Gabidulin codes can be achieved deterministically by solving the LR problem. It has long been believed that there are only probabilistic decoding algorithms for interleaved Gabidulin codes (IEEE TIT 2011, DCC 2014, DCC 2024). Second, we propose the Blockwise Puncturing (BP) approach for solving the BRD problem (Asiacrypt 2023, IEEE TIT 2025). For this purpose, we derive a tight upper bound of independent equations in the MM modeling for general blocks, which further addresses an open question in (Asiacrypt 2023, IEEE TIT 2025, PQC 2024). We find that the BP approach can speed up the MM modeling. When the proposed approach is applied to the BRD problem used in existing rank-based cryptosystems, such as RQC and ROLLO (IEEE TIT 2025, PQC 2024), some parameters sets are lower than the practical security strength, and the security loss is up to 25 bits; nevertheless, the schemes still preserve the claimed security level. This work further supports the hardness of the BRD problem and enhances the security and performance of cryptosystems based on the BRD problem. Third, we apply the EG codes to the structured rank decoding encryption, namely RQC based on the BRD problem (Asiacrypt 2023, IEEE TIT 2025), and obtain the Bolckwise RQC with the EG codes (BRE). We find that the gain of using the EG codes in decoding capacity outweighs the complexity loss in solving the BRD problem with the BP approach, which still makes it possible to design more efficient schemes. As a result, BRE features a more attractive size with a bandwidth of about 1.6 KB for 128-bit security. Overall, BRE outperforms Hamming metric ones of NIST PQC Round 4 submissions, such as HQC, BIKE, and Classic McEliece, in terms of bandwidth, especially about 76% more compact than HQC selected by the NIST PQC. Fourth, we apply the EG codes to the unstructured rank decoding encryption, namely NH-Multi-UR-AG (IEEE TIT 2024), with the homogeneous errors, and obtain the Homogeneous Unstructured Rank decoding encryption with the EG codes (HURE). The bandwidth of HURE is about 6.7 KB for 128-bit security, which is slightly shorter than NH-Multi-UR-AG. This bandwidth also outperforms lattice-based unstructured PKEs, namely FrodoKEM and Scloud$^{+}$, respectively about 64% and 45% more compact. We intrinsically show that it is sufficient to construct an efficient unstructured PKE scheme by only homogeneous errors, without non-homogeneous errors. This application benefits from that we derive the concise DFR for the EG codes, which allows to choose flexible parameters.

Oblivious RAM (ORAM) allows a client to securely retrieve elements from outsourced servers without leakage about the accessed elements or their virtual addresses. Two-server ORAM, designed for secure two-party RAM computation, stores data across two non-colluding servers. However, many two-server ORAM schemes suffer from excessive local storage or high bandwidth costs. To serve lightweight clients, it is crucial for ORAM to achieve concretely efficient bandwidth while maintaining O(1) local storage. Hence, this paper presents two new client-friendly two-server ORAM schemes that achieve practical logarithmic bandwidth under O(1) local storage, while incurring linear symmetric key computations. The core design features a hierarchical structure and a pairwise-area setting for the elements and their tags. Accordingly, we specify efficient read-only and write-only private information retrieval (PIR) algorithms in our schemes to ensure obliviousness in accessing two areas respectively, so as to avoid the necessity of costly shuffle techniques in previous works. We empirically evaluate our schemes against LO13 (TCC'13), AFN17 (PKC'17), and KM19 (PKC'19) in terms of both bandwidth and time cost. The results demonstrate that our schemes reduce bandwidth by approximately 2-4x compared to LO13, and by 16-64x compared to AFN17 and KM19. For a database of size 2^14 blocks, our schemes are over 64x faster than KM19, while achieving similar performance to LO13 and AFN17 in the WAN setting, with a latency of around 1 second.

With the increasing demand for access to and query of multimedia data, many applications rely on outsourcing data storage and queries to the cloud. Although efficient, this approach poses privacy risks to data owners. Researchers have sought secure methods for processing outsourced data, with the prerequisite of securely retrieving target data from datasets. In this paper, we address the performance limitations of existing three-party oblivious selection algorithms by proposing a novel online-efficient design. Furthermore, we optimize the proposed approach through algorithmic and system-level enhancements, achieving performance improvements across various settings.

Multi-party computation (MPC) has gained increasing attention in both research and industry, with many protocols adopting the preprocessing model to optimize online performance through the strategic use of offline-generated, data-independent correlated randomness (or correlation). However, while extensive research has been dedicated to enhancing the online phase, the equally critical offline phase remains largely overlooked. This gap imposes significant yet unaddressed challenges in both security and efficiency, hindering the practical adoption of MPC systems. To address these challenges, we build upon the pseudorandom correlation generator (PCG) concept by Boyle et al. (CRYPTO’19, FOCS’20) and propose HPCG, a programmable, verifiable, and concretely efficient PCG construction using small security hardware. Our core technique, termed verifiable silent preprocessing, enables virtually unbounded, on-demand generation of diverse correlated randomness with provable correctness while effectively reducing offline overhead in a correlation-agnostic manner. To demonstrate the benefits of our approach, we experimentally evaluate HPCG and compare it with other preprocessing techniques. We also show how HPCG can further optimize specialized secure computation tasks (e.g., shuffling and equality test) by promoting new, customized correlations, which may be of new interest.

Including TOR, most of the anonymous communication systems adopt source routing, that the source has to share the globally consistent view of all relays and maintain the up-to-date information. To increase the scalability of TOR, researchers mainly utilize hop-by-hop routing during circuit extension. However, hop-by-hop routing has not been widely deployed since it suffers from route capture attacks, and most of the countermeasures require the source participate in the route extension indirectly, help verify the selection of next hop by intermediate nodes, thus introduces communication overhead. In this paper, we introduce a novel routing scheme called Jump Routing. In jump routing, the route extension follows the jumping way, that each relay chooses the successor of the next hop rather than the next hop itself. In particular, to the best of our knowledge, we are the first to route in the jumping way. In addition, to defend route capture attacks, enhance data privacy, and defend collusion attacks, we propose multiple schemes including jump verification, jump encryption, and corporative jump verification. Different from previous measures on route capture attacks, jump routingdoes not need the participation of the source, but deals with the attack by intermediate nodes only. We manage to realize the full jump routing prototype, and the evaluation results show that our jump routing is scalable, lightweight, and resilient.

Private information retrieval (PIR) is a widely used technique in privacy-preserving applications that enables users to retrieve records from a database without revealing any information about their queries. This study focuses on a type of PIR that has a high ratio between the size of the record retrieved by the client and the server's response. Although significant progress has been made in high-rate PIR in recent years, the computational overhead on the server side remains rather high. This results in low server throughput, particularly for applications involving databases with moderate-size records (i.e. tens of kilobytes), such as private advertising system. In this paper, we present Npir, a high-rate single-server PIR that is based on NTRU encoding and outperforms the state-of-the-art Spiral (Menon & Wu, S&P 2022) and NTRUPIR (Xia & Wang, EuroS&P 2024) in terms of server throughput for databases with moderate-size records. In specific, for databases ranging from 1 GB to 32 GB with 32 KB records, the server throughput of Npir is 1.50 to 2.84 times greater than that of Spiral and 1.77 to 2.55 times greater than that of NTRUPIR. To improve server throughput without compromising the high-rate feature, we propose a novel tool called NTRU packing, which compresses the constant terms of underlying polynomials of multiple NTRU encodings into a single NTRU encoding, thereby reducing the size of the server's response. Furthermore, Npir naturally supports batch processing for moderate-size records, and can easily handle retrieving for records of varying sizes.tions, we advance secure communication protocols under challenging conditions.

Fine-tuning is an essential process to improve the performance of Large Language Models (LLMs) in specific domains, with Parameter-Efficient Fine-Tuning (PEFT) gaining popularity due to its capacity to reduce computational demands through the integration of low-rank adapters. These lightweight adapters, such as LoRA, can be shared and utilized on open-source platforms. However, adversaries could exploit this mechanism to inject backdoors into these adapters, resulting in malicious behaviors like incorrect or harmful outputs, which pose serious security risks to the community. Unfortunately, few current efforts concentrate on analyzing the backdoor patterns or detecting the backdoors in the adapters. To fill this gap, we first construct and release PADBench, a comprehensive benchmark that contains 13,300 benign and backdoored adapters fine-tuned with various datasets, attack strategies, PEFT methods, and LLMs. Moreover, we propose PEFTGuard, the first backdoor detection framework against PEFT-based adapters. Extensive evaluation upon PADBench shows that PEFTGuard outperforms existing detection methods, achieving nearly perfect detection accuracy (100%) in most cases. Notably, PEFTGuard exhibits zero-shot transferability on three aspects, including different attacks, PEFT methods, and adapter ranks. In addition, we consider various adaptive attacks to demonstrate the high robustness of PEFTGuard. We further explore several possible backdoor mitigation defenses, finding fine-mixing to be the most effective method. We envision that our benchmark and method can shed light on future LLM backdoor detection research.

Many network middleboxes have been deployed to performdeep packet inspection(DPI) over packet payloads. However, such middleboxes cannot accomplish their tasks when the traffic is encrypted.BlindBox(SIGCOMM 2015) provided the first solution for performing DPI over encrypted traffic. To improve its efficiency, a later proposalPrivDPI(CCS 2019) introduced a practical technique to generate encrypted rules. However, a recent proposalP2DPI(ASIACCS 2021) showed that the rule generator in PrivDPI can comprise the user's privacy. In this paper, we present a new attack on P2DPI and show that the privacy of its endpoints can still be compromised by the rule generator. We comprehensively analyze the vulnerability of prior studies and presentPrivBox, a new DPI system that achieves the same privacy guarantee as BlindBox while maintaining practical efficiency. This is based on a new technique calleddual double-masking obfuscated rule generation. For a ruleset of 3,000, PrivBox achieves connection establishment time on the endpoint side comparable to PrivDPI and supports up to 4,672 token encryptions per second, which is sufficient for a number of real-world applications. Overall, our experiment demonstrates that PrivBox is practical and well-suited for short, frequently established sessions, especially when token repeating is common.

With the rapid advancement of the digital economy, data collaboration between organizations has become a well-established business model, driving the growth of various industries. However, privacy concerns make direct data sharing impractical. To address this, Two-Party Split Learning (a.k.a. Vertical Federated Learning (VFL)) has emerged as a promising solution for secure collaborative learning. Despite its advantages, this architecture still suffers from low computational resource utilization and training efficiency. Specifically, its synchronous dependency design increases training latency, while resource and data heterogeneity among participants further hinder efficient computation. To overcome these challenges, we propose PubSub-VFL, a novel VFL paradigm with a Publisher/Subscriber architecture optimized for two-party collaborative learning with high computational efficiency. PubSub-VFL leverages the decoupling capabilities of the Pub/Sub architecture and the data parallelism of the parameter server architecture to design a hierarchical asynchronous mechanism, reducing training latency and improving system efficiency. Additionally, to mitigate the training imbalance caused by resource and data heterogeneity, we formalize an optimization problem based on participants' system profiles, enabling the selection of optimal hyperparameters while preserving privacy. We conduct a theoretical analysis to demonstrate that PubSub-VFL achieves stable convergence and is compatible with security protocols such as differential privacy. Extensive case studies on five benchmark datasets further validate its effectiveness, showing that, compared to state-of-the-art baselines, PubSub-VFL not only accelerates training by $2 \sim 7\times$ without compromising accuracy, but also achieves a computational resource utilization rate of up to 91.07%.

Threshold linearly homomorphic encryption (ThLHE) is a useful cryptographic tool for secure computation in multi-party settings, with applications in electronic voting, secure multiparty computation (MPC), and beyond. Although ThLHE offers significant advantages such as low communication overhead, its adoption in modern systems is hindered by a critical dilemma between efficiency and utility. Precisely, existing ThLHE schemes either suffer from high decryption complexity—typically $\mathcal{O}(N^2\log N)$ or worse for $N$ parties—or impose extra restrictions on the message space or participant set, limiting their practicality in large-scale and dynamic settings. In this work, we resolve this efficiency-utility dilemma for ThLHE by introducing a novel primitive termed message-space adapter (MeSA). By developing a lattice-based MeSA for exponential ElGamal (Exp-ElGamal), we mitigate the small-message restriction of Exp-ElGamal while preserving its efficient threshold decryption. This leads to the design of the first ThLHE scheme that achieves quasi-linear decryption complexity without restrictions on the message space or participant set. We implement a prototype of this new ThLHE scheme and validate the quasi-linear growth of its running time with respect to $N$. Beyond resolving this dilemma, we further extend the applications of our new ThLHE scheme. Specifically, we apply it to construct the first multi-party fully homomorphic encryption scheme with quasi-linear computation complexity and constant communication complexity, while supporting arbitrary threshold and dynamic participant set. This demonstrates the extra benefits of our ThLHE scheme with broader applicability.

Outsourcing data storage and computations to cloud servers offers a cost-effective solution for remote data management and query processing. However, ensuring the privacy of sensitive information remains a critical concern, and existing secure algorithms rely on data completeness where all attribute values are valid to ignore the dominance issues under intransitivity and cyclicity. This paper addresses the challenge of executing secure skyline predicates on outsourced incomplete data, while keeping the dataset, queries, and results confidential from the cloud servers. We propose a novel secure dominance under incomplete data as a core component of various query types. To balance security and efficiency, we introduce two filtering methods around access patterns. Additionally, we present two secure skyline extensions concerning dimension and skyband to produce meaningful skylines. The proposed solutions are empirically evaluated for efficiency and scalability on diverse datasets, demonstrating the practical viability of our approach.

Multi-scalar multiplication (MSM) is the primary building block in many pairing-based zero-knowledge proof (ZKP) systems. MSM at large scales has become the main bottleneck in ZKP implementations. Inspired by existing SIMD-accelerated work, we are focused on accelerating MSM computing efficiency using SIMD instructions in a single CPU environment. First, we propose a SIMD-accelerated MSM computing architecture with no write conflicts and constant memory overheads. This architecture utilizes multithreading to achieve task-level and loop-level parallelism and employs a three-tier buffer mechanism to maximize the utilization of the SIMD engine. Instanced with AVX512-IFMA instructions, we implement six SIMD elliptic curve arithmetic engines for different point addition in three coordinate systems and two groups. Moreover, we integrate our AVX-MSM implementation into the libsnark library, naming it AVX-ZK. In more detail, point deduplication and “Three-Stage” memory optimization are proposed to address problems existing in practical applications. Based on the RELIC library, our performance results on the BLS12-381 curve show that our AVX-MSM achieves up to 27.86x speedup over the most popular Pippenger algorithm. Compared with libsnark, our AVX-ZK implementation achieves over 11.53x (up to 20.26x) speedup under standard benchmarks.

TLS 1.3 is widely used to realize secure communication over the Internet. Existing security analyses of TLS 1.3 primarily focus on its handshake protocol which is indeed an authenticated key exchange (AKE) protocol, and implicitly neglect the so-called subversion attacks (e.g., breaking TLS via Dual EC) in the real world. Reverse firewall (RF) is a prevalent approach to defend against subversion attack. To the best of our knowledge, the only two subversion-resilient AKE protocols with RFs are proposed by Dodis et al. (CRYPTO'16) and Bossuat et al. (ESORICS'20). The security of both protocols is proved under game-based model which is insufficient for the concurrent execution of multiple TLS instances in practice. In this paper, we propose$\mathsf {srTLS}$, a variant of the TLS 1.3 full one round-trip time (1-RTT) handshake protocol with RFs under the universally composable (UC) model. In particular, we first present the ideal functionality of unilateral AKE$\mathcal {F}_{\mathsf {uaKE}}$. Then, we use RFs with outer transparency to circumvent the difficulty in sanitizing the messages of handshake protocol, and prove that$\mathsf {srTLS}$UC-realizes$\mathcal {F}_{\mathsf {uaKE}}$in the presence of subversion attacks. Finally, we integrate$\mathsf {srTLS}$and existing subversion-resilient AKE protocols into TLS 1.3. The evaluation result demonstrates that$\mathsf {srTLS}$achieves at least a 44.86% efficiency improvement over other subversion-resilient AKE protocols.

Remote data integrity auditing enables a client to efficiently ensure the integrity of entire data stored in untrusted servers via auditing. Yet, existing solutions generally emphasize on various metrics (such as minimal storage, fast update, metadata privacy), but not audit performance (e.g., low audit time, small proof size). To this end, a label-aggregating remote data integrity auditing scheme (LARDA) was proposed in ESORICS ’22, which is the state-of-the-art work in terms of proof size and storage cost. However, LARDA needs a trusted third party (TTP) for performing data auditing for all data owners, which introduces a single point of failure since the audit process routinely needs to interact with the TTP. To address this issue, we introduce a new concept called threshold label-aggregating data auditing and propose two novel schemes. Our first solution is based on Pedersen secret sharing technique, which can significantly alleviate the key escrow problem of LARDA. Our second solution is an efficient batch verifying scheme for multiple TTP’s secret key shares, utilizing the KZG (Kate, Zaverucha and Goldberg) secret sharing technique. This scheme can maintain the size of commitment for TTP’s secret key constant rather than a linear factor with the number of TTPs. We conduct comprehensive experiments to demonstrate the scalability of our schemes. In particular, our second scheme improves the verification time for TTP’s secret key shares in constant, only requiring two pairings and one exponentiation in group with an average of 7.39 ms, regardless of the number of TTPs increasing. For our first scheme, the verification procedure requires$2t$exponentiations in group (where t is the threshold value), ranging from 2.37 ms ($t = 2$) to 26.85 ms ($t = 35$).

Subversion-resilient cryptography has garnered increasing attention in recent years due to growing concerns about cryptographic subversions in real-world applications. Among the existing countermeasures, the notion of cryptographic reverse firewalls (RFs), initially proposed by Mironov and Stephens-Davidowitz (EUROCRYPT 2015) and later extended by Chakraborty et al. (EUROCRYPT 2022) to the universally composable (UC) model, has proven to be a powerful tool for building subversion-resilient cryptographic protocols. In this work, we focus on designing subversion-resilient authenticated key exchange (AKE) protocols, which are critical components of secure Internet communication. We present the f irst generic framework for subversion-resilient UC-secure AKE protocols leveraging RFs. In spired by the state-of-the-art advancements by Chakraborty et al. (ASIACRYPT 2024), we address subversions: where a party’s implementation is covertly altered to exfiltrate secrets or behave unpredictably when triggered by adversarial inputs. A key contribution of our work is the introduction of a new AKE functionality which, for the first time, incorporates security against key control, an essential aspect of achieving subversion resilience. We also provide a concrete instantiation of our framework, demonstrating its feasibility in practice. Notably, the RFs in our proposed AKE protocol are transparent, an important property of RF as defined originally, which allows deployment of RF without all parties explicitly knowing about it and allows robust security. Achieving transparency for RFs has been widely regarded as challenging, particularly when addressing broader subversion attacks (e.g., input-trigger attacks) in the UC model. Our approach, thus, not only advances the state of AKE protocol design, but also offers insights into building other subversion-resilient protocols in the UC model using transparent RFs.

The combination of Oblivious RAM (ORAM) with Trusted Execution Environments (TEE) has found numerous real-world applications due to their complementary nature. TEEs alleviate the performance bottlenecks of ORAM, such as network bandwidth and roundtrip latency, and ORAM provides general-purpose protection for TEE applications against attacks exploiting memory access patterns. The defining property of this combination, which sets it apart from traditional ORAM designs, is its ability to ensure that memory accesses, both inside and outside of TEEs, are made oblivious, thus termed doubly oblivious RAM (O$_2$RAM). Efforts to develop O$_2$RAM with enhanced performance are ongoing. In this work, we propose H$_2$O$_2$RAM, a high-performance doubly oblivious RAM construction. The distinguishing feature of our approach, compared to the existing tree-based doubly oblivious designs, is its first adoption of the hierarchical framework that enjoys inherently better data locality and parallelization. While the latest hierarchical solution, FutORAMa, achieves concrete efficiency in the classic client-server model by leveraging a relaxed assumption of sublinear-sized client-side private memory, adapting it to our scenario poses challenges due to the conflict between this relaxed assumption and our doubly oblivious requirement. To this end, we introduce several new efficient oblivious components to build a high-performance hierarchical O$_2$RAM (H$_2$O$_2$RAM). We implement our design and evaluate it on various scenarios. The results indicate that H$_2$O$_2$RAM reduces execution time by up to $\sim 10^3$ times and saves memory usage by $5\sim44$ times compared to state-of-the-art solutions.

The application of skyline queries on outsourced databases significantly aids online analysis, yet efficiently handling encrypted queries remains a formidable obstacle. Moreover, query outcomes are vulnerable to potential malicious cloud services. To circumvent these limitations, this work presents the Honest-Majority and Maliciously Skyline Query scheme (HMMSQ), which facilitates efficient skyline queries while safeguarding the privacy of datasets, queries, and skylines, as well as detecting malevolent activities. The core of HMMSQ is an optimized skyline diagram constructed by a novel skyline region-splitting algorithm for accurate skyline queries. Furthermore, it mitigates the frequency of dataset accesses by leveraging a multi-path R-tree for secure skyline retrieval. Notably, the majority of malicious behavior detection is focused on the servers, thereby minimizing user authentication overhead. The complexity and security are thoroughly analyzed, and experimental evaluations on various datasets demonstrate its efficiency and practicality in terms of computational cost and communication overhead. Remarkably, HMMSQ outperforms existing methods in query latency, achieving up to an order of magnitude improvement.

Order-Revealing Encryption (ORE) provides a practical solution for conducting range queries over encrypted data. Achieving a desirable privacy-efficiency tradeoff in designing ORE schemes has posed a significant challenge. At Asiacrypt 2018, Cash et al. proposed Parameter-hiding ORE (pORE), which specifically targets scenarios where the data distribution shape is known, but the underlying parameters (such as mean and variance) need to be protected. However, existing pORE constructions rely on impractical bilinear maps, limiting their real-world applicability. In this work, we propose an alternative and efficient method for constructing pORE using identification schemes. By leveraging the map-invariance property of identification schemes, we eliminate the need for pairing computations during ciphertext comparison. Specifically, we instantiate our framework with the pairing-free Schnorr identification scheme and demonstrate that our proposed pORE scheme reduces ciphertext size by approximately 31.25% and improves encryption and comparison efficiency by over two times compared to the current state-of-the-art pORE construction. Our work provides a more efficient alternative to existing pORE constructions and could be viewed as a step towards making pORE a viable choice for practical applications.

To address the confidentiality concerns of malicious adversaries that fully compromise the message broker in pub/sub based IoT systems, several researchers use proxy re-encryption (PRE) to realize end-to-end encrypted message distribution (from publisher to subscriber). However, the all-or-nothing share feature of PRE poses a problem that the share cannot be efficiently revoked. The only way for publishers to revoke the access rights of subscribers is to pick a new public-private key pair and re-generate the re-encryption keys for all the remaining subscribers, which hampers the scalability in practice. To realize efficient user revocation, we present REEDS, an efficient revocable end-to-end encrypted message distribution system for IoT. The core of REEDS is a novel proxy-aided identity-based conditional proxy re-encryption (PIB-CPRE) scheme. Essentially, we use a binary-tree structure to organize re-encryption keys, so that the update of re-encryption keys is reduced from linear to logarithmic in the number of subscribers. We show that REEDS satisfies confidentiality, efficient immediate revocation, decentralized authorization, and maintains low overhead for publishers and subscribers. The prototype system is implemented and its performance is evaluated. The results show that REEDS is not only easy to deploy over existing message brokers but also highly efficient.

In the aftermath of the Snowden revelations in 2013, concerns about the integrity and security of cryptographic systems have grown significantly. As adversaries with substantial resources might attempt to subvert cryptographic algorithms and undermine their intended security guarantees, the need for subversion-resilient cryptography has become paramount. Security properties are preserved in subversion-resilient schemes, even if the adversary implements the scheme used in the security experiment. This paper addresses this pressing concern by introducing novel constructions of subversion-resilient signatures and hash functions while proving the subversion-resilience of existing cryptographic primitives. Our main contribution is the first construction of subversion-resilient signatures under complete subversion in the offline watchdog model (with trusted amalgamation) without relying on random oracles. We demonstrate that one-way permutations naturally yield subversion-resilient one-way functions, thereby enabling us to establish the subversion-resilience of Lamport signatures, assuming a trusted comparison is available. Additionally, we develop subversion-resilient target-collision-resistant hash functions using a trusted XOR. By leveraging this approach, we expand the arsenal of cryptographic tools that can withstand potential subversion attacks. Our research builds upon previous work in the offline watchdog model with trusted amalgamation (Russell et al. ASIACRYPT'16) and subversion-resilient pseudo-random functions (Bemmann et al. ACNS'23), culminating in the formal proof of subversion-resilience for the classical Naor-Yung signature construction.

The revelations of Edward Snowden in 2013 rekindled concerns within the cryptographic community regarding the potential subversion of cryptographic systems. Bellare et al. (CRYPTO'14) introduced the notion of Algorithm Substitution Attacks (ASAs), which aim to covertly leak sensitive information by undermining individual cryptographic primitives. In this work, we delve deeply into the realm of ASAs against protocols built upon cryptographic primitives. In particular, we revisit the existing ASA model proposed by Berndt et al. (AsiaCCS'22), providing a more fine-grained perspective. We introduce a novel ASA model tailored for protocols, capable of capturing a wide spectrum of subversion attacks. Our model features a modular representation of subverted parties within protocols, along with fine-grained definitions of undetectability. To illustrate the practicality of our model, we applied it to Lindell's two-party ECDSA protocol (CRYPTO'17), unveiling a range of ASAs targeting the protocol's parties with the objective of extracting secret key shares. Our work offers a comprehensive ASA model suited to cryptographic protocols, providing a useful framework for understanding ASAs against protocols.

Numerous studies have underscored the significant privacy risks associated with various leakage patterns in encrypted data stores. While many solutions have been proposed to mitigate these leakages, they either (1) incur substantial overheads, (2) focus on specific subsets of leakage patterns, or (3) apply the same security notion across various workloads, thereby impeding the attainment of fine-tuned privacy-efficiency trade-offs. In light of various detrimental leakage patterns, this paper starts with an investigation into which specific leakage patterns require our focus in the contexts of key-value, range-query, and dynamic workloads, respectively. Subsequently, we introduce new security notions tailored to the specific privacy requirements of these workloads. Accordingly, we propose and instantiate SWAT, an efficient construction that progressively enables these workloads, while provably mitigating system-wide leakage via a suite of algorithms with tunable privacy-efficiency trade-offs. We conducted extensive experiments and compiled a detailed result analysis, showing the efficiency of our solution. SWATis about an order of magnitude slower than an encryption-only data store that reveals various leakage patterns and is two orders of magnitude faster than a trivial zero-leakage solution. Meanwhile, the performance of SWATremains highly competitive compared to other designs that mitigate specific types of leakage.

In this work, we provide new, tighter proofs for the $T_{RH}$-transformation by Jiang et al. (ASIACRYPT 2023), which converts OW-CPA secure PKEs into KEMs with IND-1CCA security, a variant of typical IND-CCA security where only a single decapsulation query is allowed. Such KEMs are efficient and have been shown sufficient for real-world applications by Huguenin-Dumittan and Vaudenay at EUROCRYPT 2022. We reprove Jiang et al.'s $T_{RH}$-transformation in both the random oracle model (ROM) and the quantum random oracle model (QROM), for the case where the underlying PKE is rigid deterministic. In both ROM and QROM models, our reductions achieve security loss factors of $\mathcal{O}(1)$, significantly improving Jiang et al.'s results which have security loss factors of $\mathcal{O}(q)$ in the ROM and $\mathcal{O}(q^2)$ in the QROM respectively. Notably, central to our tight QROM reduction is a new tool called ''reprogram-after-measure'', which overcomes the reduction loss posed by oracle reprogramming in QROM proofs. This technique may be of independent interest and useful for achieving tight QROM proofs for other post-quantum cryptographic schemes. We remark that our results also improve the reduction tightness of the $T_{H}$-transformation (which also converts PKEs to KEMs) by Huguenin-Dumittan and Vaudenay (EUROCRYPT 2022), as Jiang et al. provided a tight reduction from $T_H$-transformation to $T_{RH}$-transformation (ASIACRYPT 2023).

Dynamic searchable symmetric encryption (DSSE) enables a server to efficiently search and update over encrypted files. To minimize the leakage during updates, a security notion named forward and backward privacy is expected for newly proposed DSSE schemes. Those schemes are generally constructed in a way to break the linkability across search and update queries to a given keyword. However, it remains underexplored whether forward and backward private DSSE is resilient against practical leakage-abuse attacks (LAAs), where an attacker attempts to recover query keywords from the leakage passively collected during queries. In this paper, we aim to be the first to answer this question firmly through two non-trivial efforts. First, we revisit the spectrum of forward and backward private DSSE schemes over the past few years, and unveil some inherent constructional limitations in most schemes. Those limitations allow attackers to exploit query equality and establish a guaranteed linkage among different (refreshed) query tokens surjective to a candidate keyword. Second, we refine volumetric leakage profiles of updates and queries by associating each with a specific operation. By further exploiting update volume and query response volume, we demonstrate that all forward and backward private DSSE schemes can leak the same volumetric information (e.g., insertion volume, deletion volume) as those without such security guarantees. To testify our findings, we realize two generic LAAs, i.e., frequency matching attack and volumetric inference attack, and we evaluate them over various experimental settings in the dynamic context. Finally, we call for new efficient schemes to protect query equality and volumetric information across search and update queries.

Motivated by the violation of two fundamental assumptions in secure communication - receiver-privacy and sender-freedom - by a certain entity referred to as ``the dictator'', Persiano et al. introduced the concept of Anamorphic Encryption (AME) for public key cryptosystems (EUROCRYPT 2022). Specifically, they presented receiver/sender-AME, directly tailored to scenarios where receiver privacy and sender freedom assumptions are compromised, respectively. In receiver-AME, entities share a double key to communicate in anamorphic fashion, raising concerns about the online distribution of the double key without detection by the dictator. The sender-AME with no shared secret is a potential candidate for key distribution. However, the only such known schemes (i.e., LWE and Dual LWE encryptions) suffer from an intrinsic limitation and cannot achieve reliable distribution. Here, we reformulate the sender-AME, present the notion of $\ell$-sender-AME and formalize the properties of (strong) security and robustness. Robustness refers to guaranteed delivery of duplicate messages to the intended receiver, ensuring that decrypting normal ciphertexts in an anamorphic way or decrypting anamorphic ciphertexts with an incorrect duplicate secret key results in an explicit abort signal. We first present a simple construction for pseudo-random and robust public key encryption that shares the similar idea of public-key stegosystem by von Ahn and Hopper (EUROCRYPT 2004). Then, inspired by Chen et al.'s malicious algorithm-substitution attack (ASA) on key encapsulation mechanisms (KEM) (ASIACRYPT 2020), we give a generic construction for hybrid PKE with special KEM that encompasses well-known schemes, including ElGamal and Cramer-Shoup cryptosystems. The constructions of $\ell$-sender-AME motivate us to explore the relations between AME, ASA on PKE, and public-key stegosystem. The results show that a strongly secure $\ell$-sender-AME is such a strong primitive that implies reformulated receiver-AME, public-key stegosystem, and generalized ASA on PKE. By expanding the scope of sender-anamorphic encryption and establishing its robustness, as well as exploring the connections among existing notions, we advance secure communication protocols under challenging conditions.

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.

Efficiently mining frequent itemsets and association rules on the encrypted outsourced data remains a great challenge for the time-consuming ciphertext computations. Nowadays, it has been not well addressed for privacy-preserving frequent itemsets and association rule mining schemes with mining efficiency, dataset, and query confidentiality simultaneously. In this paper, we investigate the study of privacy issues on frequent itemset mining and association rule mining on outsourced data in a two-cloud model, where the data are encrypted and outsourced by multiple owners holding different public keys. We develop several secure computation protocols based on additively homomorphic cryptosystem and additive secret sharing, which enable the clouds could securely mine the frequent itemsets and association rules. Furthermore, we also design two kinds of frequent itemset and association rule query service models, i.e., service customers query the cloud-mined results, and service customers query with their own decided threshold. The proposed scheme not only supports the mining process on the data encrypted by multiple public keys without compromising the security of the datasets, query data and query results, but also offline users. In addition, the experimental results show that our query scheme is much more efficient than the state-of-the-art work.

Message-Locked Encryption (MLE) is a useful tool to enable deduplication over encrypted data in cloud storage. It can significantly improve the cloud service quality by eliminating redundancy to save storage resources, and hence user cost, and also providing defense against different types of attacks, such as duplicate faking attack and brute-force attack. A typical MLE scheme only focuses on deduplication. On the other hand, supporting search operations on stored content is another essential requirement for cloud storage. In this article, we present a message-locked searchable encryption (MLSE) scheme in a dual-server setting, which achieves simultaneously the desirable features of supporting deduplication and enabling users to perform search operations over encrypted data. In addition, it supports both multi-keyword and negative keyword searches. We formulate the security notions of MLSE and prove our scheme satisfies all the security requirements. Moreover, we provide an interesting extension of our construction to support Proof of Storage (PoS). Compared with the existing solutions, MLSE achieves better functionalities and efficiency, and hence enables more versatile and efficient cloud storage service.

Context-aware recommendation systems are of increasing popularity in the digital era to recommend personalized items to users. However, how to ensure user data privacy while remaining high recommendation accuracy is widely considered a challenge. In this work, we propose a privacy-preserving method for the context-aware recommendation system in the two-cloud model. In particular, we first adjust the standard additive secret sharing scheme to support secure negative integers computation, based on which we manage to design secure comparison protocol and division protocols that enjoy desirable security and efficiency. By using these new protocols, we propose a secure and efficient context-aware recommendation system that also supports offline users. Compared with the state-of-the-art, our scheme achieves stronger data privacy preservation by further protecting the intermediate data calculated during the system training. Experimental results on real-world datasets indicate that our scheme is efficient. Notable, our system could achieve more significant performance improvement by running the underlying schemes in parallel.

The Snowden revelations in 2013 showed that user machines running cryptographic protocols might be stealthily corrupted by attackers (e.g., manufacturers and supply-chain intermediaries) who could tamper cryptographic implementations to insert backdoors to undermine cryptographic tools. To formalize such attacks, in CRYPTO 2014, Bellareet al.proposed the notion of Algorithm-Substitution Attack (ASA) which has been extensively studied since then. In this work, we turn to investigate the security of anonymous communication (AC) protocol—a well-known tool to protect user privacy on the Internet—in the case when user machines are corrupted. Specifically, we give a formal treatment of ASAs on the universal mixnet-based AC ($\mathsf{U\text{-}Mix\text{-}AC}$) protocols. We show that ASAs on$\mathsf{U\text{-}Mix\text{-}AC}$protocols could be more dangerous than previously thought by presenting attacks that are extremely powerful. As countermeasure, we adopt cryptographic reverse firewall (CRF), originally proposed by Mironov and Stephens-Davidowitz in EUROCRYPT 2015, to restore the security of$\mathsf{U\text{-}Mix\text{-}AC}$protocols in the presence of ASAs. We also implement proposed AC protocol, ASAs and CRFs for experimental evaluations, and the results show that the execution time of subverted algorithms is almost the same as that of faithful ones and our designed CRFs are effective to guard the security of$\mathsf{U\text{-}Mix\text{-}AC}$protocol.

Due to the revelations of global-scale pervasive surveillance programs, Internet users have an increasing demand for privacy. However, this is usually undesirable for network service providers because attackers would be able to anonymize themselves and avoid regulation while conducting network attacks. Therefore, network service providers want to hold users accountable and it has been widely considered as a tussle to find a good balance point between the accountability and privacy for the Internet. In this work, we first show that existing representative approaches mainly suffer from narrow-range accountability, low efficiency or risky key management. Motivated by these observations, we propose an efficient network layer protocol called APGS to balance the accountability and privacy. At the core of our APGS is the group signature which, however, is not trivial to apply for the network layer mainly due to the efficiency, revocation, and privacy issues. We manage to overcome these challenges via proposing some novel approaches, including challenge-based cache strategy, scalable verifier-local revocation strategy, and Onion-then-Case strategy. We then evaluate the efficiency of APGS and conclude that in our environment, APGS can generate packets up to 20k pkts/s on a desktop and achieve approximately 80% of IP's goodput at most on a software router.

Our context is anonymous encryption schemes hiding their receiver, but in a setting which allows authorities to reveal the receiver when needed. While anonymous Identity-Based Encryption (IBE) is a natural candidate for such fair anonymity (it gives trusted authority access by design), the de facto security standard (a.k.a. IND-ID-CCA) is incompatible with the ciphertext rerandomizability which is crucial to anonymous communication. Thus, we seek to extend IND-ID-CCA security for IBE to a notion that can be meaningfully relaxed for rerandomizability while it still protects against active adversaries. To the end, inspired by the notion of replayable adaptive chosen-ciphertext attack (RCCA) security (Canetti et al., Crypto'03), we formalize a new security notion called Anonymous Identity-Based RCCA (ANON-ID-RCCA) security for rerandomizable IBE and propose the first construction with rigorous security analysis. The core of our scheme is a novel extension of the double-strand paradigm, which was originally proposed by Golle et al. (CT-RSA'04) and later extended by Prabhakaran and Rosulek (Crypto'07), to the well-known Gentry-IBE (Eurocrypt'06). Notably, our scheme is the first IBE that simultaneously satisfies adaptive security, rerandomizability, and recipient-anonymity to date. As the application of our new notion, we design a new universal mixnet in the identity-based setting that does not require public key distribution (with fair anonymity). More generally, our new notion is also applicable to most existing rerandomizable RCCA-secure applications to eliminate the need for public key distribution infrastructure while allowing fairness.

We introduce the problem of maximizing approximately $k$-submodular functions subject to size constraints. In this problem, one seeks to select $k$-disjoint subsets of a ground set with bounded total size or individual sizes, and maximum utility, given by a function that is "close" to being $k$-submodular. The problem finds applications in tasks such as sensor placement, where one wishes to install $k$ types of sensors whose measurements are noisy, and influence maximization, where one seeks to advertise $k$ topics to users of a social network whose level of influence is uncertain. To deal with the problem, we first provide two natural definitions for approximately $k$-submodular functions and establish a hierarchical relationship between them. Next, we show that simple greedy algorithms offer approximation guarantees for different types of size constraints. Last, we demonstrate experimentally that the greedy algorithms are effective in sensor placement and influence maximization problems.

We introduce the problem of maximizing approximately $k$-submodular functions subject to size constraints. In this problem, one seeks to select $k$-disjoint subsets of a ground set with bounded total size or individual sizes, and maximum utility, given by a function that is "close" to being $k$-submodular. The problem finds applications in tasks such as sensor placement, where one wishes to install $k$ types of sensors whose measurements are noisy, and influence maximization, where one seeks to advertise $k$ topics to users of a social network whose level of influence is uncertain. To deal with the problem, we first provide two natural definitions for approximately $k$-submodular functions and establish a hierarchical relationship between them. Next, we show that simple greedy algorithms offer approximation guarantees for different types of size constraints. Last, we demonstrate experimentally that the greedy algorithms are effective in sensor placement and influence maximization problems.

In this work we resolve the open problem raised by Prabhakaran and Rosulek at CRYPTO 2007, and present the first anonymous, rerandomizable, Replayable-CCA (RCCA) secure public-key encryption scheme. This solution opens the door to numerous privacy-oriented applications with a highly desired RCCA security level. At the core of our construction is a non-trivial extension of smooth projective hash functions (Cramer and Shoup, EUROCRYPT 2002), and a modular generic framework developed for constructing rerandomizable RCCA-secure encryption schemes with receiver-anonymity. The framework gives an enhanced abstraction of the original Prabhakaran and Rosulek's scheme (which was the first construction of rerandomizable RCCA-secure encryption in the standard model), where the most crucial enhancement is the first realization of the desirable property of receiver-anonymity, essential to privacy settings. It also serves as a conceptually more intuitive and generic understanding of RCCA security, which leads, for example, to new implementations of the notion. Finally, note that (since CCA security is not applicable to the privacy applications motivating our work) the concrete results and the conceptual advancement presented here, seem to substantially expand the power and relevance of the notion of rerandomizable RCCA-secure encryption.

Restoring the security of maliciously implemented cryptosystems has been widely considered challenging due to the fact that the subverted implementation could arbitrarily deviate from the official specification. Achieving security against adversaries that can arbitrarily subvert implementations seems to inherently require trusted component assumptions and/or architectural properties. At ASIACRYPT 2016, Russell et al. proposed an attractive model where a watchdog is used to test and approve individual components of an implementation before or during deployment. Such a detection-based strategy has been useful for designing various cryptographic schemes that are provably resilient to subversion. We consider Russell et al.'s watchdog model from a practical perspective regarding watchdog efficiency. We find that the asymptotic definitional framework while permitting strong positive theoretical results, does not yet guarantee practical watchdogs due to the fact that the running time of a watchdog is only bounded by an abstract polynomial. Hence, in the worst case, the running time of the watchdog might exceed the running time of the adversary, which seems impractical for most applications. We adopt Russell et al.'s watchdog model to the concrete security setting and design the first subversion-resilient public-key encryption scheme which allows for extremely efficient watchdogs with only linear running time. At the core of our construction is a new variant of a combiner for key encapsulation mechanisms (KEMs) by Giacon et al. (PKC'18). We combine this construction with a new subversion-resilient randomness generator that can also be checked by an efficient watchdog, even in constant time, which could be of independent interest for the design of other subversion-resilient cryptographic schemes. Our work thus shows how to apply Russell et al.'s watchdog model to design subversion-resilient cryptography with efficient watchdogs. We insist that this work does not intend to show that the watchdog model outperforms other defense approaches but to demonstrate that practical watchdogs are practically achievable. This is the full version of a work published at PKC21. We identify a subtle flaw in the proof of the previous version and show it is impossible to achieve CPA security under subversion with the proposed approach. However, the same construction can achieve one-way security under subversion.

Hierarchical identity-based signature (HIBS) plays a core role in a large community as it significantly reduces the workload of the root private key generator. To make HIBS still available and secure in post-quantum era, constructing lattice-based schemes is a promising option. In this paper, we present an efficient HIBS scheme in polynomial rings. Although there are many lattice-based signatures proposed in recent years, to the best of our knowledge, our HIBS scheme is the first ring-based construction. In the center of our construction are two new algorithms to extend lattice trapdoors to higher dimensions, which are non-trivial and of independent interest. With these techniques, the security of the new scheme can be proved, assuming the hardness of the Ring-SIS problem. Since operations in the ring setting are much faster than those over integers and the new construction is the first ring-base HIBS scheme, our scheme is more efficient and practical in terms of computation and storage cost when comparing to the previous constructions.

Anonymous communication networks (ACNs) are intended to protect the metadata during communication. As classic ACNs, onion mix-nets are famous for strong anonymity, in which the source defines a static path and wraps the message multi-times with the public keys of nodes on the path, through which the message is relayed to the destination. However, onion mix-nets lacks in resilience when the static on-path mixes fail. Mix failure easily results in message loss, communication failure, and even specific attacks. Therefore, it is desirable to achieve resilient routing in onion mix-nets, providing persistent routing capability even though node failure. The state-of-theart solutions mainly adopt mix groups and thus need to share secret keys among all the group members which may cause single point of failure. To address this problem, in this work we propose a hybrid routing approach, which embeds the onion mix-net with hop-by-hop routing to increase routing resilience. Furthermore, we propose the threshold hybrid routing to achieve better key management and avoid single point of failure. As for experimental evaluations, we conduct quantitative analysis of the resilience and realize a local T-hybrid routing prototype to test performance. The experimental results show that our proposed routing strategy increases routing resilience effectively, at the expense of acceptable latency.

In-network middleboxes are vital for the Internet-of-Things (IoT) system security, but the widely adopted transport layer security (TLS) protocol blinds application-level middleboxes due to the encryption of traffic data. To resolve this problem, many solutions have been proposed to date. Among them, SplitTLS is widely adopted in the industry by proxy manufacturers. It requires TLS client to install customized root certificates and incurs additional security flaws, e.g., disabling server authentication and using weak cipher suites. Another approach is to customize the TLS protocol where middleboxes are enabled via either performing handshake directly with TLS endpoints or receiving session key materials in an out-of-band manner. Overall, current solutions would either jeopardize the original TLS handshake procedure or incur additional overheads on the endpoints. In this article, we design a new middlebox-enhanced TLS (ME-TLS), which enables endpoints to introduce authenticated middleboxes into a TLS session while control middleboxes' access permission and processing order of traffic data. Particularly, in our proposed ME-TLS, the handshake structure of TLS keeps unchanged and middleboxes work in a passive manner. That is, middleboxes in the ME-TLS could recover session key materials by monitoring handshake messages passively instead of interacting with endpoints; secondary secure channels for key transmission are also not needed in our ME-TLS. We implement our ME-TLS based on the TLS 1.3 protocol and evaluate its performances. The experimental results demonstrate that our proposal is practical and deployable for real-world IoT scenarios.

Subversion of cryptography has received wide attentions especially after the Snowden Revelations in 2013. Most of the currently proposed subversion attacks essentially rely on the freedom of randomness choosing in the cryptographic protocol to hide backdoors embedded in the cryptosystems. Despite the fact that significant progresses in this line of research have been made, most of them mainly considered the classical setting, while the research gap regarding subversion attacks against post-quantum cryptography remains tremendous. Inspired by this observation, we investigate a subversion attack against existing protocol that is proved post-quantum secure. Particularly, we show an efficient way to undetectably subvert the well-known lattice-based encryption scheme proposed by Regev (STOC 2005). Our subversion enables the subverted algorithm to stealthily leak arbitrary messages to the outsider who knows the backdoor. Through theoretical analysis and experimental observations, we demonstrate that the subversion attack against the LWE encryption scheme is feasible and practical.

In 2013, the revelation of Edward Snowden rekindled cryptographic researchers’ interest in subversion attacks. Since then, many works have been carried out to explore the power of subversion attacks and feasible effective countermeasures as well. In this work, we investigate the study of subversion attacks against cloud auditing protocol, which has been well-known as useful primitive for secure cloud storage. We demonstrate that subverted auditing protocol enables the cloud server to recover secret information stored on the data owner side. Particularly, we first define an asymmetric subversion attack model for auditing protocol. This model serves as the principle for analyzing the undetectability and key recovery of subversion attacks against auditing protocols. We then show a general framework of asymmetric subversion attacks against auditing protocols with index-coefficient challenge. To illustrate the feasibility of our paradigm, several concrete auditing protocols are provided. As a feasible countermeasure, we propose a subversion-resilient auditing protocol with index-coefficient challenge.

Motivated by the currently widespread concern about mass surveillance of encrypted communications, Bellare et al. introduced at CRYPTO 2014 the notion of Algorithm-Substitution Attack (ASA) where the legitimate encryption algorithm is replaced by a subverted one that aims to undetectably exfiltrate the secret key via ciphertexts. Practically implementable ASAs on various cryptographic primitives (Bellare et al., CRYPTO'14 & ACM CCS'15; Ateniese et al., ACM CCS'15; Berndt and Liśkiewicz, ACM CCS'17) have been constructed and analyzed, leaking the secret key successfully. Nevertheless, in spite of much progress, the practical impact of ASAs (formulated originally for symmetric key cryptography) on public-key (PKE) encryption operations remains unclear, primarily since the encryption operation of PKE does not involve the secret key, and also previously known ASAs become relatively inefficient for leaking the plaintext due to the logarithmic upper bound of exfiltration rate (Berndt and Liśkiewicz, ACM CCS'17). In this work, we formulate a practical ASA on PKE encryption algorithm which, perhaps surprisingly, turns out to be much more efficient and robust than existing ones, showing that ASAs on PKE schemes are far more effective and dangerous than previously believed. We mainly target PKE of hybrid encryption which is the most prevalent way to employ PKE in the literature and in practice. The main strategy of our ASA is to subvert the underlying key encapsulation mechanism (KEM) so that the session key encapsulated could be efficiently extracted, which, in turn, breaks the data encapsulation mechanism (DEM) enabling us to learn the plaintext itself. Concretely, our non-black-box yet quite general attack enables recovering the plaintext from only two successive ciphertexts and minimally depends on a short state of previous internal randomness. A widely used class of KEMs is shown to be subvertible by our powerful attack. Our attack relies on a novel identification and formalization of certain properties that yield practical ASAs on KEMs. More broadly, it points at and may shed some light on exploring structural weaknesses of other ``composed cryptographic primitives,'' which may make them susceptible to more dangerous ASAs with effectiveness that surpasses the known logarithmic upper bound (i.e., reviewing composition as an attack enabler).

Due to the capacity of storing massive data and providing huge computing resources, cloud computing has been a desirable platform for doing machine learning. However, the issue of data privacy is far from being well solved and thus has been a general concern in the cloud-aided machine learning. In this work, we investigate the study of how to efficiently do decision tree training and evaluation in the cloud and meanwhile achieve privacy preservation. Unlike existing cloud server-assisted model training approaches, in our proposed solution, the whole training process is mostly done by the cloud service provider who owns the machine learning model. Since the cloud cannot directly divide the encrypted dataset according to the best attributes selected, we propose a new method for decision tree training without dataset splitting. Precisely, we design three methods for decision tree training with the different tradeoff between privacy and efficiency. In all of these methods, the outsourced data are not revealed to the cloud service provider. We also propose a privacy-preserving decision tree evaluation scheme where the cloud service provider learns nothing about the user's input and the classification result while the trained model is kept secret to the user who could only learn the classification result. Compared with previous decision tree evaluation work, our scheme achieves desirable privacy preservation against both the user and the cloud service provider, and also minimizes the user's computation and communication costs. Moreover, besides protecting the data confidentiality, our proposed scheme also supports off-line users and thus has good scalability. The real-world dataset-based experimental results demonstrate that our system is of desirable utility and efficiency.

In vehicular ad hoc networks (VANETs), conditional privacy preserving authentication (CPPA) scheme is widely deployed to solve security and privacy issues. Existing CPPA schemes usually require ideal tamper-proof devices (TPDs) on vehicles which, however, might be infeasible or do not exist in reality due to high security requirements. To address this problem, we propose a practical framework of CPPA scheme that supports more realistic TPDs which are less secure correspondingly. We demonstrate that this framework also manages to achieve nonframeability in addition to other security objectives including nonrepudiation, conditional privacy preserving, and unlinkability. Moreover, performance analysis shows that our framework has better efficiency in authentication. All these features make our framework practical for VANETs.

Summary Hardware‐based middleboxes are ubiquitous in computer networks, which usually incur high deployment and management expenses. A recently arising trend aims to address those problems by outsourcing the functions of traditional hardware‐based middleboxes to high volume servers in a cloud. This technology is promising but still faces a few challenges from different aspects, including privacy concerns, middlebox functionality, and performance. In this paper, we propose two practical approaches to implementing a cloud‐based DPI middlebox. The outsourced DPI middlebox performs payload inspection over encrypted traffic while preserving the privacy of both communication data and inspection rules. Our first approach employs a modified reversible sketch structure, which is used for efficient error‐free membership testing, and our second approach extends the famous AC pattern matching algorithm to the cipher text domain. We utilize unkeyed one‐way hash functions instead of complex cryptographic protocols to achieve the privacy preservation requirements. Our system supports a wide range of real‐world inspection rules. We conduct evaluations on the ClamAV rule set, and the experiment results demonstrate the effectiveness of our proposals.

Nowadays, outsourcing data and machine learning tasks, e.g.,$k$-nearest neighbor (KNN) classification, to clouds has become a scalable and cost-effective way for large scale data storage, management, and processing. However, data security and privacy issue have been a serious concern in outsourcing data to clouds. In this article, we propose a privacy-preserving KNN classification scheme on cloud data in a twin-cloud model based on an additively homomorphic cryptosystem and secret sharing. Compared with existing works, we redesign a set of lightweight building blocks, such as secure square Euclidean distance, secure comparison, secure sorting, secure minimum, and maximum number finding, and secure frequency calculating, which achieve the same security level but with higher efficiency. In our scheme, data owners stay offline, which is different from secure-multiparty computation-based solutions which require data owners’ stay online during computation. In addition, query users do not interact with the cloud except sending query data and receiving the query results. Our security analysis shows that the scheme protects outsourced data security and query privacy, and hides access patterns. The experiments on real-world dataset indicate that our scheme is significantly more efficient than existing schemes.

In future smart cities, the proliferation and mobility of smart devices will bring many challenges to efficient communication for the city-wide networking, including frequent link fluctuation and disconnection. GSTAR (Generalized storage-aware routing) has been a robust routing protocol that utilizes in-network storage to address these challenges. Unfortunately, the cache- and-forward mechanism adopted by GSTAR usually results in extra delay for storing real-time data, and thus makes it not applicable for some particular real- time applications, which crucially require low latency. Motivated by this problem, we propose a real-time aware strategy to reduce the total delay of time- sensitive data for real-time applications. Also, we specifically analyze the threshold to store and forward via mathematical modeling and access the rationality of associated parameters. Through NS3-based simulation, we show that our designed real-time aware strategy can decrease the average delay of time-sensitive data and prevent the block of time-insensitive data compared with other strategies.

Cloud storage services have become accessible and used by everyone. Nevertheless, stored data are dependable on the behavior of the cloud servers, and losses and damages often occur. One solution is to regularly audit the cloud servers in order to check the integrity of the stored data. The Dynamic Provable Data Possession scheme with Public Verifiability and Data Privacy presented in ACISP'15 is a straightforward design of such solution. However, this scheme is threatened by several attacks. In this paper, we carefully recall the definition of this scheme as well as explain how its security is dramatically menaced. Moreover, we proposed two new constructions for Dynamic Provable Data Possession scheme with Public Verifiability and Data Privacy based on the scheme presented in ACISP'15, one using Index Hash Tables and one based on Merkle Hash Trees. We show that the two schemes are secure and privacy-preserving in the random oracle model.

A revocable ID-based broadcast encryption scheme allows an authorized third party to revoke any receiver (decryptor) from the initial receiver set S of the original broadcast ciphertext without the need of decryption. However, the existing revocable ID-based broadcast encryption schemes in the literature cannot fully preserve the receiver privacy and have a large size of ciphertext when the revoked user sets are large. To solve these problems, in this paper, we propose a novel scheme: fully privacy-preserving ID-based broadcast encryption with authorization. Our scheme allows an authorized party to dynamically handle the decryption rights of receivers via an authorized user set L without knowing the message and the identities of the initial receivers. Only those users who are both in S and L can decrypt the ciphertext successfully. The final ciphertext reveals nothing about the identity information of receivers and the authorized users. Our scheme achieves full collusion resistance and is applicable to anonymous data sharing where the receivers are decided by the authorized third party (or multiple authorized third parties) excluding the data owner. We show that our proposed scheme is provably secure under the defined security models in the random oracle model.

Optimal security reductions for unique signatures (Coron, Eurocrypt 2002) and their generalization, i.e., efficiently re-randomizable signatures (Hofheinz et al., PKC 2012 and Baderet al., Eurocrypt 2016) have been well studied in the literature. Particularly, it has been shown that under a non-interactive hard assumption, any security reduction (with or without random oracles) for a unique signature scheme or an efficiently re-randomizable signature scheme must loose a factor of at least $q_s$ in the security model of existential unforgeability against chosen-message attacks (EU-CMA), where $q_s$ denotes the number of signature queries. Note that the number $q_s$ can be as large as $2^{30}$ in practice. All unique signature schemes and efficiently re-randomizable signature schemes are concluded to be accompanied with loose reductions from these impossibility results. Somewhat surprisingly, in contrast to previous impossibility results (Coron, Eurocrypt 2002; Hofheinz et al., PKC 2012; Bader et al., Eurocrypt 2016), in this work we show that without changing the assumption type and security model, it is not always the case that any security reduction must loose a factor of at least $q_s$. As a counterexample, we propose a unique signature scheme with a tight reduction in the EU-CMA security model under the Computational Diffie-Hellman (CDH) assumption. Precisely, in the random oracle model, we can program a security reduction with a loss factor of at most $nq^{1/{n}}$, where $n$ can be any integer independent of the security parameter for the scheme construction and $q$ is the number of hash queries to random oracles. The loss factor in our reduction can be very small. Considering $n=25$ and $q=2^{50}$ as an example, the loss factor is of at most $nq^{1/{n}}=100$ and therefore our security reduction is tight. Notice that the previous impossibility results are derived from proofs via a so-called meta-reduction technique. We stress that instead of indicating any flaw in their meta-reduction proofs, our counterexample merely demonstrates that their given meta-reduction proofs fail to capture all security reductions. More precisely, we adopt a reduction called query-based reduction, where the reduction uses a hash query from the adversary to solve an underlying hard problem. We show that the meta-reduction proofs break down in our query-based reduction. The query-based reduction is not a new notion and it has been adopted for encryption proofs, but this work is the first seminal approach for applying query-based reduction in digital signatures. The given counterexample in this work is of an independent interest as it implies a generic way of constructing a digital signature scheme (including unique signatures) with a tight reduction in the random oracle model from a digital signature scheme with a loose reduction. Although our proposed methodology is somewhat impractical due to the inefficiency of signature length, it introduces a completely new approach for tight proofs that is different from traditional approaches using a random salt.

Summary Data search and sharing are two important functionalities in social networks. The social network users can form a peer‐to‐peer group and securely and flexibly search and share cloud data through wireless applications. When the number of users increases, the communication, storage, and computational overheads will be increased, and the quality of services such as searching and data sharing for clients could be affected. In order to solve these problems, we formalize an ID‐based multi‐user searchable encryption (IDB‐MUSE) and formally define its security model, where the security notions accommodate indistinguishability against insider's keyword guessing attack, indistinguishability against chosen keyword attack, and indistinguishability against insider's identity guessing attack. We present an IDB‐MUSE scheme, where the index and search trapdoor are of constant size. We formally prove its security properties. To improve the search efficiency, we divide the computation of the trapdoor into two phases, that is, the offline phase and the online phase. The computation cost for the online phase trapdoor remains constant with respect to the number of users. Based on the IDB‐MUSE scheme, a privacy‐preserving data search and sharing protocol is proposed, where only the authorized user can access the shared group data. It captures the properties of source authenticity, data and search pattern privacy‐preserving, anonymity, and request unlinkability. The experimental results show that the protocol is practical for wireless applications. Copyright © 2016 John Wiley & Sons, Ltd.

Leakage attacks, including various kinds of side-channel attacks, allow an attacker to learn partial information about the internal secrets such as the secret key and the randomness of a cryptographic system. Designing a strong, meaningful, yet achievable security notion to capture practical leakage attacks is one of the primary goals of leakage-resilient cryptography. In this work, we revisit the modelling and design of authenticated key exchange (AKE) protocols with leakage resilience. We show that the prior works on this topic are inadequate in capturing realistic leakage attacks. To close this research gap, we propose a new security notion named leakage-resilient eCK model w.r.t. auxiliary inputs ($\mathsf{AI\text{-}LR\text{-}eCK}$) for AKE protocols, which addresses the limitations of the previous models. Our model allows computationally hard-to-invert leakage of both the long-term secret key and the randomness, and also addresses a limitation existing in most of the previous models where the adversary is disallowed to make leakage queries during the challenge session. As another major contribution of this work, we present a generic framework for the construction of AKE protocols that are secure under the proposed $\mathsf{AI\text{-}LR\text{-}eCK}$ model. An instantiation based on the Decision Diffie-Hellman (DDH) assumption in the standard model is also given to demonstrate the feasibility of our proposed framework.

Smart grid is an electrical grid that uses digital information and communication technology to gather information. Like other digital systems, security and privacy are crucial for smart grid. However, security and privacy protection will inevitably introduce computational complexity and overhead. As smart grid systems are usually operated in a large scale, computational efficiency is a challenging issue. In this paper, we propose an efficient and secure billing system for smart grid, featuring privacy‐preserving and data aggregation. We show that our system offers better privacy protection and computational efficiency, in comparison with an existing protocol. Our security analysis indicates that our protocol achieves privacy‐preserving on electricity reading aggregation and billing, perfect forward secrecy of system session keys, identity authentication, data integrity, and confidentiality. It also shows that even if we allow the collusion of server and gateways, user privacy can still be achieved. Copyright © 2016 John Wiley & Sons, Ltd.

Motivated by the revelations of Edward Snowden, post-Snowden cryptography has become a prominent research direction in recent years. In Eurocrypt 2015, Mironov and Stephens-Davidowitz proposed a novel concept named cryptographic reverse firewall (CRF) which can resist exfiltration of secret information from an arbitrarily compromised machine. In this work, we continue this line of research and present generic CRF constructions for several widely used cryptographic protocols based on a new notion named malleable smooth projective hash function. Our contributions can be summarized as follows. We introduce the notion of malleable smooth projective hash function, which is an extension of the smooth projective hash function (SPHF) introduced by Cramer and Shoup (Eurocrypt'02) with the new properties of key malleability and element rerandomizability. We demonstrate the feasibility of our new notion using graded rings proposed by Benhamouda et al. (Crypto'13), and present an instantiation from the k-linear assumption. Moreover, we show that the malleable SPHF can also be based on other standard assumptions. We show how to generically construct CRFs via malleable SPHFs in a modular way for some widely used cryptographic protocols. Specifically, we propose generic constructions of CRFs for the unkeyed message-transmission protocol and the oblivious signature-based envelope (OSBE) protocol of Blazy, Pointcheval and Vergnaud (TCC'12). We also present a new malleable SPHFfrom the linear encryption of valid signatures for instantiating the OSBE protocol with CRFs. We further study the two-pass oblivious transfer (OT) protocol and show that the malleable SPHF does not suffice for its CRF constructions. We then develop a new OT framework from graded rings and show how to construct OT-CRFs by modifying the malleable SPHF framework. This new framework encompasses the DDH-based OT-CRF constructions proposed by Mironov and Stephens-Davidowitz (Eurocrypt'15), and yields a new construction under the $k$-linear assumption.

Searchable encryption is of increasing interest for protecting the data privacy in secure searchable cloud storage. In this paper, we investigate the security of a well-known cryptographic primitive, namely, public key encryption with keyword search (PEKS) which is very useful in many applications of cloud storage. Unfortunately, it has been shown that the traditional PEKS framework suffers from an inherent insecurity called inside keyword guessing attack (KGA) launched by the malicious server. To address this security vulnerability, we propose a new PEKS framework named dual-server PEKS (DS-PEKS). As another main contribution, we define a new variant of the smooth projective hash functions (SPHFs) referred to as linear and homomorphic SPHF (LH-SPHF). We then show a generic construction of secure DS-PEKS from LH-SPHF. To illustrate the feasibility of our new framework, we provide an efficient instantiation of the general framework from a Decision Diffie-Hellman-based LH-SPHF and show that it can achieve the strong security against inside the KGA.

The indistinguishability security of a public-key cryptosystem can be reduced to a computational hard assumption in the random oracle model, where the solution to a computational hard problem is hidden in one of the adversary's queries to the random oracle. Usually, there is a finding loss in finding the correct solution from the query set, especially when the decisional variant of the computational problem is also hard. The problem of finding loss must be addressed towards tight(er) reductions under this type. In EUROCRYPT 2008, Cash, Kiltz and Shoup proposed a novel approach using a trapdoor test that can solve the finding loss problem. The simulator can find the correct solution with overwhelming probability 1, if there exists a trapdoor test for the adopted hard problem. The proposed approach is efficient and can be used for many Diffie-Hellman computational assumptions. The only limitation is the requirement of a trapdoor test that must be found for the adopted computational assumptions. In this paper, we introduce a universal approach for finding loss, namely Iterated Random Oracle, which can be applied to all computational assumptions. The finding loss in our proposed approach is very small. For $2^{60}$ queries to the random oracle, the success probability of finding the correct solution from the query set will be as large as $1/{64}$ compared to $1/{2^{60}}$ by a random pick. We show how to apply the iterated random oracle for security transformation from key encapsulation mechanism with one-way security to normal encryption with indistinguishability security. The security reduction is very tight due to a small finding loss. The transformation does not expand the ciphertext size. We also give the application of the iterated random oracle in the key exchange.

With the widely adopted GPS technology in mobile devices, users enjoy many types of location services. As a recently proposed application, determining the optimal private meeting location with an aid of a location server has been an interesting research topic. The challenge in this paper is due to the requirements of security and privacy, because user locations should not be revealed to the honest-but-curious or semi-trusted location server. Adding the security and privacy protection to a location service will inevitably introduce computational complexity and communication overhead. In order to introduce robust location service and make this location service practical, we propose an efficient optimal private meeting location determination protocol, which needs only one round communication and light computation. Our proposed protocol satisfies the requirement of location privacy against outsiders, the semi-trusted meeting location determination server, and the semi-trusted group users. In order to study the performance of our protocol in a real deployment, we simulate our scheme on smartphones. The simulation results and the performance comparison with another scheme demonstrate its advantages in communication and computation efficiency.

In this paper, we present the notion of recipient-revocable identity-based broadcast encryption scheme. In this notion, a content provider will produce encrypted content and send them to a third party (which is a broadcaster). This third party will be able to revoke some identities from the ciphertext. We present a security model to capture these requirements, as well as a concrete construction. The ciphertext consists of k+3 group elements, assuming that the maximum number of revocation identities is k. That is, the ciphertext size is linear in the maximal size of R, where R is the revocation identity set. However, we say that the additional elements compared to that from an IBBE scheme are only for the revocation but not for decryption. Therefore, the ciphertext sent to the users for decryption will be of constant size (i.e.,3 group elements). Finally, we present the proof of security of our construction.

Public key encryption with keyword search (PEKS) is a well-known cryptographic primitive for secure searchable data encryption in cloud storage. Unfortunately, it is inherently subject to the (inside) offline keyword guessing attack (KGA), which is against the data privacy of users. Existing countermeasures for dealing with this security issue mainly suffer from low efficiency and are impractical for real applications. In this paper, we provide a practical and applicable treatment on this security vulnerability by formalizing a new PEKS system named server-aided public key encryption with keyword search (SA-PEKS). In SA-PEKS, to generate the keyword ciphertext/trapdoor, the user needs to query a semitrusted third-party called keyword server (KS) by running an authentication protocol, and hence, security against the offline KGA can be obtained. We then introduce a universal transformation from any PEKS scheme to a secure SA-PEKS scheme using the deterministic blind signature. To illustrate its feasibility, we present the first instantiation of SA-PEKS scheme by utilizing the Full Domain Hash RSA signature and the PEKS scheme proposed by Boneh et al. in Eurocrypt 2004. Finally, we describe how to securely implement the client-KS protocol with a rate-limiting mechanism against online KGA and evaluate the performance of our solutions in experiments.

Authenticated Key Exchange (AKE) protocols have been widely deployed in many real-world applications for securing communication channels. In this paper, we make the following contributions. First, we revisit the security modelling of leakage-resilient AKE protocols, and show that the existing models either impose some unnatural restrictions or do not sufficiently capture leakage attacks in reality. We then introduce a new strong yet meaningful security model, named challenge-dependent leakage-resilient eCK (CLR-eCK) model, to capture challenge-dependent leakage attacks on both long-term secret key and ephemeral secret key (i.e., randomness). Second, we propose a general framework for constructing one-round CLR-eCK-secure AKE protocols based on smooth projective hash functions (SPHFs). This framework ensures the session key is private and authentic even if the adversary learns a large fraction of both long-term secret key and ephemeral secret key, and hence provides stronger security guarantee than existing AKE protocols which become insecure if the adversary can perform leakage attacks during the execution of a session. Finally, we also present a practical instantiation of the general framework based on the Decisional Diffie-Hellman assumption without random oracle. Our result shows that the instantiation is efficient in terms of the communication and computation overhead and captures more general leakage attacks.

Deduplication is a popular technique widely used to save storage spaces in the cloud. To achieve secure deduplication of encrypted files, Bellare et al. formalized a new cryptographic primitive named message-locked encryption (MLE) in Eurocrypt 2013. Although an MLE scheme can be extended to obtain secure deduplication for large files, it requires a lot of metadata maintained by the end user and the cloud server. In this paper, we propose a new approach to achieve more efficient deduplication for (encrypted) large files. Our approach, named block-level message-locked encryption (BL-MLE), can achieve file-level and block-level deduplication, block key management, and proof of ownership simultaneously using a small set of metadata. We also show that our BL-MLE scheme can be easily extended to support proof of storage, which makes it multi-purpose for secure cloud storage.