Algebra and Cryptography Seminar, Spring 2011

Organizers: Robert Gilman, Alexei Myasnikov, and Vladimir Shpilrain


2:30-3:30 pm
Room 8405, CUNY Graduate Center
365 Fifth Avenue at 34th Street


11:00 am-12:00 pm
Room Peirce 220, Stevens Institute of Technology
Hoboken, NJ


February 4, Graduate Center: workshop on Topics between Mathematics and Computer Science (coordinated by Vladimir Shpilrain, Douglas Troeger (City College), Alexei Miasnikov, Robert Gilman (Stevens Institute)), 2:00-3:30 pm. Speaker: William E. Skeith (City College), Learning with errors

February 18, Graduate Center: Vladimir Shpilrain (City College), Unconditionally secure bit commitment and oblivious transfer
Abstract: While it is fairly obvious that a secure (bit) commitment between two parties is impossible without a one-way function, we show that it is possible if the number of parties is at least 3. Then we show how our unconditionally secure (bit) commitment scheme for 3 parties can be used to arrange an unconditionally secure (bit) commitment between just two parties if they use a ``dummy" (e.g., a computer) as the third party. We explain how our concept of a ``dummy" is different from a well-known concept of a ``trusted third party". Based on a similar idea, we also offer an unconditionally secure (k-n) oblivious transfer protocol between two parties who use a ``dummy".
This is joint work with Dima Grigoriev.

February 25, Graduate Center: Stanislaw Jarecki (University of California, Irvine), Private and Covert Authentication and Conditional Oblivious Transfer
Abstract: We investigate whether it is possible for two parties to authenticate each other *privately* in the following sense: Suppose that Alice and Bob both hold certificates from some organization or certificate authority, and suppose that both Alice's and Bob's privacy policies stipulate that they want to authenticate themselves only to other holders of valid certificates from the same organization. A private mutual authentication allows them to authenticate each other without revealing any information about their certificates and/or authentication policy in the case the other party is an "outsider", i.e. someone who does not satisfy their authentication policy. We show how to construct practical private authentication using Conditional Oblivious Transfer (COT). A COT is a tool interesting in its own right, because it is an encryption counterpart of zero-knowledge proofs: It lets a sender encrypt a message under any statement in some NP language, s.t. if the statement is correct (e.g. a committed certificate satisfies sender's authentication policy) than the message can be decrypted using a witness for the statement, but if the statement is incorrect then the ciphertext hides both the message and the statement. We show efficient protocols for a class of languages which is particularly useful in practical multi-party protocols, and we show how they imply practical private authentication. We will also sketch recent improvements for both the COT tool and the resulting authentication, to "covert" protocols, which satisfy stronger notion of privacy, namely that without proper witnesses no one can distinguish an instance of the protocol from an interaction with a random beacon.

March 11, Graduate Center: workshop on Topics between Mathematics and Computer Science, 2:00-3:30 pm. Speaker: William E. Skeith (City College), Learning with errors (continued)

April 1, Graduate Center: workshop on Topics between Mathematics and Computer Science, 2:00-3:30 pm. Speaker: Nelly Fazio (City College), Learning with errors (continued)

April 8, Graduate Center: Gregory Bard (Fordham University), Exponential Generating Functions, High Powers of Random Permutations, and Very Iterated Block Ciphers
Abstract: Suppose you take a random permutation from S_n, and raise it to a power k. Then it turns out that the expected number of fixed points (in the limit as n goes to infinity) is \tau(k), the number of positive integers dividing k. Thus, if you choose k=1081079, there are 2, but only one higher, k=1081080, makes 256 fixed points.
I use this to attack an arbitrary block cipher, on the assumption that the user makes the unwise decision to iterate the cipher some large number of times. There is no reason to imagine a user doing that, except very naive users (i.e. teenage hackers) sometimes iterate a cipher 1,000,000 times thinking it would make it harder to break. To my knowledge, we are the first to show that it makes it weaker in each and every case (i.e. we assume nothing about the block cipher), via showing a "distinguisher attack."

DOUBLE HEADER: May 6, Graduate Center:
1:00 pm   workshop on Topics between Mathematics and Computer Science. Speaker: Nelly Fazio (City College), Learning with errors (continued)

2:30 pm  Alexander A. Mikhalev (Moscow State University), Standard bases of ideals of free algebras
Abstract: Canonical forms of elements of different algebraic systems were used in combinatorial algebra to solve a number of problems. In noncommutative case the Composition Lemma (a criterion for a subset of an ideal of a free algebra to be a basis of this ideal) was proved by A.I.Zhukov (1950) for free nonassociative algebras and by A.I.Shirshov (1962) for free Lie algebras. For free associative algebras this technique was developed by L.A.Bokut (1976) and by G.Bergman (1978). For free Lie superalgebras and p-superalgebras, the Composition Lemma was proved by A.A.Mikhalev (1989). Composition Lemma for free associative algebras over rings was proved by A.A.Mikhalev and A.A.Zolotykh (1998), and for free Lie algebras over rings -- by L.A.Bokut, Yuqun Chen, amd Yongshan Chen (2010). Nowadays the Composition Lemma is becoming a rather useful tool for solving algorithmic problems in ring theory. Recently a series of articles on bases of ideals (Groebner-Shirshov bases) for conformal algebras, dialgebras, pseudo-algebras was published by L.A.Bokut, by his students and co-authors.
In this talk we consider bases of ideals of free noncommutative algebras, starting with free associative algebras and free Lie (super)algebras. Some possible applications to cryptography will be discussed as well.

To subscribe to the seminar mailing list, click here

Fall 2010 talks

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