## Selective Disclosure

I seem to have to explain selective disclosure about once a week – and I’m going to try to explain it again in about 5 minutes flat, next week at an OECD workshop on identity management.

So, I figured it was finally time to write a paper on it. Feedback welcome!

Interesting. The zero-knowledge proof that I know where Waldo is only takes one step. A lot of others I’ve seen take a sequence of challenges and responses by the prover that end up convincing the verifier. Essentially, the prover can’t be guessing correctly that many times in a row.

It seems like the form of a zero-knowledge proof is very dependent on the problem or puzzle to be solved. I have a hunch that in some cases a zero-knowledge proof might even be impossible; that’s just a hunch, mind you.

So, is there a relationship between problem structure and proof structure that can be discovered, I wonder?

I someone has some time on their hands, here’s a couple of other puzzles to try.

Can you find a zero-knowledge proof that you know the solution to a Sudoku puzzle?

Can you find a zero-knowledge proof that you know where a particular word is in one of those word-search puzzles? Those are the ones with a grid of letters and words can appear frontwards, backwards, diagonally, etc.

Don’t ask me how to do it; ’cause I don’t know. It’s just a challenge.

Comment by Eric Norman — 6 May 2007 @ 1:44

Here’s an idea for Sudoku. Create a permutation of your Sudoku solution. More on that below. Commit to each cell of the permuted solution. Then the challenger chooses A or B. For A, open the commitments and reveal the permuted solution. He can verify that it is a valid Sudoku solution (no repetitions in rows, columns, or small squares). However ideally he can’t tell how it maps to the original puzzle. If he chooses B, open the commitments for the pre-specified number squares, and reveal the permutation that maps it to the original puzzle. He can see that you have prepared a valid permutation of the original, but doesn’t see any of your solution. Repeat this whole process enough times and he will be convinced.

Now, the question is, how many permutations are there? Offhand I can see that a Sudoku solution remains valid if you interchange any of the top 3 rows; any of the center 3; or any of the bottom 3. Likewise for the left, center and right sets of 3 columns. There are 6 possible arrangements of 3 so that is 6^6 permutations. Also you can permute the digits 1-9 which adds a factor of 9!. This is about 10^10 possible permutations.

It means that if he chooses A and you reveal the solution to your permuted puzzle, he can try all 10^10 possible permutations and derive the solution to the original puzzle. However he can probably solve a Sudoku in less work than this so in practice it should be OK.

A more formal approach would be to use one of the prove-a-shuffle algorithms. These are often used in message mixes for secure voting and such, and let you prove that committed or encrypted numbers are a shuffle of some other numbers. In this way you could commit to every square of your solution and prove that each row, column and 3×3 square is a shuffle of 1-9. Takes a little more cryptographic baggage but probably more efficient.

Comment by Hal — 7 May 2007 @ 22:19

For the word search, you could use Ben’s “Where’s Waldo” (not Wally) idea of a big card with a window cut in it and put that over the word grid. Now, that would reveal which way the word goes. So what you need to do is to make up a puzzle card that has the letter grid on it, plus permutation grids with letters that go backwards, crosswise, and diagonal. Then your window can be horizontal and you can put it over the appropriately permuted puzzle to show the word.

Comment by Hal — 7 May 2007 @ 22:27

Responding to Hal’s posts:

“However he can probably solve a Sudoku in less work than this so in practice it should be OK” – indeed, this is a definition of zero knowledge: the verifier cannot calculate anything more efficiently after the proof than before.

“Where’s Waldo?” – wrong – this is an Americanism.

Comment by Ben — 8 May 2007 @ 9:40

“The zero-knowledge proof that I know where Waldo is only takes one step” – actually it must take at least two, since the prover needs to show that he has actually put the card over the original picture and not just over a picture of Wally.

Comment by Ben — 8 May 2007 @ 9:46

Really good coverage of the subject which saved me from explaining it myself!

[Senior citizens looking forward to their Super Gold entitlement cards have been warned that microchips in the cards could expose them to identity theft and illegal monitoring.

Privacy Commissioner Marie Shroff said yesterday the possible use of the microchips had “far-reaching implications” that must be explored thoroughly before introduction. “Security is a real issue, both for the data stored on the cards and the risk of identity theft.”

….

A micro chipped card may mean many things â€“ especially if it is also used as an identity card for commercial purposes, perhaps with a unique identifying number for each person. There is the potential for â€˜function creepâ€™ – where the card ends up being used for far more than was originally intended.

…

There appears to be special emphasis being placed on micro-chipped or smart-cards. Introduction of an identifying card that is to be widely used by a large proportion of the population (approximately 1 in 8) has serious privacy issues regardless of the smarts in the card.

…

Technically, the micro-chip provides the means to secure the data and protect the privacy of the holder. Only with micro-chips and a selective disclosure regime is the privacy, that is apparently an issue for a few politicians around here, going to be maintained.

Selective Disclosure is a cryptographic means of ensuring that the individual retains control over personal identifying data. Ben Laurie provides a useful technical overview of the subject in his recent paper[LAURIE].

If the requirement is for the card to demonstrate that an entitlement exists, a micro-chipped card can provide confirmation of the entitlement without revealing any other data that could be used for correlating the use of the card with an individual. That is, the use of the card says it represents a pensioner and not that a uniquely identified person is a pensioner nor is the usage necessarily associated with a uniquely identified individual.]

http://davethinkingaloud.blogspot.com/2007/05/myth-and-chips-super-gold-card-issue.html

Comment by David French — 14 May 2007 @ 3:23

[…] For more introductory information on minimal disclosure, see here, here, here, here, here, here, and here. If you have some background in elementary number theory, you may be interested in digging deeper by checking out this chapter and the bibliographic notes at the end. […]

Pingback by The Identity Corner » Interview on minimal disclosure tokens — 9 Aug 2007 @ 20:28