Write a Blog >>
Thu 23 Jan 2020 15:35 - 15:56 at Ile de France III (IDF III) - Probabilistic Programming Chair(s): Ohad Kammar

An oblivious computation is one that is free of direct and indirect information leaks, e.g., due to observable differences in timing and memory access patterns. This paper presents λobliv, a core language whose type system enforces obliviousness. Prior work on type-enforced oblivious computation has focused on deterministic programs. λobliv is new in its consideration of programs that implement probabilistic algorithms, such as those involved in cryptography. λobliv employs a substructural type system and a novel notion of probability region to ensure that information is not leaked via the observed distribution of visible events. Probability regions support reasoning about probabilistic correlation and independence between values, and our use of probability regions is motivated by a source of unsoundness that we discovered in the type system of ObliVM, a language for implementing state of the art oblivious algorithms. We prove that λobliv’s type system enforces obliviousness and show that it is expressive enough to typecheck advanced tree-based oblivious RAMs.

Slides - A Language for Probabilistically Oblivious Computation (lpo-slides.pdf)2.65MiB

Thu 23 Jan

POPL-2020-Research-Papers
15:35 - 16:40: Research Papers - Probabilistic Programming at Ile de France III (IDF III)
Chair(s): Ohad KammarUniversity of Edinburgh
POPL-2020-Research-Papers15:35 - 15:56
Talk
David DaraisUniversity of Vermont, Ian SweetUniversity of Maryland, Chang LiuCitadel Securities, Michael HicksUniversity of Maryland
Link to publication DOI Media Attached File Attached
POPL-2020-Research-Papers15:56 - 16:18
Talk
Alexander VandenbrouckeKU Leuven, Belgium, Tom SchrijversKU Leuven
Link to publication DOI Media Attached File Attached
POPL-2020-Research-Papers16:18 - 16:40
Talk
Feras SaadMassachusetts Institute of Technology, Cameron FreerMassachusetts Institute of Technology, Martin RinardMIT, Vikash MansinghkaMIT
Link to publication DOI Media Attached File Attached