2:30-3:30 pm
October 22, Graduate Center: Vladimir Shpilrain (City
College), Bit commitment, mental poker, and secure multi-party computation
Abstract:
While it is fairly obvious that a secure (bit) commitment between
two players is impossible without a one-way function, we show that
it is possible if the number of players is at least 3. Building on
the same ideas, we also suggest a protocol for secure computation of
the sum or product of two or more integers that does not require a
one-way function. Yet another application is to
the so-called ``mental poker".
This is joint work with Dima Grigoriev.
October 29, Graduate Center: Gregory Bard (Fordham
University), DEMOCRACY: a new technique for solving polynomial systems
of equations over finite fields via stochastic local search
Abstract:
Polynomial systems of equations arise in cryptanalysis,
and elsewhere. The DEMOCRACY algorithm is a new technique
for finding one solution in the coefficient field, for low
degree systems. First, start with a random temporary
assignment of a field element to each variable. Then
"erase" the value of one variable, call it x. Each
equation is now a univariate polynomial, considering the
unerased variables as being constants equal to their
temporary assignment, and only x as unknown.
If x is never raised to a power > 3, then simple algebra
is sufficient to produce a set of values for x that
satisfy any particular equation in the system. The
equations then "vote” for values of x, with a "ballot
box" for each field element, and each equation voting
for any field element that will satisfy it. It is easy
to see that the box with the most votes corresponds to
the coefficient field element that will satisfy the
largest number of the given equations. Now x is changed
to that value, and another variable is targeted.
This is a simplified version of the actual method. While
extremely heuristic, this method has been effective on
systems of up to 100 equations and can quickly solve
systems that cause MAGMA to crash for lack of memory.
To subscribe to the seminar mailing list, click here