2:30-3:30 pm
February 1, Graduate Center, room 4421, 2:00 pm: Bren Cavallo (CUNY
Graduate Center),
Secret sharing (oral exam)
February 22, Graduate Center: Vladimir Shpilrain (City College),
Nature-based cryptography
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.
To subscribe to the seminar mailing list, click here