*16:17* [Pub][ePrint]
Verifiable Oblivious Storage, by Daniel Apon and Jonathan Katz and Elaine Shi and Aishwarya Thiruvengadam
We formalize the notion of Verifiable Oblivious Storage (VOS), where a client outsources the storage of data to a server while ensuring data confidentiality, access pattern privacy, and integrity and freshness of data accesses. VOS generalizes the notion of Oblivious RAM (ORAM) in that it allows the server to perform computation, and also explicitly considers data integrity and freshness.We show that allowing server-side computation enables us to

construct asymptotically more efficient VOS schemes whose bandwidth overhead cannot be matched by any ORAM scheme, due to a known lower bound by Goldreich and Ostrovsky. Specifically, for large block sizes

we can construct a VOS scheme with constant bandwidth per query; further, answering queries requires only poly-logarithmic

server computation. We describe applications of VOS to Dynamic Proofs of Retrievability, and RAM-model secure multi-party computation.

*16:17* [Pub][ePrint]
Non-Interactive Cryptography in the RAM Model of Computation, by Daniel Apon and Xiong Fan and Jonathan Katz and Feng-Hao Liu and Elaine Shi and Hong-Sheng Zhou
Using recently developed techniques for program obfuscation, we show several constructions of non-interactive cryptosystems in the random-access machine (RAM) model of computation that are asymptotically more efficient than what would be obtained using generic RAM-to-circuit compilation. In particular, let $T$ denote the running time and $n$ the memory size of a RAM program. We show that using differing-inputs obfuscation, functional encryption for arbitrary RAM programs can be achieved with evaluation time $\\tilde{O}(T+n)$.Additionally, we provide a number of RAM-model constructions assuming

the stronger notion of virtual black-box (VBB) obfuscation. We view these as initial feasibility results and leave instantiating similar protocols from weaker assumptions for future work. Specifically, using VBB obfuscation we show how to construct RAM-model functional encryption with function privacy, fully homomorphic encryption, and stateful, privacy-preserving verifiable computation in the memory-delegation model.

*16:17* [Pub][ePrint]
Honey Encryption: Security Beyond the Brute-Force Bound, by Ari Juels and Thomas Ristenpart
We introduce {\\em honey encryption} (HE), a simple, general approach to encrypting messages using low min-entropy keys such as passwords. HE is designed to produce a ciphertext which, when decrypted with any of a number of {\\em incorrect} keys, yields plausible-looking but bogus plaintexts called {\\em honey messages}. A key benefit of HE is that it provides security in cases where too little entropy is available to withstand brute-force attacks that try every key; in this sense, HE provides security beyond conventional brute-force bounds. HE can also provide a hedge against partial disclosure of high min-entropy keys. HE significantly improves security in a number of practical settings. To showcase this improvement, we build concrete HE schemes for password-based encryption of RSA secret keys and credit card numbers. The key challenges are development of appropriate instances of a new type of randomized message encoding scheme called a {\\em distribution-transforming encoder} (DTE), and analyses of the expected maximum loading of bins in various kinds of balls-and-bins games.

*01:17* [Pub][ePrint]
On the Effective Prevention of TLS Man-In-The-Middle Attacks in Web Applications, by Nikolaos Karapanos and Srdjan Capkun
In this paper we consider TLS MITM attacks in the context of web applications, where the attacker\'s goal is to impersonate the user to the legitimate server, and thus gain access to the user\'s online account. We describe in detail why the recently proposed TLS Channel ID-based client authentication, as well as client web authentication in general, cannot fully prevent such attacks. We then leverage TLS Channel ID-based authentication and combine it with the concept of sender invariance to create a novel mechanism that we call SISCA: Server Invariance with Strong Client Authentication. SISCA resists user impersonation via TLS MITM attacks even if the attacker has obtained the private key of the legitimate server. We analyze our proposal and show how it can be integrated in today\'s web infrastructure.

*22:17* [Pub][ePrint]
The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields, by Razvan Barbulescu and Cécile Pierrot
In this paper, we study the discrete logarithm problem in medium andhigh characteristic finite fields. We propose a variant of the Number Field Sieve (NFS) based on numerous number fields. Our improved algorithm computes discrete logarithms in $\\mathbb{F}_{p^n}$ for the whole range of applicability of NFS and lowers the asymptotic complexity from $L_{p^n}(1/3, (128/9)^{1/3})$ to $L_{p^n}(1/3, (2^{13} /3^6)^{1/3})$ in the medium characteristic case, and from $L_{p^n} (1/3, (64/9)^{1/3})$ to $L_{p^n}(1/3,((92 + 26\\sqrt{13})/27))^{1/3})$ in the high characteristic case.

*22:17* [Pub][ePrint]
Outsourcing Private RAM Computation, by Craig Gentry and Shai Halevi and Mariana Raykova and Daniel Wichs
We construct the first schemes that allow a client to privately outsource arbitrary program executions to a remote server while ensuring that: (I) the client\'s work is small and essentially independent of the complexity of the computation being outsourced, and (II) the server\'s work is only proportional to the run-time of the computation on a random access machine (RAM), rather than its potentially much larger circuit size. Furthermore, our solutions are non-interactive and have the structure of reusable garbled RAM programs, addressing an open question of Lu and Ostrovsky (Eurocrypt 2013). We also construct schemes for an augmented variant of the above scenario, where the client can initially outsource a large private and persistent database to the server, and later outsource arbitrary program executions with read/write access to this database.Our solutions are built from non-reusable garbled RAM in conjunction with new types of reusable garbled circuits that are more efficient than prior solutions but only satisfy weaker security. For the basic setting without a persistent database, we can instantiate the required reusable garbled circuits using indistinguishability obfuscation. For the more complex setting with a persistent database we need stronger notions of obfuscation. Our basic solution also requires the client to perform a one-time preprocessing step to garble a program at the cost of its RAM run-time, and we can avoid this cost using stronger notions of obfuscation. It remains an open problem to instantiate these new types of reusable garbled circuits under weaker assumptions, possibly avoiding obfuscation altogether.