Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Channels ▼


Trust Me, I Won

If you subscribe to the adage "seeing is believing," you may not like zero knowledge proofs. A zero knowledge proof is a two-person interaction in which a Prover P can demonstrate knowledge of some Fact F to a Verifier V without revealing F to V. Now, if you think some of your university math teachers were trying this in your differential equation classes, you are not alone.

In modern life, zero-knowledge proofs are used whenever someone uses public key cryptography to digitally sign a message. The sender S applies a decryption key D_s to the message m yielding D_s(m). Only S knows D_s, but everyone knows the corresponding public key P_s, so the recipient applies P_s(D_s(m)) to get m back. Only the possessor of D_s can have signed m in that way, so S proves that he or she knows D_s without revealing D_s. S convinces the receiver of S's possession of D_s without revealing D_s.

We will look at two zero knowledge proofs that require no cryptography, no fancy math — in fact, no computers. Here is the first problem.: You are presented with an opening Sudoku board having some numbers plugged in. You work on it.

You: "I've solved it."

Other: "Show me."

You: "No, you should trust me."

Other: "Why should I?"

You: "Ok, I'll prove it to you."

Other: "How?"

You: "I'll show you that every row has 1 through 9,every column has 1 through 9, every 3x3 Sudoku square (upper left, bottom left, middle left, etc.) has 1 through 9, and the numbers in the initial positions are what they should be."

Other: "That will be sufficient, but how can you do that without showing me the solution."

1. That is the problem. How can you prove that you have a solution without revealing that solution? Hint: use 81 cards.

If you were able to solve this problem, you understand the essential core of the zero knowledge idea as it applies here: You can prove that each row or column has 1 through 9 without revealing the order of numbers. What is remarkable in this case is that by revealing the set membership of an entire row, you tell NOTHING about the order in that row.

The general zero knowledge idea works in a similar way, but is often probabilistic. For example, suppose I claim that I can look at a bucket of sand and know how many grains there are. You may not believe me, but you can put me to the test easily enough. You ask me to leave the room and then...well, and then, you do what?

2. How would you test someone's ability to know at a glance how many grains of sand there were in a bucket without your learning anything about the number of grains that are in fact there?

A lot of problems in society could be resolved if we could find zero-knowledge ways to prove someone followed the rules without invading his privacy. For example, suppose we wanted to find out whether someone paid sufficient taxes without knowing what he or she paid.

Those are serious problems.

I would be satisfied with the solution to the following apparently simple variant of question 2, which I leave to you as an open problem. Suppose that you are convinced that the person does know how many grains there are in a bucket. Now he gives you a number. How would you test the truth of that number in time proportional to the log of the number of grains there are? To be concrete, counting a single grain, dividing the bucket into two approximately equal piles or pouring one pile over another each costs one time unit.

I have no idea how to solve the problem.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.