## CryptoDB

### David P. Woodruff

#### Publications

**Year**

**Venue**

**Title**

2006

EPRINT

Fast Algorithms for the Free Riders Problem in Broadcast Encryption
Abstract

We provide algorithms to solve the free riders problem in
broadcast encryption. In this problem, the broadcast server is
allowed to choose some small subset F of the revoked set
R of users to allow to decrypt the broadcast, despite
having been revoked. This may allow the server to significantly
reduce network traffic while only allowing a small set of
non-privileged users to decrypt the broadcast.
Although there are worst-case instances of broadcast
encryption schemes where the free riders problem is difficult to
solve (or even approximate), we show that for many specific
broadcast encryption schemes, there are efficient algorithms. In
particular, for the complete subtree method and some other schemes in the subset-cover framework, we show how to find the optimal assignment of free riders in O(|R||F|) time, which is independent of the total number of users. We also define an approximate version of this problem, and study specific distributions of R for which this
relaxation yields even faster algorithms.
Along the way we develop the first approximation algorithms for the following problem: given two integer sequences a_1 >= a_2>= ... >= a_n and b_1 >= b_2 >= ... >= b_n, output for all i, an integer j' for which a_{j'} + b_{i-j'} <= (1+\epsilon) min_j a_j + b_{i-j}. We show that if the differences a_i - a_{i+1}, b_i-b_{i+1} are bounded, then there is an O(n^{4/3}/\epsilon^{2/3})-time algorithm for this problem, improving upon the O(n^2) time of the naive algorithm.

2006

EPRINT

Revisiting the Efficiency of Malicious Two-Party Computation
Abstract

In a recent paper Mohassel and Franklin study the efficiency of secure two-party computation in the presence of malicious behavior. Their aim is to make classical solutions to this problem, such as zero-knowledge compilation, more efficient. The authors provide several schemes which are the most efficient to date. We propose a modification to their main scheme using expanders. Our modification asymptotically improves at least one measure of efficiency of all known schemes. We also point out an error, and improve the analysis of one of their schemes.

2004

EPRINT

Private Inference Control
Abstract

Access control can be used to ensure that database queries
pertaining to sensitive information
are not answered. This is not enough to prevent users from
learning sensitive information though, because users can combine
non-sensitive information to discover something sensitive.
Inference control prevents users from obtaining sensitive
information via such ``inference channels'', however, existing
inference control techniques are not private - that is, they
require the server to learn what queries the user is making in
order to deny inference-enabling queries.
We propose a new primitive - private inference control (PIC) -
which is a means for the server to provide inference control
without learning what information is being retrieved. PIC is a
generalization of private information retrieval (PIR) and
symmetrically-private information retrieval (SPIR). While it is
straightforward to implement access control using PIR (simply omit
sensitive information from the database), it is nontrivial to
implement inference control efficiently. We measure the
efficiency of a PIC protocol in terms of its communication
complexity, its round complexity, and the work the server performs
per query. Under existing cryptographic assumptions, we give a PIC
scheme which is simultaneously optimal, up to logarithmic factors,
in the work the server performs per query, the total communication
complexity, and the number of rounds of interaction. We also
present a scheme requiring more communication but sufficient
storage of state by the server to facilitate private user
revocation. Finally, we present a generic reduction which shows
that one can focus on designing PIC schemes for which the
inference channels take a particularly simple threshold form.

2004

EPRINT

Practical Cryptography in High Dimensional Tori
Abstract

At Crypto 2004, van Dijk and Woodruff introduced a new way of using the algebraic tori T_n in cryptography, and obtained an asymptotically optimal n/phi(n) savings in bandwidth and storage for a number of cryptographic applications. However, the computational requirements of compression and decompression in their scheme were impractical, and it was left open to reduce them to a practical level. We give a new method that compresses orders of magnitude faster than the original, while also speeding up the decompression and improving on the compression factor (by a constant term). Further, we give the first efficient implementation that uses T_30, compare its performance to XTR, CEILIDH, and ECC, and present new applications. Our methods achieve better compression than XTR and CEILIDH for the compression of as few as two group elements. This allows us to apply our results to ElGamal encryption with a small message domain to obtain ciphertexts that are 10% smaller than in previous schemes.

#### Coauthors

- Robert Granger (2)
- Piotr Indyk (1)
- Dan Page (2)
- Zulfikar Ramzan (2)
- Karl Rubin (2)
- Alice Silverberg (2)
- Jessica Staddon (1)
- Martijn Stam (2)
- Marten van Dijk (4)