Algebra and Cryptography Seminar, Spring 2013

Organizers: Robert Gilman, Delaram Kahrobaei, 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 1, Graduate Center, room 4421, 2:00 pm: Bren Cavallo (CUNY Graduate Center), Secret sharing (oral exam)

Abstract: This is an encore presentation of the talk given on November 9, 2012 when many people could not attend because of problems with public transportation in the aftermath of hurricane Sandy. In this presentation we will focus on understanding what it is, exactly, that makes our protocol secure against computationally unbounded adversary.
We employ physical properties of the real world to design a secure cryptographic protocol where one of the parties is able to transmit secret information to another party over an insecure channel, without any prior secret arrangements between the parties. The distinctive feature of this protocol, compared to all known public-key protocols, is that neither party uses a one-way function. In particular, our protocol is secure against (passive) computationally unbounded adversary.
This is joint work with Dima Grigoriev.

March 8, Graduate Center: Clemente Cannone (Columbia University), Testing probability distributions using conditional samples
Abstract: One of the most fundamental problem paradigms in statistics is that of inferring some information about an unknown probability distribution D, given access to independent samples drawn from it. More than a decade ago, Batu et al. initiated the study of problems of this type from within the framework of property testing, a setting where, given an unknown "massive object" an algorithm can access only by making a small (sublinear) number of "local inspections" (queries) of the object, the goal is to determine whether the object has a particular property. The algorithm must accept if the object has the desired property, and reject if the object is far from every object with the property. In distribution property testing, the "massive object" is an unknown probability distribution D over an N-element set, and the tester accesses the distribution by drawing independent samples from it.
We study a new framework for such a task, by considering distribution testing algorithms that have access to a conditional sampling oracle. This is an oracle that takes as input a subset S of the domain [N]={1,...,N} of the unknown probability distribution D and returns a draw from the conditional probability distribution D restricted to S. This new model allows considerable flexibility in the design of distribution testing algorithms; in particular, testing algorithms in this model can be adaptive.
We study a wide range of natural distribution testing problems in this new framework and some of its variants, giving both upper and lower bounds on query complexity. These problems include testing whether D is the uniform distribution U; testing whether D = D* for an explicitly provided D*; testing whether two unknown distributions D1 and D2 are equivalent; and estimating the variation distance between D and the uniform distribution.
At a high level our main finding is that the new "conditional sampling" framework we consider is a powerful one: while all the problems mentioned above have Omega(N^(1/2)) sample complexity in the standard model (and in some cases the complexity must be almost linear in N), we give poly(log N, 1/eps)-query algorithms (and in some cases poly(1/eps)-query algorithms independent of N) for all these problems in our conditional sampling setting.
Joint work with Dana Ron (Tel-Aviv University) and Rocco Servedio (Columbia University).

April 5, 2:00 pm, Graduate Center: Anja Moldenhauer (University of Hamburg), A secret sharing scheme based on the closest vector theorem and a modification to a private key cryptosystem
Abstract: An (n, t) secret sharing protocol, with n, t \in N and t \le n, is a method to distribute a secret among a group of n participants in such a way that it can be recovered only if at least t of them combine their shares. We explain the steps for an (n, t) secret sharing scheme based on the closest vector theorem first published by [C. S. Chum, B. Fine, G. Rosenberger and X. Zhang, A proposed alternative to the Shamir secret sharing scheme, Contemporary Mathematics 582 (2012), 47-50]. We take a look at the security and the complexity and compare it to Shamir's secret sharing scheme. Finally, we modify the (n, t) secret sharing scheme based on the closest vector theorem to a private key cryptosystem.
This is an extended version of my talk in the AMS Special Session on "Algorithmic problems of group theory and applications to information security" at Boston College, April 6-7, 2013.

April 12, Graduate Center: Sibel Adali (Rensselaer Polytechnic Institute), Understanding the role of trust in epistemological decision making in social networks
Abstract: When modeling trust in scenarios involving information exchange and epistemological decision making, one has to take into account multiple considerations: the trustworthiness and the competence of the sources as well as the credibility of the information. To this date, there is little work on understanding how these factors as a system can be studied. In this talk, I will first describe a study that shows how competence and trustworthiness lead to very different behaviors and hence can be studied in complementary ways. Then, I will talk about various measures of competence and prominence, and illustrate how they improve on the state of the art in this area. I will also show how trustworthiness can be modeled accurately through a generalized structural balance theory in networks. I will conclude by describing ongoing work on measuring the credibility of information, and agent models for studying the impact of various aspects of trust in decision making in organizational settings.

Sibel Adali is an Associate Professor at Renssealer Polytechnic Institute. Her work concentrates on cross-cutting problems related to trust, information processing and retrieval and social networks. As part of her work, she has worked as the ARL-lead Collaborative Technology Alliance (CTA) wide Trust Coordinator, Social and Cognitive Networks Academic Research Center (SCNARC) Associate Director. She is the author of a book on "Modeling Trust Context in Networks", to be released in April 2013 by Springer.

April 26, Graduate Center: Bren Cavallo (CUNY Graduate Center), Secret Sharing using the Shortlex Ordering
Abstract: In this talk I will talk about a modified version of the Habeeb-Kahrobaei-Shpilrain secret sharing scheme using the shortlex order on free groups. Additionally, I will present a modification of the above that allows multiple secrets to be sent out in a secure fashion.

May 3, Graduate Center: Andrei Klimakov (Moscow State University), Homogeneous almost primitive elements of free non-associative algebras
Abstract: We consider free non-associative algebras, free (anti)commutative non-associative algebras, and free Lie algebras. Subalgebras of these algebras are also free. An element of a free algebra F is primitive if it is an element of some set of free generators of this free algebra. An almost primitive element of a free algebra F is an element which is not primitive in F, but is primitive in any proper subalgebra of F containing it. We construct series of almost primitive elements of these free algebras and obtain criteria for a homogeneous element to be almost primitive.