Date: 2007/11/16(Fri) 15：45～17：15
Place: Lecture Hall (Information Science Building)
Name: Yvo Desmedt
The BT Chair of Information Security at University College London,
UK and a courtesy professor at Florida State University.
Title: Applying Recreational Mathematics to Secure Multiparty Computation
The problem of a mice traveling through a maze is well known. The maze
can be represented using a planar graph. We present a variant of the maze. We
consider a grid vertex colored planar graph in which an adversary can choose
up to t colors and remove all vertices that have these colors and their
adjacent edges. We call the grid in which these vertices and adjacent edges
are removed a reduced grid. The problem is that a mice must be able to
move in the reduced grid from the first row to the last row, and from the first
column to the last column, and this for all possible reductions. We present three
types of solutions to construct such grids. The efficiency of these
solutions is discussed.
The problem finds its origin in the problem of secure multiparty computation. Imagine going to a medical doctor in Iraq who needs to
prescribe some medication, which might be counterindicated. The typical solution is to
disclose all medical records to the doctor. If secure multiparty computation
would be used, the medical doctor in Iraq only learns from the distributed
medical databases whether the medication is, or is not, counterindicated. We
consider the problem of parties each having a secret belonging to a
non-abelian group. The parties want to compute the product of these secrets
without leaking anything that does not follow trivially from the
product. Our solution is black box, i.e., independent of the non-abelian group. This has
applications to threshold block ciphers and post-quantum cryptography.
This is joint work with Josef Pieprzyk, Ron Steinfeld and Huaxiong Wang.
Parts of it were presented at Crypto 2007 and appeared in the proceedings.