Searchable Encryption, 2014

	Searchable Encryption 2014

The phrase “searchable encryption” deals with the problems related to protecting privacy while concurrently allowing for searches within data, particularly in the cloud. The research presented here addresses several approaches. All of the research cited here was presented in 2014.

Florian Hahn, Florian Kerschbaum; “Searchable Encryption with Secure and Efficient Updates,” CCS ’14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 310-320. doi:10.1145/2660267.2660297
Abstract: Searchable (symmetric) encryption allows encryption while still enabling search for keywords. Its immediate application is cloud storage where a client outsources its files while the (cloud) service provider should search and selectively retrieve those. Searchable encryption is an active area of research and a number of schemes with different efficiency and security characteristics have been proposed in the literature. Any scheme for practical adoption should be efficient, i.e. have sub-linear search time, dynamic, i.e. allow updates, and semantically secure to the most possible extent. Unfortunately, efficient, dynamic searchable encryption schemes suffer from various drawbacks. Either they deteriorate from semantic security to the security of deterministic encryption under updates, they require to store information on the client and for deleted files and keywords or they have very large index sizes. All of this is a problem, since we can expect the majority of data to be later added or changed. Since these schemes are also less efficient than deterministic encryption, they are currently an unfavorable choice for encryption in the cloud. In this paper we present the first searchable encryption scheme whose updates leak no more information than the access pattern, that still has asymptotically optimal search time, linear, very small and asymptotically optimal index size and can be implemented without storage on the client (except the key). Our construction is based on the novel idea of learning the index for efficient access from the access pattern itself. Furthermore, we implement our system and show that it is highly efficient for cloud storage.
Keywords: dynamic searchable encryption, searchable encryption, secure index, update (ID#: 15-6102)
URL: http://doi.acm.org/10.1145/2660267.2660297

Gabriel Ghinita, Razvan Rughinis; “An Efficient Privacy-Preserving System for Monitoring Mobile Users: Making Searchable Encryption Practical,” CODASPY ’14 Proceedings of the 4th ACM Conference on Data and Application Security and Privacy, March 2014, Pages 321-332. doi:10.1145/2557547.2557559
Abstract: Monitoring location updates from mobile users has important applications in several areas, ranging from public safety and national security to social networks and advertising. However, sensitive information can be derived from movement patterns, so protecting the privacy of mobile users is a major concern. Users may only be willing to disclose their locations when some condition is met, for instance in proximity of a disaster area, or when an event of interest occurs nearby. Currently, such functionality is achieved using searchable encryption. Such cryptographic primitives provide provable guarantees for privacy, and allow decryption only when the location satisfies some predicate. Nevertheless, they rely on expensive pairing-based cryptography (PBC), and direct application to the domain of location updates leads to impractical solutions.  We propose secure and efficient techniques for private processing of location updates that complement the use of PBC and lead to significant gains in performance by reducing the amount of required pairing operations. We also implement two optimizations that further improve performance: materialization of results to expensive mathematical operations, and parallelization. Extensive experimental results show that the proposed techniques significantly improve performance compared to the baseline, and reduce the searchable encryption overhead to a level that is practical in a computing environment with reasonable resources, such as the cloud.
Keywords: location privacy, pairing-based cryptography (ID#: 15-6103)
URL: http://doi.acm.org/10.1145/2557547.2557559

Dalia Khader; “Attribute Based Search in Encrypted Data: ABSE,” WISCS ’14 Proceedings of the 2014 ACM Workshop on Information Sharing & Collaborative Security, November 2014, Pages 31-40. doi:10.1145/2663876.2663878
Abstract: Searchable encryption enables users to delegate search functionalities to third-parties without giving them the ability to decrypt. Existing schemes assume that the sender knows the identity of the receiver. In this paper we relax this assumption by proposing the first Attribute Based Searchable Encryption Scheme (ABSE). An ABSE is a type of public key encryption with keyword search that allows the user encrypting the data to specify a policy that determines, among the users of the system, who is eligible to decrypt and search the data. Each user of the system owns a set of attributes and the policy is a function of these attributes expressed as a predicate. Only members who own sufficient attributes to satisfy that policy can send the server a valid search query. In our work we introduce the concept of a secure ABSE by defining the functionalities and the relevant security notions such as correctness, chosen keyword attacks, and attribute forgeability attacks. Our definitions are based on provable security formalizations. We further propose a secure construction of an ABSE based on bilinear maps. We illustrate the use of our proposed scheme in a shared storage for medical records.
Keywords: attribute based systems, public key cryptography, searchable encryption (ID#: 15-6104)
URL:  http://doi.acm.org/10.1145/2663876.2663878

Mehmet Kuzu, Mohammad Saiful Islam, Murat Kantarcioglu; “Efficient Privacy-Aware Search over Encrypted Databases,” CODASPY ’14 Proceedings of the 4th ACM Conference on Data and Application Security and Privacy, March 2014, Pages 249-256. doi:10.1145/2557547.2557570
Abstract: In recent years, database as a service (DAS) model where data management is outsourced to cloud service providers has become more prevalent. Although DAS model offers lower cost and flexibility, it necessitates the transfer of potentially sensitive data to untrusted cloud servers. To ensure the confidentiality, encryption of sensitive data before its transfer to the cloud emerges as an important option. Encrypted storage provides protection but it complicates data processing including crucial selective record retrieval. To achieve selective retrieval over encrypted collection, considerable amount of searchable encryption schemes have been proposed in the literature with distinct privacy guarantees. Among the available approaches, oblivious RAM based ones offer optimal privacy. However, they are computationally intensive and do not scale well to very large databases. On the other hand, almost all efficient schemes leak some information, especially data access pattern to the remote servers. Unfortunately, recent evidence on access pattern leakage indicates that adversary’s background knowledge could be used to infer the contents of the encrypted data and may potentially endanger individual privacy.  In this paper, we introduce a novel construction for practical and privacy-aware selective record retrieval over encrypted databases. Our approach leaks obfuscated access pattern to enable efficient retrieval while ensuring individual privacy. Applied obfuscation is based on differential privacy which provides rigorous individual privacy guarantees against adversaries with arbitrary background knowledge.
Keywords: differential privacy, searchable encryption, security (ID#: 15-6105)
URL:  http://doi.acm.org/10.1145/2557547.2557570

Zhangjie Fu, Jiangang Shu, Xingming Sun, Daxing Zhang; “Semantic Keyword Search Based on Tree over Encrypted Cloud Data,” SCC ’14 Proceedings of the 2nd International Workshop on Security in Cloud Computing, June 2014, Pages 59-62. doi:10.1145/2600075.2600081
Abstract: Searchable encryption is a good solution to search over encrypted cloud data in cloud computing. However, most of existing searchable encryption schemes only support exact keyword search. That means they don’t support searching for different variants of the query word, which is a significant drawback and greatly affects data usability and user experience. In this paper, we formalize the problem of semantic keyword-based search over encrypted cloud data while preserving privacy. Semantic keyword-based search will greatly improves the user experience by returning all the documents containing semantically close keywords related to the query word. In our solution, we use the stemming algorithm to construct stem set, which reduces the dimension of index. And the symbol-based tree is also adopted in index construction to improve the search efficiency. Through rigorous privacy analysis and experiment on real dataset, our scheme is secure and efficient.
Keywords: cloud computing, searchable encryption, semantic search, stemming algorithm (ID#: 15-6106)
URL:  http://doi.acm.org/10.1145/2600075.2600081

Boyang Wang, Yantian Hou, Ming Li, Haitao Wang, Hui Li; “Maple: Scalable Multi-Dimensional Range Search over Encrypted Cloud Data with Tree-Based Index,” ASIA CCS ’14 Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security, June 2014, Pages 111-122.  doi:10.1145/2590296.2590305
Abstract: Cloud computing promises users massive scale outsourced data storage services with much lower costs than traditional methods. However, privacy concerns compel sensitive data to be stored on the cloud server in an encrypted form. This posts a great challenge for effectively utilizing cloud data, such as executing common SQL queries. A variety of searchable encryption techniques have been proposed to solve this issue; yet efficiency and scalability are still the two main obstacles for their adoptions in real-world datasets, which are multi-dimensional in general. In this paper, we propose a tree-based public-key Multi-Dimensional Range Searchable Encryption (MDRSE) to overcome the above limitations. Specifically, we first formally define the leakage function and security of a tree-based MDRSE. Then, by leveraging an existing predicate encryption in a novel way, our tree-based MDRSE efficiently indexes and searches over encrypted cloud data with multi-dimensional tree structures (i.e., R-trees). Moreover, our scheme is able to protect single-dimensional privacy while previous efficient solutions fail to achieve. Our scheme is selectively secure, and through extensive experimental evaluation on a large-scale real-world dataset, we show the efficiency and scalability of our scheme.
Keywords: encrypted cloud data, multiple dimension, range search, tree structures (ID#: 15-6107)
URL: http://doi.acm.org/10.1145/2590296.2590305

Florian Kerschbaum; “Client-Controlled Cloud Encryption,” CCS ’14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 1542-1543. doi:10.1145/2660267.2660577
Abstract: Customers of cloud service demand control over their data. Next to threats to intellectual property, legal requirements and risks, such as data protection compliance or the possibility of a subpoena of the cloud service provider, also pose restrictions. A commonly proposed and implemented solution is to encrypt the data on the client and retain the key at the client. In this tutorial we will review: the available encryption methods, such deterministic, order-preserving, homomorphic, searchable (functional) encryption and secure multi-party computation; possible attacks on currently deployed systems like dictionary and frequency attacks; architectures integrating these solutions into SaaS and PaaS (DBaaS) applications.
Keywords: cloud, encryption, tutorial (ID#: 15-6108)
URL: http://doi.acm.org/10.1145/2660267.2660577

David McGrew; “Privacy vs. Efficacy in Cloud-based Threat Detection,” CCSW ’14 Proceedings of the 6th edition of the ACM Workshop on Cloud Computing Security, November 2014, Pages 3-4. doi:10.1145/2664168.2664183
Abstract: Advanced threats can be detected by monitoring information systems and networks, then applying advanced analytic techniques to the data thus gathered. It is natural to gather, store, and analyze this data in the Cloud, but doing so introduces significant privacy concerns. There are technologies that can protect privacy to some extent, but these technologies reduce the efficacy of threat analytics and forensics, and introduce computation and communication overhead. This talk considers the tension between privacy and efficacy in Cloud threat detection, and analyzes both pragmatic techniques such as data anonymization via deterministic encryption and differential privacy as well as interactive techniques such as private set intersection and searchable encryption, and highlights areas where further research is needed.
Keywords: cloud, privacy, threat monitoring (ID#: 15-6109)
URL: http://doi.acm.org/10.1145/2664168.2664183

Florian Kerschbaum, Axel Schroepfer; “Optimal Average-Complexity Ideal-Security Order-Preserving Encryption,” CCS ’14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 275-286. doi:10.1145/2660267.2660277
Abstract: Order-preserving encryption enables performing many classes of queries—including range queries—on encrypted databases. Popa et al. recently presented an ideal-secure order-preserving encryption (or encoding) scheme, but their cost of insertions (encryption) is very high. In this paper we present an also ideal-secure, but significantly more efficient order-preserving encryption scheme. Our scheme is inspired by Reed’s referenced work on the average height of random binary search trees. We show that our scheme improves the average communication complexity from O(n log n) to O(n) under uniform distribution. Our scheme also integrates efficiently with adjustable encryption as used in CryptDB. In our experiments for database inserts we achieve a performance increase of up to 81% in LANs and 95% in WANs.
Keywords: adjustable encryption, efficiency, ideal security, in-memory column database, indistinguishability, order-preserving encryption (ID#: 15-6110)
URL:  http://doi.acm.org/10.1145/2660267.2660277

Andreas Schaad, Anis Bkakria, Florian Keschbaum, Frederic Cuppens, Nora Cuppens-Boulahia, David Gross-Amblard; “Optimized and Controlled Provisioning of Encrypted Outsourced Data,” SACMAT ’14 Proceedings of the 19th ACM Symposium on Access Control Models and Technologies, June 2014, Pages 141-152. doi:10.1145/2613087.2613100
Abstract: Recent advances in encrypted outsourced databases support the direct processing of queries on encrypted data. Depending on functionality (i.e. operators) required in the queries the database has to use different encryption schemes with different security properties. Next to these functional requirements a security administrator may have to address security policies that may equally determine the used encryption schemes. We present an algorithm and tool set that determines an optimal balance between security and functionality as well as helps to identify and resolve possible conflicts. We test our solution on a database benchmark and business-driven security policies.
Keywords: encrypted database, encryption algorithm, policy configuration (ID#: 15-6111)
URL: http://doi.acm.org/10.1145/2613087.2613100

Yitao Duan; “Distributed Key Generation for Encrypted Deduplication: Achieving the Strongest Privacy,” CCSW ’14 Proceedings of the 6th edition of the ACM Workshop on Cloud Computing Security, November 2014, Pages 57-68. doi:10.1145/2664168.2664169
Abstract: Large-scale cloud storage systems often attempt to achieve two seemingly conflicting goals: (1) the systems need to reduce the copies of redundant data to save space, a process called deduplication; and (2) users demand encryption of their data to ensure privacy. Conventional encryption makes deduplication on ciphertexts ineffective, as it destroys data redundancy. A line of work, originated from Convergent Encryption [27], and evolved into Message Locked Encryption [13] and the latest DupLESS architecture [12], strives to solve this problem. DupLESS relies on a key server to help the clients generate encryption keys that result in convergent ciphertexts. In this paper, we first introduce a new security notion appropriate for the setting of deduplication and show that it is strictly stronger than all relevant notions. We then provide a rigorous proof of security against this notion, in the random oracle model, for the DupLESS architecture which is lacking in the original paper. Our proof shows that using additional secret, other than the data itself, for generating encryption keys achieves the best possible security under current deduplication paradigm. We also introduce a distributed protocol that eliminates the need for the key server. This not only provides better protection but also allows less managed systems such as P2P systems to enjoy the high security level. Implementation and evaluation show that the scheme is both robust and practical.
Keywords: cloud computing security, deduplication, deterministic encryption (ID#: 15-6112)
URL:  http://doi.acm.org/10.1145/2664168.2664169

Warren He, Devdatta Akhawe, Sumeet Jain, Elaine Shi, Dawn Song; “ShadowCrypt: Encrypted Web Applications for Everyone,” CCS ’14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 1028-1039. doi:10.1145/2660267.2660326
Abstract: A number of recent research and industry proposals discussed using encrypted data in web applications. We first present a systematization of the design space of web applications and highlight the advantages and limitations of current proposals. Next, we present ShadowCrypt, a previously unexplored design point that enables encrypted input/output without trusting any part of the web applications. ShadowCrypt allows users to transparently switch to encrypted input/output for text-based web applications. ShadowCrypt runs as a browser extension, replacing input elements in a page with secure, isolated shadow inputs and encrypted text with secure, isolated cleartext. ShadowCrypt’s key innovation is the use of Shadow DOM, an upcoming primitive that allows low-overhead isolation of DOM trees. Evaluation results indicate that ShadowCrypt has low overhead and of practical use today. Finally, based on our experience with ShadowCrypt, we present a study of 17 popular web applications, across different domains, and the functionality impact and security advantages of encrypting the data they handle.
Keywords: privacy, shadow dom, web security (ID#: 15-6113)
URL:  http://doi.acm.org/10.1145/2660267.2660326

Michael Herrmann, Alfredo Rial, Claudia Diaz, Bart Preneel; “Practical Privacy-Preserving Location-Sharing Based Services with Aggregate Statistics,” WiSec ’14 Proceedings of the 2014 ACM Conference on Security and Privacy in Wireless & Mobile Networks, July 2014, Pages 87-98. doi:10.1145/2627393.2627414
Abstract: Location-sharing-based services (LSBSs) allow users to share their location with their friends in a sporadic manner. In currently deployed LSBSs users must disclose their location to the service provider in order to share it with their friends. This default disclosure of location data introduces privacy risks. We define the security properties that a privacy-preserving LSBS should fulfill and propose two constructions. First, a construction based on identity based broadcast encryption (IBBE) in which the service provider does not learn the user’s location, but learns which other users are allowed to receive a location update. Second, a construction based on anonymous IBBE in which the service provider does not learn the latter either. As advantages with respect to previous work, in our schemes the LSBS provider does not need to perform any operations to compute the reply to a location data request, but only needs to forward IBBE ciphertexts to the receivers. We implement both constructions and present a performance analysis that shows their practicality. Furthermore, we extend our schemes such that the service provider, performing some verification work, is able to collect privacy-preserving aggregate statistics on the locations users share with each other.
Keywords: broadcast encryption, location privacy, vector commitments (ID#: 15-6114)
URL:  http://doi.acm.org/10.1145/2627393.2627414

Aikaterina Latsiou, Panagiotis Rizomiliotis; “The Rainy Season of Cryptography,” PCI ’14 Proceedings of the 18th Panhellenic Conference on Informatics, October 2014, Pages 1-6. doi:10.1145/2645791.2645798
Abstract: Cloud Computing (CC) is the new trend in computing and resource management, an architectural shift towards thin clients and conveniently centralized provision of computing and networking resources. Worldwide cloud services revenue reached 148.8 billion in 2014. However, CC introduces security risks that the clients of the cloud have to deal with. More precisely, there are many security concerns related to outsourcing storage and computation to the cloud and these are mainly attributed to the fact that the clients do not have direct control over the systems that process their data. In this paper, we investigate the new challenges that cryptography faces in the CC era. We introduce a security framework for analysing these challenges, and we describe the cryptographic techniques that have been proposed until now. Finally, we provide a list of open problems and we propose new directions for research.
Keywords: Cloud Computing, Cryptography, Outsourcing (ID#: 15-6115)
URL:  http://doi.acm.org/10.1145/2645791.2645798

Hu Chun, Yousef Elmehdwi, Feng Li, Prabir Bhattacharya, Wei Jiang; “Outsourceable Two-Party Privacy-Preserving Biometric Authentication,” ASIA CCS ’14 Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security, June 2014, Pages 401-412.  doi:10.1145/2590296.2590343
Abstract: Biometric authentication, a key component for many secure protocols and applications, is a process of authenticating a user by matching her biometric data against a biometric database stored at a server managed by an entity. If there is a match, the user can log into her account or obtain the services provided by the entity. Privacy-preserving biometric authentication (PPBA) considers a situation where the biometric data are kept private during the authentication process. That is the user’s biometric data record is never disclosed to the entity, and the data stored in the entity’s biometric database are never disclosed to the user. Due to the reduction in operational costs and high computing power, it is beneficial for an entity to outsource not only its data but also computations such as biometric authentication process to a cloud. However, due to well-documented security risks faced by a cloud, sensitive data like biometrics should be encrypted first and then outsourced to the cloud. When the biometric data are encrypted and cannot be decrypted by the cloud, the existing PPBA protocols are not applicable. Therefore, in this paper, we propose a two-party PPBA protocol when the biometric data in consideration are fully encrypted and outsourced to a cloud. In the proposed protocol, the security of the biometric data is completely protected since the encrypted biometric data are never decrypted during the authentication process. In addition, we formally analyze the security of the proposed protocol and provide extensive empirical results to show its runtime complexity.
Keywords: biometric authentication, cloud computing, security (ID#: 15-6116)
URL: http://doi.acm.org/10.1145/2590296.2590343

Hua Deng, Qianhong Wu, Bo Qin, Sherman S.M. Chow, Josep Domingo-Ferrer, Wenchang Shi; “Tracing and Revoking Leaked Credentials: Accountability in Leaking Sensitive Outsourced Data,” ASIA CCS ’14 Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security, June 2014, Pages 425-434. doi:10.1145/2590296.2590342
Abstract: Most existing proposals for access control over outsourced data mainly aim at guaranteeing that the data are only accessible to authorized requestors who have the access credentials. This paper proposes TRLAC, an a posteriori approach for tracing and revoking leaked credentials, to complement existing a priori solutions. The tracing procedure of TRLAC can trace, in a black-box manner, at least one traitor who illegally distributed a credential, without any help from the cloud service provider. Once the dishonest users have been found, a revocation mechanism can be called to deprive them of access rights. We formally prove the security of TRLAC, and empirically shows that the introduction of the tracing feature incurs little costs to outsourcing.
Keywords: access control, accountability, broadcast encryption, cloud computing, data security, leakage, tracing (ID#: 15-6117)
URL: http://doi.acm.org/10.1145/2590296.2590342

Mohammad Saiful Islam, Mehmet Kuzu, Murat Kantarcioglu; “Inference Attack Against Encrypted Range Queries on Outsourced Databases,” CODASPY ’14 Proceedings of the 4th ACM Conference on Data and Application Security and Privacy, March 2014, pages 235-246. doi:10.1145/2557547.2557561
Abstract: To mitigate security concerns of outsourced databases, quite a few protocols have been proposed that outsource data in encrypted format and allow encrypted query execution on the server side. Among the more practical protocols, the “bucketization” approach facilitates query execution at the cost of reduced efficiency by allowing some false positives in the query results. Precise Query Protocols (PQPs), on the other hand, enable the server to execute queries without incurring any false positives. Even though these protocols do not reveal the underlying data, they reveal query access pattern to an adversary. In this paper, we introduce a general attack on PQPs based on access pattern disclosure in the context of secure range queries. Our empirical analysis on several real world datasets shows that the proposed attack is able to disclose significant amount of sensitive data with high accuracy provided that the attacker has reasonable amount of background knowledge. We further demonstrate that a slight variation of such an attack can also be used on imprecise protocols (e.g., bucketization) to disclose significant amount of sensitive information.
Keywords: database-as-a-service, encrypted range query, inference attack (ID#: 15-6118)
URL: http://doi.acm.org/10.1145/2557547.2557561

Matteo Maffei, Giulio Malavolta, Manuel Reinert, Dominique Schröder; “Brief Announcement: Towards Security and Privacy for Outsourced Data in the Multi-Party Setting,” PODC ’14 Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, July 2014, Pages 144-146. doi:10.1145/2611462.2611508
Abstract: Cloud storage has rapidly acquired popularity among users, constituting a seamless solution for the backup, synchronization, and sharing of large amounts of data. This technology, however, puts user data in the direct control of cloud service providers, which raises increasing 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. We present GORAM, a cryptographic system that protects the secrecy and integrity of the data outsourced to an untrusted server and guarantees the anonymity and unlinkability of consecutive accesses to such data. GORAM allows the database owner to share outsourced data with other clients, selectively granting them read and write permissions. GORAM is the first system to achieve such a wide range of security and privacy properties for outsourced storage. Technically, GORAM builds on a combination of ORAM to conceal data accesses, attribute-based encryption to rule the access to outsourced data, and zero-knowledge proofs to prove read and write permissions in a privacy-preserving manner. We implemented GORAM and conducted an experimental evaluation to demonstrate its feasibility.
Keywords: GORAM, ORAM, cloud storage, oblivious ram, privacy-enhancing technologies (ID#: 15-6119)
URL:  http://doi.acm.org/10.1145/2611462.2611508

Paul Weiser, Simon Scheider; “A Civilized Cyberspace for Geoprivacy,” GeoPrivacy ’14 Proceedings of the 1st ACM SIGSPATIAL International Workshop on Privacy in Geographic Information Collection and Analysis, November 2014, Article No. 5. doi:10.1145/2675682.2676396
Abstract: We argue that current technical and legal attempts aimed at protecting Geoprivacy are insufficient. We propose a novel 2-dimensional model of privacy, which we term “civilized cyberspace.” On one dimension there are engineering, social and legal tools while on the other there are different kinds of interaction with information. We argue why such a civilized cyberspace protects privacy without sacrificing personal freedom on the one hand and opportunities for businesses on the other. We also discuss its realization and propose a technology stack including a permission service for geoprocessing.
Keywords: geoprivacy, geoprocessing, licensing, privacy model (ID#: 15-6120)
URL:  http://doi.acm.org/10.1145/2675682.2676396

Xiao Shaun Wang, Kartik Nayak, Chang Liu, T-H. Hubert Chan, Elaine Shi, Emil Stefanov, Yan Huang; “Oblivious Data Structures,” CCS ’14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 215-226. doi:10.1145/2660267.2660314
Abstract: We design novel, asymptotically more efficient data structures and algorithms for programs whose data access patterns exhibit some degree of predictability. To this end, we propose two novel techniques, a pointer-based technique and a locality-based technique. We show that these two techniques are powerful building blocks in making data structures and algorithms oblivious. Specifically, we apply these techniques to a broad range of commonly used data structures, including maps, sets, priority-queues, stacks, deques; and algorithms, including a memory allocator algorithm, max-flow on graphs with low doubling dimension, and shortest-path distance queries on weighted planar graphs. Our oblivious counterparts of the above outperform the best known ORAM scheme both asymptotically and in practice.
Keywords: cryptography, oblivious algorithms, security (ID#: 15-6121)
URL: http://doi.acm.org/10.1145/2660267.2660314

Jinsheng Zhang, Wensheng Zhang, Daji Qiao; “S-ORAM: a Segmentation-based Oblivious RAM,” ASIA CCS ’14 Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security, June 2014, Pages 147-158. doi:10.1145/2590296.2590323
Abstract: As outsourcing data to remote storage servers gets popular, protecting user’s pattern in accessing these data has become a big concern. ORAM constructions are promising solutions to this issue, but their application in practice has been impeded by the high communication and storage overheads incurred. Towards addressing this challenge, this paper proposes a segmentation-based ORAM (S-ORAM). It adopts two segment-based techniques, namely, piece-wise shuffling and segment-based query, to improve the performance of shuffling and query by factoring block size into design. Extensive security analysis proves that S-ORAM is a highly secure solution with a negligible failure probability of O(N-log N). In terms of communication and storage overheads, S-ORAM outperforms the Balanced ORAM (B-ORAM) and the Path ORAM (P-ORAM), which are the state-of-the-art hash and index based ORAMs respectively, in both practical and theoretical evaluations. Particularly under practical settings, the communication overhead of S-ORAM is 12 to 23 times less than B-ORAM when they have the same constant-size user-side storage, and S-ORAM consumes 80% less server-side storage and around 60% to 72% less bandwidth than P-ORAM when they have the similar logarithmic-size user-side storage.
Keywords: access pattern, data outsourcing, oblivious RAM, privacy (ID#: 15-6122)
URL:  http://doi.acm.org/10.1145/2590296.2590323

Loi Luu, Shweta Shinde, Prateek Saxena, Brian Demsky; “A Model Counter for Constraints over Unbounded Strings,” PLDI ’14 Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2014, Pages 565-576. doi:10.1145/2594291.2594331
Abstract: Model counting is the problem of determining the number of solutions that satisfy a given set of constraints. Model counting has numerous applications in the quantitative analyses of program execution time, information flow, combinatorial circuit designs as well as probabilistic reasoning. We present a new approach to model counting for structured data types, specifically strings in this work. The key ingredient is a new technique that leverages generating functions as a basic primitive for combinatorial counting. Our tool SMC which embodies this approach can model count for constraints specified in an expressive string language efficiently and precisely, thereby outperforming previous finite-size analysis tools. SMC is expressive enough to model constraints arising in real-world JavaScript applications and UNIX C utilities. We demonstrate the practical feasibility of performing quantitative analyses arising in security applications, such as determining the comparative strengths of password strength meters and determining the information leakage via side channels.
Keywords: (not provided) (ID#: 15-6123)
URL:  http://doi.acm.org/10.1145/2666356.2594331

Suman Phangal, Mukesh Kumar; “A Dual Security Scheme Using DNA Key-Based DNA Cryptography,” ICTCS ’14 Proceedings of the 2014 International Conference on Information and Communication Technology for Competitive Strategies, November 2014, Article No. 37. doi:10.1145/2677855.2677882
Abstract: Cryptography is one of the most traditional and secure approach to provide reliable transmission over the web. The presented work is the improvement over the traditional symmetric cryptography approach by including the concept of DNA Sequencing. In this work, a two stage model is presented to improve the DNA Cryptography. This cryptography model uses the DNA Sequence as the Input Key to the system as well as uses the DNA object based substitution for cryptography. The work is applied on Images. The analysis of work is done under MSE and PSNR values. The obtained result shows the effective generation of cryptography image.
Keywords: Cryptography, DNA, MSE, PSNR, Secure (ID#: 15-6124)
URL: http://doi.acm.org/10.1145/2677855.2677882

Hamidreza Ghafghazi, Amr El Mougy, Hussein T. Mouftah, Carlisle Adams; “Classification of Technological Privacy Techniques for LTE-Based Public Safety Networks,” Q2SWinet ’14 Proceedings of the 10th ACM symposium on QoS and Security for Wireless and Mobile Networks, September 2014, Pages 41-50. doi:10.1145/2642687.2642693
Abstract: Public Protection and Disaster Relief (PPDR) organizations emphasize the need for dedicated and broadband Public Safety Networks (PSNs) with the capability of providing a high level of security for critical communications. Considering the preceding fact, Long Term Evolution (LTE) has been chosen as the leading candidate technology for PSNs. However, a study of privacy challenges and requirements in LTE-based PSNs has not yet emerged. This paper aims to highlight those challenges and further discusses possible scenarios in which privacy might be violated in this particular environment. Then, a classification of technological privacy techniques is proposed in order to protect and enhance privacy in LTE-based PSNs. The given classification is a useful means for comparison and assessment of applicable privacy preserving methods. Moreover, our classification highlights further requirements and open problems for which available privacy techniques are not sufficient.
Keywords: long term evolution, privacy, private information retrieval, public safety networks (ID#: 15-6125)
URL:  http://doi.acm.org/10.1145/2642687.2642693

Se Eun Oh, Ji Young Chun, Limin Jia, Deepak Garg, Carl A. Gunter, Anupam Datta; “Privacy-Preserving Audit for Broker-Based Health Information Exchange,” CODASPY ’14 Proceedings of the 4th ACM Conference on Data and Application Security and Privacy, March 2014, Pages 313-320.  doi:10.1145/2557547.2557576
Abstract: Developments in health information technology have encouraged the establishment of distributed systems known as Health Information Exchanges (HIEs) to enable the sharing of patient records between institutions. In many cases, the parties running these exchanges wish to limit the amount of information they are responsible for holding because of sensitivities about patient information. Hence, there is an interest in broker-based HIEs that keep limited information in the exchange repositories. However, it is essential to audit these exchanges carefully due to risks of inappropriate data sharing. In this paper, we consider some of the requirements and present a design for auditing broker-based HIEs in a way that controls the information available in audit logs and regulates their release for investigations. Our approach is based on formal rules for audit and the use of Hierarchical Identity-Based Encryption (HIBE) to support staged release of data needed in audits and a balance between automated and manual reviews. We test our methodology via an extension of a standard for auditing HIEs called the Audit Trail and Node Authentication Profile (ATNA) protocol.
Keywords: audit, formal logic, health information technology, hierarchical identity based encryption (ID#: 15-6126)
URL: http://doi.acm.org/10.1145/2557547.2557576

David Koll, Jun Li, Xiaoming Fu; “SOUP: An Online Social Network by the People, for the People,” Middleware ’14 Proceedings of the 15th International Middleware Conference, December 2014, Pages 193-204. doi:10.1145/2663165.2663324
Abstract: Concomitant with the tremendous growth of online social networking (OSN) platforms are increasing concerns from users about their privacy and the protection of their data. As user data management is usually centralized, OSN providers nowadays have the unprecedented privilege to access every user’s private data, which makes large-scale privacy leakage at a single site possible. One way to address this issue is to decentralize user data management and replicate user data at individual end-user machines across the OSN. However, such an approach must address new challenges. In particular, it must achieve high availability of the data of every user with minimal replication overhead and without assuming any permanent online storage. At the same time, it needs to provide mechanisms for encrypting user data, controlling access to the data, and synchronizing the replicas. Moreover, it has to scale with large social networks and be resilient and adaptive in handling both high churn of regular participants and attacks from malicious users. While recent works in this direction only show limited success, we introduce a new, decentralized OSN called the Self-Organized Universe of People (SOUP). SOUP employs a scalable, robust and secure mirror selection design and can effectively distribute and manage encrypted user data replicas throughout the OSN. An extensive evaluation by simulation and a real-world deployment show that SOUP addresses all aforementioned challenges.
Keywords: OSN, decentralized OSN, online social networks, privacy (ID#: 15-6127)
URL:  http://doi.acm.org/10.1145/2663165.2663324

Jude C. Nelson, Larry L. Peterson; “Syndicate: Virtual Cloud Storage Through Provider Composition,” BigSystem ’14 Proceedings of the 2014 ACM International Workshop on Software-Defined Ecosystems, June 2014, Pages 1-8. doi:10.1145/2609441.2609639
Abstract: Syndicate is a storage service that builds a coherent storage abstraction from already-deployed commodity components, including cloud storage, edge caches, and dataset providers. It is unique in that it not only offers consistent semantics across multiple providers, but also offers a flexible programming model to applications so they can define their own provider-agnostic storage functionality. In doing so, Syndicate fully decouples applications from providers, allowing applications to choose them based on how well they enhance data locality and durability, instead of whether or not they provide requisite features. This paper presents the motivation and design of Syndicate, and gives the results of a preliminary evaluation showing that separating storage functionality from provider implementation is feasible in practice.
Keywords: service composition, software-defined storage, storage gateway (ID#: 15-6128)
URL:  http://doi.acm.org/10.1145/2609441.2609639

Varunya Attasena, Nouria Harbi, Jérôme Darmont; “fVSS: A New Secure and Cost-Efficient Scheme for Cloud Data Warehouses,” DOLAP ’14 Proceedings of the 17th International Workshop on Data Warehousing and OLAP, November 2014, Pages 81-90. doi:10.1145/2666158.2666173
Abstract: Cloud business intelligence is an increasingly popular choice to deliver decision support capabilities via elastic, pay-per-use resources. However, data security issues are one of the top concerns when dealing with sensitive data. In this paper, we propose a novel approach for securing cloud data warehouses by flexible verifiable secret sharing, fVSS. Secret sharing encrypts and distributes data over several cloud service providers, thus enforcing data privacy and availability. fVSS addresses four shortcomings in existing secret sharing-based approaches. First, it allows refreshing the data warehouse when some service providers fail. Second, it allows on-line analysis processing. Third, it enforces data integrity with the help of both inner and outer signatures. Fourth, it helps users control the cost of cloud warehousing by balancing the load among service providers with respect to their pricing policies. To illustrate fVSS’ efficiency, we thoroughly compare it with existing secret sharing-based approaches with respect to security features, querying power and data storage and computing costs.
Keywords: OLAP, cloud computing, data availability, data integrity, data privacy, data warehouses, secret sharing (ID#: 15-6129)
URL:  http://doi.acm.org/10.1145/2666158.2666173

Tomäš Pevný, Andrew D. Ker; “Steganographic Key Leakage Through Payload Metadata,” IH&MMSec ’14 Proceedings of the 2nd ACM Workshop on Information Hiding and Multimedia Security, June 2014, Pages 109-114. doi:10.1145/2600918.2600921
Abstract: The only steganalysis attack which can provide absolute certainty about the presence of payload is one which finds the embedding key. In this paper we consider refined versions of the key exhaustion attack exploiting metadata such as message length or decoding matrix size, which must be stored along with the payload. We show simple errors of implementation lead to leakage of key information and powerful inference attacks; furthermore, complete absence of information leakage seems difficult to avoid. This topic has been somewhat neglected in the literature for the last ten years, but must be considered in real-world implementations.
Keywords: bayesian inference, brute-force attack, key leakage, steganographic security (ID#: 15-6130)
URL:  http://doi.acm.org/10.1145/2600918.2600921

Greig Paul, James Irvine; “Privacy Implications of Wearable Health Devices,” SIN ’14 Proceedings of the 7th International Conference on Security of Information and Networks, September 2014, Page 117. doi:10.1145/2659651.2659683
Abstract: With the recent rise in popularity of wearable personal health monitoring devices, a number of concerns regarding user privacy are raised, specifically with regard to how the providers of these devices make use of the data obtained from these devices, and the protections that user data enjoys. With waterproof monitors intended to be worn 24 hours per day, and companion smartphone applications able to offer analysis and sharing of activity data, we investigate and compare the privacy policies of four services, and the extent to which these services protect user privacy, as we find these services do not fall within the scope of existing legislation regarding the privacy of health data. We then present a set of criteria which would preserve user privacy, and avoid the concerns identified within the policies of the services investigated.
Keywords: Health monitoring, privacy, security, wearables (ID#: 15-6131)
URL: http://doi.acm.org/10.1145/2659651.2659683

Note:

Articles listed on these pages have been found on publicly available internet pages and are cited with links to those pages. Some of the information included herein has been reprinted with permission from the authors or data repositories. Direct any requests via Email to news@scienceofsecurity.net for removal of the links or modifications to specific citations. Please include the ID# of the specific citation in your correspondence.