We love secrets and gossip. We enjoy being trusted with limited access information. We relish showing off our privileged status of confidant by sharing this secret information with others. So, can we really be trusted? Is there a way to show off our knowledge of this information, without revealing it?
Try using Cryptography. It is a field developed to allow communication in the presence of an adversary. The coolest stories of cryptography come from covert information transfers during war, and the most practical, modern use is for secure credit card data handling over the Internet. Interestingly enough, we can also apply it to our gossip or secret keeping and sharing scenario.
In 1985 a woman cryptographer, Shafi Goldwasser, along with two of her colleagues, Silvio Micali and Charles Rackoff, created what came to be called zero-knowledge proofs – describing how to prove you know something without revealing anything about this something. Zero-knowledge proofs are defined as a game between a prover and a verifier. For example, the prover can be you and the verifier is a friend you are trying to convince of something without revealing this something. Usually it is an interactive game where the verifier asks questions and the prover answers. This goes on and on, till the prover convinces the verifier that her statement is true. The goal is for the verifier to gain zero knowledge about the statement other than the conviction that it is valid. Zero-knowledge proofs became one of the most beautiful and influential concepts in Computer Science.
For example, if you can distinguish between cheap and expensive wines, by taste only, try proving this to your friends. Zero- knowledge proof means convincing your friends that you have this ability, without revealing how – i.e., without explaining the intricate details of taste difference, sensation on the tongue, smell nuances etc. Interactive zero- knowledge proof process would go as follows. Behind your back someone flips a coin and depending on the outcome, pours either cheap or expensive wine in your cup, you taste it and tell which kind of wine it is. Repeat it many times with different wines and, assuming that you are always right, you have convinced everyone, with a rather high probability, that you can tell the difference in taste. This is a probabilistic interactive proof approach. Without actually revealing a single detail about how you distinguish between wines (zero-knowledge), you have convinced your friends that you are able to do it.
Another simplified example of a zero-knowledge proof, as described in this entertaining paper is to show that you know a secret code that can open a door connecting a circular passage, without revealing this code. To prove it using zero-knowledge protocol, you need to repeatedly demonstrate that you can enter the passage from one side of the door and exit on another. The verifier would flip coins to randomly assign your starting position in the circular passage. Eventually, if you really knew the secret word, and were able to open the door with it every time, you would convince the verifier that you most certainly knew a secret word, without actually revealing it.
A perfect example of a more complex zero-knowledge protocol use is a smart card. It may contain your medical records, bank account data and other personal information and demonstrate knowledge of this information without revealing any of it.
Shafi Goldwasser also significantly contributed to another intriguing cryptographic method - verifiable secret sharing protocols. The idea behind secret sharing protocols is brilliant and has been used in a simplified version since pirate times: since you cannot trust a single person with a secret, divide your secret into a set of clues and share these clues among a number of people. Only when all (or many) gather can they combine the clues and make sense of the secret.
Try this trivial example: cut words out of an interesting “secret” announcement, send one word to each friend along with the order of this word in a sentence. From a single or even a few of these words, your friends would be unable to figure out the secret. Gather everyone up, line up the words and the dissected announcement will be jointly revealed.
But cryptography is a thriller rather than a romance. It studies personal communication assuming the possibility of malicious intent. So, what if one of your friends-participants - is a dishonest pirate that substituted her word with another one? Or, what if the secret owner is dishonest? Shafi and her colleagues proposed an interactive process improvement to this secret sharing protocol, which allows participants to validate their pieces of information. The actual details are too long for this story, and outside the scope of my intention to illuminate the exciting field of cryptography and one of the brilliant contemporary woman scientists at the center of it.
I first saw Shafi in a corridor of an Israeli university where she had recently gotten a professorship. In fact she is one of the few people in the world allowed to divide their time between two highly esteemed universities, MIT in the US and the Weizmann Institute of Science in Israel. Shafi was tall, approachable, and effortlessly beautiful. She was also pregnant. Everything about her was natural and admirable, sweetening mathematical infatuation for boys and girls alike. It stimulated and encouraged us to attempt our dive into science and math adventures.
Shafi Goldwasser has won two very prestigious awards: the Gödel Prize and the RSA Award in Mathematics, as well as numerous other tributes. She was elected to the National Academy of Science and to the National Academy of Engineering. She is our contemporary, prominent woman scientist with applications of her research spread across many fields, including secure medical record exchange and online identity protection and authentication.
March 24th 2009 was proclaimed to be Ada Lovelace Day - an international day of blogging to draw attention to women excelling in technology. This post is my contribution to the Ada Lovelace Day Pledge.
Try it at home:
Make a Cryptographic Treasure Hunt Game for you child's next birthday. Buy loads of candy or some other treasure and hide it in a secret place. Write a note describing this place (e.g. “Where sweet dreams come to you,” if you hid the treasure bag under your child's pillow). Above each word in this sentence write the number corresponding to the word's order in the sentence. Cut the sentence, with scissors, into words. Hide each word in a separate place. Create a pirate style clue map drawing of your home or describe where each word is hidden. Tell your kids that each word by itself does not have any meaning, but by combining all the words they will have a “key” to the treasure place.
Share this with your friends:
Our weekly newsletter with stories, puzzles and ideas can spice up your weekend and help present math to your family as a toy and a friend. Join 1,500+ subscribers: