Lune

POPL2024Top-tier venue

Internalizing Indistinguishability with Dependent Types

Yiyun Liu, Jonathan Chan, Jessica Shi, Stephanie Weirich

Abstract

In type systems with dependency tracking, programmers can assign an ordered set of levels to computations and prevent information flow from high-level computations to the low-level ones. The key notion in such systems is indistinguishability : a definition of program equivalence that takes into account the parts of the program that an observer may depend on. In this paper, we investigate the use of dependency tracking in the context of dependently-typed languages. We present the Dependent Calculus of Indistinguishability (DCOI), a system that adopts indistinguishability as the definition of equality used by the type checker. DCOI also internalizes that relation as an observer-indexed propositional equality type, so that programmers may reason about indistinguishability within the language. Our design generalizes and extends prior systems that combine dependency tracking with dependent types and is the first to support conversion and propositional equality at arbitrary observer levels. We have proven type soundness and noninterference theorems for DCOI and have developed a prototype implementation of its type checker.

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.

2 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

  • Consistency of a Dependent Calculus of Indistinguishability cites A graded dependent type system with a usage-aware semantics
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Consistency of a Dependent Calculus of IndistinguishabilityYiyun Liu, Jonathan Chan, Stephanie WeirichPOPL 2025 · 3 citations
  2. Structural Information Flow: A Fresh Look at Types for Non-interferenceHemant Gouni, Frank Pfenning, Jonathan AldrichOOPSLA 2025 · 1 citation

Builds on1

  1. A graded dependent type system with a usage-aware semanticsPritam Choudhury, Harley Eades III, Richard A. Eisenberg, Stephanie WeirichPOPL 2021 · 33 citations

Related papers

  1. Impredicative Observational EqualityLoïc Pujet, Nicolas TabareauPOPL 2023 · 14 citations
  2. Definitional Proof Irrelevance Made AccessibleThiago Felicissimo, Yann Leray, Loïc Pujet, Nicolas Tabareau et al.LICS 2026
  3. Label dependent lambda calculus and gradual typingWeili Fu, Fabian Krause, Peter ThiemannOOPSLA 2021
  4. A relational theory of effects and coeffectsUgo Dal Lago, Francesco GavazzoPOPL 2022 · 22 citations
  5. Coeffects for sharing and mutationRiccardo Bianchini, Francesco Dagnino, Paola Giannini, Elena Zucca et al.OOPSLA 2022 · 5 citations
Dusk over the sea between two cliffs drawn in fine vertical lines