*21:17* [Pub][ePrint]
Private Database Queries Using Somewhat Homomorphic Encryption, by Dan Boneh and Craig Gentry and Shai Halevi and Frank Wang and David J. Wu
In a private database query system, a client issues queries to a database and obtains the results without learning anything else about the database and without the server learning the query. While previous work has yielded systems that can efficiently support disjunction queries, performing conjunction queries privately remains an open problem. In this work, we show that using a polynomial encoding of the database enables efficient implementations of conjunction queries using somewhat homomorphic encryption. We describe a three-party protocol that supports efficient evaluation of conjunction queries. Then, we present two implementations of our protocol using Paillier\'sadditively homomorphic system as well as Brakerski\'s somewhat homomorphic cryptosystem. Finally, we show that the additional homomorphic properties of the Brakerski cryptosystem allow us to handle queries involving several thousand elements over a million-record database in just a few minutes, far outperforming the implementation using the additively homomorphic system.

*21:17* [Pub][ePrint]
Locally Computable UOWHF with Linear Shrinkage, by Benny Applebaum and Yoni Moses
We study the problem of constructing locally computable Universal One-Way Hash Functions (UOWHFs) $\\mathcal{H}:\\{0,1\\}^n \\rightarrow \\{0,1\\}^m$. A construction with constant \\emph{output locality}, where every bit of the output depends only on a constant number of bits of the input, was established by [Applebaum, Ishai, and Kushilevitz, SICOMP 2006]. However, this construction suffers from two limitations: (1) It can only achieve a sub-linear shrinkage of $n-m=n^{1\\epsilon}$; and (2) It has a super-constant \\emph{input locality}, i.e., some inputs influence a large super-constant number of outputs. This leaves open the question of realizing UOWHFs with constant output locality and linear shrinkage of $n-m= \\epsilon n$, or UOWHFs with constant input locality and minimal shrinkage of $n-m=1$.We settle both questions simultaneously by providing the first construction of UOWHFs with linear shrinkage, constant input locality, and constant output locality. Our construction is based on the one-wayness of ``random\'\' local functions -- a variant of an assumption made by Goldreich (ECCC 2000). Using a transformation of [Ishai, Kushilevitz, Ostrovsky and Sahai, STOC 2008], our UOWHFs give rise to a digital signature scheme with a minimal \\emph{additive} complexity overhead: signing $n$-bit messages with security parameter $\\kappa$ takes only $O(n+\\kappa)$ time instead of $O(n\\kappa)$ as in typical constructions. Previously, such signatures were only known to exist under an \\emph{exponential} hardness assumption.

As an additional contribution, we obtain new locally-computable hardness amplification procedures for UOWHFs that preserve linear shrinkage.

*21:17* [Pub][ePrint]
Efficient Garbling from a Fixed-Key Blockcipher, by Mihir Bellare and Viet Tung Hoang and Sriram Keelveedhi and Phillip Rogaway
We advocate schemes based on fixed-key AES as the best route to highlyefficient circuit-garbling. We provide such schemes making only one AES call per garbled-gate evaluation. On the theoretical side, we justify the security of these methods in the random-permutation model, where parties have access to a public random permutation. On the practical side, we provide the JustGarble system, which implements our schemes.

JustGarble evaluates moderate-sized garbled-circuits at an amortized

cost of 23.2 cycles per gate (7.25 nsec), far faster than any prior reported results.

*16:00* [Job][New]
Assistant/Associate Professors, *University of Washington Tacoma, USA, Earth*
The Institute of Technology at the University of Washington Tacoma is seeking applications for five full-time, tenure-track Associate/Assistant Professor positions for the Computer Science and Systems program and the Information Technology and Systems program. A Ph.D. or foreign equivalent in Computer Science, Information Technology, Information Systems or related field is required. Applicants should have experience in teaching and in externally-funded research. Our priority areas for research are (1) information assurance and cybersecurity – 2 positions, (2) data analytics – AI/intelligent systems, (3) CS theory/algorithms, and (4) spatial data/GIS; other areas will also be considered, especially if they are related to needs of the other Institute of Technology programs. Successful candidates will have demonstrated experience or promise for strong potential in research (as evidenced by publications). Evidence of potential to build strong relationships with partners in the technology industry and in developing collaborative research programs is highly desirable.Applications should be submitted electronically to https://secure.interfolio.com/apply/21679 and include (1) a cover letter describing academic qualifications and experience for this position, (2) a statement of the candidate’s research program, (3) a list of publications, (4) a description of teaching philosophy, including a list of courses the candidate is qualified to teach, (5) evidence of teaching effectiveness, (6) a curriculum vitae, and (7) at least three letters of reference. Screening of applications will begin on October 15, 2013, and will continue until the positions are filled. Salary is competitive and will be commensurate with experience and qualifications.

*19:27* [PhD][Update]
Viet Tung Hoang: Foundations of garbled circuits
Name: Viet Tung Hoang

Topic: Foundations of garbled circuits

Category:foundations

Description:
Garbled circuits, a classical idea rooted in the work of Andrew Yao, have long been understood as a cryptographic technique, not a cryptographic goal. Here we cull out a primitive corresponding to this technique. We call it a garbling scheme. We provide a provable-security treatment for garbling schemes, endowing them with a versatile syntax and multiple security definitions. The most basic of these, privacy, suffices for two-party secure function evaluation (SFE) and private function evaluation (PFE). We next consider obliviousness and authenticity, properties needed for private and verifiable outsourcing of computation. Starting from a PRF, we give efficient schemes to achieve all security notions above, and analyze their concrete security. Our treatment of garbling schemes provides ground for more efficient garbling, more rigorous analyses, and more modularly designed higher-level protocols.

On the practical side, we provide extremely efficient garbling schemes based on fixed-key AES. We justify the security of these methods in the random-permutation model, where parties have access to a public random permutation, and build the JustGarble system to implement them. JustGarble evaluates moderate-sized garbled circuits at an amortized cost of 23.2 cycles per gate (7.25 nsec), far faster than any prior reported results.

Standard constructions of garbling schemes, including ours, provide only static security, meaning the input x is not allowed to depend on the garbled circuit F. But some application—notably one-time programs (Goldwasser, Kalai, and Rothblum 2008) and secure outsourcing (Gennaro, Gentry, Parno 2010)—need adaptive security, where x may depend on F. We identify gaps in proofs from these papers with regard to adaptive security, which signifies the absence of a good abstraction boundary. We then investigate adaptive security of garbling schemes, giving definitions encompassing privacy, authenticity, and obliviousness, wi[...]

*19:11* [PhD][New]
Viet Tung Hoang: Foundations of garbled circuits
Name: Viet Tung Hoang

Topic: Foundations of garbled circuits

Category: foundations

Description: \r\nGarbled circuits, a classical idea rooted in the work of Andrew Yao, have long been understood as a cryptographic technique, not a cryptographic goal. Here we cull out a primitive corresponding to this technique. We call it a garbling scheme. We provide a provable-security treatment for garbling schemes, endowing them with a versatile syntax and multiple security definitions. The most basic of these, privacy, suffices for two-party secure function evaluation (SFE) and private function evaluation (PFE). We next consider obliviousness and authenticity, properties needed for private and verifiable outsourcing of computation. Starting from a PRF, we give efficient schemes to achieve all security notions above, and analyze their concrete security. Our treatment of garbling schemes provides ground for more efficient garbling, more rigorous analyses, and more modularly designed higher-level protocols.\r\n

\r\nOn the practical side, we provide extremely efficient garbling schemes based on fixed-key AES. We justify the security of these methods in the random-permutation model, where parties have access to a public random permutation, and build the JustGarble system to implement them. JustGarble evaluates moderate-sized garbled circuits at an amortized cost of 23.2 cycles per gate (7.25 nsec), far faster than any prior reported results.\r\n

\r\nStandard constructions of garbling schemes, including ours, provide only static security, meaning the input x is not allowed to depend on the garbled circuit F. But some application—notably one-time programs (Goldwasser, Kalai, and Rothblum2008) and secure outsourcing (Gennaro, Gentry, Parno 2010)—need adaptive security, where x may depend on F. We identify gaps in proofs from these papers with regard to adaptive security, which signifies the absence of a good abstraction boundary. We then investigate adaptive security of garbling schemes, giving definitions encompassing privacy, authenticity, and obliviousness,[...]