Algebra and Cryptography Seminar, Fall 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


October 14, Graduate Center: Xiaowen Zhang (College of Staten Island), Hash function based secret sharing scheme designs
Abstract: Secret sharing schemes create an effective way to protect a secret by dividing it among several participants. In this talk we’ll briefly review the concepts: iterative hash function, herding and Nostradamus attack, secret sharing scheme, and access structure. Using hash functions and the herding hashes technique, we first set up a (t+1, n) threshold scheme which is perfect and ideal, and then we extend it to schemes for any general access structure. The schemes can be further set up as proactive or verifiable if necessary. The setup and recovery of the secret is efficient due to the fast calculation of the hash function. The proposed scheme is flexible because of the use of existing hash functions.
This is joint work with Chi Chum.

October 28, Graduate Center: Dov Gordon (Columbia University), Secure Computation: From Theory Towards Practice
Abstract: In 1982, Yao introduced the field of "secure computation", in which n parties, holding private inputs x_1,...,x_n, engage in a protocol to compute some function f(x_1,...,x_n), while revealing nothing more than the output. In the decade that followed, the topic of secure computation was thoroughly explored, and almost every theoretical question was answered. In the past decade, the focus has shifted towards improving efficiency, and building implementations. Today, secure computation is poised to become an extremely powerful tool with wide-ranging application. Both bodies of research were essential in bringing this about.
In this talk, we review several recent results. The first will provide insight into one of the few remaining theoretical questions in secure computation. We then demonstrate improved efficiency for secure computation in several particular settings of interest. On the theoretical side, we discuss the problem of "fairness" in secure computation, which is a security property guaranteeing simultaneous output delivery to both parties. Until recently, this was widely believed to be impossible to achieve. We will discuss a new relaxed notion of fairness and show broad feasibility results. We will also touch on a very exciting result demonstrating (for the first time) that some interesting functions can in fact be computed with complete fairness. In the second half of the talk, we will focus on several settings that arise in more modern, real-world environments, and show how we can tailor the theoretical results to greatly improve efficiency. Our goal is to demonstrate the importance of both foundational and applied cryptographic theory.

November 4, Graduate Center: Vladimir Shpilrain (City College), A Secret Sharing Scheme Using Groups
Abstract: A (t,n)-threshold secret sharing scheme is a method to distribute a secret among n participants in such a way that any t participants can recover the secret, but no t-1 participants can. Here we propose two new secret sharing schemes using non-abelian groups. One scheme is the special case where all the participants must get together to recover the secret. The second one is a (t,n)-threshold scheme that is a hybrid of Shamir's scheme and our group-theoretic scheme. The question of security of long-term secrets in our schemes yields an interesting question of group theory as to what information about relators of a finitely presented group can be recovered from a collection of words that are equal to 1 in this group.
This is joint work with Maggie Habeeb and Delaram Kahrobaei.

November 11, Graduate Center, room 4214-03, 2:00 pm: Maggie Habeeb (CUNY Graduate Center), PhD thesis: 'Groups, Complexity, Cryptology'


To subscribe to the seminar mailing list, click here

Spring 2011 talks

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