Search Results

1 - 10 of 34 items :

  • "efficiency" x
  • IT-Security and Cryptology x
Clear All
Security-Efficiency Tradeoffs in Searchable Encryption

–368. Springer, Heidelberg (May 2014). [DDF + 16] Devadas, S., Dijk, M., Fletcher, C.W., Ren, L., Shi, E., and Wichs, D. Onion ORAM: A constant bandwidth blowup oblivious RAM. In: E. Kushilevitz and T. Malkin (eds.), TCC 2016-A, Part II, LNCS , vol. 9563, pp. 145–174. Springer, Heidelberg (Jan. 2016). [DPP18] Demertzis, I., Papadopoulos, D., and Papamanthou, C. Searchable encryption with optimal locality: Achieving sublogarithmic read efficiency. In: H. Shacham and A. Boldyreva (eds.), CRYPTO 2018, Part I, LNCS , vol. 10991, pp. 371–406. Springer, Heidelberg (Aug

Open access
Polynomial Batch Codes for Efficient IT-PIR

Abstract

Private information retrieval (PIR) is a way for clients to query a remote database without the database holder learning the clients’ query terms or the responses they generate. Compelling applications for PIR are abound in the cryptographic and privacy research literature, yet existing PIR techniques are notoriously inefficient. Consequently, no such PIRbased application to date has seen real-world at-scale deployment. This paper proposes new “batch coding” techniques to help address PIR’s efficiency problem. The new techniques exploit the connection between ramp secret sharing schemes and efficient information-theoretically secure PIR (IT-PIR) protocols. This connection was previously observed by Henry, Huang, and Goldberg (NDSS 2013), who used ramp schemes to construct efficient “batch queries” with which clients can fetch several database records for the same cost as fetching a single record using a standard, non-batch query. The new techniques in this paper generalize and extend those of Henry et al. to construct “batch codes” with which clients can fetch several records for only a fraction the cost of fetching a single record using a standard non-batch query over an unencoded database. The batch codes are highly tuneable, providing a means to trade off (i) lower server-side computation cost, (ii) lower server-side storage cost, and/or (iii) lower uni- or bi-directional communication cost, in exchange for a comparatively modest decrease in resilience to Byzantine database servers.

Open access
A Bit More Than a Bit Is More Than a Bit Better
Faster (essentially) optimal-rate many-server PIR

Abstract

We study both the practical and theoretical efficiency of private information retrieval (PIR) protocols in a model wherein several untrusted servers work to obliviously service remote clients’ requests for data and yet no pair of servers colludes in a bid to violate said obliviousness. In exchange for such a strong security assumption, we obtain new PIR protocols exhibiting remarkable efficiency with respect to every cost metric—download, upload, computation, and round complexity—typically considered in the PIR literature.

The new constructions extend a multiserver PIR protocol of Shah, Rashmi, and Ramchandran (ISIT 2014), which exhibits a remarkable property of its own: to fetch a b-bit record from a collection of r such records, the client need only download b + 1 bits total. We find that allowing “a bit more” download (and optionally introducing computational assumptions) yields a family of protocols offering very attractive trade-offs. In addition to Shah et al.’s protocol, this family includes as special cases (2-server instances of) the seminal protocol of Chor, Goldreich, Kushilevitz, and Sudan (FOCS 1995) and the recent DPF-based protocol of Boyle, Gilboa, and Ishai (CCS 2016). An implicit “folklore” axiom that dogmatically permeates the research literature on multiserver PIR posits that the latter protocols are the “most efficient” protocols possible in the perfectly and computationally private settings, respectively. Yet our findings soundly refute this supposed axiom: These special cases are (by far) the least performant representatives of our family, with essentially all other parameter settings yielding instances that are significantly faster.

Open access
Private Set Intersection for Unequal Set Sizes with Mobile Applications

Abstract

Private set intersection (PSI) is a cryptographic technique that is applicable to many privacy-sensitive scenarios. For decades, researchers have been focusing on improving its efficiency in both communication and computation. However, most of the existing solutions are inefficient for an unequal number of inputs, which is common in conventional client-server settings. In this paper, we analyze and optimize the efficiency of existing PSI protocols to support precomputation so that they can efficiently deal with such input sets. We transform four existing PSI protocols into the precomputation form such that in the setup phase the communication is linear only in the size of the larger input set, while in the online phase the communication is linear in the size of the smaller input set. We implement all four protocols and run experiments between two PCs and between a PC and a smartphone and give a systematic comparison of their performance. Our experiments show that a protocol based on securely evaluating a garbled AES circuit achieves the fastest setup time by several orders of magnitudes, and the fastest online time in the PC setting where AES-NI acceleration is available. In the mobile setting, the fastest online time is achieved by a protocol based on the Diffie-Hellman assumption.

Open access
Efficient Verifiable Range and Closest Point Queries in Zero-Knowledge

Abstract

We present an efficient method for answering one-dimensional range and closest-point queries in a verifiable and privacy-preserving manner. We consider a model where a data owner outsources a dataset of key-value pairs to a server, who answers range and closest-point queries issued by a client and provides proofs of the answers. The client verifies the correctness of the answers while learning nothing about the dataset besides the answers to the current and previous queries. Our work yields for the first time a zero-knowledge privacy assurance to authenticated range and closest-point queries. Previous work leaked the size of the dataset and used an inefficient proof protocol. Our construction is based on hierarchical identity-based encryption. We prove its security and analyze its efficiency both theoretically and with experiments on synthetic and real data (Enron email and Boston taxi datasets).

Open access
Secure and scalable match: overcoming the universal circuit bottleneck using group programs

Abstract

Confidential Content-Based Publish/Subscribe (C-CBPS) is an interaction model that allows parties to exchange content while protecting their security and privacy interests. In this paper we advance the state of the art in C-CBPS by showing how all predicate circuits in NC1 (logarithmic-depth, bounded fan-in) can be confidentially computed by a broker while guaranteeing perfect information-theoretic security. Previous work could handle only strictly shallower circuits (e.g. those with depth O(ℑ)). We present three protocols—UGP-Match, FSGP-Match and OFSGP-Match—based on 2-decomposable randomized encodings of group programs for circuits in NC1. UGP-Match is conceptually simple and has a clean proof of correctness but its running time is a polynomial with a high exponent and hence impractical. FSGP-Match uses a “fixed structure” construction that reduces the exponent drastically and achieves efficiency and scalability. OFSGP-Match optimizes the group programs further to shave off a linear factor.

Open access
PHI: Path-Hidden Lightweight Anonymity Protocol at Network Layer

Abstract

We identify two vulnerabilities for existing highspeed network-layer anonymity protocols, such as LAP and Dovetail. First, the header formats of LAP and Dovetail leak path information, reducing the anonymity-set size when an adversary launches topological attacks. Second, ASes can launch session hijacking attacks to deanonymize destinations. HORNET addresses these problems but incurs additional bandwidth overhead and latency.

In this paper, we propose PHI, a Path-HIdden lightweight anonymity protocol that solves both challenges while maintaining the same level of efficiency as LAP and Dovetail. We present an efficient packet header format that hides path information and a new back-off setup method that is compatible with current and future network architectures. Our experiments demonstrate that PHI expands anonymity sets of LAP and Dovetail by over 30x and reaches 120 Gbps forwarding speed on a commodity software router.

Open access
Hardware-Supported ORAM in Effect: Practical Oblivious Search and Update on Very Large Dataset

Abstract

The ability to query and update over encrypted data is an essential feature to enable breach-resilient cyber-infrastructures. Statistical attacks on searchable encryption (SE) have demonstrated the importance of sealing information leaks in access patterns. In response to such attacks, the community has proposed the Oblivious Random Access Machine (ORAM). However, due to the logarithmic communication overhead of ORAM, the composition of ORAM and SE is known to be costly in the conventional client-server model, which poses a critical barrier toward its practical adaptations.

In this paper, we propose a novel hardware-supported privacy-enhancing platform called Practical Oblivious Search and Update Platform (POSUP), which enables oblivious keyword search and update operations on large datasets with high efficiency. We harness Intel SGX to realize efficient oblivious data structures for oblivious search/update purposes. We implemented POSUP and evaluated its performance on a Wikipedia dataset containing ≥229 keyword-file pairs. Our implementation is highly efficient, taking only 1 ms to access a 3 KB block with Circuit-ORAM. Our experiments have shown that POSUP offers up to 70× less end-to-end delay with 100× reduced network bandwidth consumption compared with the traditional ORAM-SE composition without secure hardware. POSUP is also at least 4.5× faster for up to 99.5% of keywords that can be searched compared with state-of-the-art Intel SGX-assisted search platforms.

Open access
Breach-Resistant Structured Encryption

Abstract

Motivated by the problem of data breaches, we formalize a notion of security for dynamic structured encryption (STE) schemes that guarantees security against a snapshot adversary; that is, an adversary that receives a copy of the encrypted structure at various times but does not see the transcripts related to any queries. In particular, we focus on the construction of dynamic encrypted multi-maps which are used to build efficient searchable symmetric encryption schemes, graph encryption schemes and encrypted relational databases. Interestingly, we show that a form of snapshot security we refer to as breach resistance implies previously-studied notions such as a (weaker version) of history independence and write-only obliviousness. Moreover, we initiate the study of dual-secure dynamic STE constructions: schemes that are forward-private against a persistent adversary and breach-resistant against a snapshot adversary. The notion of forward privacy guarantees that updates to the encrypted structure do not reveal their association to any query made in the past. As a concrete instantiation, we propose a new dual-secure dynamic multi-map encryption scheme that outperforms all existing constructions; including schemes that are not dual-secure. Our construction has query complexity that grows with the selectivity of the query and the number of deletes since the client executed a linear-time rebuild protocol which can be de-amortized. We implemented our scheme (with the de-amortized rebuild protocol) and evaluated its concrete efficiency empirically. Our experiments show that it is highly efficient with queries taking less than 1 microsecond per label/value pair.

Open access
A Practical Set-Membership Proof for Privacy-Preserving NFC Mobile Ticketing

Abstract

To ensure the privacy of users in transport systems, researchers are working on new protocols providing the best security guarantees while respecting functional requirements of transport operators. In this paper1, we design a secure NFC m-ticketing protocol for public transport that preserves users’ anonymity and prevents transport operators from tracing their customers’ trips. To this end, we introduce a new practical set-membership proof that does not require provers nor verifiers (but in a specific scenario for verifiers) to perform pairing computations. It is therefore particularly suitable for our (ticketing) setting where provers hold SIM/UICC cards that do not support such costly computations. We also propose several optimizations of Boneh-Boyen type signature schemes, which are of independent interest, increasing their performance and efficiency during NFC transactions. Our m-ticketing protocol offers greater flexibility compared to previous solutions as it enables the post-payment and the off-line validation of m-tickets. By implementing a prototype using a standard NFC SIM card, we show that it fulfils the stringent functional requirement imposed by transport operators whilst using strong security parameters. In particular, a validation can be completed in 184.25ms when the mobile is switched on, and in 266.52ms when the mobile is switched off or its battery is flat.

Open access