Most of the protocols in the cryptography world require two or more participants, and if we start to refer to them as the “party to the first part” and the “party to the second part” then we not only begin to sound like frustrated lawyers, but we run the risk of further complicating what can already be a complicated protocol to explain. To avoid this confusion we enlist the help of a number of actors, the most prominent of these are Alice and Bob. Alice and Bob normally represent two entities who wish to communicate in a secure manner, and that is the case in this scenario.
Getting back to our real world problem, which is prediction without disclosure. What exactly do we mean by this? Well, there are a number of occasions in business where one party wishes to sell his ability to predict an event, or events, to another party. The buyer will require proof of this ability before parting with his hard earned cash, but if the seller reveals the secret too early then the buyer need not purchase the services of the seller.
Let me demonstrate this problem with a scenario featuring our friends Alice and Bob. Alice works as a fund manager in the City and is trying to secure the capital of a large investor, Bob, for her fund. Alice tells Bob that she has predicted the 10 top performing shares for the last three months on the trot, and if Bob invests in her fund she will do the same this month and net him a large profit. Not only that, but if Bob continues to invest his money in the fund for a year then Alice will continue to predict the top performing shares and at the end of the year Bob can retire.
Bob has heard this sort of sales patter before and is naturally cautious with his hard-earned money. He tries to deal with Alice telling her that if she picks 5 shares and they all rise this month then he will invest in her fund. Alice is having none of it though, and tells Bob that if she did that then he could invest his money in her shares and make a huge profit without paying her a penny, she would prefer to let him see her predictions for last month and he will see that she was right.
Bob smells a rat and points out to Alice that she could have changed her prediction after the results were known and he would have no way of knowing that she had done that. “You will just have to trust me,” states Alice. “No,” counters Bob, “you will just have to trust me.”
The resulting stalemate would probably mean that Alice would lose out on the business and Bob would lose out on the profit from the deal. Happily, on this occasion though, not only is Alice a brilliant fund manager, she also happens to be a gifted cryptographer. This means that she is well aware of the Bit Commitment Protocol and how it can resolve the situation. Let me explain.
Alice wants to commit to a prediction, (a bit, or in this case a series of bits making a number of strings), but she does not want to reveal her prediction until after the fact. Bob, on the other hand, wants to ensure that Alice cannot change her prediction after she has committed to it. Alice needs to employ the Bit Commitment Protocol, using a one-way function.
To do this, Alice generates two random strings, we'll call these S1 and S2. Then Alice creates a message consisting of her random strings concatenated with the bit she wants to commit to. In this case, the bit will be a string containing Alice's five shares. Next, Alice computes the hash of the message and sends that, along with one of the random strings to Bob. By sending these to Bob she has committed to her prediction, whilst the one-way function prevents Bob from determining Alice's prediction.
After the event, when it is time for Alice to reveal her prediction, she sends Bob her original message. Bob then computes the one-way function on the message and compares it with the one he received from Alice, along with the value of the random string that Alice also sent him. If they match then Alice's prediction has not been changed and Bob can make his judgement as to how accurate, or otherwise, Alice has been, safe in the knowledge that he is making that judgement on her actual prediction prior to the event.
I have written a C# console application which implements this protocol. The full source code for this application is shown below.
using System;
using System.Security.Cryptography;
using System.Text;
namespace BitCommitmentExample
{
/// <summary>
/// MakeCommitment, a class to demonstrate the bit commitment protocol.
/// </summary>
class MakeCommitment
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
// Ensure the user has passed the correct parameters
if(!CheckParameters(args)){return;}
// Retrieve the parameters
string commitString = args[0];
string s1 = args[1];
string s2 = args[2];
// Build the message to be hashed
string message = s1 + s2 + commitString;
// Convert the message to a byte array
Byte[] byteData = Encoding.Unicode.GetBytes(message);
// Hash the message
MD5 Hasher = new MD5CryptoServiceProvider();
Byte[] hashResult = Hasher.ComputeHash(byteData);
// Convert the byte array to something printable
StringBuilder sb = new StringBuilder();
for (int i=0;i<hashResult.Length;i++)
{
sb.Append(hashResult[i].ToString(“X2”));
}
// Output the results to the user
Console.WriteLine();
Console.WriteLine(“The hash is : “ + sb.ToString());
Console.WriteLine(“The message is: “ + message);
Console.WriteLine(“The first random string is: “ + s1);
Console.WriteLine(“The second random string is: “ + s2);
}
static bool CheckParameters(string[] args)
{
// Check that the user entered the correct number of strings
if(args.Length != 3)
{
ShowUsage(“Incorrect number of parameters!”);
return false;
}
// Return true as the parameters are correct
return true;
}
static void ShowUsage(string ErrorMessage) {
// Show the error message then append usage
Console.WriteLine();
Console.WriteLine(ErrorMessage);
Console.WriteLine();
Console.WriteLine(“Usage:”);
Console.WriteLine(“MakeCommitment s1 s2 s3”);
Console.WriteLine(“Where s1 is the string you wish to commit to,”);
Console.WriteLine(“s2 is the first random string”);
Console.WriteLine(“and s3 is the second random string.”);
Console.WriteLine(“Note: If any parameter contains two or “ +
“ more words then you must enclose the parameter in quotes.”);
}}}
We will now examine this code and see what it does before going on to use it in a real world example.
The class MakeCommitment has three static functions, these are Main, CheckParameters and ShowUsage. The latter two are there to provide guidance to the user, when required, and play no part in the protocol, so we will not examine them further. The protocol itself is implemented in the Main function.
The MakeCommitment exe takes three parameters, they are the string that Alice wishes to commit to, the first random string and the second random string, as in: MakeCommitment “Share 1, Share 2, Share 3, Share 4, Share 5” “111111” “000000”. The random strings can be of any size.
Once the parameters have been checked and retrieved from the parameter array, the message can be created, then the hash computed. As you can see, the message is constructed by concatenating the random strings with the string Alice wishes to commit to:
string message = s1 + s2 + commitString;Before the message can be hashed it must first be converted from a string to a byte array as:
Byte[] byteData = Encoding.Unicode.GetBytes(message);The algorithm I have selected to carry out the hash is MD5, but you can select an algorithm of your choice should you prefer. To compute the hash we must first instantiate an instance of the MD5 crypto service provider, before calling the ComputeHash() function, which returns a byte array:
MD5 Hasher = new MD5CryptoServiceProvider(); Byte[] hashResult = Hasher.ComputeHash(byteData)Having created the hash we need to turn the byte array into something that is printable. To do this we create a new string builder instance and iterate over the byte array adding the hex representation of the bytes to the string builder:
StringBuilder sb =
new StringBuilder();
for (int i=0;i<hashResult.Length;i++)
{
sb.Append(
hashResult[i].ToString(“X2”));
}
Lastly, we output the hash, the message and the two random strings so that the user can review them:
Console.WriteLine(); Console.WriteLine(“The hash is : “ + sb.ToString()); Console.WriteLine(“The message is: “ + message); Console.WriteLine( “The first random string is: “ + s1); Console.WriteLine( “The second random string is: “ + s2);Now that we've examined the code, let's walk through an example of the protocol in action. Firstly, Alice predicts five stocks for Bob, to demonstrate her ability to correctly predict the movement of the stock market. These stocks are ACME Telecom, ACME Software, ACME Housing, ACME Biotechnology and ACME Retail.
Next, Alice generates two random strings, S1 and S2 such that S1 = “111111” and S2 = “000000”. Then Alice computes the hash of the message obtained by concatenating S1, S2 and her prediction as follows:
MakeCommitment “ACME Telecom, ACME Software, ACME Housing, ACME Biotechnology and ACME Retail” “111111” “000000”The output from which is:
The hash is : 5CFD7C53C8A7A54B1EC51D5759B7D340 The message is: 111111000000ACME Telecom, ACME Software, ACME Housing, ACME Biotechnology and ACME Retail The first random string is: 111111 The second random string is: 000000Alice then sends the hash and one of the random strings, (say S1), to Bob. When the time comes for Alice to reveal her prediction she sends Bob the message, (111111000000ACME Telecom, ACME Software, ACME Housing, ACME Biotechnology and ACME Retail). Bob then uses his own software to calculate the MD5 hash of the message. He then compares it and S1 with the value and the random string he received from Alice earlier, if they match then Alice's prediction has not been changed since she sent it to Bob and he is free to make a judgement about its accuracy.
What I have implemented here and examined in some depth, is the use of the Bit Commitment Protocol using a one-way function. Cryptography is a versatile tool however, and there exists two other ways in which this protocol can be implemented. The first uses symmetric cryptography in the following way.
Bob generates a random string, S1, and sends it to Alice. Alice creates a message consisting of the string she wishes to commit to, (say C1), and Bob's random string. She then encrypts it with a key, K1, and sends the result to Bob. This is the commitment part of the protocol. As Bob does not have the key, K1, he cannot decrypt the message and discover Alice's prediction. When it's time for Alice to reveal the prediction, she sends Bob K1. Bob decrypts the message and checks his random string is there, thus ensuring the prediction has not been changed.
The other way to implement the protocol is with a pseudo random sequence generator. Bob generates a random string, S1, and sends it to Alice. Alice generates a random seed for a pseudo random bit generator. Then, for every bit in S1, she sends Bob either the output from the generator, if Bob's bit is 0, or the XOR of the output and her bit if Bob's bit is 1. Alice reveals her prediction by sending Bob her random seed. Bob ensures Alice has not cheated by repeating her generation steps.
In this article I have shown that the power of cryptography not only resides in its ability to allow two or more parties to communicate in private, but also in the ability of the individual blocks that cryptography is built on, to act independently, so as to solve business problems that might not, at first glance, appear to be related to the cryptographic field.
Gary Short is an independent software engineer, with 14 years experience, currently specialising in secure software using C# and the .NET framework. He welcomes your feedback at [email protected].
Comments