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

Displayed time zone: Saskatchewan, Central America change

15:35 - 16:40
Probabilistic ProgrammingResearch Papers at Ile de France III (IDF III)
Chair(s): Ohad Kammar University of Edinburgh
15:35
21m
Talk
A Language for Probabilistically Oblivious Computation
Research Papers
David Darais University of Vermont, Ian Sweet University of Maryland, Chang Liu Citadel Securities, Michael Hicks University of Maryland
Link to publication DOI Media Attached File Attached
15:56
21m
Talk
PλωNK: Functional Probabilistic NetKAT
Research Papers
Alexander Vandenbroucke KU Leuven, Belgium, Tom Schrijvers KU Leuven
Link to publication DOI Media Attached File Attached
16:18
21m
Talk
Optimal Approximate Sampling From Discrete Probability Distributions
Research Papers
Feras A. Saad Massachusetts Institute of Technology, Cameron Freer Massachusetts Institute of Technology, Martin C. Rinard MIT, Vikash K. Mansinghka MIT
Link to publication DOI Media Attached File Attached