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
Spring 2010 talks
Fall 2009 talks
Spring 2009 talks
Fall 2008 talks
Spring 2008 talks
Fall 2007 talks
Spring 2007 talks
Fall 2006 talks
Spring 2006 talks
Fall 2005 talks