Notes

Zero Knowledge Proofs Motivation & Foundational Context ZKPs sit at the intersection of Complexity Theory, Cryptography, and Interactive Proof Systems. The core question: can you convince someone you know something without revealing what you know? This has profound implications for privacy-preserving authentication, blockchain protocols, and verifiable computation. Interactive Proof Systems Interactive Theorem Provers The Classical Model An interactive proof system involves two parties exchanging messages: Prover (P): Computationally unbounded; claims a statement is true. Verifier (V): Probabilistic polynomial-time (PPT); decides accept/reject. “An interactive proof system for a language $L$ is a protocol $(P, V)$ such that completeness and soundness hold.” ~ Goldwasser, Micali, Rackoff (1985) ...

Universal Composability (UC) Framework Motivation and Background The UC framework, introduced by Ran Canetti (FOCS 2001, JACM 2020), addresses a fundamental limitation of prior security definitions for cryptographic protocols: composability. Traditional security proofs analyze protocols in isolation (“in vitro”), but real-world deployments involve concurrent execution of many protocol sessions in adversarially-controlled environments (“in vivo”). A protocol proven secure stand-alone may catastrophically fail when composed with other protocols—even with itself. The key insight: define security once, for a single protocol session, but in a way that automatically guarantees security under arbitrary concurrent composition with any other protocols. This is a paradigm shift from property-specific game-based definitions to a unified simulation-based framework. ...

Process Calculus and Session Types (Honda, Yoshida, Carbone) Historical Lineage and Motivation The process calculus literature on session types originates from the fundamental insight that communication itself can be typed. Just as data types codify the structure of data, session types codify the structure of communication and make it available to programming tools. The key intellectual trajectory runs: Milner et al. (1992): The π-calculus — a calculus of mobile processes with name-passing and channel mobility. Honda (1993): “Types for Dyadic Interaction” at CONCUR'93 — the first session type system. Takeuchi, Honda & Kubo (1994): An interaction-based language with typing at PARLE'94. Honda, Vasconcelos & Kubo (1998): The canonical binary session type system at ESOP'98 (awarded ETAPS Test-of-Time Award, 2019). Honda, Yoshida & Carbone (2008/2016): Multiparty Asynchronous Session Types (MPST) at POPL'08, journal version in JACM 2016. The driving application domain is structured communication-centred programming: web services, business protocols, parallel scientific computing, multi-core programming. The thing you have to remember is that session types are not just about preventing type mismatches on messages — they statically enforce the entire conversational protocol. ...

NOTE: this is an old set of note, and it is of quite bad quality, it should be completely rewritten. $$ F(x) = \int _{-\infty}^{x} f(t) \, dt $$ A volte la densità non è definita, mentre la funzione cumulativa lo è , per questo spesso cominciamo a definire partendo dalla definizione. $$ F_{X}(x) = \mathbb{P}(X \leq x) = \int_{-\infty}^{x} f_{X}(z) \, dz $$Generalized inverse This is known as the universality of the uniform, every invertible CDF can be written with respect to the uniform distribution. ...

Questo è stato creato da 1948 Shannon in (Shannon 1948). Questa nozione è basata sulla nozione di probabilità, perché le cose rare sono più informative rispetto a qualcosa che accade spesso. Introduction to Entropy The Shannon Information Content $$ h(x = a_{i}) = \log_{2}\frac{1}{P(x = a_{i})} $$ We will see that the entropy is a weighted average of the information, so the expected information content in a distribution. Kolmogorov complexity è un modo diverso per definire la complessità. Legato è Neural Networks#Kullback-Leibler Divergence. ...

These notes cover the core concepts of the Information Bottleneck method, widely used in machine learning and theoretical neuroscience. We start by defining the fundamental tension in learning and representation. Learning Design Goals Compression: The representation should be as simple as possible (Occam’s Razor). Relevance: The representation must retain enough information to predict the target variable accurately. Generalization: The system should perform well on unseen data, which is often a function of finding the right balance between the first two. Invariance: The representation should ignore “nuisance variables” (noise) present in the input that do not correlate with the output. ...

Log Linear Models can be considered the most basic model used in natural languages. The main idea is to try to model the correlations of our data, or how the posterior $p(y \mid x)$ varies, where $x$ is our single data point features and $y$ are the labels of interest. This is a form of generalization because contextualized events (x, y) with similar descriptions tend to have similar probabilities. These kinds of models are so common that it has been discovered in many fields (and thus assuming different names): some of the most famous are Gibbs distributions, undirected graphical models, Markov Random Fields or Conditional Random Fields, exponential models, and (regularized) maximum entropy models. Special cases include logistic regression and Boltzmann machines. ...

2.1 Elementi di base 2.1.1 Definizione e caratteristiche Tutto è un insieme (su questo si basa la maggior parte della matematica) Efficace nella descrizione degli oggetti (infiniti è ez), ma non è efficiente nel calcolo in quanto non dà nessun indizio sul’implementazione in memoria o sul modo per calcolarlo, c’è solo una associazione Si può concludere che per l’informatico non serve a molto questa teoria, ma è la base per la matematica. ...

pWith confidential computing we want to guarantee confidentiality and integrity of a user’s computation running on a remote (cloud) system, including: The program Its inputs and outputs Intermediate state, control flow, etc. Even if do not trust the cloud provider! Usually it is easy to guarantee that kind of privacy if you are storing or communicating using encryption methods (see Asymmetric Cryptography, Block Ciphers), but it’s difficult to do so if the program is running. ...

Trusted Execution Environments and the Secure Computation Trust Spectrum Motivation & Foundational Context How do you verify that a computation was performed correctly — and privately — when you don’t control the machine? This question sits at the intersection of Cryptography, Hardware Security, Mechanism Design, and Multi-Agent Systems. Different answers trade off trust assumptions, performance, and expressiveness, forming a trust spectrum that has deep consequences for agent coordination, blockchain protocols, and verifiable AI. ...