International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

David Freeman

Publications

Year
Venue
Title
2011
PKC
2011
EUROCRYPT
2011
EUROCRYPT
2011
ASIACRYPT
2010
PKC
2010
PKC
2010
JOFC
2010
ASIACRYPT
2010
EUROCRYPT
2010
EPRINT
Preventing Pollution Attacks in Multi-Source Network Coding
Shweta Agrawal Dan Boneh David Mandell Freeman Xavier Boyen
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
Dan Boneh David Mandell Freeman
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.
2009
PKC
2008
EPRINT
Abelian varieties with prescribed embedding degree
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
David Freeman
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
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
David Freeman Kristin E. Lauter
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
David Freeman
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
David Freeman
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
David Freeman Michael Scott Edlyn Teske
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
David Freeman
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.