Dynamic Searchable Symmetric Encryption (DSSE) provides efficient techniques for securely searching and updating an encrypted database. However, efficient DSSE schemes leak some sensitive information to the server. Recent works have implemented forward and backward privacy as security properties to reduce the amount of information leaked during update operations. Many attacks have shown that leakage from search operations can be abused to compromise the privacy of client queries. However, the attack literature has not rigorously investigated techniques to abuse update leakage. In this work, we investigate update leakage under DSSE schemes with forward and backward privacy from the perspective of a passive adversary. We propose two attacks based on a maximum likelihood estimation approach, the UFID Attack and the UF Attack, which target forward-private DSSE schemes with no backward privacy and Level 2 backward privacy, respectively. These are the first attacks to show that it is possible to leverage the frequency and contents of updates to recover client queries. We propose a variant of each attack which allows the update leakage to be combined with search pattern leakage to achieve higher accuracy. We evaluate our attacks against a real-world dataset and show that using update leakage can improve the accuracy of attacks against DSSE schemes, especially those without backward privacy. / Master of Science / Remote data storage is a ubiquitous application made possible by the prevalence of cloud computing. Dynamic Symmetric Searchable Encryption (DSSE) is a privacy-preserving technique that allows a client to search and update a remote encrypted database while greatly restricting the information the server can learn about the client's data and queries. However, all efficient DSSE schemes have some information leakage that can allow an adversarial server to infringe upon the privacy of clients. Many prior works have studied the dangers of leakage caused by the search operation, but have neglected the leakage from update operations. As such, researchers have been unsure about whether update leakage poses a threat to user privacy. To address this research gap, we propose two new attacks which exploit leakage from DSSE update operations. Our attacks are aimed at learning what keywords a client is searching and updating, even in DSSE schemes with forward and backward privacy, two security properties implemented by the strongest DSSE schemes. Our UFID Attack compromises forward-private schemes while our UF Attack targets schemes with both forward privacy and Level 2 backward privacy. We evaluate our attacks on a real-world dataset and show that they efficiently compromise client query privacy under realistic conditions.

Large-scale data management systems rely more and more on cloud storage, where the need for efficient search capabilities clashes with the need for data confidentiality. Encryption and efficient accessibility are naturally at odds, as for instance strong encryption necessitates that ciphertexts reveal nothing about underlying data. Searchable encryption is an active field in cryptography studying encryption schemes that provide varying levels of efficiency, functionality, and security, and efficient searchable encryption focuses on schemes enabling sub-linear (in the size of the database) search time. I present the first cryptographic study of efficient searchable symmetric encryption schemes supporting two types of search queries, range queries and error-tolerant queries. The natural solution to accommodate efficient range queries on ciphertexts is to use order-preserving encryption (OPE). I propose a security definition for OPE schemes, construct the first OPE scheme with provable security, and further analyze security by characterizing one-wayness of the scheme. Efficient error-tolerant queries are enabled by efficient fuzzy-searchable encryption (EFSE). For EFSE, I introduce relevant primitives, an optimal security definition and a (somewhat space-inefficient, but in a sense efficient as possible) scheme achieving it, and more efficient schemes that achieve a weaker, but practical, security notion. In all cases, I introduce new appropriate security definitions, construct novel schemes, and prove those schemes secure under standard assumptions. The goal of this line of research is to provide constructions and provable security analysis that should help practitioners decide whether OPE or FSE provides a suitable efficiency-security-functionality tradeoff for a given application.

La recherche sur les bases de données chiffrées vise à rendre efficace une tâche apparemment simple : déléguer le stockage de données à un serveur qui ne serait pas de confiance, tout en conservant des fonctionnalités de recherche. Avec le développement des services de stockage dans le Cloud, destinés aussi bien aux entreprises qu'aux individus, la mise au point de solutions efficaces à ce problème est essentielle pour permettre leur déploiement à large échelle. Le principal problème de la recherche sur bases de données chiffrées est qu'un schéma avec une sécurité ''parfaite'' implique un surcoût en termes de calcul et de communication qui serait inacceptable pour des fournisseurs de services sur le Cloud ou pour les utilisateurs - tout du moins avec les technologies actuelles. Cette thèse propose et étudie de nouvelles notions de sécurité et de nouvelles constructions de bases de données chiffrées permettant des recherches efficaces et sûres. En particulier, nous considérons la confidentialité persistante et la confidentialité future de ces bases de données, ce que ces notions impliquent en termes de sécurité et d'efficacité, et comment les réaliser. Ensuite, nous montrons comment protéger les utilisateurs de bases de données chiffrées contre des attaques actives de la part du serveur hébergeant la base, et que ces protections ont un coût inévitable. Enfin, nous étudions les attaques existantes contre ces bases de données chiffrées et comment les éviter. / Searchable encryption aims at making efficient a seemingly easy task: outsourcing the storage of a database to an untrusted server, while keeping search features. With the development of Cloud storage services, for both private individuals and businesses, efficiency of searchable encryption became crucial: inefficient constructions would not be deployed on a large scale because they would not be usable. The key problem with searchable encryption is that any construction achieving ''perfect security'' induces a computational or a communicational overhead that is unacceptable for the providers or for the users --- at least with current techniques and by today's standards. This thesis proposes and studies new security notions and new constructions of searchable encryption, aiming at making it more efficient and more secure. In particular, we start by considering the forward and backward privacy of searchable encryption schemes, what it implies in terms of security and efficiency, and how we can realize them. Then, we show how to protect an encrypted database user against active attacks by the Cloud provider, and that such protections have an inherent efficiency cost. Finally, we take a look at existing attacks against searchable encryption, and explain how we might thwart them.

Encrypting data is a solution to enhance the privacy and confidentiality of the data owners when outsourcing storage to cloud storage providers. However, using conventional encryption algorithms would render search queries based on the content of the data useless. One solution to that problem is encrypting the data using a searchable encryption scheme which allows querying the encrypted data by its contents while keeping it encrypted on the cloud to maintain the privacy and confidentiality of the data. One sector that might benefit from using a searchable encryption scheme is the public procurement sector. Preparing to bid on public procurement can be complex because the potential bidder needs to fulfill requirements to confirm that they are eligible. The information and documents needed to win a bid are confidential. Thus, privacy is essential. Tendium offers services to potential bidders to manage their documents with potentially sensitive data in a cloud-based environment. Clients using this service can benefit from using a searchable encryption scheme. A searchable encryption scheme was designed and implemented as a proof of concept. The implemented scheme builds an index database based on keywords extracted from the documents where each keyword is encrypted and stored in the database. Each entry in the database has encrypted keywords and associated identifiers for the corresponding document that the keyword occurs in. The documents are then encrypted using the AES encryption algorithm. Searching the database is performed by utilizing deterministic cryptographic primitives to encrypt the searched keywords and query the database for the resulting ciphertext, which returns its corresponding document identifiers. The document identifiers are used to retrieve the encrypted documents. The documents are decrypted after they are retrieved. The implemented scheme has a linear time complexity relative to the number of words in the document when encrypting a document. The implemented scheme utilizes MongoDB for its index database. It is demonstrated that the scheme is efficient and performs queries for single keyword search and multi-keyword search in less than one millisecond. / Kryptering av data är en lösning för att förbättra integriteten och sekretessen för dataägarna vid outsourcing av lagring till molnlagringsleverantörer. Använ- -dning av konventionella krypteringsalgoritmer skulle dock göra sökfrågor baserat på innehållet i data värdelös. En lösning på det problemet är att kryptera data med hjälp av ett sökbart krypteringsschema som gör det möjligt att söka efter krypterade data med dess innehåll och samtidigt hålla den krypterad på molnet för att upprätthålla upprätthålla dataskyddet och konfident- -ialiteten. En sektor som kan ha nytta av att använda ett sökbart krypteringssche- -ma är sektorn för offentliga upphandlingar. Att förbereda sig för att lägga ett bud på en offentlig upphandling kan vara komplext eftersom den potentiella budgivaren måste uppfylla kraven för att bekräfta att de är berättigade. Informat- -ionen och dokumenten som behövs för att vinna ett bud är konfidentiella. Därför är integritet viktigt. Tendium erbjuder tjänster för att hjälpa potentiella anbudsgivare hantera sina dokument i en molnbaserad miljö. Kunder som använder denna tjänst kan dra nytta av att använda ett sökbart krypteringssc- -hema. Ett sökbart krypteringsschema utformades och implementerades som ett bevis på koncept. Det implementerade schemat bygger en indexdatabas baserad på nyckelord extraherade från dokumenten där varje nyckelord är krypterat och lagrat i databasen. Varje objekt i databasen har krypterade sökord och tillhörande identifierare för motsvarande dokument som sökordet förekommer i. Dokumenten krypteras sedan med AES-krypteringsalgoritmen. Sökning i databasen utförs genom att använda deterministiska kryptografiska primitiv för att kryptera de sökte sökorden och söka databasen efter den resulterande krypterade texten, som returnerar motsvarande dokumentidentifierare. Dokum- -entidentifierarna används för att hämta de krypterade dokumenten. Dokument- -en avkrypteras efter att de har hämtats. Det implementerade schemat har en linjär tidskomplexitet i förhållande till antalet ord i dokumentet vid kryptering av ett dokument. Det implementerade schemat använder MongoDB för sin indexdatabas. Det har visat sig att schemat är effektivt och utför sökfrågor för enstaka nyckelord och flera nyckelord på mindre än en millisekund.

No description available.

Cloud computing which provides computation and storage resources in a pay-per-usage manner has emerged as the most popular computation model nowadays. Under the new paradigm, users are able to request computation resources dynamically in real-time to accommodate their workload requirements. The flexible resource allocation feature endows cloud computing services with the capability to offer affordable and efficient computation services. However, moving data and applications into the cloud exposes a privacy leakage risk of the user data. As the growing awareness of data privacy, more and more users begin to choose proactive protection for their data in the cloud through data encryption. One major problem of data encryption is that it hinders many necessary data utilization functions since most of the functions cannot be directly applied to the encrypted data. The problem could potentially jeopardize the popularity of the cloud computing, therefore, achieving efficient data utilization over encrypted data while preserving user data privacy is an important research problem in cloud computing. The focus of this dissertation is to design secure and efficient schemes to address essential data utilization functions over encrypted data in cloud computing. To this end, we studied three problems in this research area. The first problem that is studied in this dissertation is fuzzy multi-keyword search over encrypted data. As fuzzy search is one of the most useful and essential data utilization functions in our daily life, we propose a novel design that incorporates Bloom filter and Locality-Sensitive Hashing to fulfill the security and function requirements of the problem. Secondly, we propose a secure index which is based on the most popular index structure, i.e., the inverted index. Our innovative design provides privacy protection over the secure index, the user query as well as the search pattern and the search result. Also, users can verify the correctness of the search results to ensure the proper computation is performed by the cloud. Finally, we focus ourselves on the privacy-sensitive data application in cloud computing, i.e., genetic testings over DNA sequences. To provide secure and efficient genetic testings in the cloud, we utilize Predicate Encryption and design a bilinear pairing based secure sequence matching scheme to achieve strong privacy guarantee while fulfilling the functionality requirement efficiently. In all of the three research thrusts, we present thorough theoretical security analysis and extensive simulation studies to evaluate the performance of the proposed schemes. The results demonstrate that the proposed schemes can effectively and efficiently address the challenging problems in practice. / Ph. D.

In the Master’s thesis were described privacy protection problems while using cloud technologies. Some of the problems can be solved with help of homomorphic encryption, data splitting or searchable encryption. These techniques were described and compared by provided security, privacy protection and efficiency. The data splitting technique was chosen and implemented in the C language. Afterwards a performance of the implemented solution was compared to AES encryption/decryption performance. An application for secured data storing in cloud was designed and implemented. This application is using the implemented data splitting technique and third-party application CloudCross. The designed application provides command line interface (CLI) and graphical user interface (GUI). GUI extends the capabilities of CLI with an ability to register cloud and with an autodetection of registered clouds. The process of uploading/downloading the data to/from cloud storage is transparent and it does not overload the user with technical details of used data splitting technique.

In the Master’s thesis were described privacy protection problems while using cloud technologies. Some of the problems can be solved with help of homomorphic encryption, data splitting or searchable encryption. These techniques were described and compared by provided security, privacy protection and efficiency. The data splitting technique was chosen and implemented in the C language. Afterwards a performance of the implemented solution was compared to AES encryption/decryption performance. An application for secured data storing in cloud was designed and implemented. This application is using the implemented data splitting technique and third-party application CloudCross. The designed application provides command line interface (CLI) and graphical user interface (GUI). GUI extends the capabilities of CLI with an ability to register cloud and with an autodetection of registered clouds. The process of uploading/downloading the data to/from cloud storage is transparent and it does not overload the user with technical details of used data splitting technique.

In the Master’s thesis were described privacy protection problems while using cloud technologies. Some of the problems can be solved with help of homomorphic encryption, data splitting or searchable encryption. These techniques were described and compared by provided security, privacy protection and efficiency. The data splitting technique was chosen and implemented in the C language. Afterwards a performance of the implemented solution was compared to AES encryption/decryption performance. An application for secured data storing in cloud was designed and implemented. This application is using the implemented data splitting technique and third-party application CloudCross. The designed application provides command line interface (CLI) and graphical user interface (GUI). GUI extends the capabilities of CLI with an ability to register cloud and with an autodetection of registered clouds. The process of uploading/downloading the data to/from cloud storage is transparent and it does not overload the user with technical details of used data splitting technique.

Les services cloud offrent des coûts réduits, une élasticité et un espace de stockage illimité qui attirent de nombreux utilisateurs. Le partage de fichiers, les plates-formes collaboratives, les plateformes de courrier électroniques, les serveurs de sauvegarde et le stockage de fichiers sont parmi les services qui font du cloud un outil essentiel pour une utilisation quotidienne. Actuellement, la plupart des systèmes d'exploitation proposent des applications de stockage externalisées intégrées, par conception, telles que One Drive et iCloud, en tant que substituts naturels succédant au stockage local. Cependant, de nombreux utilisateurs, même ceux qui sont disposés à utiliser les services susmentionnés, restent réticents à adopter pleinement le stockage et les services sous-traités dans le cloud. Les préoccupations liées à la confidentialité des données augmentent l'incertitude pour les utilisateurs qui conservent des informations sensibles. Il existe de nombreuses violations récurrentes de données à l'échelle mondiale qui ont conduit à la divulgation d'informations sensibles par les utilisateurs. Pour en citer quelques-uns : une violation de Yahoo fin 2014 et annoncé publiquement en Septembre 2016, connue comme la plus grande fuite de données de l'histoire d'Internet, a conduit à la divulgation de plus de 500 millions de comptes utilisateur ; une infraction aux assureurs-maladie, Anthem en février 2015 et Premera BlueCross BlueShield en mars 2015, qui a permis la divulgation de renseignements sur les cartes de crédit, les renseignements bancaires, les numéros de sécurité sociale, pour des millions de clients et d'utilisateurs. Une contre-mesure traditionnelle pour de telles attaques dévastatrices consiste à chiffrer les données des utilisateurs afin que même si une violation de sécurité se produit, les attaquants ne peuvent obtenir aucune information à partir des données. Malheureusement, cette solution empêche la plupart des services du cloud, et en particulier, la réalisation des recherches sur les données externalisées.Les chercheurs se sont donc intéressés à la question suivante : comment effectuer des recherches sur des données chiffrées externalisées tout en préservant une communication, un temps de calcul et un stockage acceptables ? Cette question avait plusieurs solutions, reposant principalement sur des primitives cryptographiques, offrant de nombreuses garanties de sécurité et d'efficacité. Bien que ce problème ait été explicitement identifié pendant plus d'une décennie, de nombreuses dimensions de recherche demeurent non résolues. Dans ce contexte, le but principal de cette thèse est de proposer des constructions pratiques qui sont (1) adaptées aux déploiements dans les applications réelles en vérifiant les exigences d'efficacité nécessaires, mais aussi, (2) en fournissant de bonnes assurances de sécurité. Tout au long de notre recherche, nous avons identifié le chiffrement cherchable (SSE) et la RMA inconsciente (ORAM) comme des deux potentielles et principales primitives cryptographiques candidates aux paramètres des applications réelles. Nous avons identifié plusieurs défis et enjeux inhérents à ces constructions et fourni plusieurs contributions qui améliorent significativement l'état de l'art.Premièrement, nous avons contribué à rendre les schémas SSE plus expressifs en permettant des requêtes booléennes, sémantiques et de sous-chaînes. Cependant, les praticiens doivent faire très attention à préserver l'équilibre entre la fuite d'information et le degré d'expressivité souhaité. Deuxièmement, nous améliorons la bande passante de l'ORAM en introduisant une nouvelle structure récursive de données et une nouvelle procédure d'éviction pour la classe d'ORAM ; nous introduisons également le concept de redimensionnabilibté dans l'ORAM qui est une caractéristique requise pour l'élasticité de stockage dans le cloud. / Cloud services offer reduced costs, elasticity and a promised unlimited managed storage space that attract many end-users. File sharing, collaborative platforms, email platforms, back-up servers and file storage are some of the services that set the cloud as an essential tool for everyday use. Currently, most operating systems offer built-in outsourced cloud storage applications, by design, such as One Drive and iCloud, as natural substitutes succeeding to the local storage. However, many users, even those willing to use the aforementioned cloud services, remain reluctant towards fully adopting cloud outsourced storage and services. Concerns related to data confidentiality rise uncertainty for users maintaining sensitive information. There are many, recurrent, worldwide data breaches that led to the disclosure of users' sensitive information. To name a few: a breach of Yahoo late 2014 and publicly announced on September 2016, known as the largest data breach of Internet history, led to the disclosure of more than 500 million user accounts; a breach of health insurers, Anthem in February 2015 and Premera BlueCross BlueShield in March 2015, that led to the disclosure of credit card information, bank account information, social security numbers, data income and more information for more than millions of customers and users. A traditional countermeasure for such devastating attacks consists of encrypting users' data so that even if a security breach occurs, the attackers cannot get any information from the data. Unfortunately, this solution impedes most of cloud services, and in particular, searching on outsourced data. Researchers therefore got interrested in the fllowing question: how to search on outsourced encrypted data while preserving efficient communication, computation and storage overhead? This question had several solutions, mostly based on cryptographic primitives, offering numerous security and efficiency guarantees. While this problem has been explicitly identified for more than a decade, many research dimensions remain unsolved. The main goal of this thesis is to come up with practical constructions that are (1) suitable for real life deployments verifying necessary efficiency requirements, but also, (2) providing good security insurances. Throughout our reseach investigation, we identified symmetric searchable encryption (SSE) and oblivious RAM (ORAM) as the two potential and main cryptographic primitives' candidate for real life settings. We have recognized several challenges and issues inherent to these constructions and provided a number of contributions that improve upon the state of the art. First, we contributed to make SSE schemes more expressive by enabling Boolean, semantic, and substring queries. Practitioners, however, need to be very careful about the provided balance between the security leakage and the degree of desired expressiveness. Second, we improve ORAM's bandwidth by introducing a novel recursive data structure and a new eviction procedure for the tree-based class of ORAM contructions, but also, we introduce the concept of resizability in ORAM which is a required feature for cloud storage elasticity.