Results 1521 - 1530 of 23856

This talk introduces BitGC, a computationally efficient rate-one garbling scheme based on ring-RLWE with key-dependent message security. The garbling consists of a SWHE-encrypted seed and one-bit per gate stitching information. The computation requires homomorphically expanding the seed using a low-depth PRG and then two additional levels of multiplication to assemble the garbled tables. As a result, it does not require bootstrapping operations needed for FHE. The talk ends on some recent progress in the implementation of BitGC.

Yao's Garbled Circuit (GC) technique is one of our many primitives for achieving secure multiparty computation (MPC), and it is particularly powerful in that it enables MPC protocols that consume only a constant number of rounds of communication. Traditionally, GC was limited in that it worked only for computations expressed as Boolean circuits. More recently, the literature has erupted with new asymptotically-efficient techniques that augment GC with efficient support for more expressive computational primitives, such as arithmetic gates, random access memory, and lookup tables.

In this talk, I will describe handling two of these primitives -- arithmetic gates and random access memory -- by showing how to compile these primitives to simple operations that are easily implemented inside GC.

My focus in this talk will be on those GC techniques that can be achieved from simple symmetric key cryptography, i.e. using only a random oracle.

Can we securely compute a two-party function?

This question went unanswered for nearly 40 years in the information-theoretic setting. In 1989, Beaver, Chor, and Kushilevitz characterized securely computable functions with deterministic output. But, in general, functions have randomized output. For them, we present a finite procedure to answer this question.

We geometrically approach this foundational question in information complexity. We prove specific lamination hulls are semi-algebraic, which was an open problem in geometry. Lamination hulls generalize convex hulls and are motivated by the hydrodynamics literature.

Paper links:
1. https://www.cs.purdue.edu/homes/hmaji/papers/BKMN22.pdf
2. https://www.cs.purdue.edu/homes/hmaji/papers/BKMN23.pdf
3. https://www.cs.purdue.edu/homes/hmaji/papers/BKMN24.pdf

How efficient can secure computation be? I will discuss the goal of minimizing the cost of secure computation under different optimization metrics, and how it motivates other questions about low-complexity cryptography that are of independent interest.

No abstract available.