Algebra and Cryptography Seminar, Fall 2009

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


October 9, Graduate Center: Vladimir Shpilrain (The City College of New York), Zero-knowledge authentication by the Sherlock Holmes method
Abstract: We propose a class of authentication schemes that are literally zero-knowledge, as compared to what is formally defined as "zero-knowledge" in cryptographic literature. The principal idea behind our schemes is: the verifier challenges the prover with a question that has only a small number of possible answers (say, just 2), and such that the verifier himself knows the right answer. The prover then responds with one of the possible answers, and the verifier compares it to the answer he already knew. We prove that no information about the prover's long-term private key can possibly be leaked during such an authentication session.
These schemes can also be used for encryption.
This is joint work with Dima Grigoriev.

October 23, Graduate Center: Xiaowen Zhang (College Of Staten Island), Logical Analysis of RFID Authentication Protocols
Abstract: Radio Frequency Identification (RFID) Authentication Protocols (AP) are an active research topic. In this talk we consider three recently proposed RFID APs based on dynamic and static shared secret: CRAP, LCAP and O-TRAP. We examine them using GNY logic to determine whether they can be proved to have achieved their protocol goals. We show that when an authentication protocol uses static shared secret, encryption can be used to achieve the protocol goals. Meanwhile, when a protocol uses dynamic shared secret, hash operations seem to be good enough to achieve the protocol goals.

October 30, Graduate Center: Pascal Weil (LaBRI, Université de Bordeaux and CNRS), Automorphic orbits in F_2: words vs. subgroups
Abstract: We show that the following problems are decidable in a rank 2 free group F_2: does a finitely generated subgroup H contain primitive elements? does H meet the orbit of a given element u of F under the action of G, the group of automorphisms of F? Decidability subsists even in we restrict G to be a rational subset of the set of invertible substitutions (a.k.a. positive automorphisms) of F_2.
These results were obtained in joint work with P. Silva. They rely on a careful analysis of the action of certain simple automorphisms on the Stallings graph of H.
We will also discuss the decidability of a weaker problem in higher rank free groups. A. Clifford and R. Z. Goldstein independently solved the primitivity problem without rank restriction.

November 6, Graduate Center: William Skeith (The City College of New York), Public key encryption with efficient amortized updates
Abstract: Searching and modifying public-key encrypted data has received a lot of attention in recent literature. We re-visit this important topic and achieve improved amortized bounds including resolving a prominent open question posed by Boneh et al.

December 4, 1:00-7:00, Graduate Center: Manhattan Algebra Day

To subscribe to the seminar mailing list, click here

Spring 2009 talks

Fall 2008 talks

Spring 2008 talks

Fall 2007 talks

Spring 2007 talks

Fall 2006 talks

Spring 2006 talks

Fall 2005 talks