DROPS

Document

DOI: 10.4230/LIPIcs.LICS.2026.33

Interpreting De Finetti’s Theorem in the Category of Integrable Cones

Authors: Raphaëlle Crubillé

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract

We establish a connection between two results in the literature on probabilistic semantics: a formulation of De Finetti’s theorem in the language of category theory due to Jacobs and Staton, and the generic construction of the free exponential of Linear Logic by Melliès et al, that has been instantiated in the model of probabilistic coherence spaces by Crubillé et al. The structural proximity of these two constructions is manifest, but making this connection formal requires technical developements on the relationship between the category of stochastic kernels and the category of integrable cones, two well-known categories in probabilistic semantics. We then use this connection to give a characterisation of the total elements of the probabilistic coherence space !Bool.

Cite as

Raphaëlle Crubillé. Interpreting De Finetti’s Theorem in the Category of Integrable Cones. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 33:1-33:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{crubille:LIPIcs.LICS.2026.33,
  author =	{Crubill\'{e}, Rapha\"{e}lle},
  title =	{{Interpreting De Finetti’s Theorem in the Category of Integrable Cones}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{33:1--33:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.33},
  URN =		{urn:nbn:de:0030-drops-268208},
  doi =		{10.4230/LIPIcs.LICS.2026.33},
  annote =	{Keywords: De Finetti theorem, probabilistic semantics, Lafont models of Linear Logic}
}

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2020.108

On Higher-Order Cryptography

Authors: Boaz Barak, Raphaëlle Crubillé, and Ugo Dal Lago

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract

Type-two constructions abound in cryptography: adversaries for encryption and authentication schemes, if active, are modeled as algorithms having access to oracles, i.e. as second-order algorithms. But how about making cryptographic schemes themselves higher-order? This paper gives an answer to this question, by first describing why higher-order cryptography is interesting as an object of study, then showing how the concept of probabilistic polynomial time algorithm can be generalized so as to encompass algorithms of order strictly higher than two, and finally proving some positive and negative results about the existence of higher-order cryptographic primitives, namely authentication schemes and pseudorandom functions.

Cite as

Boaz Barak, Raphaëlle Crubillé, and Ugo Dal Lago. On Higher-Order Cryptography. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 108:1-108:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barak_et_al:LIPIcs.ICALP.2020.108,
  author =	{Barak, Boaz and Crubill\'{e}, Rapha\"{e}lle and Dal Lago, Ugo},
  title =	{{On Higher-Order Cryptography}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{108:1--108:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.108},
  URN =		{urn:nbn:de:0030-drops-125153},
  doi =		{10.4230/LIPIcs.ICALP.2020.108},
  annote =	{Keywords: Higher-order computation, probabilistic computation, game semantics, cryptography}
}

Search Results

Documents authored by Crubillé, Raphaëlle

Interpreting De Finetti’s Theorem in the Category of Integrable Cones

Abstract

Cite as

On Higher-Order Cryptography

Abstract

Cite as

Thanks for your feedback!

Could not send message