-
Random Self-Reducibility Properties of Learning Problems over Burnside Groups of Exponent 3
By Nelly Fazio, Kevin Iga, Antonio R. Nicolosi, Ludovic Perret, and William E. Skeith III.
Technical Report, CUNY - City College, 2011.
E-print | Abstract
In this work we investigate the hardness of a computational problem
introduced in the recent work of Baumslag et al. In particular, we study
the -LHN problem, which is a
generalized version of the learning with errors (LWE) problem, instantiated
with a particular family of non-abelian groups (free Burnside groups of
exponent 3). In our main result, we demonstrate a random self-reducibility
property for -LHN. Along the way, we also
prove a sequence of lemmas regarding homomorphisms of free Burnside groups
of exponent 3 that may be of independent interest.
-
Generalized Learning Problems and Applications to Non-Commutative Cryptography
By Gilbert Baumslag, Nelly Fazio, Antonio R. Nicolosi, Vladimir Shpilrain, and William E. Skeith III.
International Conference on Provable Security—ProvSec ’11 (to appear). Springer-Verlag, 2011.
E-print | Abstract
We propose a generalization of the learning parity with noise (LPN) and
learning with errors (LWE) problems to an abstract class of
group-theoretic learning problems that we term learning homomorphisms with
noise (LHN). This class of problems contains LPN and LWE as special
cases, but is much more general. It allows, for example, instantiations based
on non-abelian groups, resulting in a new avenue for the application of
combinatorial group theory to the development of cryptographic primitives. We
then study a particular instantiation using relatively free groups and
construct a symmetric cryptosystem based upon it.
-
A Framework for Group-Theoretic Cryptography
By Nelly Fazio and William E. Skeith III.
Technical report, CUNY - City College, 2010.
-
Public-Key Encryption with Efficient Amortized Updates
By Nishanth Chandran, Rafail Ostrovsky, William E. Skeith III.
Proc. of Security and Cryptography for Networks (SCN 2010)
E-print
-
Communication Complexity in Algebraic Two-Party Protocols
By Rafail Ostrovsky, William E. Skeith III.
Proc. of Advances in Cryptology, (CRYPTO-2008) Springer-Verlag/IACR Lecture Notes in Computer Science.
E-print
-
Private Searching on Streaming Data
By Rafail Ostrovsky, William Skeith III.
Journal of Cryptology. Vol. 20, No. 4, Oct. 2007. Springer New York. pp 397-430.
E-Print | Abstract
In this paper, we consider the problem of private searching on streaming data,
where we can efficiently implement searching for documents that satisfy a
secret criteria (such as presence or absence of a hidden combination of hidden
keywords) under various cryptographic assumptions. Our results can be viewed
in a variety of ways: as a generalization of the notion of Private Information
Retrieval (to more general queries and to a streaming environment); as positive
results on privacy-preserving datamining; and as a delegation of hidden program
computation to other machines.
-
Public Key Encryption that Allows PIR Queries
By Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, William E. Skeith III.
Proc. of Advances in Cryptology, (CRYPTO-2007) Springer-Verlag/IACR Lecture Notes in Computer Science.
E-print | Abstract
Consider the following problem: Alice wishes to maintain her email using a
storage-provider Bob (such as a Yahoo! or hotmail e-mail account). This
storage-provider should provide for Alice the ability to collect, retrieve,
search and delete emails but, at the same time, should learn neither the
content of messages sent from the senders to Alice (with Bob as an
intermediary), nor the search criteria used by Alice. A trivial solution is
that messages will be sent to Bob in encrypted form and Alice, whenever she
wants to search for some message, will ask Bob to send her a copy of the entire
database of encrypted emails. This however is highly inefficient.
We
will be interested in solutions that are communication-efficient and, at the
same time, respect the privacy of Alice. In this paper, we show how to create a
public-key encryption scheme for Alice that allows PIR searching over encrypted
documents. Our solution is the first to reveal no partial information
regarding the user's search (including the access pattern) in the public-key
setting and with non-trivially small communication complexity. This provides a
theoretical solution to a problem posed by Boneh, DiCrescenzo, Ostrovsky and
Persiano on ``Public-key Encryption with Keyword Search.'' The main technique
of our solution also allows for Single-Database PIR writing with sub-linear
communication complexity, which we consider of independent interest.
-
Private Information Retrieval: Single-Database Techniques and Applications
By Rafail Ostrovsky, William E. Skeith III
Homeland Security Technology Challenges, Chapter 6, pp 143-176. Artech House Publishing, 2008. G. Franceschetti, M. Grossi, Ed.
E-print