Jonathan Poritz's [P]reprint Page

Publications:

1. Universal Gates in Other Universes
   • Appeared in G.W. Dueck and D.M. Miller (Eds.): RC 2013, LNCS 7948, pp. 155-167; © Springer-Verlag Berlin Heidelberg 2013
   • Abstract:
     I describe a new formalization for computation which is similar to traditional circuit models but which depends upon the choice of a family of [semi]groups — essentially, a choice of the structure group of the universe of the computation. Choosing the symmetric groups results in the reversible version of classical computation; the unitary groups give quantum computation. Other groups can result in models which are stronger or weaker than the traditional models, or are hybrids of classical and quantum computation.

     One particular example, built out of the semigroup of doubly stochastic matrices, yields classical but probabilistic computation, helping explain why probabilistic computation can be so fast. Another example is a smaller and entirely $\RR$eal version of the quantum one which uses a (real) rotation matrix in place of the (complex, unitary) Hadamard gate to create algorithms which are exponentially faster than classical ones.

     I also articulate a conjecture which would help explain the different powers of these different types of computation, and point to many new avenues of investigation permitted by this model.

   • The final publication is available at link.springer.com
   • Here is my personal version: PDF -- 256K
2. Sharing the Power Over, and the Responsibility for, Information Technology Decisions in Academia
   • Presented at the October AAUP Shared Governance Conference
   • Abstract:
     Information technology (IT) — hardware, software, and networks — is enormously important in the daily lives of everyone on university campuses. Yet decisions about academic IT are usually made by a small administrative team with almost no faculty input. This can lead to policies and priorities which poorly serve pedagogical and scholarly needs, and is a clear violation of the AAUP Statement on Government of Colleges and Universities, hence violating academic freedom. I propose here a different model of shared IT governance in academia and suggest that the first step towards realizing this new model is for faculty to educate itself a little about real IT alternatives.
   • Here (PDF -- 192K) is a preliminary version of this article.
3. Information Technology Wants to Be Free
   • Appeared in the September/October 2012 issue of Academe: Magazine of the AAUP; the AAUP released it under a CC BY-NC-SA 3.0 US licence
   • Abstract:
     The free-software and open-source communities, dedicated to the open exchange of research and to the idea that knowledge is a public good, are the natural allies of academic faculty.
   • This is the official electronic version
   • And here are two guest posts I made on the AAUP's "Academe Blog related to my article:
     • FLOSS for the Mind: From the Free Software Foundation to the Creative Commons
     • Commercial Software is Authoritarian, FLOSS is the Enlightenment
   • And here is a version with my own typesetting, more graphics, and an extra paragraph of text: PDF -- 820K
4. On entropy-preserving stochastic averages
   • With Alan Poritz
   • Appeared as Linear Algebra and Its Applications 434(6) 1425-1443 (2010); © 2010 Elsevier Inc
   • Abstract:
     When an $n\times n$ doubly stochastic matrix $A$ acts on $\RR^n$ on the left as a linear transformation and $P$ is an $n$-long probability vector, we refer to the new probability vector $AP$ as the stochastic average of the pair $(A,P)$. Let $\boldsymbol{\Gamma}_n$ denote the set of pairs $(A,P)$ whose stochastic average preserves the entropy of $P$: $H(AP)=H(P)$. $\boldsymbol{\Gamma}_n$ is a subset of $\mathbf{B}_n\times\boldsymbol{\Sigma}_n$ where $\mathbf{B}_n$ is the Birkhoff polytope and $\boldsymbol{\Sigma}_n$ is the probability simplex.

     We characterize $\boldsymbol{\Gamma}_n$ and determine its geometry, topology, and combinatorial structure. For example, we find that $(A,P)\in\boldsymbol{\Gamma}_n$ if and only if $A^tAP=P$. We show that for any $n$, $\boldsymbol{\Gamma}_n$ is a connected set, and is in fact piecewise-linearly contractible in $\mathbf{B}_n\times\boldsymbol{\Sigma}_n$. We exhibit two finite decompositions of $\boldsymbol{\Gamma}_n$. We derive the geometry of the fibers $(A,\cdot)$ and $(\cdot,P)$ of $\boldsymbol{\Gamma}_n$. $\boldsymbol{\Gamma}_3$ is worked out in detail. Our analysis exploits the convexity of $x\log x$ and the structure of an efficiently computable bipartite graph that we associate to each ds-matrix. This graph also lets us represent such a matrix in a permutation-equivalent, block diagonal form where each block is doubly stochastic and fully indecomposable.

   • The definitive version is available at LAA's web site or through the doi:10.1016/j.laa.2010.10.014
   • The text of the following is the corrected, final (published) version, however without the journal's formatting: PDF -- 256K
5. Who searches the searchers? community privacy in the age of monolithic search engines
   • Appeared as The Information Society 23(5) 383-389 (2007); © 2007 Taylor & Francis Group, LLC
   • Abstract:
     Privacy has largely been equated with every individual's right to privacy. Accordingly, current efforts to protect privacy on the Internet have sought anonymity by breaking, where possible, links with personally identifiable information (PII) — all uses of aggregated data stripped of PII are considered legitimate. This article argues that we need to use a broader concept, general or group identifying information (GII), because even aggregated data stripped of PII violate privacy at the community level. The search engine companies, or anyone else with access to their log files, can use these data to generate a moment-by-moment view of what is on the collective mind. Such a view can be used in a variety of ways, some with deep economic and even political impact. In order to frame this discussion, it is necessary to examine some of the realities of the search engine-mediated associative interface to the World Wide Web. While this interface has enormous benefits for the networked world, it also fundamentally changes a number of issues underlying various current debates about Internet governance.
   • PDF -- 184K
6. Intrusion-Tolerant Middleware: The Road to Automatic Security
   • With Christian Cachin, Yves Deswarte, Nuno Neves, David Powell, Robert Stroud, Paulo Verissimo, and Ian Welch
   • Appeared as IEEE Security & Privacy 4 (2006) 54-62; © 2006 IEEE
   • Abstract:
     The pervasive interconnection of systems throughout the world has given computer services a significant socioeconomic value that both accidental faults and malicious activity can affect. The classical approach to security has mostly consisted of trying to prevent bad things from happening–by developing systems without vulnerabilities, for example, or by detecting attacks and intrusions and deploying ad hoc countermeasures before any part of the system is damaged. But what if we could address both faults and attacks in a seamless manner, through a common approach to security and dependability? This is the proposal of intrusion tolerance, which assumes that

     • systems remain somewhat faulty or vulnerable;
     • attacks on components will sometimes be successful; and
     • automatic mechanisms ensure that the overall system nevertheless remains secure and operational.

     No large-scale computer network can be completely protected from attacks or intrusions. Just as chains break at their weakest link, any inconspicuous vulnerability left behind by firewall protection or any subtle attack that goes unnoticed by intrusion detection will be enough to let a hacker defeat a seemingly powerful defense. Using ideas from fault tolerance that put emphasis on automatically detecting, containing, and recovering from attacks, the European project MAFTIA (Malicious-and Accidental-Fault Tolerance for Internet Applications) set out to develop an architecture and a comprehensive set of mechanisms and protocols for tolerating both accidental faults and malicious attacks in complex systems. Here, we report some of the advances made by the several teams involved in this project, which brought together international expertise in the areas of information security and fault tolerance.
   • ps.gz -- 660K
   • PDF -- 172K
7. Trust[ed| in] computing, signed code, and the heat death of the Internet
   • Appeared at the 2nd ACM SAC TRECK Track, April 2006. © ACM, (2006)
   • Abstract:
     The Trusted Computing Group (TCG) is an industry consortium which has invested in the design of a small piece of hardware (roughly a smartcard), called a Trusted Platform Module (TPM), and associated APIs and protocols which are supposed to help increase the reliability of TPM-endowed computing platforms (trusted platforms). The TCG envisions that boot loaders, OSes and applications programs on trusted platforms will all collaborate in building a cryptographic hash chain which represents the current execution state of the platform, and which resides on the TPM. Remote sites can then verify that the platform in question is ``in a trusted state'' by requesting the TPM to produce a signed data blob containing the value of this hash chain, which can then be compared against a library of recognized (``trusted'') values; this process is called remote attestation, and the whole picture is sometimes referred to as integrity-based computing (IBC).

     We argue that there is a fundamental gap between the stated goals of the TCG's IBC and the central technology that is intended to achieve these goals, which gap is simply that remote attestation asks the attesting platform to answer the wrong question -- the platform is not attesting to its security state, but rather to its execution state, and this underlies all of the troublesome use cases, as well as a number of the practical difficulties, of the TCG world-view. One response to this is to replace standard TCG attestation with property-based attestation (PBA), which places the emphasis on deriving security properties from (potentially) elaborate trust models and conditional statements of security property dependencies. Herein the central rôle for IBC of trust and deriving consequences from precise trust models becomes clear.

     Finally, we claim that the TCG's own remote attestation is most properly viewed in fact as a form of PBA, with a certain simple trust model and database of security properties. From this point of view, it becomes clear that IBC can have a much less restrictive range of applications than envisioned merely by the TCG. In fact, with the right ``trust infrastructure'' and sufficiently open software using and relying upon this infrastructure, IBC could actually realize some of the portentous early promises of the TCG for truly increasing the reliability of individual users' platforms and pushing back the apocalyptic rise of malware, especially if platforms and OSes virtualize and enforce some kind of signed code contracts.

   • This (ps.gz -- 88K; PDF -- 92K) is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version is published by the ACM.
8. Hash woes
   • With Morton Swimmer
   • Appeared as Virus Bulletin October, 2004, 14-16; © 2004 Virus Bulletin, Ltd.
   • Abstract:
     In a rump session of the August 2004 Crypto conference, where attendees have the chance to give informal (non-refereed) presentations of works in progress, a group of Chinese researchers demonstrated flaws in a whole set of hash functions and the entire crypto community was abuzz. In this article, we will clarify the situation and draw lessons from this incident.
   • PDF -- 432K
9. Secure intrusion-tolerant replication on the Internet
   • With Christian Cachin
   • Appeared in Proceedings of the International Conference on Dependable Systems and Networks (DSN-2002) (2002) 167-176; © 2002 IEEE
   • Abstract:
     This paper describes a Secure INtrusion-Tolerant Replication Architecture (SINTRA) for coordination in asynchronous networks subject to Byzantine faults. SINTRA supplies a number of group communication primitives, such as binary and multi-valute Byzantine agreement, reliable and consistent broadcast, and an atomic broadcast channel. Atomic broadcast immediately provides secure state-machine replication. The protocols are designed for an asynchronous wide-area network, such as the Internet, where messages may be delayed indefinitely, the servers do not have acces to a common clock, and up to one third of the servers may fail in potentially malicious ways. Security is achieved trhough the use of threshold public-key cryptography, in particular through a cryptographic common coin based on the Diffie-Hellman problem that underlies the randomized protocols in SINTRA. The implementation of SINTRA in Java is described and timing measurements are given for a test-bed of servers distributed over three continents. They show that extensive use of public-key cryptography does not impose a large overhead for coordination in wide-area networks.
   • ps.gz -- 76K
   • PDF -- 168K
10. Social preferences and price cap regulation
    • With Alberto Iozzi and Edilio Valentini
    • Appeared as Journal of Public Economic Theory 4 (2002) 93-112; © 2002 Blackwell Publishers
    • The definitive version is available at www.blackwell-synergy.com
    • Abstract:
      This paper analyses the allocative properties of price cap regulation under a very general hypothesis on the nature of society's preferences. We propose a generalised form of price cap formula (GPC) and we show that it ensures the convergence to optimal (second best) prices in the long-run equilibrium for virtually any form of the welfare function. In particular, we show that the GPC guarantees that the social welfare increases over time and converges to a long run equilibrium value which is socially optimal, given the level of profits obtained by the regulated firm in equilibrium. Hence, the result of the convergence to Ramsey prices of Laspeyres-type price cap regulation is a particular instance of our more general result. The generalisation of the price cap mechanism we propose does not substantially alter the simplicity typical of traditional price cap schemes nor does it impose much higher informational requirements on the regulator's side. To substantiate this argument, we provide an explicit and relatively easy to calculate and implement price cap formula for a distributionally weighted utilitarian welfare functions, as proposed by Feldstein (1972a).
    • ps.gz -- 242K
    • PDF -- 127K
11. Around polygons in $\RR^3$ and $S^3$
    • With John J. Millson
    • Appeared as Communications in Mathematical Physics 218 (2001) 315-331; © 2001 Springer-Verlag
    • The original publication is available at www.springerlink.com
    • Abstract:
      We survey certain moduli spaces in low dimensions and some of the geometric structures that they carry, and then construct identifications among all of these spaces. In particular, we identify the moduli spaces of polygons in $\RR^3$ and $S^3$, the moduli space of restricted representations of the fundamental group of a punctured 2-sphere, the moduli space of flat connections on a punctured sphere, the moduli space of parabolic bundles on a sphere, the moduli space of weighted points on $\CC\PP^1$ and the symplectic quotient of $SO(3)$ acting diagonally on $(S^2)^n$. All of these spaces depend upon parameters and some of the above identifications require the parameters to be small. One consequence of this work is that these spaces are all biholomorphic with respect to the most natural complext structures they can each be given.
    • ps.gz -- 119K
    • PDF -- 143K
12. The moduli space of boundary compactifications of $SL(2,\RR)$
    • With Alessandra Iozzi
    • Appeared as Geometriae Dedicata 76 (1999) 65-79; © 1999 Kluwer Academic Publishers
    • The original publication is available at www.springerlink.com
    • Abstract:
      In an earlier paper, the authors introduced the notion of a boundary compactification of $SL(2,\RR)$ and $SL(2,\CC)$, a normal projective embedding of $PSL_2$ arising as the Zariski closure of an orbit in $(\PP^1)^n$ under the diagonal action of $SL_2$. Here the moduli space of such boundary compactifications of $SL(2,\RR)$ is shown to be a contractible hyperbolic orbifold, by using the Schwarz-Christoffel transformation to identify it with a quotient of the moduli space of equi-angular planar polygons.
    • ps.gz -- 527K
    • PDF -- 546K
13. Boundary compactifications of $SL(2,\RR)$ and $SL(2,\CC)$
    • With Alessandra Iozzi
    • Appeared as Forum Mathematicum 11 (1999) 385-397; © 1999 de Gruyter
    • Abstract:
      We construct a class of normal projective embeddings of $PSL(2,k)$, for $k=\RR$ and $\CC$, which we call boundary compactifications of $SL(2,k)$. These arise essentially as the Zariski closures of orbits in $(\PP^1_k)^n$ under the diagonal action of $SL(2,k)$. In addition, we determine precisely when our examples can be $SL(2,k)$-homeomorphic, showing that the resulting deformation space is a countable union of positive-dimensional families.
    • ps.gz -- 176K
    • PDF -- 153K
14. Ford and Dirichlet domains for cyclic subgroups of $PSL(2,\CC)$ acting on $H^3_\RR$ and $\partial H^3_\RR$
    • With Todd Drumm
    • First published in Conformal Geometry and Dynamics 3 (1999) 116-150; © 1999 American Mathematical Society
    • Electronic version available at the AMS web site -- check it out, it's interactive!
    • Abstract:
      Let $\Gamma$ be a cyclic subgroup of $PSL_2(\CC)$ generated by a loxodromic element. The Ford and Dirichlet fundamental domains for the action of $\Gamma$ on $\HH^3_\RR$ are the complements of configurations of half-balls centered on the plane at infinity $\partial\HH^3_\RR$. Jørgensen (On cyclic groups of Möbius transformations, Math. Scand. 33 (1973), 250-260) proved that the boundary of the intersection of the Ford fundamental domain with $\partial\HH^3_\RR$ always consists of either two, four or six circular arcs and stated that an arbitrarily large number of hemispheres could contribute faces to the Ford domain in the interior of $\HH^3_\RR$. We give new proofs of Jørgensen's results, prove analogous facts for Dirichlet domains and for Ford and Dirichlet domains in the interior of $\HH^3_\RR$, and give a complete decomposition of the parameter space by the combinatorial type of the corresponding fundamental domain.
    • ps.gz -- 3812K
    • PDF -- 651K
15. Parabolic vector bundles and Hermitian-Yang-Mills connections over a Riemann surface
    • Appeared as International Journal of Mathematics 4 (1993) 467-501; © 1993 World Scientific Publishing Company
    • Abstract:
      We study a certain moduli space of irreducible Hermitian-Yang-Mills connections on a unitary vector bundle over a punctured Riemann surface. The connections used have non-trivial holonomy around the punctures lying in fixed conjugacy classes of $U(n)$ and differ from each other by elements of a weighted Sobolev space; these connections give rise to parabolic bundles in the sense of Mehta and Seshadri. We show in fact that the moduli space of stable parabolic bundles can be identified with our moduli space of HYM connections, by proving that every stable bundle admits a unique unitary gauge orbit of Hermitian-Yang-Mills connections.
    • Here is an electronic version of an article with doi:10.1142/S0129167X9300025X
    • dvi.gz -- 72K
    • ps.gz -- 129K

IBM Research Reports and European Union project deliverables:

1. Property attestation--scalable and privacy-friendly security assessment of peer computers
   • With Matthias Schunter, Els Van Herreweghen and Michael Waidner
   • IBM Research Report RZ3548, 2004; © 2004 IBM
   • PDF -- 296K
   • Abstract:
     A core security challenge is the integrity verification of the software that is executed on a machine. For example, an enterprise needs to know whether a gate- way machine has been infected by malicious code. One prevailing approach is to use directories of configuration check-sums to detect when a configuration has been changed (see www.tripwire.org). These software-only solutions have limitations when the operating system itself is compromised. The tamper-resistant Trusted Platform Module (TPM) specified by the Trusted Computing Group (TCG) allows a TPM-enhanced platform to securely attest to a configuration of a machine. Based on such binary attestation, a verifying peer computer can then decide whether or not to trust the verified platform.

     In this paper, we argue that the approach of binary attestation is not privacy-friendly, scalable or open and vendor-neutral. The main criticism is that this approach needlessly discloses the complete configuration (i.e., all executed software) of a machine. The focus of binary attestation are the binaries instead of their security. We present a protocol and architecture for property attestation that resolves these problems. With property attestation, a verifier is securely assured of security properties of the verified platform's execution environment without receiving detailed configuration data. This enhances privacy and scalability since the verifier needs to be aware of its few required security properties instead of an huge number of acceptable configurations.

   • Also available directly from IBM.
2. Alternative computational devices and architectures
   • With Giovanni Cherubini, Heike Riel and Gian Salis
   • Published 2003
   • Unfortunately, this is an IBM Confidential research report.
3. Full Design of Dependable Third Party Services
   • With Christian Cachin (editor), et al.
   • Deliverable D5, Project MAFTIA IST-1999-11583, 2001
   • Abstract:
     This document describes the designs of a generic distributed certification authority and of a trusted party for optimistic fair exchange that are based on fault-tolerant middleware for service replication. It also discusses other uses of the replication middleware for implementing trusted services. It may serve as a blueprint for building generic trusted third-party services that use the state-machine replication approach.
   • See below for copyright information
   • PDF -- 188K
   • Also available as IBM Research Report RZ3394 (which is © 2001 IBM)
4. First specification of APIs and protocols for the MAFTIA middleware
   • With Nuno Ferreira Neves and Paulo Verissimo (editors), et al.
   • Deliverable D24, Project MAFTIA IST-1999-11583, 2001
   • Abstract:
     This document describes the first specification of the APIs and Protocols for the MAFTIA Middleware. The architecture of the middleware subsystem has been described in a previous document, where the several modules and services were introduced: Activity Services; Communication Services; Network Abstraction; Trusted and Untrusted Components. The purpose of the present document is to make concrete the functionality of the middleware components, by defining their application programming interfaces, and describing the protocols implementing the above-mentioned functionality.
   • See below for copyright information
   • PDF -- 816K
   • Also available as IBM Research Report RZ3365 (which is © 2001 IBM)
5. Specification of dependable trusted third parties
   • With Christian Cachin (editor), et al.
   • Deliverable D26, Project MAFTIA IST-1999-11583, 2001
   • Abstract:
     This document describes an architecture for secure service replication in an asynchronous network like the Internet, where a malicious adversary may corrupt some servers and control the network. The underlying protocols for Byzantine agreement and for atomic broadcast rely on recent developments in threshold cryptography. These assumptions are discussed in detail and compared to related work from the last decade. A formal model using concepts from modern cryptography is developed, modular definitions for several broadcast problems are presented, including reliable, atomic, and secure causal broadcast, and protocols implementing them. Reliable broadcast is a basic primitive, also known as the Byzantine generals problem, providing agreement on a delivered message. Atomic broadcast imposes additionally a total order on all delivered messages. A randomized asynchronous atomic broadcast protocol is presented that maintains liveness and safety at the same time. It is based on a new efficient protocol for multi-valued asynchronous Byzantine agreement with an external validity condition. Secure causal broadcast extends atomic broadcast by encryption to guarantee a causal order among the delivered messages. Furthermore, it is discussed how several distributed trusted applications can be realized using such an architecture: a digital notary service, a trusted third party for fair exchange, a certification authority, and an authentication service.
   • See below for copyright information
   • PDF -- 456K
   • Also available as IBM Research Report RZ3318 (which is © 2001 IBM)

Articles in Progress:

1. Finding geometry in classical number theory: the Chinese Remainder Theorem, Kronecker's Theorem and wrapping lines around tori
   • Under construction
2. Perelman proves Poincaré
   • This is an expository paper on the Poincaré and Geometrization Conjectures. The goal of the paper is to lay out all of the definitions, as well as some related motivational results and explanatory material, in a form which should be accessible to an advanced undergraduate mathematics student (say who has had advanced calculus and some linear and abstract algebra). The paper has been submitted for publication.
   • PDF -- 268K
3. Hash chains: a weak link in trusted computing
   • Undergoing revisions
   • ...but here (ps.gz -- 180K; PDF -- 220K) is a preliminary version
4. Who?ogle: an associative interface to the web which preserves individual and community privacy
   • In preparation, watch this space.
5. Hem-lines, web rankings and other correlates of the stock market
   • In preparation, watch this space.
6. Ergodic theory and cryptography
   • In preparation, watch this space.

1. Method and device for verifying the security of a computing platform
   • With Matthias Schunter, Els Van Herreweghen and Michael Waidner
   • US 7,770,000 B2, granted August 3, 2010
   • Here is the patent summary page: PDF -- 180K
   • Abstract:
     Method and device for verifying the security of a computing platform. In the method for verifying the security of a computing platform a verification machine is first transmitting a verification request via an integrity component to the platform. Then the platform is generating by means of a trusted platform module a verification result depending on binaries loaded on the platform, and is transmitting it to the integrity verification component. Afterwards, the integrity verification component is determining with the received verification result the security properties of the platform and transmits them to the verification machine. Finally, the verification machine is determining whether the determined security properties comply with desired security properties.
   • owned by IBM
2. Attestation of computing platforms
   • With Jan Camenisch and Roger Zimmermann
   • US Patent Application No. 12/439,236, Publication No. US 2009/0271618 A1, filed July 3, 2007
   • PDF -- 104K
   • Abstract:
     A method and apparatus for attesting the configuration of a computing platform to a verifier. A signature key ($SK$) is bound to the platform and bound to a defined configuration of the platform. A credential ($C(SK)$,$C_{DAA}(SK)$) for the signature key ($SK$) is obtained from an evaluator. This credential ($C(SK)$,$C_{DAA}(SK)$) certifies that the signature key ($SK$) is bound to an unspecified trusted platform configuration. The platform can then demonstrate to the verifier the ability to sign a challenge from the verifier using the signature key ($SK$), and demonstrate possession of the credential ($C(SK)$,$C_{DAA}(SK)$) to the verifier, thereby attesting that the platform has a trusted configuration without disclosing the platform configuration to the verifier.
   • owned by IBM
3. Method and system to authenticate an application in a computing platform operating in Trusted Computing Group (TCG) domain
   • With Bernhard Jansen, Luke O'Connor, and Els Van Herreweghen
   • US Patent Application No. 11/957,408, Publication No. US 2008/0288783 A1, filed December 14, 2007
   • PDF -- 152K
   • Abstract:
     A method and system for verifying authenticity of an application in a computing-platform operating in a Trusted Computing Group (TCG) domain is provided. The method includes computing one or more integrity measurements corresponding to one or more of the applicatoin, a plurality of precedent-applications, and an output file. The output file includes an output of the application, the application is executing on the computing-platform. Each precedent-application is excuted before the application. The method further includes comparing one or more integrity measurements with re-computed integrity meaurements. The re-computed integrity measurements are determined corresponding to one or more of the application, the plurality of precedent-applications, and the computing-platform.
   • owned by IBM