The rising demand for data privacy in cloud-based environments has led to the development of advanced mechanisms for securely managing sensitive information. A prominent solution in this domain is the "Data Privacy Vault," a concept that is being provided commercially by companies such as Hashicorp, Basis Theory, Skyflow Inc., VGS, Evervault, Protegrity, Anonomatic, and BoxyHQ. However, no existing work has rigorously defined the security notions required for a Data Privacy Vault or proven...

Searchable Symmetric Encryption (SSE) has emerged as a promising tool for facilitating efficient query processing over encrypted data stored in un-trusted cloud servers. Several techniques have been adopted to enhance the efficiency and security of SSE schemes. The query processing costs, storage costs and communication costs of any SSE are directly related to the size of the encrypted index that is stored in the server. To our knowledge, there is no work directed towards minimizing the...

The proliferation of attacks to cloud computing, coupled with the vast amounts of data outsourced to online services, continues to raise major concerns about the privacy for end users. Traditional cryptography can help secure data transmission and storage on cloud servers, but falls short when the already encrypted data needs to be processed by the cloud provider. An emerging solution to this challenge is fully homomorphic encryption (FHE), which enables computations directly on encrypted...

Strike-lists are a common technique for rollback and replay prevention in protocols that require that clients remain anonymous or that their current position in a state machine remain confidential. Strike-lists are heavily used in anonymous credentials, e-cash schemes, and trusted execution environments, and are widely deployed on the web in the form of Privacy Pass (PoPETS '18) and Google Private State Tokens. In such protocols, clients submit pseudorandom tokens associated with each...

Users increasingly store their data in the cloud, thereby benefiting from easy access, sharing, and redundancy. To additionally guarantee security of the outsourced data even against a server compromise, some service providers have started to offer end-to-end encrypted (E2EE) cloud storage. With this cryptographic protection, only legitimate owners can read or modify the data. However, recent attacks on the largest E2EE providers have highlighted the lack of solid foundations for this...

Searchable Symmetric Encryption (SSE) has opened up an attractive avenue for privacy-preserved processing of outsourced data on the untrusted cloud infrastructure. SSE aims to support efficient Boolean query processing with optimal storage and search overhead over large real databases. However, current constructions in the literature lack the support for multi-client search and dynamic updates to the encrypted databases, which are essential requirements for the widespread deployment of SSE...

Vehicular Social Networks (VSNs) rely on data shared by users to provide convenient services. Data is outsourced to the cloud server and the distributed roadside unit in VSNs. However, roadside unit has limited resources, so that data sharing process is inefficient and is vulnerable to security threats, such as illegal access, tampering attack and collusion attack. In this article, to overcome the shortcomings of security, we define a chain tolerance semi-trusted model to describe the...

$\newcommand{\gen}{\mathsf{Gen}}\newcommand{\enc}{\mathsf{Enc}}\newcommand{\dec}{\mathsf{Dec}}$ A recent work of Fleischhacker, Larsen, and Simkin (Eurocrypt 2023) shows how to efficiently compress encrypted sparse vectors. Subsequently, Fleischhacker, Larsen, Obremski, and Simkin (Eprint 2023) improve upon their work and provide more efficient constructions solving the same problem. Being able to efficiently compress such vectors is very useful in a variety of applications, such as...

Searchable Symmetric Encryption (SSE) supports efficient keyword searches over encrypted outsourced document collections while minimizing information leakage. All practically efficient SSE schemes supporting conjunctive queries rely crucially on quantum-broken cryptographic assumptions (such as discrete-log hard groups) to achieve compact storage and fast query processing. On the other hand, quantum-safe SSE schemes based on purely symmetric-key crypto-primitives either do not support...

Proof of Storage-time (PoSt) is a cryptographic primitive that enables a server to demonstrate non-interactive continuous avail- ability of outsourced data in a publicly verifiable way. This notion was first introduced by Filecoin to secure their Blockchain-based decentral- ized storage marketplace, using expensive SNARKs to compact proofs. Recent work [2] employs the notion of trapdoor delay function to address the problem of compact PoSt without SNARKs. This approach however entails...

Electronic Medical Records (EMRs) have been utilized in plentiful medical institutions due to their superior convenience and low storage overhead. Nevertheless, it is difficult for medical departments with disparate management regulations to share EMRs through secure communication channels since sensitive EMRs are prone to be tampered with. Therefore, the EMRs should be encrypted before being outsourced to the network servers. Public key Encryption with Keyword Search (PEKS) has the ability...

Dynamic Symmetric Searchable Encryption (SSE) enables a user to outsource the storage of an encrypted database to an untrusted server, while retaining the ability to privately search and update the outsourced database. The performance bottleneck of SSE schemes typically comes from their I/O efficiency. Over the last few years, a line of work has substantially improved that bottleneck. However, all existing I/O-efficient SSE schemes have a common limitation: they are not forward-secure. Since...

Homomorphic encryption (HE) allows for computations over ciphertexts while they are encrypted. Because of this, HE supports the outsourcing of computation on private data. Due to the additional risks caused by data outsourcing, the ability to recover from losses is essential, but doing so on data encrypted under an HE scheme introduces additional challenges for recovery and usability. This work introduces X-Cipher, which aims to make HE ciphertexts resilient by ensuring they are private and...

Secure cryptographic storage is one of the most important issues that both businesses and end-users take into account before moving their data to either centralized clouds or blockchain-based decen- tralized storage marketplace. Recent work [4 ] formalizes the notion of Proof of Storage-Time (PoSt) which enables storage servers to demonstrate non-interactive continuous availability of outsourced data in a publicly verifiable way. The work also proposes a stateful compact PoSt...

We study the task of obliviously compressing a vector comprised of $n$ ciphertexts of size $\xi$ bits each, where at most $t$ of the corresponding plaintexts are non-zero. This problem commonly features in applications involving encrypted outsourced storages, such as searchable encryption or oblivious message retrieval. We present two new algorithms with provable worst-case guarantees, solving this problem by using only homomorphic additions and multiplications by constants. Both of our...

Cloud storage provides highly available and low cost resources to users. However, as massive amounts of outsourced data grow rapidly, an effective data deduplication scheme is necessary. This is a hot and challenging field, in which there are quite a few researches. However, most of previous works require dual-server fashion to be against brute-force attacks and do not support batch checking. It is not practicable for the massive data stored in the cloud. In this paper, we present a secure...

Searchable Symmetric Encryption (SSE) supports efficient yet secure query processing over outsourced symmetrically encrypted databases without the need for decryption. A longstanding open question has been the following: can we design a fast, scalable, linear storage and low-leakage SSE scheme that efficiently supports arbitrary Boolean queries over encrypted databases? In this paper, we present the design, analysis and prototype implementation of the first SSE scheme that efficiently...

We investigate how users of instant messaging (IM) services can acquire strong encryption keys to back up their messages and media with strong cryptographic guarantees. Many IM users regularly change their devices and use multiple devices simultaneously, ruling out any long-term secret storage. Extending the end-to-end encryption guarantees from just message communication to also incorporate backups has so far required either some trust in an IM or outsourced storage provider, or use of...

Proofs of Retrievability (PoR) protocols ensure that a client can fully retrieve a large outsourced file from an untrusted server. Good PoRs should have low communication complexity, small storage overhead and clear security guarantees. We design a good PoR based on a family of graph codes called expander codes. We use expander codes based on graphs derived from point-line incidence relations of finite affine planes. Høholdt et al. showed that, when using Reed-Solomon codes as...

Updatable Encryption (UE) allows to rotate the encryption key in the outsourced storage setting while minimizing the bandwith used. The server can update ciphertexts to the new key using a token provided by the client. UE schemes should provide strong confidentiality guarantees against an adversary that can corrupt keys and tokens. This paper studies the problem of building UE in the group action framework. We introduce a new notion of Mappable Effective Group Action (MEGA) and show that we...

Privacy and security challenges due to the outsourcing of data storage and processing to third-party cloud providers are well known. With regard to data privacy, Oblivious RAM (ORAM) schemes provide strong privacy guarantees by not only hiding the contents of the data (by encryption) but also obfuscating the access patterns of the outsourced data. But most existing ORAM datastores are not fault tolerant in that if the external storage server (which stores encrypted data) or the trusted proxy...

We propose homomorphic algorithms for privacy-preserving applications where we are given an encrypted dataset and we want to compute the number of elements that share a common property. We consider a two-party scenario between a client and a server, where the storage and computation is outsourced to the server. We present two new efficient methods to solve this problem by homomorphically evaluating a selection function encoding the desired property, and counting the number of elements which...

Attribute based encryption (ABE) is a cryptographic technique allowing fine-grained access control by enabling one-to-many encryption. Existing ABE constructions suffer from at least one of the following limitations. First, single point of failure on security meaning that, once an authority is compromised, an adversary can either easily break the confidentiality of the encrypted data or effortlessly prevent legitimate users from accessing data; second, the lack of user and/or attribute...

Proofs of Retrievability (PoR) protocols ensure that a client can fully retrieve a large outsourced file from an untrusted server. Good PoRs should have low communication complexity, small storage overhead and clear security guarantees with tight security bounds. The focus of this work is to design good PoR schemes with simple security proofs. To this end, we use the Constructive Cryptography (CC) setting by Maurer [13]. We propose a framework for the design of secure and efficient PoR...

Many recent studies focus on dynamic searchable encryption (DSE), which provides efficient data-search and data-update services directly on outsourced private data. Most encryption schemes are not optimized for update-intensive cases, which say that the same data record is frequently added and deleted from the database. How to build an efficient and secure DSE scheme for update-intensive data is still challenging. We propose UI-SE, the first DSE scheme that achieves single-round-trip...

With the rapid development of cloud computing, an increasing number of companies are adopting cloud storage technology to reduce overhead. However, to ensure the privacy of sensitive data, the uploaded data need to be encrypted before being outsourced to the cloud. The concept of public-key encryption with keyword search (PEKS) was introduced by Boneh \textit{et al.} to provide flexible usage of the encrypted data. Unfortunately, most of the PEKS schemes are not secure against inside...

Volumetric leakage in encrypted databases had been overlooked by the community for a long time until Kellaris et al. (CCS ’16) proposed the first database reconstruction attack leveraging communication volume. Their attack was soon improved and several query recovery attacks were discovered recently. In response to the advancements of volumetric leakage attacks, volume-hiding searchable symmetric encryption (SSE) schemes have been proposed (Kamara and Moataz, Eurocrypt ’19 & Patel et al.,...

Updatable encryption (UE) is symmetric encryption which additionally supports key rotation. UE was introduced for scenarios where a user stores encrypted data on a cloud and, in order to mitigate secret key leakage, periodically sends a short update token, which the cloud uses to re-encrypt stored data to a fresh key. A long line of research resulted in a wide variety of security properties UE schemes can provide, including confidentiality, integrity protection, and hiding...

Updatable Encryption (UE), as originally defined by Boneh et al. in 2013, addresses the problem of key rotation on outsourced data while maintaining the communication complexity as low as possible. The security definitions for UE schemes have been constantly updated since then. However, the security notion that is best suited for a particular application remains unclear. To solve this problem in the ciphertext-independent setting, we use the Constructive Cryptography (CC) framework defined...

Oblivious RAM (ORAM) enables a user to read/write her outsourced cloud data without access-pattern leakage. Not all users want a fully functional ORAM all the time since it always creates inefficiency. We show that forward-private/backward-private (FP/BP) ORAMs are also good alternatives for reducing the search-pattern leakage of dynamic searchable encryption (DSE). We introduce the FP/BP-ORAM definitions and present LL-ORAM, the first FP/BP-ORAM that achieves near-zero client storage,...

Oblivious Parallel RAM (OPRAM) enables multiple clients to synchronously make read and write accesses to shared memory (more generally, any data-store) whilst hiding the access patterns from the owner/provider of that shared memory. Prior work is best suited to the setting of multiple processors (or cores) within a single client device, and consequently there are shortcomings when applying that work to the multi-client setting where distinct client devices may not trust each other, or may...

We put forward a symmetric encryption primitive tailored towards a specific application: outsourced storage. The setting assumes a memory-bounded computing device that inflates the amount of volatile or permanent memory available to it by letting other (untrusted) devices hold encryptions of information that they return on request. For instance, web servers typically hold for each of the client connections they manage a multitude of data, ranging from user preferences to technical...

A high-quality outsourced storage service is crucial for many existing applications. For example, hospitals and data centers need to guarantee the availability of their systems to perform routine daily activities. Such a system should protect users against downtime and ensure data availability over time. Continuous data availability is a critical property to measure the quality of an outsourced storage service, which implies that outsourced data is continuously available to the server...

Cloud Storage Providers (CSPs) offer solutions to relieve users from locally storing vast amounts of data, including personal and sensitive ones. While users may desire to retain some privacy on the data they outsource, CSPs are interested in reducing the total storage space by employing compression techniques such as deduplication. We propose a new cryptographic primitive that simultaneously realizes both requirements: Multi-Key Revealing Encryption (MKRE). The goal of MKRE is to disclose...

Efficient user revocation and description of the access policy are essential to enhance the practicality of attribute-based encryption (ABE) in real-life scenarios, such as cloud-assisted IoT. Nevertheless, existing ABE works fail to balance the two vital indicators. Motivated by this, in this paper, we present a revocable ciphertext-policy attribute-based encryption with arithmetic span programs (R-CPABE-ASP) for cloud-assisted IoT. For the first time, the presented R-CPABE-ASP achieves...

In cloud-based outsourced storage systems, many users wish to securely store their files for later retrieval, and additionally to share them with other users. These retrieving users may not be online at the point of the file upload, and in fact they may never come online at all. In this asynchoronous environment, key transport appears to be at odds with any demands for forward secrecy. Recently, Boyd et al. (ISC 2018) presented a protocol that allows an initiator to use a modified key...

A symmetric searchable encryption (SSE) scheme allows a client (data owner) to search on encrypted data outsourced to an untrusted cloud server. The search may either be a single keyword search or a complex query search like conjunctive or Boolean keyword search. Information leakage is quite high for dynamic SSE, where data might be updated. It has been proven that to avoid this information leakage an SSE scheme with dynamic data must be forward private. A dynamic SSE scheme is said to be...

Searchable symmetric encryption (SSE) for multi-owner model draws much attention as it enables data users to perform searches over encrypted cloud data outsourced by data owners. However, implementing secure and precise query, efficient search and flexible dynamic system maintenance at the same time in SSE remains a challenge. To address this, this paper proposes secure and efficient multi-keyword ranked search over encrypted cloud data for multi-owner model based on searching adversarial...

With the rapid development of cloud computing, searchable encryption for multiple data owners model (multi-owner model) draws much attention as it enables data users to perform searches on encrypted cloud data outsourced by multiple data owners. However, there are still some issues yet to be solved nowadays, such as precise query, fast query, dimension disaster and flexible system dynamic maintenance. To target these issues, this paper proposes a secure and efficient multi-keyword ranked...

Rapid advances in Internet technologies have fostered the emergence of the “software as a service” model for enterprise computing. The “Database as a Service” model provides users with the power to create, store, modify, and retrieve data from any location, as long as they have access to the Internet. As more and more datasets (including those containing private and sensitive data) are outsourced to remote / cloud storage providers, the data owner, firstly, needs to be certain of the...

Logic locking has been proposed as an obfuscation technique to protect outsourced IC designs from Intellectual Property (IP) piracy by untrusted entities in the design and fabrication process. It obfuscates the netlist by adding extra key-gates, to mislead an adversary, whose aim is to reverse engineer the netlist. The correct functionality will be obtained only if a correct key is applied to the key-gates. The key is written into a nonvolatile memory (NVM) after the fabrication by the IP...

Dynamic searchable symmetric encryption (DSSE) allows a client to search or update over an outsourced encrypted database. Range query is commonly needed (AsiaCrypt'18) but order-preserving encryption approach is vulnerable to reconstruction attacks (SP'17). Previous range-searchable schemes (SIGMOD'16, ESORICS'18) require an ad-hoc instance of encrypted database to store the updates and/or suffer from other shortcomings, some brought by the usage of asymmetric primitives. In this paper,...

Oblivious RAM (ORAM) and private information retrieval (PIR) are classic cryptographic primitives used to hide the access pattern to data whose storage has been outsourced to an untrusted server. Unfortunately, both primitives require considerable overhead compared to plaintext access. For large-scale storage infrastructure with highly frequent access requests, the degradation in response time and the exorbitant increase in resource costs incurred by either ORAM or PIR prevent their usage....

In this work, we study privacy-preserving storage primitives that are suitable for use in data analysis on outsourced databases within the differential privacy framework. The goal in differentially private data analysis is to disclose global properties of a group without compromising any individual’s privacy. Typically, differentially private adversaries only ever learn global properties. For the case of outsourced databases, the adversary also views the patterns of access to data. Oblivious...

While businesses shift their databases to the cloud, they continue to depend on them to operate correctly. Alarmingly, cloud services constantly face threats from exploits in the privileged computing layers (e.g. OS, Hypervisor) and attacks from rogue datacenter administrators, which tamper with the database's storage and cause it to produce incorrect results. Although integrity verification of outsourced storage and file systems is a well-studied problem, prior techniques impose prohibitive...

Searchable encryption has received a significant attention from the research community with various constructions being proposed, each achieving asymptotically optimal complexity for specific metrics (e.g., search, update). Despite their elegancy, the recent attacks and deployment efforts have shown that the optimal asymptotic complexity might not always imply practical performance, especially if the application demands a high privacy. Hence, there is a significant need for searchable...

Proxy Re-Encryption (PRE) allows a ciphertext encrypted under Alice’s public key to be transformed to an encryption under Bob’s public key without revealing either the plaintext or the decryption keys. PRE schemes have clear applications to cryptographic access control by allowing outsourced data to be selectively shared to users via re-encryption to appropriate keys. One concern for this application is that the server should not be able to perform unauthorised re-encryptions. We argue that...

We seek to answer the following question: To what extent can we deduplicate replicated storage? To answer this question, we design ReDup, a secure storage system that provides users with strong integrity, reliability, and transparency guarantees about data that is outsourced at cloud storage providers. Users store multiple replicas of their data at different storage servers, and the data at each storage server is deduplicated across users. Remote data integrity mechanisms are used to check...

Data loss is perceived as one of the major threats for cloud storage. Consequently, the security community developed several challenge-response protocols that allow a user to remotely verify whether an outsourced file is still intact. However, two important practical problems have not yet been considered. First, clients commonly outsource multiple files of different sizes, raising the question how to formalize such a scheme and in particular ensuring that all files can be simultaneously...

The security of data outsourcing mechanisms has become a crucial aspect of today's IT infrastructures and are the cryptographic foundations of real-world applications. The very fundamental goals are ensuring storage integrity and auditability, confidentiality, and access pattern hiding, as well as combinations of all of them. Despite sharing a common setting, security analyses of these tasks are often performed in a stand-alone fashion expressed in different models, which makes it hard to...

Since the development of tree-based Oblivious RAM by Shi et al. (Asiacrypt '11) it has become apparent that privacy preserving outsourced storage can be practical. Although most current constructions follow a client-server model, in many applications it is desirable to share data between different clients, in a way that hides the access patterns, not only from the server, but also between the clients. In this work, we introduce Blurry-ORAM, an extension of Path-ORAM that allows for oblivious...

Proof systems for verifiable computation (VC) have the potential to make cloud outsourcing more trustworthy. Recent schemes enable a verifier with limited resources to delegate large computations and verify their outcome based on succinct arguments: verification complexity is linear in the size of the inputs and outputs (not the size of the computation). However, cloud computing also often involves large amounts of data, which may exceed the local storage and I/O capabilities of the...

This paper proposes MSKT-ORAM, an efficient multiple server ORAM construction, to protect a client’s access pattern to outsourced data. MSKT-ORAM organizes each of the server storage as a k-ary tree and adopts XOR based PIR and a novel delayed eviction technique to optimize both the data query and data eviction process. MSKT-ORAM is proved to protect the data access pattern privacy at a failure probability of $2^{80}$ when $k\geq 128$. Meanwhile, given constant local storage, when $N$ (i.e.,...

While cloud storage services offer manifold benefits such as cost-effectiveness or elasticity, there also exists various security and privacy concerns. Among such concerns, we pay our primary attention to data residency – a notion that requires outsourced data to be retrievable in its entirety from local drives of a storage server in-question. We formulate such notion under a security model called Proofs of Data Residency (PoDR). PoDR can be employed to check whether the data is replicated...

There has been considerable recent interest in ``cloud storage'' wherein a user asks a server to store a large file. One issue is whether the user can verify that the server is actually storing the file, and typically a challenge-response protocol is employed to convince the user that the file is indeed being stored correctly. The security of these schemes is phrased in terms of an extractor which will recover the file given any ``proving algorithm'' that has a sufficiently high success...

Outsourcing data to remote storage servers has become more and more popular, but the related security and privacy concerns have also been raised. To protect the pattern in which a user accesses the outsourced data, various oblivious RAM (ORAM) constructions have been designed. However, when existing ORAM designs are extended to support multi-user scenarios, they become vulnerable to stealthy privacy attacks targeted at revealing the data access patterns of innocent users, even if only one...

With the growing popularity of remote storage, the ability to outsource a large private database yet be able to search on this encrypted data is critical. Searchable symmetric encryption (SSE) is a practical method of encrypting data so that natural operations such as searching can be performed on this data. It can be viewed as an efficient private-key alternative to powerful tools such as fully homomorphic encryption, oblivious RAM, or secure multiparty computation. The main drawbacks of...

Together with its great advantages, cloud storage brought many interesting security issues to our attention. Since 2007, with the first efficient storage integrity protocols Proofs of Retrievability (PoR) of Juels and Kaliski, and Provable Data Possession (PDP) of Ateniese et al., many researchers worked on such protocols. The first proposals worked for static or limited dynamic data, whereas later proposals enabled fully dynamic data integrity and retrievability. Since the beginning, the...

Storage requirements for visual data have been increasing in recent years, following the emergence of many new highly interactive multimedia services and applications for both personal and corporate use. This has been a key driving factor for the adoption of cloud-based data outsourcing solutions. However, outsourcing data storage to the Cloud also leads to new challenges that must be carefully addressed, especially regarding privacy. In this paper we propose a secure framework for...

One of the most important benefits of public cloud storage is outsourcing of management and maintenance with easy accessibility and retrievability over the internet. However, outsourcing data on the cloud brings new challenges such as integrity verification and privacy of data. More concretely, once the users outsource their data on the cloud they have no longer physical control over the data and this leads to the integrity protection issue. Hence, it is crucial to guarantee proof of data...

Cyber-physical-social system (CPSS) allows individuals to share personal information collected from not only cyberspace, but also physical space. This has resulted in generating numerous data at a user's local storage. However, it is very expensive for users to store large data sets, and it also causes problems in data management. Therefore, it is of critical importance to outsource the data to cloud servers, which provides users an easy, cost-effective and flexible way to manage data....

Cloud computing has greatly facilitated large-scale data outsourcing due to its cost efficiency, scalability and many other advantages. Subsequent privacy risks force data owners to encrypt sensitive data, hence making the outsourced data no longer searchable. Searchable Symmetric Encryption (SSE) is an advanced cryptographic primitive addressing the above issue, which maintains efficient keyword search over encrypted data without disclosing much information to the storage provider. Existing...

The problem of verifiable data streaming (VDS) considers a client with limited computational and storage capacities that streams an a-priori unknown number of elements to an untrusted server. The client may retrieve and update any outsourced element. Other parties may verify each outsourced element's integrity using the client's public-key. All previous VDS constructions incur a bandwidth and computational overhead on both client and server side, which is at least logarithmic in the number...

Cloud storage has rapidly become a cornerstone of many IT infrastructures, constituting a seamless solution for the backup, synchronization, and sharing of large amounts of data. Putting user data in the direct control of cloud service providers, however, raises security and privacy concerns related to the integrity of outsourced data, the accidental or intentional leakage of sensitive information, the profiling of user activities and so on. Furthermore, even if the cloud provider is...

This paper considers the problem of secure storage of outsourced data in a way that permits deduplication. We are for the first time able to provide privacy for messages that are both correlated and dependent on the public system parameters. The new ingredient that makes this possible is interaction. We extend the message-locked encryption (MLE) primitive of prior work to interactive message-locked encryption (iMLE) where upload and download are protocols. Our scheme, providing security for...

Private Information Retrieval (PIR) protects users' privacy in outsourced storage applications and can be achieved using additively homomorphic encryption schemes. Several PIR schemes with a “real world” level of practicality, both in terms of computational and communication complexity, have been recently studied and implemented. One of the possible building block is a conceptually simple and computationally efficient protocol proposed by Trostle and Parrish at ISC 2010, that relies on an...

The problem of securely outsourcing computation to an untrusted server gained momentum with the recent penetration of cloud computing services. The ultimate goal in this setting is to design efficient protocols that minimize the computational overhead of the clients and instead rely on the extended resources of the server. In this paper, we focus on the outsourced database search problem which is highly motivated in the context of delegatable computing since it offers storage alternatives...

In secure delegatable computation, computationally weak devices (or clients) wish to outsource their computation and data to an untrusted server in the cloud. While most earlier work considers the general question of how to securely outsource any computation to the cloud server, we focus on concrete and important functionalities and give the first protocol for the pattern matching problem in the cloud. Loosely speaking, this problem considers a text $T$ that is outsourced to the cloud...

This paper proposes KT-ORAM, a new hybrid ORAM-PIR construction, to protect a client's access pattern to outsourced data. KT-ORAM organizes the server storage as a $k$-ary tree with each node acting as a fully-functional PIR storage, and adopts a novel delayed eviction technique to optimize the eviction process. KT-ORAM is proved to protect the data access pattern privacy at a failure probability negligible in $N$ ($N$ is the number of exported data blocks), when system parameter $k=\log N$....

Big data and its applications are attracting more and more research interests in recent years. As the new generation distributed computing platform, cloud computing is believed to be the most potent platform. With the data no longer under users' direct control, data security in cloud computing is becoming one of the most obstacles of the proliferation of cloud. In order to improve service reliability and availability, storing multiple replicas along with original datasets is a common...

Multi-Authority Attribute-Based Encryption (MA-ABE) is an emerging cryptographic primitive for enforcing fine-grained attribute-based access control on the outsourced data in cloud storage. However, most of the previous multi-authority attribute-based systems are either proven security in a weak model or lack of efficiency in user revocation. In this paper, we propose a novel multi-authority attribute-based data access control system for cloud storage. We construct a new multi-authority...

Oblivious RAM (ORAM) has recently attracted a lot of interest since it can be used to protect the privacy of data user's data access pattern from (honest but curious) outsourced storage. This is achieved by simulating each original data read or write operation with some read and write operations on some real and dummy data items. This paper proposes two single-server write-only ORAM schemes and one multi-server write-only ORAM scheme, which simulate only the write operations and protect only...

For securing databases outsourced to the cloud, it is important to allow cloud users to verify that their queries to the cloud-hosted databases are correctly executed by the cloud. Existing solutions on this issue suffer from a high communication cost, a heavy storage overhead or an overwhelming computational cost on clients. Besides, only simple SQL queries (e.g., selection query, projection query, weighted sum query, etc) are supported in existing solutions. For practical considerations,...

Data outsourcing is a growing business model offering services to individuals and enterprises for processing and storing a huge amount of data. It is not only economical but also promises higher availability, scalability, and more effective quality of service than in-house solutions. Despite all its benefits, data outsourcing raises serious security concerns for preserving data confidentiality. There are solutions for preserving confidentiality of data while supporting search on the data...

We address the problem in which a client stores a large amount of data with an untrusted server in such a way that, at any moment, the client can ask the server to compute a function on some portion of its outsourced data. In this scenario, the client must be able to efficiently verify the correctness of the result despite no longer knowing the inputs of the delegated computation, it must be able to keep adding elements to its remote storage, and it does not have to fix in advance (i.e., at...

When outsourcing large sets of data to the cloud, it is desirable for clients to efficiently check, whether all outsourced data is still retrievable at any later point in time without requiring to download all of it. Provable data possession (PDP)/proofs of retrievability (PoR), for which various constructions exist, are concepts to solve this issue. Interestingly, by now, no PDP/PoR scheme leading to an efficient construction supporting both private and public verifiability simultaneously...

Structure-preserving signatures (SPS) are signature schemes where messages, signatures and public keys all consist of elements of a group over which a bilinear map is efficiently computable. This property makes them useful in cryptographic protocols as they nicely compose with other algebraic tools (like the celebrated Groth-Sahai proof systems). In this paper, we consider SPS systems with homomorphic properties and suggest applications that have not been provided before (in...

Oblivious RAM (ORAM) allows a client to access her data on a remote server while hiding the access pattern (which locations she is accessing) from the server. Beyond its immediate utility in allowing private computation over a client's outsourced data, ORAM also allows mutually distrustful parties to run secure-computations over their joint data with sublinear on-line complexity. In this work we revisit the tree-based ORAM of Shi et al. [SCSL11] and show how to optimize its performance as a...

With the growing trend toward using outsourced storage, the problem of efficiently checking and proving data integrity needs more consideration. Starting with PDP and POR schemes in 2007, many cryptography and security researchers have addressed the problem. After the first solutions for static data, dynamic versions were developed (e.g., DPDP). Researchers also considered distributed versions of such schemes. Alas, in all such distributed schemes, the client needs to be aware of the...

With the rising trend of outsourcing databases to the cloud, it is important to allow clients to securely verify that their queries on the outsourced databases are correctly executed by the cloud. Existing solutions on this issue either suffer from a high communication cost, or introduce too much computational cost on the client side. Besides, so far only four types of SQL queries (i.e., selection query, projection query, join query and weighted sum query) are supported in existing...

We formalize a new cryptographic primitive, Message-Locked Encryption (MLE), where the key under which encryption and decryption are performed is itself derived from the message. MLE provides a way to achieve secure deduplication (space-efficient secure outsourced storage), a goal currently targeted by numerous cloud-storage providers. We provide definitions both for privacy and for a form of integrity that we call tag consistency. Based on this foundation, we make both practical and...

As databases are increasingly outsourced to the cloud, data owners require various security assurances. This paper investigates one particular assurance, query integrity, by which a database querier (either the data owner or a third party) can verify that its queries were faithfully executed by the cloud server with respect to the outsourced database. Query integrity is investigated in the setting of dynamic databases, where the outsourced databases can be updated by the data owners as...

In cloud storage service, clients upload their data together with authentication information to cloud storage server. To ensure the availability and integrity of clients' stored data, cloud server(CS) must prove to a verifier that he is actually storing all of the client's data unchanged. And, enabling public auditability for cloud storage is of critical importance to users with constrained computing resources, who can resort to a third party auditor (TPA) to check the integrity of...

The emergence and wide availability of remote storage service providers prompted work in the security community that allows a client to verify integrity and availability of the data that she outsourced to an untrusted remove storage server at a relatively low cost. Most recent solutions to this problem allow the client to read and update (i.e., insert, modify, or delete) stored data blocks while trying to lower the overhead associated with verifying the integrity of the stored data. In this...

Cloud Computing as the on-demand and remote provision of computational resources has been eagerly waited for a long time as a computing utility. It helps users to store their data in the cloud and enjoy the high quality service. However, users do not have physical possession on their own data, hence it is indispensable to create mechanisms on how to protect the security of the data stored. Thus, some auditing protocols are introduced to ensure authenticity and integrity of the outsourced...

Both security and efficiency are crucial to the success of cloud storage. So far, security and efficiency of cloud storage have been separately investigated as follows: On one hand, security notions such as Proof of Data Possession (\PDP) and Proof of Retrievability (\POR) have been introduced for detecting the tamperation of data stored in the cloud. One the other hand, the notion of Proof of Ownership (\POW) has also been proposed to alleviate the cloud server from storing multiple copies...

We study the verification of \emph{set operations} in the model of \emph{authenticated data structures}, namely the problem of cryptographically checking the correctness of outsourced set operations performed by an untrusted \emph{server} over a dynamic collection of sets that are owned (and updated) by a trusted \emph{source}. We present a new authenticated data structure scheme that allows any entity to \emph{publicly} verify the correctness of primitive sets operations such as...

Using Cloud Storage, users can remotely store their data and enjoy the on-demand high quality applications and services from a shared pool of configurable computing resources, without the burden of local data storage and maintenance. However, the fact that users no longer have physical possession of the outsourced data makes the data integrity protection in Cloud Computing a formidable task, especially for users with constrained computing resources. Moreover, users should be able to just use...

As storage-outsourcing services and resource-sharing networks have become popular, the problem of efficiently proving the integrity of data stored at untrusted servers has received increased attention. In the provable data possession (PDP) model, the client pre-processes the data and then sends it to an untrusted server for storage, while keeping a small amount of meta-data. The client later asks the server to prove that the stored data has not been tampered with or deleted (without...

Storage outsourcing is a rising trend which prompts a number of interesting security issues, many of which have been extensively investigated in the past. However, Provable Data Possession (PDP) is a topic that has only recently appeared in the research literature. The main issue is how to frequently, efficiently and securely verify that a storage server is faithfully storing its client’s (potentially very large) outsourced data. The storage server is assumed to be untrusted in terms of both...