Lune

POPL2020Top-tier venue

A probabilistic separation logic

Gilles Barthe, Justin Hsu, Kevin Liao

Abstract

Probabilistic independence is a useful concept for describing the result of random sampling—a basic operation in all probabilistic languages—and for reasoning about groups of random variables. Nevertheless, existing verification methods handle independence poorly, if at all. We propose a probabili stic separation logic PSL, where separation models probabilistic independence. We first give a new, probabilistic model of the logic of bunched implications (BI). We then build a program logic based on these assertions, and prove soundness of the proof system. We demonstrate our logic by verifying information-theoretic security of cryptographic constructions for several well-known tasks, including private information retrieval, oblivious transfer, secure multi-party addition, and simple oblivious RAM. Our proofs reason purely in terms of high-level properties, like independence and uniformity.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

24 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties cites Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning
  • Outcome Logic: A Unifying Foundation for Correctness and Incorrectness Reasoning cites Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers24

  1. Outcome Logic: A Unifying Foundation for Correctness and Incorrectness ReasoningNoam Zilberstein, Derek Dreyer, Alexandra SilvaOOPSLA 2023 · 39 citations
  2. Twist: sound reasoning for purity and entanglement in Quantum programsCharles Yuan, Christopher McNally, Michael CarbinPOPL 2022 · 30 citations
  3. Hyper Hoare Logic: (Dis-)Proving Program HyperpropertiesThibault Dardinier, Peter MüllerPLDI 2024 · 28 citations
  4. Asynchronous Probabilistic Couplings in Higher-Order Separation LogicSimon Oddershede Gregersen, Alejandro Aguirre, Philipp G. Haselwarter, Joseph Tassarotti et al.POPL 2024 · 23 citations
  5. Lilac: A Modal Separation Logic for Conditional ProbabilityJohn M. Li, Amal Ahmed, Steven HoltzenPLDI 2023 · 22 citations

Builds on1

  1. A language for probabilistically oblivious computationDavid Darais, Ian Sweet, Chang Liu, Michael HicksPOPL 2020 · 12 citations

Related papers

  1. Combining Classical and Probabilistic Independence Reasoning to Verify the Security of Oblivious AlgorithmsPengbo Yan, Toby Murray, Olga Ohrimenko, Van-Thuan Pham et al.FM 2024 · 2 citations
  2. A Bunched Logic for Conditional IndependenceJialu Bao, Simon Docherty, Justin Hsu, Alexandra SilvaLICS 2021 · 15 citations
  3. Probabilistic Concurrent Reasoning in Outcome Logic: Independence, Conditioning, and InvariantsNoam Zilberstein, Alexandra Silva, Joseph TassarottiPOPL 2026 · 4 citations
  4. A separation logic for negative dependenceJialu Bao, Marco Gaboardi, Justin Hsu, Joseph TassarottiPOPL 2022 · 17 citations
  5. Bayesian Separation Logic: A Logical Foundation and Axiomatic Semantics for Probabilistic ProgrammingShing Hin Ho, Nicolas Wu, Azalea RaadPOPL 2026 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines