Today
Bookmark and Share    
Full Text
Peer Reviewed
See detailQuantifying information flow in interactive systems
Mestel, David UL

in 2019 IEEE 32nd Computer Security Foundations Symposium (CSF) (in press)

We consider the problem of quantifying information flow in interactive systems, modelled as finite-state transducers in the style of Goguen and Meseguer. Our main result is that if the system is ... [more ▼]

We consider the problem of quantifying information flow in interactive systems, modelled as finite-state transducers in the style of Goguen and Meseguer. Our main result is that if the system is deterministic then the information flow is either logarithmic or linear, and there is a polynomial-time algorithm to distinguish the two cases and compute the rate of logarithmic flow. To achieve this we first extend the theory of information leakage through channels to the case of interactive systems, and establish a number of results which greatly simplify computation. We then show that for deterministic systems the information flow corresponds to the growth rate of antichains inside a certain regular language, a property called the width of the language. In a companion work we have shown that there is a dichotomy between polynomial and exponential antichain growth, and a polynomial time algorithm to distinguish the two cases and to compute the order of polynomial growth. We observe that these two cases correspond to logarithmic and linear information flow respectively. Finally, we formulate several attractive open problems, covering the cases of probabilistic systems, systems with more than two users and nondeterministic systems where the nondeterminism is assumed to be innocent rather than demonic. [less ▲]

Detailed reference viewed: 32 (0 UL)
Full Text
See detailRank n swapping algebra for Grassmannian
Sun, Zhe UL

E-print/Working paper (2019)

The rank n swapping algebra is the Poisson algebra defined on the ordered pairs of points on a circle using the linking numbers, where a subspace of (K^n×K^{n∗})^r/GL(n,K) is its geometric mode. In this ... [more ▼]

The rank n swapping algebra is the Poisson algebra defined on the ordered pairs of points on a circle using the linking numbers, where a subspace of (K^n×K^{n∗})^r/GL(n,K) is its geometric mode. In this paper, we find an injective Poisson homomorphism from the Poisson algebra on Grassmannian G(n,r) arising from boundary measurement map to the rank n swapping fraction algebra. [less ▲]

Detailed reference viewed: 24 (2 UL)
Full Text
See detailRank n swapping algebra for PGLn Fock--Goncharov X moduli space
Sun, Zhe UL

E-print/Working paper (2019)

The rank n swapping algebra is a Poisson algebra defined on the set of ordered pairs of points of the circle using linking numbers, whose geometric model is given by a certain subspace of (K^n×K^{n∗})^r ... [more ▼]

The rank n swapping algebra is a Poisson algebra defined on the set of ordered pairs of points of the circle using linking numbers, whose geometric model is given by a certain subspace of (K^n×K^{n∗})^r/GL(n,K). For any ideal triangulation of D_k---a disk with k points on its boundary, using determinants, we find an injective Poisson algebra homomorphism from the fraction algebra generated by the Fock--Goncharov coordinates for X_{PGL_n,D_k} to the rank n swapping multifraction algebra for r=k⋅(n−1) with respect to the (Atiyah--Bott--)Goldman Poisson bracket and the swapping bracket. This is the building block of the general surface case. Two such injective Poisson algebra homomorphisms related to two ideal triangulations T and T′ are compatible with each other under the flips. [less ▲]

Detailed reference viewed: 32 (1 UL)
Full Text
See detailMcShane identities for Higher Teichmüller theory and the Goncharov-Shen potential
Sun, Zhe UL; Huang, Yi

E-print/Working paper (2019)

In [GS15], Goncharov and Shen introduce a family of mapping class group invariant regular functions on their A-moduli space to explicitly formulate a particular homological mirror symmetry conjecture ... [more ▼]

In [GS15], Goncharov and Shen introduce a family of mapping class group invariant regular functions on their A-moduli space to explicitly formulate a particular homological mirror symmetry conjecture. Using these regular functions, we obtain McShane identities general rank positive surface group representations with loxodromic boundary monodromy and (non-strict) McShane-type inequalities for general rank positive representations with unipotent boundary monodromy. Our identities are expressed in terms of projective invariants, and we study these invariants: we establish boundedness and Fuchsian rigidity results for triple ratios. Moreover, we obtain McShane identities for finite-area cusped convex real projective surfaces by generalizing the Birman--Series geodesic scarcity theorem. We apply our identities to derive the simple spectral discreteness of unipotent bordered positive representations, collar lemmas, and generalizations of the Thurston metric. [less ▲]

Detailed reference viewed: 18 (0 UL)
Full Text
See detailAn introduction to the theory of unconditionally secure message authentication using the constructive cryptography framework
Ostrev, Dimiter UL

E-print/Working paper (2019)

We provide an introduction to certain ideas from the theory of unconditionally secure message authentication. We explain the notions of impersonation and substitution attacks, and explain how protection ... [more ▼]

We provide an introduction to certain ideas from the theory of unconditionally secure message authentication. We explain the notions of impersonation and substitution attacks, and explain how protection against these two types of attack implies composable, information theoretic security. We explain the relation of authentication protocols to universal hashing. We give both probabilistic and explicit constructions proving the existence of one way authentication protocols using a short secret key and we prove matching lower bounds on the required secret key size. Then, we turn attention to interactive authentication protocols. We explain the message size reduction technique used by Gemmell and Naor and later Naor, Segev and Smith, and how it leads to protocols with secret key size independent of the message length. We also prove a matching lower bound on the secret key entropy. We generalize the lower bound proof of Naor, Segev and Smith and remove the assumption that the message is revealed in the first flow of the protocol. [less ▲]

Detailed reference viewed: 39 (3 UL)