Saturday, July 26, 2014

Bridge bidding arithmetic

[I don't suppose any non-Bridge players will read this. But just in case I'll give some info in square brackets at times. In Bridge players partner in pairs who have to cooperate in bidding. The (pseudo-)auction involves bids by the four players (partners opposite) in order 1c,1d,1h,1s,1nt,2c,...7nt. One way to cooperate is a relay where one player always makes the cheapest bid and the other describes their hand. The hand has 13 cards. We say a hand is 3541 if it has 3 spades, 5 hearts, 4 diamonds and 1 club. "Game" is 4h or 4s or 5c or 5d (or 3nt) and scores a lot extra. Slam (12 or 13 tricks out of 13) scores even more.]

After a relay the asker needs to set the suit below game [to allow slam investigation]. We need to do this below 4h, so it can be done starting at 3s, for example: 4d sets spades; 4c sets hearts; 3s sets a minor and responder always bids 3nt after which 4c sets clubs and 4d sets diamonds.

So lets assume for the moment that we are only showing distributions. How many different distributions can each bid now show:

3h: 1
3d: 1
3c: 1
2nt: 2 (asker then bids 3c and responder can bid 3d or 3h with the 2 distributions)
2s: 3 (asker then bids 2nt and responder can bid 3c or 3d or 3h with the 3 distributions)
2h: 5 (asker bids 2s, responder bids 2nt with 2, 3c/3d/3h with others)
2d: 8 (...)
2c: 13 (...)

Which continues to be the fibonacci numbers (each number the sum of the previous 2): 21,34,55,...

So how many distributions are there:
distprobabilityvariantscumulativeprob/variant
4-3-3-30.1054440.02635
4-4-3-20.215512160.01795833333
5-3-3-20.155212280.01293333333
5-4-2-20.105812400.008816666667
4-4-4-10.02994440.007475
5-4-3-10.129324680.0053875
6-3-2-20.056412800.0047
6-3-3-10.034512920.002875
5-5-2-10.0317121040.002641666667
6-4-2-10.047241280.001958333333
7-2-2-20.005141320.001275
5-4-4-00.0124121440.001033333333
7-3-2-10.0188241680.0007833333333
5-5-3-00.009121800.00075
6-5-1-10.0071121920.0005916666667
6-4-3-00.0133242160.0005541666667
7-4-1-10.0039122280.000325
6-5-2-00.0065242520.0002708333333
7-3-3-00.0027122640.000225
8-2-2-10.0019122760.0001583333333
7-4-2-00.0036243000.00015
8-3-1-10.0012123120.0001
6-6-1-00.00072123240.00006
7-5-1-00.0011243480.00004583333333


Though the cumulative total goes up linearly and fibonacci goes up exponentially, still we don't have a lot of room to cover low probability distributions. And certainly we can't afford to waste much space.

One can consider what order to show distributions in. A simple scheme is: (a) show more balanced hands first (lower number of distribution points [doubleton=1, singleton=2, void=3]); (b) within that constraint show hands with more major cards (i.e. in decreasing number of hearts+spades); (c) within that constraint show in decreasing heart length.

The reason for showing more balanced hands first is that this makes slam less likely, so asker can often quickly bid game after a lower bid, without relaying it out and telling the defenders more than necessary.

One of the objectives of bidding is to find useful trump fits. [It is desirable to have 8 trumps. Hands without an 8 card major (heart/spade) fit are usually best in 3nt if possible.] Relaying wastes space compared to having both partners contributing. The question of how to best use both partners is a difficult problem. A simple approximation/guess is to use binary search. Here's how that works:

Taking a suit at a time in some algorithmically defined order the bidder cuts the length of that suit in half and bids one step with the higher (or lower) range and otherwise goes up a level and repeats.

Suppose you are playing "Romex" and a 1NT opening is 20+ points [ace=4,k=3,q=2,j=1]. One way to play the responses follows. Note that 1 step is towards the middle, bypass shows more extreme.

At any time by either player: 3s/4c/4d set the suit, as described above.
2c: 0-4 points. Higher bids forcing to game.
2d: 0-3H
2h: 4-7H 0-3S -- beyond this we further breakdown the majors
2s: 4-5H 4-7S
2nt: 6-7H 4-5S
3c: 6H 6-7S
3d: 7H 6S 0C 0D made it with a bid to spare

That worked well because narrowing the range in the majors also narrowed the range in the minors. But in other auctions we can find all 8 card major fits but the minors don' get narrowed down (as much). For example here are continuations after 1n-2s:
4c/4d: setting major with 4, otherwise deny 4
2n: 2-3S (i.e. matching the top half of responders 4-7)
3c: 3H 0-1S (ie hitting top of openers 4-5H range)
3d: 0-2H 1S (hearts eliminated)
3h: 0-2H 0S 4-5C 4-7D -- With 11-13 minor cards can be 47 56 65 or 74.
and a few more.

Given the fibonacci connection it might be better to split unevenly with approximately 38% in 1 step and 62% beyond (1:1.62 = 0.62:1 is the golden ration and consecutive fibonacci numbers tend towards that ratio). But this is not nearly enough and low probability distributions have to be lumped together to make it work when starting at 2d. Realistically one also needs to start lower or start with a restriction on the range of distributions. And indeed that is commonly the case for auctions starting lower than 1nt.

Tuesday, May 6, 2014

Mathematics and programming collide

Mathematics is (by my definition) about thinking clearly about problems (that have been made sufficiently precise, sometimes by simplifying assumptions). Programming is about thinking clearly about algorithms.

So we see that programming should be a part of Mathematics. And, lo and behold, now that we finally understand how to do functional programming, it makes heavy use of concepts from Category Theory which is a modern unifying part of mathematics. It would be good if more of the best Mathematicians became interested in this very important application of modern Mathematics.

And this is likely to happen because, from the other direction, Mathematicians need computers to control the complexity of modern Mathematics. This is described by Vladimir Voevodsky (one of the world's top mathematicians) in a recent talk. You don't have to understand the mathematics to get the core message, that complex new Mathematics needs to be mechanically verified to be trusted. And it turns out that the proof assistants used for this mechanical verification are within a whisker of being programming languages.

Indeed the functional programming world seems to be most aware of this expanding intersection of Mathematics and programming. This is partly because proof assistants can sometimes be used to prove programs correct. So it was the Sydney Functional Programming society that recently held a "coq fight", which involved the live competitive generation of proofs using the coq proof assistant.

Here's something that I expect will flow from this cross pollination of Mathematics and programming. There will be emphasis on the precise definition of the problem. Often in the programming side there won't be any need to do more, because a large proportion of current programming activity just involves doing obvious things to create the web site or other program type. Computers should do those obvious things for us. Once we get past that hurdle, then the human programmer can spend more time where real creativity is needed, either artistic or algorithmic. And the many situations where Mathematics can help us will be much more accessible because mathematics will be organized so that those prepared to understand it can easily apply it.

Tuesday, February 18, 2014

name change at marriage

It was nice to see that a lady we would all want to remember had a trophy named after her. The one niggle was that her name is given as the married name of her second rather brief marriage. And looking at the record of some of her achievements we see that her name has been changed, for consistency, to that married name. And, indeed, my wife is annoyed to find that her maiden name has been expunged from the record in the same way on one of her early achievements.

Women changing their name at marriage doesn't work well in the modern world. Here's an alternative scheme:

  • Women keep their last name at marriage, but change their middle name to their husband's surname. And similarly the man changes his middle name to the wife's surname.
  • Children are given the last name of the same sex parent, and start with the middle name of their other parent.
Note that middle name here means the last middle name. Other middle names are also possible though I wouldn't like to see that get out of control.

I did think of having the boys get their mum's lastname, and the girls get their dad's. However looking back to when I was a kid, even though I was closer to my mother, I know I would have wanted to have my dad's surname. I presume that most girls would want to have their mum's name.

Monday, January 20, 2014

Natural Gas is not a good step towards solving AGW

The Greens have discovered that a lot of anti-AGW activity is fake, being secretly funded by multi-billionaires and corporations with commercial interests in pumping out CO2 and other greenhouse gases. The way this is being written up is meant to give the impression that all the criticism of the Green movement is motivated by these base motives. I'd just like to say that, though I am persona non grata in various forums for my negative comments on Greens and AGW activity, I have never received any funding from any source. I'll list some of my criticisms below, but first let me make a new one:

The Green/AGW movement seems incorrectly content about the move from coal burning to natural gas burning. This, they say, will allow us to meet our initial goals of 5-20% reduction in CO2 emissions, on the road to the necessary eventual reduction of 80% and more. Yes it does make that first step easy, but then it acts as an impediment to any further steps. The reason is that it creates infrastructure for burning natural gas and that infrastructure can't easily be abandoned. I suppose the Green/AGW folk imagine that a higher carbon price, or other government action, will mean that the natural gas burning company will be unable to meet its costs, including interest payments on the construction cost, and this will force it to close. But this misunderstands how capitalism works. In an unregulated world what would happen is that the owner would go bankrupt. Then its assets would be sold. The buyer would then have a lower capital cost to fund with interest payments. And so the new owner can make electricity more cheaply without going broke. It is as if the infrastructure, being there, wants to be used. And the infrastructure is more than just the electricity plant: it includes gas drilling equipment, pipelines, various sorts of human expertise, and more. Of course this is just words. You would need a good model of the economy (and the technology and the geology and more) to really know how important my point is, but I don't get the impression the proponents of natural gas have even given this matter any thought.

Here are some other points I have made:

1. Modern nuclear power is the only chance for energy that is cheap and reliable enough to displace fossil fuels. Renewable energy (and CCS) are so implausible as a power source for modern civilization that they can only be regarded as a front for the fossil fuel industries. And what do we see when countries move away from nuclear power? Lots of talk about renewables and lots of quiet implementation of coal burning.

2. We need to try to understand the climate so that we can manage it. The Greens insist that we need to avoid effecting the natural world, and put up with the consequences. This puts the Greens firmly against the ordinary voter and makes it impossible to get countries like Canada and Russia onside. We need the world to be on the warm and wet side of natural to feed 10 billion people. In particular we need to expend more effort trying to understand what happened at the end of the previous interglacial when the sea level (a proxy for temperature) rose gradually throughout the interglacial, before plummeting at amazing speed for thousands of years at the end. It seems to me that one needs to worry about what happens when Arctic water warms up, increasing the amount of open water. This can lead to more snow on the surrounding land and one must consider how this might interact with natural events such as a period of weak sun (which we seem to be getting right now) and a big volcanic eruption (which has been recently shown to happen regularly without the need for additional input from the movement of magma).

3. Greens who aren't scientists often say that others shouldn't be allowed to have opinions on AGW because they aren't scientists (or aren't climate scientists). This makes everybody suspicious. Indeed it would be a good thing if we could get all the old socialists who have drifted over to the Greens to shut up.

Sunday, January 12, 2014

What is real?

I'm not that interested in Philosophy, but I just thought I'd write this down to get it out of the way. The following stuff seems obvious to me, but I suspect that many people will not agree with it.

Timothy Gowers' latest blog post (http://gowers.wordpress.com/2014/01/11/introduction-to-cambridge-ia-analysis-i-2014/) discusses the fact that there is exactly one complete ordered field, namely the Real numbers. [You don't need to understand that stuff for the following discussion]. He points out two ways of describing a real number: (a) via an infinite decimal sequence; (b) via pairs of complementary sets of rational numbers (Dedekind cut). It will mystify non-mathematicians that these different things are said to be the same. The point is that they are exactly the same for all the practical purposes that we need the real line for, as is the description of a complete ordered field without even explicitly constructing the Reals. What we'll come back to is the question of whether the Real numbers really exist at all. First we move from Mathematics to Science.

The other day I was telling my grandson what a scientific theory is, namely it makes predictions which can, at least in principle, be falsified by observation. Two scientific theories are the same if they make the same predictions, even if the theories seem different. We have a recent example that illustrates this, in quantum theory. The original quantum theory was expressed in terms of infinite dimensional Complex vector spaces (yikes). The predictions then made met the most exacting standards of accuracy available, and continue to do so. Richard Feynman showed how one could instead draw collections of diagrams (the famous Feynman diagrams we often see in popular science) and use those to do calculations in a simpler and certainly more humanly accessible way. But these quickly get hard in more complex situations. Recently there has been a claim that we can portray quantum situations in a sophisticated mathematical context that allows calculations to be done much more efficiently. All these ways of describing reality make the same predictions, with varying degrees of computational efficiency and human accessibility. It is just not sensible, and certainly not Science, to say that one of them correctly describes reality while the others just happen to give the same answer. However human accessibility and ease of computation are key ways of evaluating theories, and what follows is an extreme example.

As we know, the Earth gives every indication of being 4.5 billion years old, and to have undergone massive changes during that time. Geology and related Sciences are all written as if that were the case. But suppose you lived in a society where you were likely to get burnt at the stake if you expressed the view that the world was more than 6.5 thousand years old. Then you might come up with an alternative theory: that God created the world 6.5 thousand years ago, exactly as if it had existed for 4.5 billion years and as if it had experienced many exciting events since that time. Maybe he ran a perfect simulation to see what it should be like. Now all scientific papers can still be written, but they have to have frequent weasel words so as not to suggest that the world really existed before 6.5 thousand years ago. The two theories are identical and lead to the same predictions and expectations. To claim that one theory is true and the other false is therefore not Science. However, like Feynman diagrams, the idea that the world really is 4.5 billion years old is the one that is more humanly accessible. Also the scientific community has a role in picking, from equivalent formulations, standard ways of describing scientific theories so that the scientific conversation can proceed smoothly. If the Geology literature was a mix of those describing a 4.5 billion year old world, and those describing a recent but equivalent creation, then the conversation would not proceed smoothly.

We can see that making specific choices from equivalent descriptions of scientific theories is very similar to specific representations of the Real numbers. It is relevant to look into the status of the Real numbers themselves. Our conception of the Real line plays an important role in our understanding of space, time and many other aspects of reality. However the Real numbers themselves have a rather tenuous connection to reality. We can easily ascribe a meaning to the Rational numbers (such as 2/3) and also to the computable numbers. A computable number is one where a computer program can (for example) give you as many decimal places as you request for that number. However there are only a countable number of computable numbers (so we could in principle give each one an integer index from 1 up), because there are only a countable number of programs (since programs are finite strings taken from a finite alphabet of symbols). And it is quite easy to prove that the Reals of the complete ordered field are not countable (http://en.wikipedia.org/wiki/Cantor's_diagonal_argument). What can we make of these multiferous uncomputable Reals? The key point is that all Mathematics is done with finite strings taken from a finite alphabet. There are no infinities there. Yet hypothetical infinities are a recurring theme. The infinite things, such as uncomputable Real numbers, are a human construct that gives meaning to the Mathematics, which in turn enables us to understand reality.

In the early days of calculus, the practitioners (such as Newton) liked to talk about infinitesimal numbers. These sure make it easier to think about calculus. But there was a backlash against this, since "infinitesimal numbers don't really exist", and the whole edifice was reconstructed less elegantly using just the Reals. It was subsequently shown (Model Theory) that you can use infinitesimals in a rigorous way. In fact the reality of Real numbers is just as dubious as infinitesimals. They both enable human intuition to make sense of mathematics and then of the world.

Well it turns out that mathematicians are trying to build mathematics up from core principles in a new way: that respects the fact that Maths is done with finite strings from a finite alphabet; that takes seriously the question of when two things are equal. This is Homotopy Type Theory. I'm trying to understand it. I can also say that the Wombat Programming language (wombatlang.blogspot.com.au) makes extensive use of the idea of multiple representations of the same value, and also has a flexible notion of equality. Maybe when I understand HoTT I can make Wombat even better.

Monday, December 16, 2013

The Mathematics Game

The world mathematics community has become disenchanted with the system of peer review for academic journals, but is struggling to find a way to replace it. For the purposes of appointment and promotion they need a way to allow Mathematicians to be evaluated for their research and also their breadth and depth of knowledge. This is also important because clever young people love being able to show off their inventiveness: It is what leads many young people into Mathematics.

Rather than inventing a solution from scratch, let's take what we know works and add a little cryptographic magic. Here are some things that we know work:
  1. The Arxiv system for holding academic papers and for tracking changes to them.
  2. The mathoverflow system (and similar) for asking questions and for rating questions and answers and participants.
  3. Polymath style cooperative projects.
  4. Khan Academy and similar systems of self-paced learning.
  5. Repositories of knowledge such as Wikipedia and ncatlab.
  6. Math Olympiad and other competitions.
The proposal will have the following features:
  1. You can play the game at any level, starting with K-12 mathematics, and up to new research.
  2. Participant IDs are linked to unique real world individuals. However you can play with pseudonyms, then claim the credit if you do well, but never need to own up to mistakes. Reviews can also be pseudonymous, freeing the reviewer to be honest.
  3. Abusive pseudonyms can be unmasked. Subsequent pseudonyms by that user will, for some time, have an elevated "abuse level" that users and software can take into account. Fair but tough reviews need to be endorsed by others as non-abusive to prevent abuse of the abuse system.
The system runs on various sorts of points and the interactions between them. The stackexchange folk (who run mathoverflow and similar sites) are experts on this and their advice should be sought. A possible scheme might be:
  1. Mathcoins are earned in various ways (including doing moocs and accompanying tests), and can then be spent to allow the participant to attempt higher level actions which can allow them to move up on a more permanent basis.
  2. Achievement points are earned by well-regarded actions and they accumulate. This is rather like masterpoints in Bridge and encourages the enthusiast as much as the skillful. This is important because there will be lots of work (such as marking middle level participation) needed to keep the wheels ticking over.
  3. Levels are more like the rankings in Tennis, though more blurred. At the top it is the judgement of peers. At the bottom it is mostly automated. In between the judgement of people above is the key. Moving up the levels is the objective of the game, and hopefully those at the top become stars, though they can, if they like, hide behind a pseudonym.
To start with, every participant would have an authenticating public key. The player can then generate as many additional public keys as necessary to represent pseudonyms. The activities (Arxiv/etc) would need to be modified to support this (or replaced), including supporting the authentication of all actions.

The easy thing will be for the participant to link from pseudonym to themself (or other pseudonym). All that is needed is to generate a "certificate" claiming that the public keys represent the same person, and have the certificate be signed by both public keys.

There are lots of other things that need to be done. They can all be done with a Trusted 3rd Party solution. Many of them can be done more elegantly and securely with cryptographic cleverness. It can also sometimes be possible to divide information between trusted 3rd parties so that compromise of only one doesn't reveal important information.
  1. Proving that a pseudonymous identity has sufficient points/etc to participate in high level activities.
  2. Identifying the abusiveness status of pseudonyms without identifying the real participant.
  3. Transferring mathcoins to, from and between pseudonyms.
  4. ... and much more
I think that the idea of Mathematics as a vast interconnected system, with no insurmountable barriers from the bottom to the top, would be very powerful and productive.

Saturday, November 16, 2013

The key2key project

After retiring I mostly pursued my interests in peak oil and in computer network security. While at CSIRO I had published an Internet Draft on "Basic Internet Security Model". It is still online at http://tools.ietf.org/html/draft-smart-sec-model-00, though it expired long ago. Later I tried to build on that to create a secure Internet, in what I called the Key2key Project.

After the recent security issues on the Internet (brought to light by Snowden) I thought I should look into reviving it. However it doesn't seem like something where I am likely to make any headway, given the cool/hostile reaction to my `99 Internet Draft years ago. Anyway, for the record, here is the last, rather dated and very incomplete, key2key overview doc:

The Key2key Project

The end2end interest group created the ideas on scalability that led to the Internet. The aim of the key2key project is to extend this philosophical framework into the security area to create a secure overlay network.


A trusted system is one that can harm the truster. It may actually do harm if it fails in some way, or if the trust that was placed in it was misplaced.


Security is when you know which systems you trust, and explicitly agree to place that trust. We don't consider whether that is because the trusted systems are actually believed to be trustworthy, or just that the alternatives are believed to be worse. Food security is when you get to balance the risk that the food is poison against the risk of starvation. Food insecurity is when you are force fed. In the Internet today, security is not end-to-end. That is why Internet users are trusting intermediate hardware and software systems that they don't know exist.


This document covers the following areas:
  • Modelling Internet entities and sub-entities. This is a necessary step to understanding the problem.
  • Modelling cryptographic security technology: hashes, encryption, verification, signatures.
  • Modelling communication between entities. This will make it possible to define when a protocol is secure, and define a framework for building secure protocols. These secure protocols will be necessary for building our secure overlay network.
  • Modelling the common and crucial situation when one entity executes software "on behalf of" another (OBO).
  • A device for human signatures (DHS), and the implications of its limitations.
  • Delegating specified limited powers to sub-entities.
  • Securely booting a PC and setting it up as a sub-entity capable of representing the user on the network, and referring matters beyond its delegation up to the DHS.
  • A protocol for communication by "on behalf of" execution. It is intended to show eventually, but not in this document, that this is the only reasonable approach to this problem.
  • A simplistic e-commerce application will illustrate in detail how these components work together to make a secure system.

Entities and sub-entities

Distributed computing is very different when the computers involved are under the control of a single entity, compared with the case where the computers are controlled by separate entities. For the former the important issue is performance. The key2key project is all about the latter, communication between separate entities. In this case the main issue is security [footnote: However key2key can have good performance. Though the main control communication in key2key is often forced to follow potentially low performance routes, bulk data transfer is direct].
Legal entities (people and organizations) have sub-entities, such as employees and computer systems, which are not legal entities themselves, but can be given a delegation to act on behalf of the legal entity. Legal entities are not connected directly to the network. So in order to perform actions on the Internet they need to have some way to give a delegation to a computer system to act on their behalf. This can be quite informal, and the legal implications of the mechanism chosen will rarely be tested in court. In this document we will discuss well defined mechanisms which are appropriate as the basis for more serious interaction between legal entities via the network.
We want to get the communication between separate legal entities via the network onto a sound logical footing. It is important to understand that an individual acting with delegation as an employee is, for our purposes, entirely different from that individual acting as themselves. The fact that these two (sub)entities share the same brain gives rise to serious security issues. However this problem predates computing and networking. We aren't going to attempt to solve it, though it is useful to consider how well traditional legal approaches carry over into the network world.

Cryptographic technology

The key2key project relies on certain capabilities that are usually provided by cryptographic technologies, but can sometimes be provided in a simpler way by a trusted third party:
  • Secure hash (cryptographic checksum). This is a small fixed sized number, typically 256 bits, which uniquely determines some larger bit string. In key2key: end points are represented by the secure hash of a public key; immutable files are represented by the secure hash of the contents. The required characteristic is that there is vanishing probability that two bit strings will give the same hash; and it is computationally infeasible, if given a bit string to find a different bit string that hashes to the same result. This capability could be provided by a trusted 3rd party that remembered bit strings and returned a sequence number.
  • Encryption in key2key applications is used for access control of information that has to go via a 3rd party. Of course this often includes providers of network services. It is commonly the case that, if data is not completely public domain, it is easier to encrypt it than evaluate whether the 3rd parties who will see it are entitled to. Note that the important public keys in key2key are not used for encryption, only for signature verification. Encryption public keys are always separate and usually temporary.
  • The bulk of communication between key2key end points is verified by a temporary agreed shared key (whether or not the communication is encrypted). This means that each party knows the communication came from the other but doesn't allow them to prove that to a 3rd party.
  • Digital signing and verification is only used during the setup phase of communication, and for communications that the recipient wants to be able to prove to a 3rd party that they received. If clever algorithms based on sophisticated mathematics were to cease to be secure then a system using shared keys via a trusted third party would also be possible. Important long term public keys can use combined algorithms, and/or use multiple keys where the matching private keys are not held in one place.
Communication in key2key is between end-points identified by the hash of a public key. The first thing sent between the parties is the public key itself, which must hash to the identifying hash to be accepted. After that other cryptographic services and keys can be agreed between the end points.

Logical communication model

Each end-point is under the control of a legal entity (or in rare cases multiple entities, in some and-or tree structure [footnote: In the 'and' case all communication goes to each of the entities, and anything coming from it is approved by all. In the 'or' case communication goes to an unknown one of the entities and anything coming from it is approved by one of them.]). Initially the end points don't, by default, know what entity controls the other end. Often the initiating party will use a temporary public key just for that connection, and there may never be any call for the initiator to reveal who they are.
Two machines acting under common control might just move data back and forth according to some distributed computing algorithm that the owner has chosen to use. Communication between separate legal entities can only take place if it is meaningful. The agreed protocol must be able to be interpreted as a sequence of assertions and requests, in order for it to be possible to check if the protocol securely protects the interests of each party.
If end point 1 (EP1) sends the assertion "the sky is blue", then the receiving end can only infer and record the fact that "EP1 asserts that the sky is blue". Each end point keeps a store of beliefs and of business logic. When a request comes in, then the end point will effectively try to construct a proof that the request should be honoured.
End points can also send "out of band" hints to the other end. The correctness or otherwise of hints doesn't affect the trust in the main communication. One sort of hint will be about how to contact 3rd party keys mentioned in the communication. This might save a lookup in a directory, or it might actually be the only way for the recipient to get that information. Another sort of hint will be proposed proofs for the recipient. This is desirable because constructing proofs is inherently undecidable and the receiver of the request might be unwilling to invest the resources, and it might be more fair for the requester to do the work. This sort of hint might look something like this in English translation "Assuming your belief store holds 'trust bank public key about assertions of the form ...' and '...' then follow these steps ...".
Communication is between sub (or subsub) entities. Before events with real world significance (such as purchases) can take place, assertions about delegation may need to be exchanged, with a chain leading up to a key that is provably the key of the legal entity. However exchanges of real world significance can be anonymous on one or both sides, as in the real world when we go into a shop and pay cash.

"On Behalf Of" execution

We are familiar with the situation where we visit a web site like google or facebook or a poker server or an airline reservation site, and we perform actions which are carried out on our behalf on a computer that is not under our control. We might have an explicit or implicit legal contract, which might constrain how honestly or correctly the actions are carried out. But in general we have to assume that the requests we make will be handled in a way that suits the owner, not us, as we saw in the case of the cheating owner of a poker service, and in the case (some time ago) of a search for "linux" on MSN-India's search service, which returned linuxsucks.com as the first hit.
Other OBO cases we have a stronger expectation that the owner of the environment will honestly carry out the user's requests: when the owner provides a web hosting service, or a unix login service, or a container for isolated execution, or a virtual machine that the user seems to completely control.
Still in all these cases it hardly seems wise for the user of the service to transfer, to that environment, credentials which have power over significant amounts of money or other valuable property. Rather than trying to work out what credentials can be transferred and when, the key2key project takes an alternative approach: credentials are never transferred, but access to external resources is still possible from the OBO execution in exactly the circumstances where this is secure. More on this later.

Device for Human Signatures

We want to make it possible for real world legal entities to interact via the network. What is needed is a way to link people to the network in a way that makes legal sense. The proposed solution will work for an individual representing themself, or for an employee with some delegated ability to act for the employer. We don't consider the possibility of combining these in a single physical device.

The solution is a Device for Human Signature, DHS. The DHS requirements mean that it must be a separate device, not part of a more complex device. The proposed device has the following characteristics:
  • It has biometric authentication which is unchangeably linked to the owner.
  • It has a private key that is generated when first activated. Only the public key ever leaves the device.
  • It has a black and white screen and a mechanism for scrolling the image left-right and up-down.
  • It has a way that the owner can agree to sign what is displayed on the screen. This is such that it can't be done accidentally, nor can it be done without simultaneous biometric authentication.
  • There is another mechanism to clear the current image without signing it.
  • The device is connected to the world by wireless mechanisms and/or cable. If a cable is plugged in then it only uses that, which is desirable for signing things that have privacy restrictions. Either way it displays any offered image and, if signed, it sends the signature back on the reverse route.
The user signs the extended black and white image. She is not able to sign it till she has used the scroll control to view all of it.
The image will always be created, by a defined and public process, from information in a computer friendly format (such as XML). For example one of the known processes will be "English". The information in computer format, and the well know translation process will be sent with the signature of the text when it is used for internal computer purposes. For legal purposes only the actual visible text applies.
Any computer software can "understand" the signed text by using the conversion process on the computer friendly variant and checking that the resultant image is the one that the user signed. E.g. the user might sign "pay $1000 from my account 061234567 to Example Company (ABN 1234) account 0698765". What they actually sign is an array of black and white dots which has the appearance of this sentence. However the receiving computer (presumably the bank) doesn't have to understand the visual dots because such signed documents always come with an accompanying computer friendly structure which converts to the image in a well defined mechanical way. The signed document comes with an accompanying solution to the problem of determining its meaning.
It is important to sign a picture rather than "text", because it removes questions about how the text was rendered, and as we see it works just as well.
The signing device is only intended to be used for important things, or to create a temporary delegation to some more practical computer system which will sign as needed to act on the network within that delegation.

Delegating to sub-entities

For organizations delegating to employees or commercial network servers this is particularly important, and might be quite complicated, specifying what assertions and requests the delegate can make on behalf of the organization and what requests it will honour. This may not be practical for a person delegating to a computer system using the DHS: all the rules would have to be translated into English and read.
The form of delegation which will be initially implemented in key2key is a system of well known named delegation types. In particular the user will probably give his desktop system the "Standard Anonymous Desktop" delegation, which will enable the user to work anonymously on the network as we ordinarily do most of the time. When things come up so that the desktop system needs extra delegation, that will come up as a specific delegation request on the user's DHS.

Architecture of key2key end-point computers

The DHS doesn't remove the need for end-point systems, particularly desktop systems, to be secure. The standard techniques of managed code and sandboxing are crucial to allow applications to run without the need for them to be trusted with the crown jewels: the ability to use the private key to sign assertions and requests.


The traditional file system model of files that can be updated in place is inappropriate for the needs of key2key. Instead files are read only and identified by their hash, so that they are to a large extent self-verifying. The traditional unix updateable file is actually a form of simple database, and is handled in that way with appropriate security mechanisms shared with other network accessible databases.


This will also cover the secure execution of code that is only partly trusted, and of code that is executed on behalf of an external entity.

Desktop system: booting and running

To do anything useful, a user needs to book a desktop system. That system needs to be physically secure, and it should be booted from reliable read only media to place it in a predictable state. That system needs to generate a private and public key pair to allow it to operate on the network using key2key mechanisms.
When that is all done, the next problem is to use the DHS to associate the desktop with the user and appropriate delegation. The desktop will generate an appropriate message, sometimes incorporating user input to adjust the delegation (though normally additional delegation is added later). That message will appear on the desktop's screen, and be transferred to the DHS by wire or wireless mechanism. The DHS will offer that to the user to sign. It will be in the user's own language and will say something like: "I have securely booted on trusted hardware, and the key signature of that system is 123456789ABCEDEF. It is delegated to act for me on all services not requiring specific delegation.". This signed result will be returned to the desktop system and sent as an assertion wherever needed.

OBO execution model

Suppose that user X is running a shell on a remote computer owned and managed by Y, and a program tries to access a resource on a system owned by Z that X is allowed to access. The traditional approach is that X does something which reveal the credentials for accessing Z in a way that Y could easily take advantage of. X might type a password into the interactive session on Y, or might have transferred some cryptographic credentials, such as a a kerberos TGT or a private key to Y. This is wrong.
The key2key approach is that the request from Y's system to Z's system must use Y's credentials. Y will normally tell Z that this is on behalf of X, but this will only be used by Z to reduce its willingness to agree to the request. If Z won't execute the request using Y's credentials then Y can seek an alternative to make that request, and the natural and default alternative is to go back up the chain leading to the OBO execution. So in this simple case, Y will ask X to send the request to Z with X's credentials. And, of course, X is well placed to know if this is a request that naturally springs from the OBO execution on Y. If the execution of the request involves a bulk file transfer than that will go between Y and Z directly, and not be forced to go via X.

Illustrative e-commerce application

Payment by Reservation (PbR) is the key2key native e-commerce application. It associates accounts with keys. It handles need-to-know revelation of information about the end points: i.e. typically only when there is a conflict.