Abstract Authenticated private information retrieval (APIR) is the state-of-the-art error-detecting private information retrieval (ED-PIR), using Distributed Point Functions (DPFs) for subpolynomial complexity and privacy. However, its finite field structure restricts it to prime-order DPFs, leading to prohibitively large key sizes under information-theoretic settings, while its dual-DPF-key design introduces unnecessary communication overhead, limiting its practicality for large-scale deployments. This paper proposes a novel ring-based information-theoretic ED-PIR (itED-PIR) scheme that overcomes these limitations by leveraging prime-power-order information-theoretic DPFs (itDPFs). Built over a prime-power ring, the proposed scheme breaks APIR’s field-induced constraint to enable more efficient DPF utilization, significantly reducing key size growth and rendering the scheme feasible for high-security scenarios. Additionally, a single-itDPF-key design halves query-side communication overhead by eliminating APIR’s redundant dual-key setup, without compromising privacy or verifiability. Beyond immediate efficiency gains, this work establishes a lightweight, flexible framework for constructing DPF-based malicious-resilient private information retrieval, opening new avenues for privacy-preserving data retrieval in distributed storage systems and post-quantum privacy protocols.

Revocable ring signatures protect signer anonymity. A trusted authority can revoke signing rights when necessary. This makes them attractive for blockchains and vehicular networks. Existing lattice-based ring signature schemes are only traceable. They can de-anonymize a malicious signer, yet fail to stop the revoked signer from creating a valid signature. This contradicts the very notion of revocation. We introduce a polynomial-based revocation list. It is enforced with non-interactive zero-knowledge proofs of knowledge. Our protocol implicitly verifies the up-to-date revocation list during signature generation. Consequently, revoked signers cannot authenticate and are effectively excluded. Integrating this mechanism into a lattice setting, we obtain a compact revocable ring signature. The scheme is correct, anonymous, unforgeable, and truly revocable under the random oracle model. No costly key updates are required. Compared with prior trace-and-update schemes, our construction offers a practical post-quantum primitive. It guarantees both privacy and accountable revocation. Overhead analysis shows that we have added very little cost while ensuring true revocation.

Data deduplication contributes to avoiding great waste of cloud storage resources. Most of current data deduplication schemes focus on file-level data deduplication, without realizing deduplication ownership privacy protection, data blocks retrieval or error data blocks recovery. To this end, this paper proposes cross-clouds encrypted data fine-grained deduplication and recovery (CC-FGDR) scheme supporting blockchain collaborative computing. CC-FGDR exploits two-party joint generation of deduplication tags to prevent deduplication privacy leakage, and constructs vector-commitment ciphertext tree to realize proofs of ownership verification of distributed backup data blocks via blockchain systems. CC-FGDR achieves secure cross-clouds deduplication detection by constructing twin bloom filter tree and privacy puncture pseudo-random function. To achieve data availability, a ciphertext reconstruction matrix is introduced and combined with countable bloom filter to achieve the location, search and retrieval of distributed outsourced data blocks. CC-FGDR further designs low-density parity check code to achieve cross-clouds encrypted error data recovery through collaborative computing of smart contracts. The security analysis demonstrates CC-FGDR ensures data storage verifiability, data confidentiality, and ownership privacy protection. Performance evaluation demonstrates the feasibility of CC-FGDR in the deployment of multiple clouds via blockchain systems, and CC-FGDR significantly improves the deduplication efficiency by joint deduplication in multi-clouds.

With the growing demand for outsourcing data to decentralized storage systems, ensuring the integrity of out-sourced data becomes a critical challenge. Existing auditing schemes, however, often assume single-copy or centralized models, and suffer from inefficiency, lack of public verifiability, or poor scalability in multi-replica settings. To address these limitations, we propose MPA, a lightweight and publicly verifiable auditing scheme tailored for multi-copy cloud storage. By integrating polynomial commitment schemes with Merkle trees, our design achieves efficient block-level integrity verification while enabling dynamic updates. To mitigate collusion between cloud service providers, each data copy is uniquely encrypted, and the audit process supports simultaneous verification across multiple providers. Furthermore, we introduce an optimized batch auditing mechanism that allows the verifier to aggregate proofs across different files and providers, reducing both computation and communication overhead. To enhance audit transparency and unpredictability, we adopt a blockchain-assisted challenge generation protocol based on commit-and-reveal randomness. Theoretical analysis and performance evaluation demonstrate that MPA achieves strong security guarantees under standard assumptions, while significantly outperforming existing solutions in terms of efficiency and scalability.

Internet of Vehicles (IoV) requires robust security and privacy protection mechanisms to enable trusted traffic information exchange, while also requiring low communication and low computing overhead to meet the real-time requirements of IoV. Existing signcryption schemes suffer from quantum vulnerability, inadequate unlinkability/vehicle anonymity, absence of revocability, poor scalability, inadequate management of malicious entities, and high communication and computational overhead. So we propose an efficient lattice-based conditional privacy-preserving multi-receiver signcryption scheme (LCMS) that systematically addresses these gaps through three core innovations: 1) Privacy preservation is achieved via a pseudonym mechanism integrated with certificateless key generation, which ensures vehicle anonymity and weak unlinkability while preventing malicious key generation center and key escrow; 2) Malicious entity management through dynamic revocability and distributed decryption among roadside units, preventing unilateral message access; and 3) Post-quantum efficiency is achieved by leveraging the Learning With Rounding problem to eliminate expensive Gaussian sampling, combined with ciphertext packing techniques. This reduces time overhead, the size of signcryptexts, and communication overhead, while lowering the overall storage overhead of the scheme through the MP12 trapdoor. Security proofs show LCMS achieves Existential Unforgeability under Adaptive Identity Chosen-Message Attack and Indistinguishability under Adaptive Identity ChosenCiphertext Attack in the Random Oracle Model, with rigorously validated resistance against multiple IoV -specific attacks. Experimental results via SageMath implementation demonstrate that our scheme exhibits a smaller signcryptext size and lower signcryption/unsigncryption time compared to existing random lattice-based signcryption schemes. Scalability tests with 300 vehicles and 300 roadside units (RSUs) were completed within 56 seconds. Communication overhead analysis confirms practical feasibility for IEEE 802.11p vehicle communication protocol, and RSU serving capability evaluation under realistic vehicle density (100-200km2) and speed (40-60km/h) further validates system practicality. LCMS provides a quantum.

Dynamic Searchable Symmetric Encryption (DSSE) plays a crucial role in secure cloud-based database systems, as it enables efficient keyword search and dynamic updates over encrypted data. However, practical deployment of DSSE schemes faces two significant challenges. First, clients may inadvertently perform faulty updates—such as re-adding an existing keyword-identifier pair or attempting to delete a non-existent one—which can compromise the correctness of subsequent search results. Second, even with correctly issued updates, malicious servers may return incorrect or incomplete search results, undermining data integrity. To address these challenges, we propose FVDSSE, the first fault-tolerant DSSE scheme that tolerates client-side operational faults and provides result verifiability against malicious servers. Moreover, it simultaneously ensures strong privacy by guaranteeing forward and backward privacy—two essential properties for any practical DSSE. To further optimize performance, we present FVDSSE-C, an enhanced variant that leverages caching techniques. Experimental evaluations on a real-world dataset show that FVDSSE-C achieves up to 130× improvement in search efficiency and 3× reduction in communication overhead compared to the state-of-the-art scheme (YCR22-C).

To enhance the reliability and credibility of graph neural networks (GNNs) and improve the transparency of their decision logic, a new field of explainability of GNNs (XGNN) has emerged. However, two major limitations severely degrade the performance and hinder the generalizability of existing XGNN methods: they (a) fail to capture the complete decision logic of GNNs across diverse distributions in the entire dataset's sample space, and (b) impose strict prerequisites on edge properties and GNN internal accessibility. To address these limitations, we propose OPEN, a novel cOmprehensive and Prerequisite-free Explainer for GNNs. OPEN, as the first work in the literature, can infer and partition the entire dataset's sample space into multiple environments, each containing graphs that follow a distinct distribution. OPEN further learns the decision logic of GNNs across different distributions by sampling subgraphs from each environment and analyzing their predictions, thus eliminating the need for strict prerequisites. Experimental results demonstrate that OPEN captures nearly complete decision logic of GNNs, outperforms state-of-the-art methods in fidelity while maintaining similar efficiency, and enhances robustness in real-world scenarios.

Cross-domain fake news detection aims to mitigate domain shift and improve detection performance by transferring knowledge across domains. Existing approaches transfer knowledge based on news content and user engagements from a source domain to a target domain. However, these approaches face two main limitations, hindering effective knowledge transfer and optimal fake news detection performance. Firstly, from a micro perspective, they neglect the negative impact of veracity-irrelevant features in news content when transferring domain-shared features across domains. Secondly, from a macro perspective, existing approaches ignore the relationship between user engagement and news content, which reveals shared behaviors of common users across domains and can facilitate more effective knowledge transfer. To address these limitations, we propose a novel macro- and micro- hierarchical transfer learning framework (MMHT) for cross-domain fake news detection. Firstly, we propose a micro-hierarchical disentangling module to disentangle veracity-relevant and veracity-irrelevant features from news content in the source domain for improving fake news detection performance in the target domain. Secondly, we propose a macro-hierarchical transfer learning module to generate engagement features based on common users' shared behaviors in different domains for improving effectiveness of knowledge transfer. Extensive experiments on real-world datasets demonstrate that our framework significantly outperforms the state-of-the-art baselines.

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

Verifiable data streaming (VDS) enables the client to incrementally store a sequence of ordered data on an untrusted cloud server, and verify the validity of the retrieved data. Moreover, the client can replace a data with another value. The common security problem caused by updating operation is the cloud server may use old authentication information to make expired data pass the verification. To solve this problem, the known approaches use the cryptographic accumulator that actually influences the performance of VDS scheme. The main concerns can be generalized as how to design a VDS scheme without cryptographic accumulator, in such a way that further optimizes the performance of VDS scheme. We put forward the idea to convert the standard digital signature relevant to the updated data into chameleon digital signature whose non-transferability is the key to solve the problem. This is the first attempt to securely authenticate the dynamic data without cryptographic accumulator. In the proposed VDS scheme, the client's local storage overhead, computation overheads of the cloud server in responding to a query and updating the data are constant. As the experimental results shown, the proposed VDS scheme outperforms the scheme in terms of the efficiency.

Federated learning, as a solution to address the increasingly severe data isolation problem, holds great promise. However, it faces two significant security challenges: how to ensure the data privacy of participants and how to guarantee the correctness of the aggregation results. In addition, existing secure federated learning schemes have their limitations and drawbacks. Some schemes cannot handle participant dropouts, and others do not consider the privacy of the global model. Moreover, they all rely on a trusted authority, resulting in impracticality. To address these challenges, we introduce TSVFL, a two-server verifiable and privacy-preserving federated learning scheme. It tolerates participant dropouts during the training process and enables secure federated learning model training without needing a trusted authority. Comprehensive security analysis demonstrates that TSVFL effectively protects the data privacy of participants against various potential inference attacks and ensures training integrity. Furthermore, extensive experiments on real-world datasets confirm that TSVFL achieves lossless accuracy and practical performance.

Transfer of knowledge across domains is the focus for cross-domain and multi-domain fake news detection. However, most of the existing methods based on cross-domain knowledge transfer have two issues: (1) they usually ignore domain-specific features; (2) they are less effective in handling the imbalanced data distribution across domains. Targeting these two issues, we focus on how to effectively leverage user-news engagements in both data-richer and data-sparser domains. This is because not only users' engagement characteristics closely relate to the veracity of the engaged news, but also there are consistent patterns in common users' engagements with news across domains. Considering these two insights, this work aims to perform dual-target cross-domain fake news detection via well modeling users' engagement patterns. In particular, it aims to transfer knowledge based on user-news engagements for handling the imbalanced data distribution across domains, which is novel but challenging. To this end, in this paper, we propose a novel framework to mine User-news engagement Patterns for DuAl-TargEt cross-domain fake news detection (UPDATE). In UPDATE, we first mine user-news engagement patterns as the key auxiliary information for cross-domain knowledge transfer. In such a way, it avoids the necessity to remove the domain-specific news information, and thereby, better preserve useful news information. Then, we combine engagement features of common users in both data-richer and data-sparser domains. By doing so, UPDATE improves the information richness in each of the two domains, thus improving detection performance in both domains when detecting news from domains with imbalanced data distribution. Extensive experiments conducted on real-world datasets demonstrate that UPDATE significantly outperforms state-of-the-art cross-domain and multi-domain methods as well as large language models (LLMs), such as GPT-3.5-turbo in terms of AUC and Fl-score for fake news detection.

Internet of Medical Things (IoMTs) is revolutionizing the healthcare industry regarding how diagnosis process takes place, how treatment is provided, and how public health policies are made. A real-world use case of IoMTs is to investigate how infectious diseases, e.g. COVID-19, spread in a population through social events. In this use case, people’s social contact records in certain venues are collected by sensors and saved locally; pandemic modellers, as third-party vendors, are desired to construct social contact network based on contacts records, and to simulate the process of disease transmission over the contact network by transmission modelling; results from the simulation will be provided to authorities for policymaking and pandemic control. However, concerns are raised on data breaches from modellers. In reality, sharing the data in clear with modellers is not allowed by regulations for the sake of privacy. In this work, we will be addressing the contradiction between data privacy and usability when vendors are involved in IoMTs. We propose a secure cloud-edge computing architecture based on an efficient fully homomorphic encryption (FHE) scheme. This architecture allows vendors to securely and “blindly” process medical data without compromising the quality of their service. Moreover, we apply the proposed architecture to the use case of pandemic modelling. By comparisons with a differential privacy-based solution, we demonstrate the favorable feasibility, accuracy and security of the proposed solution.

Due to enormous computing and storage overhead for well-trained Deep Neural Network (DNN) models, protecting the intellectual property of model owners is a pressing need. As the commercialization of deep models is becoming increasingly popular, the pre-trained models delivered to users may suffer from being illegally copied, redistributed, or abused. In this paper, we propose DeepDIST, the first end-to-end secure DNNs distribution framework in a black-box scenario. Specifically, our framework adopts a dual-level fingerprint (FP) mechanism to provide reliable ownership verification, and proposes two equivalent transformations that can resist collusion attacks, plus a newly designed similarity loss term to improve the security of the transformations. Unlike the existing passive defense schemes that detect colluding participants, we introduce an active defense strategy, namely damaging the performance of the model after the malicious collusion. The extensive experimental results show that DeepDIST can maintain the accuracy of the host DNN after embedding fingerprint conducted for true traitor tracing, and is robust against several popular model modifications. Furthermore, the anti-collusion effect is evaluated on two typical classification tasks (10-class and 100-class), and the proposed DeepDIST can drop the prediction accuracy of the collusion model to 10% and 1% (random guess), respectively.

AI-as-a-Service has emerged as an important trend for supporting the growth of the digital economy. Digital service providers make use of their vast amount of customer data to train AI models (such as image recognition, financial modelling and pandemic modelling etc) and offer them as a service on the cloud. While there are convincing advantages for using such third-party models, the fact that model users are required to upload their data to the cloud is bound to raise serious privacy concerns, especially in the face of increasingly stringent privacy regulations and legislation. To promote the adoption of AI-as-a-Service while addressing privacy issues, we propose a practical approach for constructing privacy-enhanced neural networks by designing an efficient implementation of fully homomorphic encryption. With this approach, an existing neural network can be converted to process FHE-encrypted data and produce encrypted output which are only accessible by the model users, and more importantly, within an operationally acceptable time (e.g. within 1 second for facial recognition in typical border control systems). Experimental results show that in many practical tasks such as facial recognition, text classification and so on, we obtained the state-of-the-art inference accuracy in less than one second on a 16 cores CPU.

Keyword-based search over encrypted data is an important technique to achieve both data confidentiality and utilization in cloud outsourcing services. While commonly used access control mechanisms, such as identity-based encryption and attribute-based encryption, do not generally scale well for hierarchical access permissions. To solve this problem, we propose a Role-based Encrypted Keyword Search (REKS) scheme by using the role-based access control and broadcast encryption. Specifically, REKS allows owners to deploy hierarchical access control by allowing users with parent roles to have access permissions from child roles. Using REKS, we further facilitate token generation preprocessing and efficient user management, thereby significantly reducing the users' final token generation and index update overheads, respectively. Formal security analysis proves that REKS is secure against chosen keyword and internal keyword guessing attacks, and findings from the empirical evaluations demonstrate that REKS is efficient and practical.

Multi-party computation (MPC) allows parties to interact with cloud-based data and services while maintaining privacy and confidentiality of their private data. As a special case of MPC, private set intersection (PSI) protocols focus on securely computing the intersection between a server and a client of their private set. Our research extends the threshold functionality for PSI within the realm of cloud computing, where the server possesses a larger set than the client. This paper fills this gap by proposing new private intersection cardinality (PSI-CA) protocol, and more broadly, threshold private set intersection (tPSI) protocol using fully homomorphic encryption (FHE). In tPSI protocol, two parties holding two private sets collaboratively compute the intersection and reveal the result if and only if the size of the intersection exceeds some predefined threshold. In this process, no other information, in particular, elements not in the intersection remain hidden. The problem of PSI-CA and tPSI has many applications in online collaboration,e.g., fingerprint matching, online dating, and ride sharing. At a high level, we use FHE to encrypt a Bloom filter (BF) that encodes the small set and homomorphically check whether the elements in the larger set belongs to the small set,e.g., homomorphic membership test. Counting the number of positive membership directly already yields a PSI-CA protocol with optimal asymptotic communication complexity Ω(n) = Ω(min(N,n)), whereN(resp.n) is the size of the large (resp. small) set. To construct a tPSI protocol, we develop a novel secret token generation protocol: a shared secret token is generated if and only if the intersection size satisfies the threshold condition, by exploiting the programmable bootstrapping technique in FHE. This new secret token generation protocol, when composed with any standard PSI protocol, yields a tPSI with the same asymptotic communication complexity as the chosen plain PSI. Along the way, we develop specific FHE optimizations that might be of independent interest. These optimizations overcome the weakness of low precision in programmable bootstrapping. As a result, tPSI over relatively large sets can be supported.

Private Information Retrieval (PIR) protocols allow a client to retrieve any file of interest while keeping the files identity hidden from the database servers. While many existing PIR protocols assume servers to be honest but curious, we investigate the scenario of dishonest servers that provide incorrect answers to mislead clients into obtaining wrong results. We propose a unified framework for polynomial PIR protocols encompassing various existing protocols that optimize the download rate or total communication cost. We introduce a way to transform a polynomial PIR to a verifiable one without increasing the number of involved servers by doubling the queries. The security guarantees can be information-theoretic or computational, and the verification keys can be public or private. Moreover, in one of our protocols, the ratio between the additional download overhead associated with verification and the normal download cost approaches zero as the file size goes to infinity.

Motivated by applications in distributed storage, distributed computing, and homomorphic secret sharing, we study communication-efficient schemes for computing linear combinations of coded symbols. Specifically, we design low-bandwidth schemes that evaluate the weighted sum of ℓ coded symbols in a codewordc∈ Fn, when we are given access todof the remaining components inc. Formally, suppose that F is a field extension of B of degreet. Letcbe a codeword in a Reed-Solomon code of dimensionkand our task is to compute the weighted sum of ℓ coded symbols. In this paper, for somest, we provide an explicit scheme that performs this task by downloadingd(t-s) sub-symbols in B fromdavailable nodes, wheneverd≥ ℓ|B|s-ℓ +k. In many cases, our scheme outperforms previous schemes in the literature. Furthermore, we provide a characterization of evaluation schemes for general linear codes. Then in the special case of Reed-Solomon codes, we use this characterization to derive a lower bound for the evaluation bandwidth.

Cloud computing has become prevalent due to its extensive storage resources and robust computational capacities. To protect data security and privacy, data owners opt for uploading encrypted data to the cloud. Flexible sharing of these encrypted data in a group of users is a critical functionality in cloud storage. In addition, given that users may exit the group, revocation becomes a crucial requirement in group data-sharing systems. The Key-Aggregate Cryptosystem (KAC) has become a promising mechanism for group data sharing. The decryption rights for any set of ciphertexts can be efficiently delegated by distributing a constant-size aggregate key, while the confidentiality of other ciphertexts outside the set is maintained. However, in previous KAC schemes, revocation remains a challenging task regarding key update, ciphertext re-encryption, and collision resistance. In this paper, we propose a Key-Aggregate Cryptosystem with User Revocation (KAC-UR) scheme to overcome this challenge. The KAC-UR scheme not only achieves flexible data sharing, but also can perform secure and efficient user revocation with properties including collision resistance, revocation without data owner-user communication, and constant ciphertext size. The KAC-UR scheme also enables the cloud server to perform partial decryption, thereby significantly alleviating the computational burden for users. The KAC-UR scheme is chosen plaintext attack secure under the decisional Bilinear Diffie-Hellman Exponent assumption.

Motivated by applications in distributed storage, distributed computing, and homomorphic secret sharing, we study communication-efficient schemes for computing linear combinations of coded symbols. Specifically, we design low-bandwidth schemes that evaluate the weighted sum of ℓ coded symbols in a codeword ${\mathbf{c}} \in {\mathbb{F}^n}$, when we are given access to d of the remaining components in c. Formally, suppose that $\mathbb{F}$ is a field extension of $\mathbb{B}$ of degree t. Let c be a codeword in a Reed-Solomon code of dimension k and our task is to compute the weighted sum of ℓ coded symbols. In this paper, for some s < t, we provide an explicit scheme that performs this task by downloading d(t − s) sub-symbols in $\mathbb{B}$ from d available nodes, whenever $d \geq \ell |\mathbb{B}{|^s} - \ell + k$. In many cases, our scheme outperforms previous schemes in the literature. Furthermore, we provide a characterization of evaluation schemes for general linear codes. Then in the special case of Reed-Solomon codes, we use this characterization to derive a lower bound for the evaluation bandwidth.

Private Information Retrieval (PIR) schemes allow a client to retrieve any file of interest, while hiding the file identity from the database servers. In contrast to most existing PIR schemes that assume honest-but-curious servers, we study the case of dishonest servers. The latter provide incorrect answers and try to persuade the client to output the wrong result. We introduce several PIR schemes with information-theoretic privacy and result verification for the case of two servers. Security guarantees can be information-theoretical or computational, and the verification keys can be public or private. In this work, our main performance metric is the download rate.

We consider the problem of designing a Private Information Retrieval (PIR) scheme on m files replicated on k servers that can collude or, even worse, can return incorrect answers. Our goal is to correctly retrieve a specific message while keeping its identity private from the database servers. We consider the asymptotic information-theoretic capacity of this problem defined as the maximum ratio of the number of correctly retrieved symbols to the downloaded one for a large enough number of stored files. We propose an achievable scheme with a small file size and prove that such a file size is minimal for the fixed number of retrieved symbols, solving the problem pointed out by Banawan and Ulukus.A full version [1] of this paper is accessible at: https://arxiv.org/abs/2302.02230

We consider the repair scheme of Guruswami-Wootters for the Reed-Solomon code and ask: can we correctly repair a failed node in the presence of erroneous nodes? Equivalently, we consider the collection of downloaded traces as a code and investigate its code-distance properties. We propose three lower bounds on its minimum distance and study methods to efficiently correct errors close to these bounds.

Abstract Homomorphic Encryption (HE) supports computation on encrypted data without the need to decrypt, enabling secure outsourcing of computing to an untrusted cloud. Motivated by application scenarios where private information is offered by different data owners, Multi-Key Homomorphic Encryption (MKHE) and Threshold Homomorphic Encryption (ThHE) were proposed. Unlike MKHE, ThHE schemes do not require expensive ciphertext extension procedures and are therefore as efficient as their underlying single-key HE schemes. In this work, we propose a novel NTRU-type ThHE scheme which caters to the computation scenarios with pre-defined participants. In addition to inheriting the simplicity of NTRU scheme, our construction has no expensive relinearization and correspondingly no costly evaluation keys. Controlling noise to make it increase linearly and then using a wide key distribution, our scheme is immune to the subfield lattice attacks and its security follows from the hardness of the standard R-LWE problem. Finally, based on the {0,1}-linear secret sharing and noise flooding techniques, we design a single round distributed threshold decryption protocol, where the decryption is able to be completed even when only given a subset (say $t$-out-of-$k$) of partial decryptions. To the best of our knowledge, our construction is the first NTRU-type ThHE scheme.

Abstract An accumulator is a function that hashes a set of inputs into a short, constant-size string while preserving the ability to efficiently prove the inclusion of a specific input element in the hashed set. It has proved useful in the design of numerous privacy-enhancing protocols, in order to handle revocation or simply prove set membership. In the lattice setting, currently known instantiations of the primitive are based on Merkle trees, which do not interact well with zero-knowledge proofs. In order to efficiently prove the membership of some element in a zero-knowledge manner, the prover has to demonstrate knowledge of a hash chain without revealing it, which is not known to be efficiently possible under well-studied hardness assumptions. In this paper, we provide an efficient method of proving such statements using involved extensions of Stern’s protocol. Under the Small Integer Solution assumption, we provide zero-knowledge arguments showing possession of a hash chain. As an application, we describe new lattice-based group and ring signatures in the random oracle model. In particular, we obtain: (i) the first lattice-based ring signatures with logarithmic size in the cardinality of the ring and (ii) the first lattice-based group signature that does not require any GPV trapdoor and thus allows for a much more efficient choice of parameters.

In this paper, we investigate the practical performance of rank-code based cryptography on FPGA platforms by presenting a case study on the quantum-safe KEM scheme based on LRPC codes called ROLLO, which was among NIST post-quantum cryptography standardization round-2 candidates. Specifically, we present an FPGA implementation of the encapsulation and decapsulation operations of the ROLLO KEM scheme with some variations to the original specification. The design is fully parameterized, using code-generation scripts to support a wide range of parameter choices for security levels specified in ROLLO. At the core of the ROLLO hardware, we presented a generic approach for hardware-based Gaussian elimination, which can process both non-singular and singular matrices. Previous works on hardware-based Gaussian elimination can only process non-singular ones. However, a plethora of cryptosystems, for instance, quantum-safe key encapsulation mechanisms based on rank-metric codes, ROLLO and RQC, which are among NIST post-quantum cryptography standardization round-2 candidates, require performing Gaussian elimination for random matrices regardless of the singularity. To the best of our knowledge, this work is the first hardware implementation for rank-code-based cryptographic schemes. The experimental results suggest rank-code-based schemes can be highly efficient.

The rapid growth of the blockchain size is a major bottleneck hindering its implementations in data-heavy applications. Current efforts improve the distributed storage ways and transactions' storage mechanisms of blockchain, however, the blockchain distribution and integrity are destroyed. Simplified Payment Verification (SPV) is closely related to blockchain storage, but the current solutions did not explore the privacy-preserving SPV. In this paper, we propose a new storage structure for blockchain transactions, called Coloring Index (CI), to reduce the blockchain's space occupation. Specifically, we devise an index building algorithm to simply calculate the indices of transactions for the sake of information concealing. By improving the Coloring Embedder for multi-sets query, we can store the indices into the Coloring Embedder to achieve the structured storage of transactions with small space occupation. Using CI, SPV query proceeds without revealing the user's address, thereby achieving secure data sharing in applications such as the intelligent vehicles' communications and distributed IoT. We prove CI's security against malicious full nodes when establishing possible connections between the address and the user. The experiments show that blockchain systems using our CI store one time more transactions than Merkle tree and half more than Bloom filter.

The surging interest in cryptocurrency has revitalized the research for digital signature schemes with strong security. In particular, signature schemes are investigated to resist the malleability attacks in cryptocurrency platforms. However, existing signature schemes only conquer partial malleability attacks due to various sources of attacks. Other solutions of new transaction realizations cannot simultaneously avoid the malleability attacks on both standard and contract transactions. Furthermore, the malleability attack becomes more stubborn in fast clearing applications. In this paper, we propose SigNT, an accessional signature scheme with unmalleable transaction implementations. The key of SigNT is an improved interactive signature scheme for securely instant confirmation of transactions. Unlike standard signatures, this signature is generated by the owner and block producers. Combining it with several other optimizations (i.e., hash execution of intermediate transactions and secret-based claiming conditions), SigNT achieves complete resistance against malleability attacks in both the standard and contract transactions. As an example, we show an implementation in Bitcoin with the “providing a deposit” protocol. The security analysis and comparative experiments demonstrate that SigNT has the best resistance against malleability attacks than previous malleability solutions. Besides, better performance is achieved than other schemes.

The Modular Inversion Hidden Number Problem (MIHNP), which was proposed at Asiacrypt 2001 by Boneh, Halevi, and Howgrave-Graham, is summarized as follows: Assume that the$\delta $most significant bits of$z$are denoted by${\mathrm {MSB}}_{\delta }(z)$. The goal is to retrieve the hidden number$\alpha \in \mathbb {Z}_{p}$given many samples$\left ({t_{i}, {\mathrm {MSB}}_{\delta }((\alpha + t_{i})^{-1} \bmod {p})}\right)$for random$t_{i} \in \mathbb {Z}_{p}$. MIHNP is a significant subset of Hidden Number Problems. Eichenauer and Lehn introduced the Inversive Congruential Generator (ICG) in 1986. It is basically characterized as follows: For iterated relations$v_{i+1}=(av^{-1}_{i}+b)\bmod {p}$with a secret seed$v_{0} \in \mathbb {Z}_{p}$, each iteration produces$\mathrm {MSB}_{\delta }(v_{i+1})$where$i \geq 0$. The ICG family of pseudorandom number generators is a significant subclass of number-theoretic pseudorandom number generators. Sakai-Kasahara scheme is an identity-based encryption (IBE) system proposed by Sakai and Kasahara. It is one of the few commercially implemented identity-based encryption schemes. We explore the Coppersmith approach for solving a class of modular polynomial equations, which is derived from the recovery issue for the hidden number$\alpha $in MIHNP and the secret seed$v_{0}$in ICG, respectively. Take a positive integer$n=d^{3+o(1)}$for some positive integer constant$d$. We propose a heuristic technique for recovering the hidden number$\alpha $or secret seed$v_{0}$with a probability close to 1 when$\delta /\log _{2} p>\frac {1}{d+1}+o\left({\frac {1}{d}}\right)$. The attack’s total time complexity is polynomial in the order of$\log _{2} p$, with the complexity of the LLL algorithm increasing as$d^{\mathcal {O}(d)}$and the complexity of the Gröbner basis computation increasing as$d^{\mathcal {O}(n)}$. When$d> 2$, this asymptotic bound surpasses the asymptotic bound$\delta /\log _{2} p>\frac {1}{3}$established by Boneh, Halevi, and Howgrave-Graham at Asiacrypt 2001. This is the first time a more precise constraint for solving MIHNP is established, implying that the claim that MIHNP is difficult is violated whenever$\delta /\log _{2} p < \frac {1}{3}$. Then we study ICG. To our knowledge, we achieve the best performance for attacking ICG to date. Finally, we provide an MIHNP-based lattice approach that recovers the signer’s secret key in the Sakai-Kasahara type signatures when the most (least) significant bits of the signing exponents are exposed. This improves the existing work in this direction.

Cloud computing technologies rely on powerful storage services to maintain massive data for users. Sensitive data are encrypted before outsourcing, but this limits the availability of data. Public-key encryption with keyword search (PEKS) contributes to searching target encrypted data with keywords. However, existing PEKS mechanisms require to manage certificates, they are also vulnerable to adversaries equipped with quantum-computing devices. In this paper, we devise a biometric identity-based multi-keyword search (BIB-MKS) mechanism from lattices over encrypted outsourced data, which inherently resists quantum-computing attacks. Each user in BIB-MKS is identified with her/his biometric information, which could be envisioned as the public key, thereby avoiding complex certificate managements. Particularly, BIB-MKS enables a data owner to produce an index associated with a biometric identity$BID'$, such that a user with a biometric identity$BID$issues multiple keywords in a single search query and retrieves corresponding encrypted data, if and only if$BID$and$BID'$are within a certain distance of each other as judged by some metric. BIB-MKS narrows down the search scope, and improves users search experience significantly. We define the formal security model of BIB-MKS, and prove the security of BIB-MKS under this model. The performance evaluation demonstrates that BIB-MKS is practical.

A b Byzantine-robust K-out-of-ℓ private information retrieval ((b, K,ℓ)-BRPIR) scheme allows a user to retrieve any item of a database from ℓ servers, even if only K out of the ℓ servers respond and at most b out of the K responding servers provide false answers. The existing BRPIR schemes require either an exponential time decoding algorithm or a communication complexity no better than O(n1/(2k-1) k ℓ log ℓ) with k=K-2b. In this paper, we show a new (b,K,ℓ)-BRPIR scheme that has both a polynomial time decoding algorithm and a communication cost of ℓ • exp(O((log n)1-over 1 r (log log n) 1 overr)) for r=log (K/(2b+1)), which is more efficient when n→ ∞.

The conflicts between input privacy and efficiency in single-server non-interactive verifiable computation (NIVC) makes it interesting to consider the multi-server models of NIVC. Although the existing multi-server NIVC schemes provide meaningful improvements, they either require the servers to communicate or leave the client’s data unprotected. It has been an open problem to design multi-server NIVC with both input privacy and non-communicating servers. In this paper we define a multi-server verifiable computation (MSVC) model where the client secret-shares its input x among non-communicating servers, each server locally computes a function F to get a partial result, and finally the client reconstructs F(x) from all partial results. We construct five MSVC schemes for outsourcing low-degree polynomials and thus answer the open question for such polynomials. Our schemes are t-private such that any t servers learn no information about x. Our schemes are t-secure such that any t servers cannot persuade the client to output wrong results. The privacy and security can be either information-theoretic or computational. Comparing with the existing schemes, our servers can be at least two orders faster.

Reputation/trust-based blockchain systems have attracted considerable research interests for better integrating Internet of Things with blockchain in terms of throughput, scalability, energy efficiency, and incentive aspects. However, most existing works only consider static adversaries. Hence, they are vulnerable to slowly adaptive attackers, who can target validators with high reputation value to severely degrade the system performance. Therefore, we introduce$\textsf{zkRep}$, a privacy-preserving scheme tailored for reputation-based blockchains. Our basic idea is to hide both the identity and reputation of the validators by periodically changing the identity and reputation commitments (i.e., aliases), which makes it much more difficult for slowly adaptive attackers to identify validators with high reputation value. To realize this idea, we utilize privacy-preserving Pedersen-commitment-based reputation updating and leader election schemes that operate on concealed reputations within an epoch. We also introduce a privacy-preserving identity update protocol that changes the identity and time-window-based cumulative reputation commitments during each epoch transition. We have implemented and evaluated$\textsf{zkRep}$on the Amazon Web Service. The experimental results and analysis show that$\textsf{zkRep}$achieves great privacy-preserving features against slowly adaptive attacks with little overhead.

Anomaly detection offers a powerful approach to identifying unusual activities and uncommon behaviors in real-world video scenes. At present, convolutional neural networks (CNN) have been widely used to tackle anomalous events detection, which mainly rely on its stronger ability of feature representation than traditional hand-crafted features. However, massive video data and high cost of CNN model training are a challenge to achieve satisfactory detection results for resource-limited users. In this article, we propose a secure video anomaly detection framework (SecureAD) based on CNN. Specifically, we introduce additive secret sharing to design several calculation protocols for achieving safe CNN training and video anomaly detection. Besides, we propose a Bloom filter based fine-grained access control policy to authenticate legitimate users, without leaking the privacy of raw personal attributes. In addition, edge computing instead of cloud computing is integrated into the architecture to reduce response time between servers and users in an outsourced environment. Finally, we prove that the proposed SecureAD achieves secure video anomaly detection without compromising the privacy of the related data. Also, the simulation results demonstrate the effectiveness and security of our SecureAD.

Deterministic Wallet (DW) and Stealth Address (SA) mechanisms have been widely adopted in the cryptocurrency community, due to their virtues on functionality and privacy protection, which come from a key derivation mechanism that allows an arbitrary number of derived keys to be generated from a master key. However, these algorithms suffer a vulnerability that, when one derived key is compromised somehow, the damage is not limited to the leaked derived key only, but to the master key and in consequence all derived keys are compromised. In this article, we introduce and formalize a new signature variant, called Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key (PDPKS), which fully captures and improves the functionality, security, and privacy requirements of DW and SA. We propose a PDPKS construction and prove its security and privacy in the random oracle model. Furthermore, we implement the construction with parameters for 128-bit security, and the results show that it is practically efficient for the setting of cryptocurrencies. With its solid guarantee on functionality, security and privacy, as well as its practical efficiency, our PDPKS construction provides a practical cryptographic tool that refines DW and SA, without security vulnerability.

Despite decades of intensive research, it is still challenging to design a practical multi-factor user authentication scheme for wireless sensor networks (WSNs). This is because protocol designers are confronted with a long-standing “security versus efficiency” dilemma: sensor nodes are lightweight devices with limited storage and computation capabilities, while the security requirements are demanding as WSNs are generally deployed for sensitive applications. Hundreds of proposals have been proposed, yet most of them have been found to be problematic, and the same mistakes are repeated again and again. Two of the most common security failures are regarding smart card loss attacks and node capture attacks. The former has been extensively investigated in the literature, while little attention has been given to understanding the node capture attacks. To alleviate this undesirable situation, this article takes a substantial step towards systematically exploring node capture attacks against multi-factor user authentication schemes for WSNs. We first investigate the various causes and consequences of node capture attacks, and classify them into ten different types in terms of the attack targets, adversary’s capabilities and vulnerabilities exploited. Then, we elaborate on each type of attack through examining 11 typical vulnerable protocols, and suggest corresponding countermeasures. Finally, we conduct a large-scale comparative measurement of 61 representative user authentication schemes for WSNs under our extended evaluation criteria. We believe that such a systematic understanding of node capture attacks would help design secure user authentication schemes for WSNs.

We consider an outsourced computation model in the selective data sharing setting. Specifically, one of the data owners outsources the encrypted data to an untrusted cloud server, and wants to share the specific function of these data with a group of data users. A data user can perform the specific computation on the data that it is authorized to access. We propose a construction under this model for the inner product computation by using the Inner Product Functional Encryption (IPFE) as a building block. A standard IPFE used on this model has two privacy weaknesses regarding the master secret key and the encrypted vector. We propose a strengthened IPFE that revises these weaknesses. We construct a new IPFE scheme and use it to construct an efficient outsourced inner product computation scheme. In our outsourced computation scheme, the storage overhead and the computation cost for a data user are independent of the vector size. The result privacy and the outsourced data privacy are well preserved against the untrusted cloud server. The experimental results show that our schemes are efficient and practical.

Communication efficient secret sharing (CESS) schemes are a class of threshold schemes that aim to minimize the so-called decoding bandwidth, namely the necessary amount of communication between a combiner who wants to reconstruct the secret and the available participants storing shares of the secret. Previous works proved that the decoding bandwidth had a tight lower bound related to the number of available participants. Some threshold schemes that achieved the lower bound (optimal decoding bandwidth) and optimal information rate were constructed for a given number (non-universal case) or multiple distinct number ($\triangle $-universal case) of available participants. However, all those CESS schemes have large share sizes. Moreover, they have a common feature that each secret and share are a vector with multiple coordinates, which results in thedecoding delaysince the combiner must reconstruct a part of coordinates of the secret at first, and these recovered coordinates will be used to reconstruct another part of coordinates of the secret. In this work, we describe a new construction for CESS schemes of non-universal and$\triangle $-universal cases, whereas each secret and share of our schemes are asingleelement of a finite field$\mathbb {F}_{q^{e}}$, and each participant of an authorized subset provides asingleelement of a same subfield of$\mathbb {F}_{q^{e}}$to the combiner to reconstruct the secret. We find that the CESS schemes of this type, termed balanced CESS schemes, have an inevitable restriction on the number of available participants, but our schemes has no decoding delay. Furthermore, our schemes havesmallershare sizes than other existing works, which are realized by using a smaller sub-packetization$e$and a smaller base field$\mathbb {F}_{q}$. Indeed, the sub-packetizations of our schemes areminimumfor given$\mathbb {F}_{q}$among balanced CESS schemes. In addition, when our constructions are used to generate communication efficient$(n,r)$threshold schemes, we derive a generalized Shamir’s scheme that universally achieves optimal decoding bandwidth and optimal information rate forthe first time, where the restriction on the number of available participants is removed.

Public verification enables cloud users to employ a third party auditor (TPA) to check the data integrity. However, recent breakthrough results on quantum computers indicate that applying quantum computers in clouds would be realized. A majority of existing public verification schemes are based on conventional hardness assumptions, which are vulnerable to adversaries equipped with quantum computers in the near future. Moreover, new security issues need to be solved when an original data owner is restricted or cannot access the remote cloud server flexibly. In this paper, we propose an efficient identity-based data outsourcing with public integrity verification scheme (DOPIV) in cloud storage. DOPIV is designed on lattice-based cryptography, which achieves post-quantum security. DOPIV enables an original data owner to delegate a proxy to generate the signatures of data and outsource them to the cloud server. Any TPA can perform data integrity verification efficiently on behalf of the original data owner, without retrieving the entire data set. Additionally, DOPIV possesses the advantages of being identity-based systems, avoiding complex certificate management procedures. We provide security proofs of DOPIV in the random oracle model, and conduct a comprehensive performance evaluation to show that DOPIV is more practical in post-quantum secure cloud storage systems.

In this article, we analyze the inherent characteristics of smart grids, and point out that some electricity consumption data are very sensitive and should be encrypted. However, once the corresponding private key is compromised, the content of encrypted data would be leaked, thereby violating users' privacy. Additionally, since a control center (CC) is always required to conduct accurate statistic analysis on these data for subsequent services, it is highly demanded for CC to check the integrity of encrypted data. To this end, based on a modified Boneh-Goh-Nissim (BGN) cryptosystem, we propose a key-leakage resilient encrypted data aggregation (KLR-EDA) scheme with lightweight verification in fog-assisted smart grids. KLR-EDA enables each fog node to aggregate first-level verifiable encrypted data from smart meters in the same grid area, and forward them to the cloud server (CS) for long-term storage. Upon receiving flexible challenging list of fog nodes from CC, CS produces second-level verifiable encrypted aggregated data and returns the results to CC. KLR-EDA enables CC to check the integrity of encrypted aggregated data efficiently, and further obtain the statistic analysis results on the aggregated data without learning any information of individual user. In particular, even the private key of CC is exposed or compromised, any adversary cannot break users' privacy. We provide security analysis of KLR-EDA, and conduct performance evaluation to demonstrate its lightweight statistical analysis and verification advantages on the CC side.

Wireless body area networks (WBANs) rely on powerful cloud storage services to manage massive medical data. As precise medical diagnosis analysis is heavily based on these medical data, any altered medical data may cause severe consequences, the integrity of outsourced medical data has become the most concerning security issue. Up to date, most existing public auditing mechanisms have been proposed to check the data integrity, but they could not achieve conditional identity privacy, any patient would not like others to know his/her real identity corresponding to certain serious disease, and some malicious patients should be revoked timely due to misbehaviors. Additionally, they are vulnerable to malicious auditors, by colluding with the cloud server to cheat patients. In this paper, we propose a conditional identity privacy-preserving public auditing (CIPPPA) mechanism for cloud-based WBANs. CIPPPA is the first public auditing mechanism achieving conditional identity privacy of patients in WBANs, the real identity of a patient is unknown to anyone in cloud-based WBANs other than the private key generator (PKG). We attempt to integrate Ethereum blockchain into CIPPPA, which gives assistance to patients for validating malicious auditing behaviors. Formal security analysis and performance evaluation demonstrate that CIPPPA is practical for cloud-based WBANs.

Person re-identification (Re-ID) has attracted extensive attention due to its potential to identify a person of interest from different surveillance videos. With the increasing amount of the surveillance videos, high computation and storage costs have posed a great challenge for the resource-constrained users. In recent years, the cloud storage services have made a large volume of video data outsourcing become possible. However, person Re-ID over outsourced surveillance videos could lead to a security threat, i.e., the privacy leakage of the innocent person in these videos. Therefore, we propose an efFicient privAcy-preseRving peRson Re-ID Scheme (FARRIS) over outsourced surveillance videos, which can ensure the privacy of the detected person while providing the person Re-ID service. Specifically, FARRIS exploits the convolutional neural network (CNN) and kernels based supervised hashing (KSH) to extract the efficient person Re-ID feature. Then, we design a secret sharing based Hamming distance computation protocol to allow cloud servers to calculate similarities among obfuscated feature indexes. Furthermore, a dual Merkle hash trees based verification is proposed, which permits users to validate the correctness of the matching results. The extensive experimental results and security analysis demonstrate that FARRIS can work efficiently, without compromising the privacy of the involved person.

To achieve security and privacy for data stored on the cloud, we need the ability to secure data in compute. Equality comparisons, “$x=y, x\ne y$”, have been widely studied with many proposals but there is much room for improvement for order comparisons, “$x < y,~x \leq y,~x > y \text{ and } x \geq y$”. Most protocols for order comparisons have some limitation, either leaking some information about the data or requiring several rounds of communication between client and server. In addition, little work has been done on retrieving with compound conditions, mixing several equality and order comparisons. Fully homomorphic encryption (FHE) promises the ability to compute arbitrary functions on encrypted data without sacrificing privacy and without communication, but its potential has yet to be fulfilled. Particularly, private comparisons for database queries using FHE are expensive to compute. In this article, we design an efficient private database query (PDQ) protocol which supports compound conditions with equality and order comparisons. To this end, we first present a private comparison algorithm on encrypted integers using FHE, which scales efficiently for the length of input integers, by applying techniques from finite field theory. Then, we consider a scenario for PDQ protocols, querying for values based on a conjunction of one order and four equality conditions on key columns. The proposed algorithm and protocol are implemented and tested to determine their performance in practice. The proposed comparison algorithm takes about$25.259$seconds to compare 697 pairs of 64-bit integers using Brakerski-Gentry-Vaikuntanathan's leveled FHE scheme with single instruction multiple data (SIMD) techniques at more than 138 bits of security. This yields an amortized rate of just 36 milliseconds per comparison. On top of that, we show that our techniques achieve an efficient PDQ protocol for one order and four equality comparisons, achieving an amortized time and communication cost of 57 milliseconds and 448 bytes per database element.

Cloud-assisted Industrial Internet of Things (IIoT) relies on cloud computing to provide massive data storage services. To ensure the confidentiality, sensitive industrial data need to be encrypted before being outsourced to cloud storage server. Public-key encryption with keyword search (PEKS) enables users to search target encrypted data by keywords. However, most existing PEKS schemes are based on conventional hardness assumptions, which are vulnerable to adversaries equipped with quantum computers in the near future. Moreover, they suffer from key exposure, and thus the security would be broken once the keys are compromised. In this paper, we propose a forward secure PEKS scheme (FS-PEKS) based on lattice assumptions for cloud-assisted IIoT, which is post-quantum secure. We integrate a lattice-based delegation mechanism into FS-PEKS to achieve forward security, such that the security of the system is still guaranteed even the keys are compromised by the adversaries. We define the first formal security model on forward security of PEKS, and prove the security of FS-PEKS under the model. As the keywords of industrial data are with inherently low entropy, we further extend FS-PEKS to resist insider keyword guessing attacks (IKGA). The comprehensive performance evaluation demonstrates that FS-PEKS is practical for cloud-assisted IIoT.

Formal analyses of blockchain protocols have received much attention recently. Consistency results of Nakamoto's blockchain protocol are often expressed in a quantity c, which denotes the expected number of network delays before some block is mined. With μ (resp., ν) denoting the fraction of computational power controlled by benign miners (resp., the adversary), where μ+ν =1, we prove for the first time that to ensure the consistency property of Nakamoto's blockchain protocol in an asynchronous network, it suffices to have c to be just slightly greater than 2μ/(ln(μ/ν)). Such a result is both neater and stronger than existing ones. In the proof, we formulate novel Markov chains which characterize the numbers of mined blocks in different rounds.

In this paper, we present a lightweight hardware design for a recently proposed quantum-safe key encapsulation mechanism based on QC-LDPC codes called LEDAkem, which has been admitted as a round-2 candidate to the NIST post-quantum standardization project. Existing implementations focus on high speed while few of them take into account area or power efficiency, which are particularly decisive for low-cost or power constrained IoT applications. The solution we propose aims at maximizing the metric of area efficiency by rotating the QC-LDPC code representations amongst the block RAMs in digit level. Moreover, optimized parallelized computing techniques, lazy accumulation and block partition are exploited to improve key decapsulation in terms of area and timing efficiency. We show for instance that our area-optimized implementation for 128-bit security requires 6.82 x 105 cycles and 2.26 x 106 cycles to encapsulate and decapsulate a shared secret, respectively. The area-optimized design uses only 39 slices (3 percent of the available logic) and 809 slices (39 percent of the available logic) for key encapsulation and key decapsulation respectively, on a small-size low-end Xilinx Spartan-6 FPGA.

We solve an open question in code-based cryptography by introducing two provably secure group signature schemes from code-based assumptions. Our basic scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise problem, and a variant of the Syndrome Decoding problem. The construction produces smaller key and signature sizes than the previous group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed 224, which is roughly comparable to the current population of the Netherlands. We develop the basic scheme further to achieve the strongest anonymity notion, i.e., CCA-anonymity, with a small overhead in terms of efficiency. The feasibility of two proposed schemes is supported by implementation results. Our two schemes are the first in their respective classes of provably secure groups signature schemes. Additionally, the techniques introduced in this work might be of independent interest. These are a new verifiable encryption protocol for the randomized McEliece encryption and a novel approach to design formal security reductions from the Syndrome Decoding problem.

Since the introduction of Bitcoin in 2008, cryptocurrency has been undergoing a quick and explosive development. At the same time, privacy protection, one of the key merits of cryptocurrency, has attracted much attention by the community. A deterministic wallet algorithm and a stealth address algorithm have been widely adopted in the community, due to their virtues on functionality and privacy protection, which come from a key derivation mechanism that an arbitrary number of derived keys can be generated from a master key. However, these algorithms suffer a vulnerability. In particular, when a minor fault happens (say, one derived key is compromised somehow), the damage is not limited to the leaked derived key only, instead, it spreads to the master key and all derived keys are compromised. In this paper, to provide a formal treatment for the problem, we introduce and formalize a new signature variant, called Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key (PDPKS), which forms a convenient and robust cryptographic tool for offering the virtues of deterministic wallet and stealth address, while eliminating the security vulnerabilities. Specifically, PDPKS allows anyone to derive new signature verification keys for a user, say Alice, based on her long-term public key, while only Alice can derive the signing keys corresponding to those verification keys. In terms of privacy, given a derived verification key and valid signatures with respect to it, an adversary is not able to tell which long-term public key, out of a set of known long-term public keys, is the one from which the verification key was derived. A distinguishing security feature of PDPKS, with the above functionality and privacy features, is that the derived keys are independent/insulated from each other, namely, compromising the signing key associated with a verification key does not allow an adversary to forge a valid signature for another verification key, even if both verification keys are derived from the same long-term public key. We formalize the notion of PDPKS and propose a practical and proven secure construction, which could be a convenient and secure cryptographic tool for building privacy-preserving cryptocurrencies and supporting promising use cases in practice, as it can be used to implement secure stealth addresses, and can be used to implement deterministic wallets and the related appealing use cases, without security concerns.

Shamir's celebrated secret sharing scheme provides an efficient method for encoding a secret of arbitrary length $\ell$ among any $N \leq 2^\ell$ players such that for a threshold parameter $t$, (i) the knowledge of any $t$ shares does not reveal any information about the secret and, (ii) any choice of $t+1$ shares fully reveals the secret. It is known that any such threshold secret sharing scheme necessarily requires shares of length $\ell$, and in this sense Shamir's scheme is optimal. The more general notion of ramp schemes requires the reconstruction of secret from any $t+g$ shares, for a positive integer gap parameter $g$. Ramp secret sharing scheme necessarily requires shares of length $\ell/g$. Other than the bound related to secret length $\ell$, the share lengths of ramp schemes can not go below a quantity that depends only on the gap ratio $g/N$. In this work, we study secret sharing in the extremal case of bit-long shares and arbitrarily small gap ratio $g/N$, where standard ramp secret sharing becomes impossible. We show, however, that a slightly relaxed but equally effective notion of semantic security for the secret, and negligible reconstruction error probability, eliminate the impossibility. Moreover, we provide explicit constructions of such schemes. One of the consequences of our relaxation is that, unlike standard ramp schemes with perfect secrecy, adaptive and non-adaptive adversaries need different analysis and construction. For non-adaptive adversaries, we explicitly construct secret sharing schemes that provide secrecy against any $τ$ fraction of observed shares, and reconstruction from any $ρ$ fraction of shares, for any choices of $0 \leq τ< ρ\leq 1$. Our construction achieves secret length $N(ρ-τ-o(1))$, which we show to be optimal. For adaptive adversaries, we construct explicit schemes attaining a secret length $Ω(N(ρ-τ))$.

Non-malleable codes are randomized codes that protect coded messages against modification by functions in a tampering function class. These codes are motivated by providing tamper resilience in applications where a cryptographic secret is stored in a tamperable storage device and the protection goal is to ensure that the adversary cannot benefit from their physical tampering with the device. In this paper we consider nonmalleable codes for protection of secure communication against active physical layer adversaries. We define a class of functions that closely model tampering of communication by adversaries who can eavesdrop on a constant fraction of the transmitted codeword, and use this information to select a vector of tampering functions that will be applied to a second constant fraction of codeword components (possibly overlapping with the first set). We derive rate bounds for non-malleable codes for this function class and give a modular construction that adapts and provides new analysis for an existing construction in the new setting. We discuss our results and directions for future work.

Non-malleable codes protect against an adversary who can tamper with the coded message by using a tampering function in a specified function family, guaranteeing that the tampering result will only depend on the chosen function and not the coded message. The codes have been motivated for providing protection against tampering with hardware that stores the secret cryptographic keys, and have found significant attention in cryptography. Traditional Shannon model of communication systems assumes the communication channel is perfectly known to the transmitter and the receiver. Arbitrary Varying Channels (AVCs) remove this assumption and have been used to model adversarially controlled channels. Transmission over these channels has been originally studied with the goal of recovering the sent message, and more recently with the goal of detecting tampering with the sent messages. In this paper we introduce non-malleability as the protection goal of message transmission over these channels, and study binary (discrete memoryless) AVCs where possible tampering is modelled by the set of channel states. Our main result is that non-malleability for these channels is achievable at a rate asymptotically approaching 1. We also consider the setting of an AVC with a special state s*, and the additional requirement that the message must be recoverable if s* is applied to all the transmitted bits. We give the outline of a message encoding scheme that in addition to non-malleability, can provide recovery for all s* channel.

Abstract Efficient user revocation is a necessary but challenging problem in many multi-user cryptosystems. Among known approaches, server-aided revocation yields a promising solution, because it allows to outsource the major workloads of system users to a computationally powerful third party, called the server, whose only requirement is to carry out the computations correctly. Such a revocation mechanism was considered in the settings of identity-based encryption and attribute-based encryption by Qin et al. (2015, ESORICS) and Cui et al. (2016, ESORICS ), respectively. In this work, we consider the server-aided revocation mechanism in the more elaborate setting of predicate encryption (PE). The latter, introduced by Katz et al. (2008, EUROCRYPT), provides fine-grained and role-based access to encrypted data and can be viewed as a generalization of identity-based and attribute-based encryption. Our contribution is 2-fold. First, we formalize the model of server-aided revocable PE (SR-PE), with rigorous definitions and security notions. Our model can be seen as a non-trivial adaptation of Cui et al.’s work into the PE context. Second, we put forward a lattice-based instantiation of SR-PE. The scheme employs the PE scheme of Agrawal et al. (2011, ASIACRYPT) and the complete subtree method of Naor et al. (2001, CRYPTO) as the two main ingredients, which work smoothly together thanks to a few additional techniques. Our scheme is proven secure in the standard model (in a selective manner), based on the hardness of the learning with errors problem.

RFID tags have become ubiquitous and cheaper to implement. It is often imperative to design ultralightweight authentication protocols for such tags. Many existing protocols still rely on triangular functions, which have been shown to have security and privacy vulnerabilities. This work proposes UMAPSS, an ultralightweight mutual-authentication protocol based on Shamir’s ( 2 , 𝑛 ) secret sharing. It includes mechanisms for double verification, session control, mutual authentication, and dynamic update to enhance security and provide a robust privacy protection. The protocol relies only on two simple bitwise operations, namely addition modulo 2 𝑚 and a circular shift R o t ⁡ ( 𝑥 , 𝑦 ) , on the tag’s end. It avoids other, unbalanced, triangular operations. A security analysis shows that the protocol has excellent privacy properties while offering a robust defense against a broad range of typical attacks. It satisfies common security and the low-cost requirements for RFID tags. It is competitive against existing protocol, scoring favourably in terms of computational cost, storage requirement, and communication overhead .

Public key encryption with equality test (PKEET) is a variant of classical public key encryption (PKE) with the special functionality of an equality test, and can be used in many applications such as in keyword search on encrypted data and for efficient management by partitioning encrypted data in the cloud. Since the original proposal of Yang et al. (CT-RSA, 2010), several subsequent proposals to improve the efficiency or functionality of PKEET have been reported. We present a PKEET construction from generic assumptions in the random oracle model . In particular, whereas previous results require number-theoretic assumptions or strictly stronger generic assumptions such as the existence of secure hierarchical identity-based encryption, our proposal requires only the existence of cryptographic hash functions and secure PKE schemes satisfying a special property , called randomness extractability . Informally, randomness extractability means that one can recover the randomness used in a ciphertext when given a secret key corresponding to a public key for the ciphertext . We investigate the fact that PKE schemes satisfying this property can be designed by the Fujisaki-Okamoto (FO) transformation, which is the widely utilized method to obtain secure PKE schemes from basic cryptographic primitives in the random oracle model . As a result, in combination with the FO transformation, we obtain a PKEET construction in the random oracle model if there exist a one-way PKE scheme, a one-time secure symmetric key encryption scheme , collision-resistant and one-way hash functions , and a pseudorandom function. In this sense, we remark that our PKEET construction is derived from fundamental generic assumptions only.

Public-key encryption with keyword search (PEKS) enables users to search over encrypted data and retrieve target data efficiently. However, most of existing PEKS schemes are vulnerable to adversaries equipped with quantum computers in the near future, and even incur complex certificate management procedures due to the public key infrastructure (PKI). To this end, we propose a proxy-oriented identity-based encryption with keyword search (PO-IBEKS) scheme from lattices for cloud storage, which is post-quantum secure. In PO-IBEKS, an original data owner authorizes a proxy to encrypt sensitive data as well as corresponding keywords and upload ciphertexts to clouds, which alleviates the data processing burden on the original data owner. Besides, PO-IBEKS can resist inside keyword guessing attacks (IKGA) from misbehaved cloud servers by integrating the learning with errors (LWE) encryption and preimage sampleable function. Each entity in PO-IBEKS is identified with her/his recognizable information, thereby eliminating managing certificates. Formal security analysis proves that PO-IBEKS can achieve ciphertext indistinguishability, existential unforgeability, and delegation security. Experimental results demonstrate PO-IBEKS is much more practical when compared with existing schemes.

Fully homomorphic encryption (FHE) brings a paradigm shift in cryptographic engineering by enabling us to resolve various unsolved problems. Among them, this work solves the problem to design a private database query (PDQ) protocol that supports compound queries with wildcard conditions on encrypted databases using FHE. More precisely, we consider a setting where clients outsource an encrypted database using FHE to a remote server, and later request results of compound queries including a wildcard search condition-given a set of attribute values {A1; A2; ...; An} and a search pattern W, retrieve a set of all attribute values Ai's in which the pattern W occurs. To this end, we first develop an algorithm for testing whether an encrypted string contains an encrypted pattern without revealing any information of the pattern, taking auxiliary encryptions as additional inputs. Then, using this algorithm, we design PDQ protocols on encrypted databases, which support compound queries using wildcard search conditions. Finally, we demonstrate proof-of-concept implementation results of our protocols by exploiting single-instruction-multiple-data operations and multi-threading techniques.

Private query processing is a very attractive problem in the fields of both cryptography and databases. In this work, we restrict our attention to the efficiency aspect of the problem, particularly for basic queries with conditions on various combinations of equality. Without loss of generality, these conditions can be regarded as a Boolean function, and this Boolean function can then be evaluated at ciphertexts produced by a fully homomorphic encryption (FHE) scheme without decryption. From the efficiency perspective, the remaining concern is to efficiently test the equality function without severely downgrading the performance of FHE-based querying solutions. To this end, we first analyze the multiplicative depth required for an equality test algorithm with respect to the plaintext space inhabited by general FHE schemes. The primary reason for this approach is that given an equality test algorithm, its efficiency is measured in terms of the multiplicative depth required to construct its arithmetic circuit expression. Indeed, the implemented equality test algorithm dominates the entire performance of FHE-based query solutions, apart from the performance of the underlying FHE scheme. Then, we measure the multiplicative depth considering an FHE scheme that takes an extension field as its plaintext space and that supports the depth-free evaluation of Frobenius maps. According to our analysis, when the plaintext space of an FHE scheme is a field of characteristic 2, the equality test algorithm for `-bit messages requires the lowest multiplicative depth dlog`e. Furthermore, we design a set of private query protocols for conjunctive, disjunctive, and threshold queries based on the equality test algorithm. Similarly, applying the equality test algorithm over F2ℓ, our querying protocols require the minimum depths. More specifically, a multiplicative depth of [log ℓ] + [log (1 + ρ)] is required for conjunctive and disjunctive queries, and a depth of [log ℓ] + 2[log (1+ρ )] is required for threshold conjunctive queries, when their query conditions have p attributes to be compared. Finally, we provide a communication-efficient version of our solutions, though with additional computational costs, when an upper bound δ (0 ≤ δ ≤ 1) on the selectivity of a database is given. Consequently, we reduce the communication cost from n to approximately [δn] ciphertexts with [log n] additional depth when the database consists of n tuples.

In this article, we identify a flaw in Huang et al.'s public key encryption with authorized equality test (The Computer Journal, 2015). More precisely, we point out that the proof of the indistinguishability under adaptive chosen ciphertext attack (IND-CCA2) security for their scheme has a serious flaw. We illustrate this flaw by presenting a polynomial time CCA2 attack on their scheme. We also provide a solution to correct this flaw by modifying their scheme slightly. Our solution is quite efficient because it provides security against CCA2 attack by exploiting only the hash computation of a two times longer input without any increase in the sizes of ciphertexts and warrants.

Public key encryption with equality test (PKEET), which was first introduced by Yang et al. (CT-RSA, 2010), has various applications including facilitating keyword search on encrypted data and partitioning encrypted data on the cloud. It can be also applied to manage personal health records on the internet. For these reasons, there have been improvements on earlier PKEET schemes in terms of performance and functionality. We present a semi-generic method for PKEET constructions, assuming only the existence of IND-CCA2 secure traditional public key encryption (PKE) schemes, the hardness of Computational Diffie-Hellman (CDH) problems, and random oracles. Our approach has several advantages; it enables us to understand requirements for the equality test functionality more clearly. Furthermore, our approach is quite general, in that if we change the underlying PKE scheme with the identity-based encryption (IBE) scheme (and we assume the hardness of Bilinear Diffie-Hellman problems instead of CDH), then we obtain the first IBE scheme with equality test (IBEET) satisfying analogous security arguments to those of PKEET. Although an IBEET construction was recently proposed, but we note that it satisfies only weak security requirements.

[Abstract Not Available]

Searchable Symmetric Encryption (SSE) allows a client to store encrypted data on a storage provider in such a way, that the client is able to search and retrieve the data selectively without the storage provider learning the contents of the data or the words being searched for. Practical SSE schemes usually leak (sensitive) information during or after a query (e.g., the search pattern). Secure schemes on the other hand are not practical, namely they are neither efficient in the computational search complexity, nor scalable with large data sets. To achieve efficiency and security at the same time, we introduce the concept of distributed SSE (DSSE), which uses a query proxy in addition to the storage provider. We give a construction that combines an inverted index approach (for efficiency) with scrambling functions used in private information retrieval (PIR) (for security). The proposed scheme, which is entirely based on XOR operations and pseudo-random functions, is efficient and does not leak the search pattern. For instance, a secure search in an index over one million documents and 500 keywords is executed in less than 1 second.

Password-authenticated key exchange (PAKE) is where a client and a server, who share a password, authenticate each other and meanwhile establish a cryptographic key by exchange of messages. In this setting, all the passwords necessary to authenticate clients are stored in a single server. If the server is compromised, due to, for example, hacking or even insider attack, passwords stored in the server are all disclosed. In this paper, we consider a scenario where two servers cooperate to authenticate a client and if one server is compromised, the attacker still cannot pretend to be the client with the information from the compromised server. Current solutions for two-server PAKE are either symmetric in the sense that two peer servers equally contribute to the authentication or asymmetric in the sense that one server authenticates the client with the help of another server. This paper presents a symmetric solution for two-server PAKE, where the client can establish different cryptographic keys with the two servers, respectively. Our protocol runs in parallel and is more efficient than existing symmetric two-server PAKE protocol, and even more efficient than existing asymmetric two-server PAKE protocols in terms of parallel computation.

Interorganizational workflow systems play a fundamental role in business partnerships. We introduce and investigate the concept of workflow signatures. Not only can these signatures be used to ensure authenticity and protect integrity of workflow data, but also to prove the sequence and logical relationships, such as AND-join and AND-split, of a workflow. Hence, workflow signatures can be electronic evidence useful for auditing, that is proving compliance of business processes against some regulatory requirements. Furthermore, signing keys can be used to grant permissions to perform tasks. Since the signing keys are issued on-the-fly, authorization to execute a task within a workflow can be controlled and granted dynamically at runtime. In this paper, we propose a concrete workflow signature scheme, which is based on hierarchical identity-based cryptography, to meet security properties required by interorganizational workflows.

The sum of k mins protocol was proposed by Hopper and Blum as a protocol for secure human identification. The goal of the protocol is to let an unaided human securely authenticate to a remote server. The main ingredient of the protocol is the sum of k mins problem. The difficulty of solving this problem determines the security of the protocol. In this paper, we show that the sum of k mins problem is NP-Complete and W[1]-Hard. This latter notion relates to fixed parameter intractability. We also discuss the use of the sum of k mins protocol in resource-constrained devices.

We study the multicast stream authentication problem when the communication channel is under control of an opponent who can drop, reorder and inject data packets. Recently, many coding theory based protocols have been developed to treat the stream authentication problem over such a channel. In this paper, our goal is to provide a general coding approach for multicast stream authentication. We design an authentication protocol which combines any list recoverable code (provided some conditions on its construction parameters). We demonstrate that the previous schemes can be viewed as instances of our construction when a Reed-Solomon code is used as a list recoverable code. In such settings, we also show that our approach leads to a better upper bound on the number of signature verification queries for each receiver.

The purpose of this paper is to describe a new decomposition construction for perfect secret sharing schemes with graph access structures. The previous decomposition construction proposed by Stinson is a recursive method that uses small secret sharing schemes as building blocks in the construction of larger schemes. When the Stinson method is applied to the graph access structures, the number of such “small” schemes is typically exponential in the number of the participants, resulting in an exponential algorithm. Our method has the same flavor as the Stinson decomposition construction; however, the linear programming problem involved in the construction is formulated in such a way that the number of “small” schemes is polynomial in the size of the participants, which in turn gives rise to a polynomial time construction. We also show that if we apply the Stinson construction to the “small” schemes arising from our new construction, both have the same information rate.

Recently a new human authentication scheme called PAS (predicate-based authentication service) was proposed, which does not require the assistance of any supplementary device. The main security claim of PAS is to resist passive adversaries who can observe the whole authentication session between the human user and the remote server. In this paper we show that PAS is insecure against both brute force attack and a probabilistic attack. In particular, we show that its security against brute force attack was strongly overestimated. Furthermore, we introduce a probabilistic attack, which can break part of the password even with a very small number of observed authentication sessions. Although the proposed attack cannot completely break the password, it can downgrade the PAS system to a much weaker system similar to common OTP (one-time password) systems.

With the growing demand of databases outsourcing and its security concerns, we investigate privacy-preserving set intersection in a distributed scenario. We propose a one-round protocol for privacy-preserving set intersection based on a combination of secret sharing scheme and ho- momorphic encryption. We then show that, with an extra permutation performed by each contacted server, the cardinality of set intersection can be computed efficiently. All protocols constructed in this paper are provably secure against an honest-but-curious adversary under the Decisional Diffie-Hellman assumption.

A dynamic accumulator is an algorithm, which merges a large set of elements into a constant-size value such that for an element accumulated, there is a witness confirming that the element was included into the value, with a property that accumulated elements can be dynamically added and deleted into/from the original set. Recently Wang et al. presented a dynamic accumulator for batch updates at ICICS 2007. However, their construction suffers from two serious problems. We analyze them and propose a way to repair their scheme. We use the accumulator to construct a new scheme for common secure indices with conjunctive keyword-based retrieval.

An accumulator based on bilinear pairings was proposed at CT-RSA'05. Here, it is first demonstrated that the security model proposed by Lan Nguyen does lead to a cryptographic accumulator that is not collision resistant. Secondly, it is shown that collision-resistance can be provided by updating the adversary model appropriately. Finally, an improvement on Nguyen's identity escrow scheme, with membership revocation based on the accumulator, by removing the trusted third party is proposed.

A secret sharing scheme typically requires secure communications in each of two distribution phases: (1) a dealer distributes shares to participants (share distribution phase); and later (2) the participants in some authorised subset send their share information to a combiner (secret reconstruction phase). While problems on storage required for participants, for example, the size of shares, have been well studied, problems regarding the communication complexity of the two distribution phases seem to have been mostly neglected in the literature so far. In this correspondence, we deal with several communication related problems in the secret reconstruction phase. Firstly, we show that there is a tradeoff between the communication costs and the number of participants involved in the secret reconstruction. We introduce the communication rate as the ratio of the secret size and the total number of communication bits transmitted from the participants to the combiner in the secret reconstruction phase. We derive a lower bound on the communication rate and give constructions that meet the bound. Secondly, we show that the point-to-point secure communication channels for participants to send share information to the combiner can be replaced with partial broadcast channels. We formulate partial broadcast channels as set systems and show that they are equivalent to the well-known combinatorial objects of cover-free family. Surprisingly, we find that the number of partial broadcast channels can be significantly reduced from the number of point-to-point secure channels. Precisely, in its optimal form, the number of channels can be reduced from n to O(log n), where is the number of participants in a secret sharing scheme. We also study the communication rates of partial broadcast channels for the secret reconstruction.

We consider the problem of increasing the threshold parameter of a secret-sharing scheme after the setup (share distribution) phase, without further communication between the dealer and the shareholders. Previous solutions to this problem require one to start off with a nonstandard scheme designed specifically for this purpose, or to have communication between shareholders. In contrast, we show how to increase the threshold parameter of thestandardShamir secret-sharing scheme without communication between the shareholders. Our technique can thus be applied to existing Shamir schemes even if they were set up without consideration to future threshold increases.

We present a text watermarking scheme that embeds a bitstream watermark Wi in a text document P preserving the meaning, context, and flow of the document. The document is viewed as a set of paragraphs, each paragraph being a set of sentences. The sequence of paragraphs and sentences used to embed watermark bits is permuted using a secret key. Then, English language sentence transformations are used to modify sentence lengths, thus embedding watermarking bits in the Least Significant Bits (LSB) of the sentences' cardinalities. The embedding and extracting algorithms are public, while the secrecy and security of the watermark depends on a secret key K. The probability of False Positives is extremely small, hence avoiding incidental occurrences of our watermark in random text documents. Majority voting provides security against text addition, deletion, and swapping attacks, further reducing the probability of False Positives. The scheme is secure against the general attacks on text watermarks such as reproduction (photocopying, FAX), reformatting, synonym substitution, text addition, text deletion, text swapping, paragraph shuffling and collusion attacks.

In this paper, we consider a new class of unconditionally secure authentication codes, called linear authentication codes (or linear A-codes). We show that a linear A-code can be characterized by a family of subspaces of a vector space over a finite field. We then derive an upper bound on the size of the source space when other parameters of the system, that is, the sizes of the key space and the authenticator space, and the deception probability, are fixed. We give constructions that are asymptotically close to the bound and show applications of these codes in constructing distributed authentication systems.

A secure multicast scheme allows a group controller (or a centre) to send messages securely over a multicast channel to a dynamically changing group of users.In this paper we show eÆcient methods of establishing a common key among dynamic subgroups of a multicast group such that collusion of up to w malicious users cannot have information about the established key.W e call this re-keying problem.We proposetwo basic constructions, called AND and OR schemes, for multicast re-keying problem using perfect hash families.We show that one scheme is most eÆcient when the subgroup size is close to the full group, and the other when the subgroup size is very small.Both schemes require O(log n) keys storage for both the group controller and the user, and achieve O(log n) communication complexity in their optimal applications.We further show h o w to improve communication eÆciency of the basic OR scheme using erasure codes.Finally we extend the model of the single controller to dynamic controller in which a n y user of the group can establish a common key with a subgroup of the original group, and give extensions of AND and OR schemes for this case.

We present a new application of algebraic curves over finite fields to the constructions of universal hash families and unconditionally secure codes. We show that the constructions derived from the Garcia-Stichtenoth curves yield new classes of authentication codes and universal hash families which are substantially better than those previously known.

We consider the problem of redistributing shares in a secret sharing scheme in such a way that shareholders of a scheme with one access structure can transfer information to a new set of shareholders, resulting in a sharing of the old secret among a new access structure. We describe a number of different scenarios and applications within which such a redistribution might be required, give some techniques for conducting a redistribution, and discuss the optimisation of the efficiency of such a process.