How should one implement a delegated shared trust protocol?

Question

Consider the following (probably naive) scenario.

Alice, who is very limited in her knowledge of security in general (clueless about securing a private key for example), wishes to delegate certain contractual operations to Trent, an apparent trusted expert in that field.

However, Alice is rightly cautious and is of the opinion that Trent could be compromised (by Eve or Mallory) and so she asks Trent to provide a number of substitutes (Steve, Sam and Sarah) who can fulfil the same role as Trent (if he is away) and also make sure that Trent remains trustworthy (by observing his behaviour). Steve, Sam and Sarah cannot request to talk to Alice directly since all communication directly to her is through Trent.

Fortunately, Alice is protected by Walter, who she trusts completely, who is able to convert her simple password-like authorisation into a one-time only authorisation that Trent, Steve, Sam and Sarah can all see and verify.

From the above, it is apparent that in the normal situation when Alice requires a contract to be issued she provides Trent with the basic details, along with her authorisation via Walter. Trent creates and signs a contract on Alice's behalf (first problem) and then appeals to Steve, Sam or Sarah to counter-sign. Steve, Sam and Sarah all check Trent's public record of contracts to ensure that he is not exceeding agreed boundaries (second problem) and, after checking with Walter, sign if everything is OK. Once all signatures are in place then the contract is valid.

However, problems arise in the abnormal situations when Mallory enters the scene. Mallory may attempt to create a contract by taking Alice's authorisation and altering the provided details. Equally, since Trent is able to create arbitrary contracts, perhaps Mallory could create one that does not require Steve, Sam and Sarah to counter-sign but still appears to originate from Alice.

So my question is this: how can Alice ensure that her contracts can only be issued with her express permission without alteration, but still allow her to delegate the mechanics of this operation to others?

Please forgive the rather basic approach, I imagine that this scenario has been solved, but I'm not sure where I can find the details. Also, there are probably gaping holes which I would appreciate a more experienced eye pointing out.

It can be assumed that a contract requires a private key associated with Alice to enforce non-repudiation. However, if that private key could be hidden from both Trent and Mallory, perhaps by distributing it around Steve, Sam and Sarah that would be extra protection for Alice.

A real world example

The above is a rather generalised version of a problem that has arisen in the Bitcoin SE site (see https://bitcoin.stackexchange.com/q/517/117 for some interesting approaches) but has wider appeal than Bitcoin. However, using Bitcoin as a real world example may help clarifying some of the problems.

First, a quick overview of Bitcon. Bitcoin is a cryptocurrency that uses transactions to indicate a change in ownership of the underlying amount. It's not necessary to understand how this works, other than that a cryptographic signing protocol (elliptic curve DSA) is used to enforce non-repudiation. This signing protocol requires a public and private key.

So, to the problem. Given that Bitcoin is intended to provide a general-purpose replacement for cash it will be used by mainstream (non-technical) people - Alice in the above scenario. The vast majority of these people will want to delegate the security of their private key to someone who has put in place strong security measures, and use a password or OpenId type authentication and authorisation process (Walter).

Those people in charge of the private key (Trent) have the ability to create arbitrary transactions. Assuming those people are never compromised all is well. However, there have been many cases where servers have been hacked and keys stolen. As Bitcoin grows so that, for example, high value international trade with suitable escrow becomes a reality then the possibility for intimidation arises (force the owner of the escrow company to copy all the private keys across to Mallory). This is another attack vector to the private key. Since Bitcoin transactions are non-refundable, once the private key is lost all hope of retrieving the bitcoins is lost - it will be very hard for a legal system to help you recover the funds.

An approach to combat this is some form of shared trust protocol so that any single operator does not have full access to the private key. Instead a random group (or federation) of co-operating, largely trustworthy, operators can collaborate to construct the key and then use it. This protects each individual operator (the Trent's) from intimidation because they have no control so it's useless to expend effort compromising or intimidating them.

It might be possible to use oblivious transfer in some way, but I am not sufficiently versed in this area to comment.

Answer 1

I found the original question vague/ambiguous but the Bitcoin example is concrete enough to answer. In short, what you want is impossible without relaxing some of your requirements.

One of the many requirements you list is that Alice, essentially, has no signing power and can only perform password-based authentication. This is problematic for a fundamental reason. If $a_i$ is some authentication token (whatever it may be) and $m_i$ is her instructions or transaction, a corrupted Trent can always take $\{a_i,m_i\}$ and replace $m_i$ with $\hat{m}_i$ of his choosing.

There are only two ways to prevent this and both are more-or-less blocked by your requirements:

1. Alice has a secure channel to a trusted party (Steve/Sarah/Sam).
2. Alice applies her authentication token to the message: $\{m_i, \mathsf{f}_{a_i}(m_i)\}$. Maybe it is possible to use something weaker than a signature for $\mathsf{f}$ but essentially you want a digital signature (in this case, $a_i$ is a secret but a related value can be used to verify $\mathsf{f}_{a_i}(m_i)$).

Contra 1, you want all communication relayed through Trent. Contra 2, you seem to object to Alice being able to sign things, however I think there is some room in your scenario to play with this. It seems your main objection to Alice being able to sign things for herself is that she needs to keep a stored private key (e.g., $\mathtt{wallet.dat}$) secure.

However it is possible to derive a signing key from a password using a password-based key derivation function (PBKDF). So an alternative Bitcoin architecture could be password-based, where the signing key is derived from the password every time Alice has a transaction to sign. Niether the password nor the key from it is ever stored.

A drawback is if she forgets it, just like loosing your $\mathtt{wallet.dat}$, it is unrecoverable. Another drawback of using a password (whether to derive a signing key or to log into a service that has signing power) is that it will have less entropy than a randomly generated private key that is not meant to be memorized (just stored).

This is where maybe some distributed entity could come in. They could hold shares of the password to allow recoverability (however if they collude, they could recover it).

Finally, if you are still interested in delegation, observe that if Steve/Sarah/Sam are able to act in the absence of Trent, they have to have sufficient power to sign anything. Since they are never corrupted by the adversary in your threat model, the trivial solution is to cut out Trent from any power except relaying messages (the messages will have to be signed or have some end-to-end encryption for the reasons above). Steve/Sarah/Sam will be a distributed authority, where you trust that no more than a certain threshold $k$ will collude and no more than $\ell$ will be offline/non-responsive. You can then use secret sharing (for recovery) or threshold signatures (for delegating the signing) to set the appropriate number of shares required to perform the operation.

Answer 2

A quick search has found this wiki article, which suggests employing a trusted third-party certificate authority in a Public-Key Infrastructure responsible for verifying the identity of a user of the system and issuing a tamper resistant and non-spoofable digital certificate for participants.

Such certificates are signed data blocks stating that this public key belongs to that person, company or other entity. This approach also has weaknesses. For example, the certificate authority issuing the certificate must be trusted to have properly checked the identity of the key-holder, the correctness of the public key when it issues a certificate, and has made arrangements with all participants to check all certificates before protected communications can begin.

Note that in the (more recent) OpenPGP specification, (a variant of the PGP protocol), trust signatures can be used to support creation of certificate authorities, also. So, whether you use PKI or PGP, the responsibility of security then falls on the certificate authority. If this is compromised, then I suppose nobody can be trusted.