2:30-3:30 pm
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