[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[freehaven-dev] universally verifiable secret sharing

On Wed, 26 Jan 2000, Ron Rivest wrote:

>    There may be other approaches to handling garbage from an adversary;
>    for example some of the "verifiable secret sharing" ideas or related
>    work...

Maybe "universally verifiable secret sharing" would be useful? Such 
secret sharing schemes have these properties :

* sharing : you can break a piece of data into n shares.
* reconstruction : any t of these shares can reconstruct the data.
* universal verification : _anyone_, not just the parties involved
	                  in the original sharing, can verify 
                          whether a given share is "valid." 

Now if an adversary tries to submit an evil share, 
	a) not only will it not work, but also
	b) you can distribute the evil share far and wide,
	as evidence of the adversary's bad faith. Everyone will be
	able to verify that the share is bad.

This only works if you get the adversary's signature on the share, and if
the adversary has an identity, and so something to lose by having his name
dragged through the mud. On the other hand, if the adversary does have
something to lose, then now you need to prevent false accusations. 

There are at least two papers on this that I know of (references below). 
I've just skimmed them so far. 

Questions I still have open are :

* What exactly does it mean to be valid?
* Is extra information required, along with the bad share, in order
  to see that it is bad? Will it break other parts of the design
  to provide this information?

* What's the computational price of verifiable secret sharing vs. Rabin IDA ?
* Are the shares larger than Rabin IDA? 
* Do any unpatented universally verifiable secret sharing schemes exist?

Other questions are appreciated. Unless this primitive does not seem
worth spending time on (say so now), I'll read the papers and aim to have
answers by our meeting on Sunday or earlier. 

Here's the two papers :  

Mao W. "Necessity and Realization of universally verifiable secret
sharing." 1998 IEEE Symposium on Security and Privacy. Oakland, CA, May
1998. pages 208-214. IEEE ComputerSociety Press, 1998.
Abstract at : http://computer.org/proceedings/s&p/8386/83860208abs.htm
Paper at :    http://www-uk.hpl.hp.com/people/wm/papers/oak98.ps

Schoenmakers, Barry "A Simple Publicly Verifiable Secret Sharing Scheme 
And Its Application To Electronic Voting" In Advances in
Cryptology-CRYPTO'99, volume 1666 of Lecture Notes in Computer Science,
pages 148-164, Berlin, 1999. Springer-Verlag. 
Abstract at: http://www.win.tue.nl/math/dw/pp/berry/papers.html#crypto99
Paper at :   http://www.win.tue.nl/math/dw/pp/berry/papers/crypto99.ps.gz

Thanks much,