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