Algebra and Cryptography Seminar, Spring 2011

Organizers: Robert Gilman, Alexei Myasnikov, and Vladimir Shpilrain

Fridays:

2:30-3:30 pm
365 Fifth Avenue at 34th Street

or

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

directions

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."