## CryptoDB

### David Freeman

#### Publications

**Year**

**Venue**

**Title**

2011

PKC

2011

EUROCRYPT

2010

ASIACRYPT

2010

EUROCRYPT

2010

EPRINT

Preventing Pollution Attacks in Multi-Source Network Coding
Abstract

Network coding is a method for achieving channel capacity in networks.
The key idea is to allow network routers to linearly mix packets as
they traverse the network so that recipients receive linear
combinations of packets. Network coded systems are vulnerable to
pollution attacks where a single malicious node floods the network
with bad packets and prevents the receiver from decoding correctly.
Cryptographic defenses to these problems are based on homomorphic
signatures and MACs. These proposals, however, cannot handle mixing of
packets from multiple sources, which is needed to achieve the full
benefits of network coding. In this paper we address integrity of
multi-source mixing. We propose a security model for this setting
and provide a generic construction.

2010

EPRINT

Homomorphic Signatures over Binary Fields: Secure Network Coding with Small Coefficients
Abstract

We propose a new signature scheme that can be used to authenticate data and prevent pollution attacks in networks that use network coding. At its core, our system is a homomorphic signature scheme that authenticates vector subspaces of a given ambient space. Our system has several novel properties not found in previous proposals:
- It is the first such scheme that authenticates vectors defined over *binary fields*; previous proposals could only authenticate vectors with large or growing coefficients.
- It is the first such scheme based on the problem of finding short vectors in integer lattices, and thus enjoys the worst-case security guarantees common to lattice-based
cryptosystems.
Security of our scheme (in the random oracle model) is based on a new hard problem on lattices, called k-SIS, that reduces to standard average-case and worst-case lattice problems.
Our construction gives an example of a cryptographic primitive -- homomorphic signatures over F_2 -- that can be built using lattice methods, but cannot currently be built using bilinear maps or other traditional algebraic methods based on factoring or discrete-log type problems.

2008

EPRINT

Abelian varieties with prescribed embedding degree
Abstract

We present an algorithm that, on input of a CM-field $K$, an integer $k \ge 1$, and a prime $r \equiv 1 \bmod k$, constructs a $q$-Weil number $\pi \in \O_K$ corresponding to
an ordinary, simple abelian variety $A$ over the field $\F$ of $q$ elements that has an $\F$-rational point of order $r$ and embedding degree $k$ with respect to $r$. We then discuss how CM-methods over $K$ can be used to explicitly construct $A$.

2008

EPRINT

A Generalized Brezing-Weng Algorithm for Constructing Pairing-Friendly Ordinary Abelian Varieties
Abstract

We give an algorithm that produces families of Weil numbers for ordinary abelian varieties over finite fields with prescribed embedding degree. The algorithm uses the ideas of Freeman, Stevenhagen, and Streng to generalize the Brezing-Weng construction of pairing-friendly elliptic curves. We discuss how CM methods can be used to construct these varieties, and we use our algorithm to give examples of pairing-friendly ordinary abelian varieties of dimension 2 and 3 that are absolutely simple and have smaller $\rho$-values than any previous such example.

2008

EPRINT

Signing a Linear Subspace: Signature Schemes for Network Coding
Abstract

Network coding offers increased throughput and improved robustness
to random faults in completely decentralized networks.
In contrast to traditional routing schemes, however, network coding
requires intermediate nodes to modify data packets en route;
for this reason, standard signature schemes are inapplicable and it
is a challenge to provide resilience to tampering by malicious
nodes.
Here, we propose two signature schemes that can be used in
conjunction with network coding to prevent malicious modification of
data. In particular, our schemes can be viewed as signing linear
subspaces in the sense that a signature on V
authenticates exactly those vectors in V.
Our first scheme is homomorphic and has better performance,
with both public key size and per-packet overhead being constant.
Our second scheme does not rely on random oracles and uses weaker assumptions.
We also prove a lower bound on the length of signatures for
linear subspaces showing that both of our schemes are essentially optimal in
this regard.

2007

EPRINT

Computing endomorphism rings of Jacobians of genus 2 curves over finite fields
Abstract

We present probabilistic algorithms which, given a genus 2 curve C defined over a finite field and a quartic CM field K, determine whether the endomorphism ring of the Jacobian J of C is the full ring of integers in K. In particular, we present algorithms for computing the field of definition of, and the action of Frobenius on, the subgroups J[l^d] for prime powers l^d. We use these algorithms to create the first implementation of Eisentrager and Lauter's algorithm for computing Igusa class polynomials via the Chinese Remainder Theorem, and we demonstrate the algorithm for a few small examples. We observe that in practice the running time of the CRT algorithm is dominated not by the endomorphism ring computation but rather by the need to compute p^3 curves for many small primes p.

2007

EPRINT

Constructing pairing-friendly genus 2 curves over prime fields with ordinary Jacobians
Abstract

We provide the first explicit construction of genus 2 curves over finite fields whose Jacobians are ordinary, have large prime-order subgroups, and have small embedding degree. Our algorithm works for arbitrary embedding degrees $k$ and prime subgroup orders $r$. The resulting abelian surfaces are defined over prime fields $\F_q$ with $q \approx r^4$. We also provide an algorithm for constructing genus 2 curves over prime fields $\F_q$ with ordinary Jacobians $J$ having the property that $J[r] \subset J(\F_{q})$ or $J[r] \subset J(\F_{q^k})$ for any even $k$.

2006

EPRINT

Constructing Pairing-Friendly Elliptic Curves with Embedding Degree 10
Abstract

We present a general framework for constructing families of elliptic curves of prime order with prescribed embedding degree. We demonstrate this method by constructing curves with embedding degree k = 10, which solves an open problem posed by Boneh, Lynn, and Shacham. We show that our framework incorporates existing constructions for k = 3, 4, 6, and 12, and we give evidence that the method is unlikely to produce infinite families of curves with embedding degree k > 12.

2006

EPRINT

A taxonomy of pairing-friendly elliptic curves
Abstract

Elliptic curves with small embedding degree and large prime-order subgroup are key ingredients for implementing pairing-based cryptographic systems. Such "pairing-friendly" curves are rare and thus require specific constructions. In this paper we give a single coherent framework that encompasses all of the constructions of pairing-friendly elliptic curves currently existing in the literature. We also include new constructions of pairing-friendly curves that improve on the previously known constructions for certain embedding degrees. Finally, for all embedding degrees up to 50, we provide recommendations as to which pairing-friendly curves to choose to best satisfy a variety of performance and security requirements.

2005

EPRINT

Pairing-based identification schemes
Abstract

We propose four different public-key identification schemes that make use of bilinear pairings, and prove their security under certain computational assumptions. Each of the schemes is more efficient and/or more secure than any known pairing-based identification scheme.

#### Coauthors

- Shweta Agrawal (3)
- Dan Boneh (7)
- Xavier Boyen (2)
- Markus Dürmuth (1)
- Oded Goldreich (1)
- Jonathan Katz (2)
- Eike Kiltz (1)
- Kristin E. Lauter (1)
- Sarah Meiklejohn (1)
- Alon Rosen (1)
- Michael Scott (2)
- Gil Segev (1)
- Hovav Shacham (1)
- Peter Stevenhagen (1)
- Marco Streng (1)
- Edlyn Teske (2)
- Vinod Vaikuntanathan (1)
- Brent Waters (2)