init attribute-based encryption

Change-Id: Iba1a3d722110abf747a0fba366f3ebc911d25b25

22 files changed, 1609 insertions, 0 deletions

diff --git a/moon-abe/pbc-0.5.14/doc/basics.txt b/moon-abe/pbc-0.5.14/doc/basics.txt
new file mode 100644
index 00000000..c9549f72
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/basics.txt
@@ -0,0 +1,58 @@
+=== Basics ===
+
+Programs using the PBC library should include the file `pbc.h`:
+
+  #include <pbc.h>
+
+and linked against the PBC library and the GMP library, e.g.
+
+  $ gcc program.c -L. -lpbc -lgmp
+
+The file `pbc.h` already includes `gmp.h`.
+
+PBC follows GMP in several respects:
+
+* Output arguments generally precede input arguments.
+* The same variable can be used as input and output in one call.
+* Before a variable may be used it must be initialized exactly once.
+When no longer needed it must be cleared. For efficiency, unnecessary
+initializating and clearing should be avoided.
+* PBC variables ending with +_t+ behave the same as
+GMP variables in function calls: effectively as call-by references.
+In other words, as in GMP, if a function that modifies an input variable,
+that variable remains modified when control return is returned to the caller.
+* Like GMP, variables automatically allocate memory when needed.
+By default, +malloc()+ and friends are called but this can be changed.
+* PBC functions are mostly reentrant.
+
+Since the PBC library is built on top of GMP, the GMP types
+are available. PBC types are similar to GMP types.
+The following example is paraphrased from an example in the GMP
+manual, and shows how to declare the PBC data type +element_t+.
+
+    element_t sum;
+    struct foo { element_t x, y; };
+    element_t vec[20];
+
+GMP has the +mpz_t+ type for integers, +mpq_t+ for rationals and so on.
+In contrast, PBC uses the +element_t+ data type for elements of different
+algebraic structures, such as elliptic curve groups, polynomial rings and
+finite fields. Functions assume their inputs come from appropriate algebraic
+structures.
+
+PBC data types and functions can be categorized as follows. The first two alone
+suffice for a range of applications.
+
+ - +element_t+: elements of an algebraic structure.
+ - +pairing_t+: pairings where elements belong; can initialize from sample
+   pairing parameters bundled with PBC in the +param+ subdirectory.
+ - +pbc_param_t+: used to generate pairing parameters.
+ - +pbc_cm_t+: parameters for constructing curves via the CM method; sometimes
+   required by +pbc_param_t+.
+ - +field_t+: algebraic structures: groups, rings and fields; used internally
+   by +pairing_t+.
+ - a few miscellaneous functions, such as ones controlling how random bits are
+   generated.
+
+Functions operating on a given data type usually have the same prefix, e.g.
+those involving +element_t+ objects begin with +element_+.
diff --git a/moon-abe/pbc-0.5.14/doc/bundle.txt b/moon-abe/pbc-0.5.14/doc/bundle.txt
new file mode 100644
index 00000000..13256d83
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/bundle.txt
@@ -0,0 +1,119 @@
+[[bundlechap]]
+== Bundled programs ==
+
+Several binaries and curve parameters are bundled with the PBC library,
+such as <<pbcintro, the `pbc` program>>.
+
+The `param` subdirectory contains pairing parameters one might use in
+a real cryptosystem. Many of the test programs read the parameters
+from files such as these on standard input, for example:
+
+  $ benchmark/benchmark < param/c159.param
+  $ example/bls < param/e.param
+
+[[pbcref]]
+=== Pairing-based calculator ===
+
+The `pbc` subdirectory contains the pairing-based calculator, `pbc`,
+which is loosely based on `bc`, a well-known arbitrary precision
+calculator.
+
+See `pairing_test.pbc` for an example script. Some differences: the assignment
+operator is `:=`, and newlines are ordinary whitespace and not statement
+terminators.
+
+If started with the `-y` option, the syntax is compatible with `bc`: newlines
+are treated as statement terminators and `=` is assignment. Additionally,
+`pbc` displays a prompt. This mode may be easier for beginners.
+
+Initially, the variables G1, G2, GT and Zr are represent groups associated with
+a particular A pairing.
+
+An element is represented with a tree of integers, such as `[[1,2], 3]`, or
+`4`.
+
+Assignments such as `variable := expression;` return the value of the variable.
+
+The arithmetic operators `+, -, /, *, ^` have the standard precedence.
+The C comparison operators and ternary operator are available.
+
+Each statement should be terminated by a semicolon.
+
+Comments are the same as in (original) C, or begin with "#" and end at a
+newline.
+
+Some of the pbc functions:
+
++init_pairing_A()+::
+Set the variables G1, G2, GT and Zr to the groups in a particular A pairing:
++
+  init_pairing_A();
++
+Other sample pairings can be used by replacing `A` with one of `D, E, F, G`.
+
++rnd(+'G'+)+::
+Returns a random element of an algebraic structure 'G', e.g:
++
+  g := rnd(Zr);
++
+Synonym: `random`.
+
++pairing(+'g, h'+)+::
+Returns the pairing applied to 'g' and 'h'.
+The element 'g' must be an element of G1 and 'h' of G2, e.g:
++
+  pairing(rnd(G1), rnd(G2));
+
+'G'+(+'g'+)+::
+Maps an element 'g' to element of the field 'G', e.g:
++
+  Zr(123);
+  GT([456, 789]);
+
+=== Parameter generation ===
+
+Programs that generate pairing parameters are located in the `gen`
+subdirectory. Some of the programs are already functional enough to be used to
+find parameters for real applications. I need to write more documentation
+first; for now, read the source!
+
+*listmnt*::
+  Searches for discriminants D that lead to MNT curves with subgroups
+  of prime order.
+
+*genaparam*, *gena1param*, *gendparam*, *geneparam*, *genfparam*, *gengparam*::
+  Prints parameters for a curve suitable for computing pairings of a given type.
+  The output can be fed to some of the other test programs.  The programs
+  `gendparam` and `gengparam` should be given a discriminant as the first
+  argument.
+
+*hilbertpoly*::
+  Prints the Hilbert polynomial for a given range of discriminants. Computing
+  the Hilbert polynomial is an intermediate step when generating type D
+  parameters.
+
+=== Example cryptosystems ===
+
+In the `example` subdirectory there are various programs that read curve
+parameters on standard input and perform computations that would be required in
+a typical implementation of a pairing-based cryptosystem. Sample schemes
+include:
+
+-   Boneh-Lynn-Shacham short signatures
+-   Hess identity-based signatures
+-   Joux tripartite Diffie-Hellman
+-   Paterson identity-based signatures
+-   Yuan-Li identity-based authenticated key agreement
+-   Zhang-Kim identity-based blind/ring signatures
+-   Zhang-Safavi-Naini-Susilo signatures
+
+More work would be required to turn these programs into real applications.
+
+=== Benchmarks ===
+
+I use the programs in the `benchmark` subdirectory to measure running times of
+pairings, and also RSA decryptions.
+
+The `benchmark` program takes pairing parameters on standard input and reports
+the average running time of the pairing over 10 runs, while `timersa` estimates
+the time required to perform one 1024-bit RSA decryption.
diff --git a/moon-abe/pbc-0.5.14/doc/contributors.txt b/moon-abe/pbc-0.5.14/doc/contributors.txt
new file mode 100644
index 00000000..aa67c91f
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/contributors.txt
@@ -0,0 +1,35 @@
+== Appendix A: Contributors ==
+
+Ben Lynn wrote the original PBC library and documentation and is still
+maintaining and developing it.
+
+Hovav Shacham wrote the multiexponentiation, sliding windows and preprocessed
+exponentiation routines, Makefile improvements, and other enhancements.
+He also helps administer the mailing list.
+
+
+Joseph Cooley wrote the GNU build system files,
+tested the library on Mac OS X, and added miscellaneous improvements.
+Among other things,
+pairings can be read from memory buffer and
+most compile-time warnings were removed.
+
+
+Rob Figueiredo and Roger Khazan wrote changes which allow the PBC library
+to be compiled on Windows (via mingw).
+
+
+Dmitry Kosolapov sent in manual corrections, and wrote
+several cryptosystem demos.
+
+
+John Bethencourt sent in many helpful patches, e.g. fixes that allow PBC to
+work on 64-bit platforms.
+
+
+Paul Miller reported bugs, manual corrections and also wrote
+the Gentoo portage overlay for PBC.
+
+
+If you're not mentioned here but should be, please let me know!
+(blynn at cs dot stanford dot edu).
diff --git a/moon-abe/pbc-0.5.14/doc/custom-nochunks.xsl b/moon-abe/pbc-0.5.14/doc/custom-nochunks.xsl
new file mode 100644
index 00000000..49256ede
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/custom-nochunks.xsl
@@ -0,0 +1,22 @@
+<?xml version='1.0'?>
+<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
+                xmlns:fo="http://www.w3.org/1999/XSL/Format"
+		                version="1.0">
+<xsl:param name="html.stylesheet" select="'default.css'"/>
+<xsl:param name="generate.toc" select="'book toc'"/>
+<xsl:output method="html" encoding="UTF-8" indent="no"
+doctype-public="-//W3C//DTD HTML 4.01 Transitional//EN"
+/>
+<xsl:template name="user.footer.navigation">
+<script type="text/javascript">
+var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
+document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
+</script>
+<script type="text/javascript">
+try{
+var pageTracker = _gat._getTracker("UA-1901330-5");
+pageTracker._trackPageview();
+} catch(err) {}
+</script>
+</xsl:template>
+</xsl:stylesheet>
diff --git a/moon-abe/pbc-0.5.14/doc/custom-pretty.xsl b/moon-abe/pbc-0.5.14/doc/custom-pretty.xsl
new file mode 100644
index 00000000..ab619ef6
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/custom-pretty.xsl
@@ -0,0 +1,32 @@
+<?xml version='1.0'?>
+<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
+                xmlns:fo="http://www.w3.org/1999/XSL/Format"
+		                version="1.0">
+<xsl:param name="chunk.section.depth" select="1"></xsl:param>
+<xsl:param name="chunk.first.sections" select="1"></xsl:param>
+<xsl:param name="css.decoration" select="0"></xsl:param>
+<xsl:param name="toc.list.type">ul</xsl:param>
+<xsl:param name="chunker.output.encoding" select="'UTF-8'"></xsl:param>
+<xsl:param name="chunker.output.doctype-public" select="'-//W3C//DTD HTML 4.01 Transitional//EN'"></xsl:param>
+<!-- use tidy instead
+<xsl:param name="chunker.output.indent" select="'yes'"></xsl:param>
+-->
+<xsl:param name="suppress.navigation" select="1"></xsl:param>
+<xsl:param name="generate.toc" select="'book toc'"/>
+<xsl:param name="html.stylesheet" select="'pretty.css'"/>
+
+<xsl:template name="user.footer.navigation">
+<script type="text/javascript" src="find_selflink.js"></script>
+<script type="text/javascript">
+var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
+document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
+</script>
+<script type="text/javascript">
+try{
+var pageTracker = _gat._getTracker("UA-1901330-5");
+pageTracker._trackPageview();
+} catch(err) {}
+</script>
+</xsl:template>
+
+</xsl:stylesheet>
diff --git a/moon-abe/pbc-0.5.14/doc/custom.xsl b/moon-abe/pbc-0.5.14/doc/custom.xsl
new file mode 100644
index 00000000..8fcac646
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/custom.xsl
@@ -0,0 +1,24 @@
+<?xml version='1.0'?>
+<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
+                xmlns:fo="http://www.w3.org/1999/XSL/Format"
+		                version="1.0">
+<!--
+To chunk by chapter only:
+<xsl:param name="chunk.section.depth" select="0"></xsl:param>
+-->
+<xsl:param name="chunker.output.encoding" select="'UTF-8'"></xsl:param>
+<xsl:param name="chunker.output.doctype-public" select="'-//W3C//DTD HTML 4.01 Transitional//EN'"></xsl:param>
+
+<xsl:template name="user.footer.navigation">
+<script type="text/javascript">
+var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
+document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
+</script>
+<script type="text/javascript">
+try{
+var pageTracker = _gat._getTracker("UA-1901330-5");
+pageTracker._trackPageview();
+} catch(err) {}
+</script>
+</xsl:template>
+</xsl:stylesheet>
diff --git a/moon-abe/pbc-0.5.14/doc/default.css b/moon-abe/pbc-0.5.14/doc/default.css
new file mode 100644
index 00000000..b386f84d
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/default.css
@@ -0,0 +1,71 @@
+body {
+    font-size: 90%;
+    font-family: verdana, arial, sans-serif;
+}
+
+tt, code, pre, .type {
+    font-family: andale mono, courier new, courier, monospace;
+    font-size: 90%;
+}
+
+.author {
+    display : none;
+}
+
+.copyright {
+    display : none;
+}
+
+div.TOC {
+    float: left;
+    width: 13em;
+    font-size: 90%;
+
+    border: 1px solid #aaaaaa;
+    background-color: #f9f9f9;
+    padding: 0.17em;
+}
+
+hr {
+    display: none;
+}
+
+div.chapter, div.preface {
+    border-left: 13em solid white;
+    padding-left: 1em;
+}
+
+h1.title {
+    border: 1px solid #aaaaaa;
+    background-color: #f9f9f9;
+    padding: 0.17em;
+}
+
+div.chapter h1, div.preface h1 {
+    padding-top: 0.5em;
+    padding-bottom: 0.17em;
+    margin: 0;
+    font-weight: normal;
+    border-bottom: 1px solid #aaaaaa;
+}
+
+h2 {
+    padding-top: 0.5em;
+    padding-bottom: 0.17em;
+    margin: 0;
+    font-weight: normal;
+    border-bottom: 1px solid #aaaaaa;
+}
+
+.programlisting, .screen {
+    margin: 0;
+    border: 1px solid #aaaaaa;
+    background-color: #f9f9f9;
+    padding: 0.17em;
+    margin: 1em;
+    margin-right: 3em;
+}
+
+.parameter {
+    font-style: italic;
+}
diff --git a/moon-abe/pbc-0.5.14/doc/elementfns.txt b/moon-abe/pbc-0.5.14/doc/elementfns.txt
new file mode 100644
index 00000000..cadf78b0
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/elementfns.txt
@@ -0,0 +1,111 @@
+== Element functions ==
+
+Elements of groups, rings and fields are stored in the +element_t+ data type.
+Variables of this type must be initialized before use, and should be cleared
+after they are no longer needed.
+
+The +element_+ functions must be used with caution.  Just as division by zero
+does not make sense for integers, some operations may not make sense for
+particular elements. For example, in a ring, one cannot in general invert
+elements.
+
+Another caveat is that many of these functions assume their arguments come from
+the same ring, group or field. No implicit type casting is performed.
+
+For debug builds, turn on run-time checks by defining `PBC_DEBUG` before
+including `pbc.h`:
+
+  #define PBC_DEBUG
+  #include <pbc.h>
+
+Also, when `PBC_DEBUG` is defined, the following macros are active.
+Normally they are replaced with empty statements.
+
+include::gen/debug.txt[]
+
+=== Initializing elements ===
+
+When an element is initialized it is associated with an algebraic structure,
+such as a particular finite field or elliptic curve group.
+
+We use G1 and G2 to denote the input groups to the pairing, and GT for the
+output group. All have order r, and Zr means the ring of integers modulo r.
+G1 is the smaller group (the group of points over the base field). With
+symmetric pairings, G1 = G2.
+
+include::gen/einit.txt[]
+
+=== Assigning elements ===
+
+These functions assign values to elements. When integers are assigned,
+they are mapped to algebraic structures canonically if it makes sense
+(e.g. rings and fields).
+
+include::gen/eassign.txt[]
+
+=== Converting elements ===
+
+include::gen/econvert.txt[]
+
+=== Element arithmetic ===
+
+Unless otherwise stated, all +element_t+ arguments to these functions must have
+been initialized to be from the same algebraic structure.  When one of these
+functions expects its arguments to be from particular algebraic structures,
+this is reflected in the name of the function.
+
+The addition and multiplication functions perform addition and multiplication
+operations in rings and fields. For groups of points on an ellitpic curve, such
+as the G1 and G2 groups associated with pairings, both addition and
+multiplication represent the group operation (and similarly both 0 and 1
+represent the identity element).  It is recommended that programs choose and
+one convention and stick with it to avoid confusion.
+
+In contrast, the GT group is currently
+implemented as a subgroup of a finite field, so only multiplicative operations
+should be used for GT.
+
+include::gen/earith.txt[]
+
+=== Exponentiating elements ===
+
+Exponentiation and multiexponentiation functions.  If it is known in advance
+that a particular element will be exponentiated several times in the future,
+time can be saved in the long run by first calling the preprocessing function:
+
+    element_pp_t g_pp;
+    element_pp_init(g_pp, g);
+    element_pp_pow(h, pow1, g_pp); // h = g^pow1
+    element_pp_pow(h, pow2, g_pp); // h = g^pow2
+    element_pp_pow(h, pow3, g_pp); // h = g^pow3
+    element_pp_clear(g_pp);
+
+include::gen/epow.txt[]
+
+=== Comparing elements ===
+
+These functions compare elements from the same algebraic structure.
+
+include::gen/ecmp.txt[]
+
+=== Element I/O ===
+
+Functions for producing human-readable outputs for elements.
+Converting elements to and from bytes are discussed later.
+
+include::gen/eio.txt[]
+
+=== Random elements ===
+
+Only works for finite algebraic structures. Effect on polynomial rings, fields
+of characteristic zero, etc. undefined.
+
+See <<randomref>> for how PBC gets random bits.
+
+include::gen/erandom.txt[]
+
+=== Element import/export ===
+
+Functions for serializing and deserializing elements.
+
+include::gen/etrade.txt[]
diff --git a/moon-abe/pbc-0.5.14/doc/extract b/moon-abe/pbc-0.5.14/doc/extract
new file mode 100644
index 00000000..77a6a69a
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/extract
@@ -0,0 +1,67 @@
+#!/usr/bin/gawk -f
+# Extract GMP-style documentation from source using AsciiDoc format.
+# Fragile:
+# - requires function definition/declaration to end with ")\n" or ");" or ") {"
+# - does not play nice with function pointer parameters
+
+# Look for the magic string "/*@manual "
+/^\/\*@manual / {
+  outfile = "gen/" gensub(".*manual ", "", 1) ".txt"
+  print "Writing to " outfile
+  n = 0
+  getline
+  # Stop at the line "*/".
+  while ($0 != "*/") {
+    a[n] = $0
+    n++
+    getline
+  }
+
+# Simple version with no markup:
+#  do {
+#     getline
+#     print
+#  } while (!match($0, ";") && !match($0, "{"))
+
+# Mark up bits of the function declaration with AsciiDoc, e.g:
+# "int main(int argc, char *argv[]);" should become
+# "int *main*('int argc', 'char *argv[]');"
+# Also suppress "static inline".
+  getline
+
+# Handle variable declarations.
+  if (!match($0, "\\(")) {
+    s = gensub("([^ ]*);", "*\\1*", 1)  # Bold variable name.
+# Handle macro declarations.
+  } else if (match($0, "^#define")) {
+    s = gensub("^#define *(.*[^ ]) *\\\\$", "*\\1*", 1)
+# Otherwise it's a function.
+  } else {
+
+    sub("static inline ", "")
+    s = gensub("(\\w*)\\(", " *\\1*(", 1)  # Bold function name.
+    s = gensub("\\((.*$)", "('\\1", 1, s)  # First parameter.
+    gsub(", *", "', '", s)  # Separating commas.
+    gsub("_ptr", "_t", s)
+# Handle multi-line function declarations.
+    while (!match(s, ");") && !match(s, ") *$") && !match(s, ") *{")) {
+      getline
+      gsub("^ *", "")      # Remove leading whitespace.
+      gsub(", *", "', '")  # Commas again.
+      gsub("_ptr", "_t")
+      s = s $0
+    }
+    s = gensub("(.*)\\)", "\\1')", 1, s)  # Last parameter
+    gsub("_ptr", "_t", s)
+    gsub(")[^)]*$", ")", s);
+  }
+
+  print s "\n" > outfile
+  if (n > 0) {
+    print "____" > outfile
+    for(i = 0; i < n; i++) {
+      print a[i] > outfile
+    }
+    print "____" > outfile
+  }
+}
diff --git a/moon-abe/pbc-0.5.14/doc/find_selflink.js b/moon-abe/pbc-0.5.14/doc/find_selflink.js
new file mode 100644
index 00000000..db436db7
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/find_selflink.js
@@ -0,0 +1,37 @@
+// From my own website(!)
+//TODO: only do this for links in the table of contents menu
+
+function find_selflink() {
+    var a = document.links;
+    var i = 0;
+    while (i < a.length) {
+	if (a[i].href == document.URL) {
+            var c;
+            var j;
+            var s_new = document.createElement("span");
+            s_new.className = "currentlink";
+            c = a[i].childNodes;
+            for (j=0; j<c.length; j++) {
+                s_new.appendChild(c[j]);
+            }
+            a[i].parentNode.replaceChild(s_new, a[i]);
+        } else {
+            i++;
+        }
+
+	/*
+	if (a[i].href == document.URL) {
+	    a[i].className = "currentlink";
+	    if (0) {
+		var s_new = document.createElement("span");
+		s_new.className = "currentlink";
+		s_new.appendChild(a[i]);
+		a[i].parentNode.replaceChild(s_new, a[i]);
+	    }
+	}
+	i++;
+	*/
+    }
+}
+
+find_selflink();
diff --git a/moon-abe/pbc-0.5.14/doc/index.txt b/moon-abe/pbc-0.5.14/doc/index.txt
new file mode 100644
index 00000000..ccf0b503
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/index.txt
@@ -0,0 +1,13 @@
+== PBC library manual ==
+
+Other editions:
+
+- link:../chunked/[Chunked HTML]: One HTML file per section, with no attempts
+  to make it easier to read.
+ 
+- link:../manual.html[Single HTML]: One big HTML file. I attemped to improve
+  its appearance.
+  
+- link:../manual.pdf[PDF file]: Portable Document Format.
+
+- link:../manual.txt[text file]
diff --git a/moon-abe/pbc-0.5.14/doc/internal.txt b/moon-abe/pbc-0.5.14/doc/internal.txt
new file mode 100644
index 00000000..b2f217e3
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/internal.txt
@@ -0,0 +1,428 @@
+== PBC internals ==
+
+The source code is organized by subdirectories:
+
+*`include`*: Headers describing the official API. Headers in other places
+are for internal use only.
+
+*`arith`*: Finite fields: modular arithmetic, polynomial rings, and polynomial
+rings modulo a polynomial. Finite fields of low characteristic are unsupported.
+
+*`ecc`*: Elliptic curve generation, elliptic curve groups and pairings. One
+source file is dedicated to each type of pairing, containing specialized
+optimizations. Some of the code requires arbitrary precision complex numbers,
+which also live here but should be moved elsewhere one day.
+
+*`misc`*: Dynamic arrays, symbol tables, benchmarking, logging, debugging,
+other utilities.
+
+*`gen`*: Programs that generate pairing parameters and list Hilbert
+polynomials. These were used to prepare the samples in the `param` directory.
+
+*`example`*: Example programs showing how to use the library.
+
+*`guru`*: Tests, experimental code.
+
+=== Groups, rings, fields ===
+
+Algebraic structures are represented in the +field_t+ data type, which mostly
+contains pointers to functions written to perform operations such as addition
+and multiplication in that particular group, ring or field:
+
+  struct field_s {
+    ...
+    void (*init)(element_ptr);
+    void (*clear)(element_ptr);
+    ...
+    void (*add)(element_ptr, element_ptr, element_ptr);
+    void (*sub)(element_ptr, element_ptr, element_ptr);
+    void (*mul)(element_ptr, element_ptr, element_ptr);
+    ...
+  };
+  typedef struct field_s *field_ptr;
+  typedef struct field_s field_t[1];
+
+The name +algebraic_structure_t+ is arguably more accurate, but far too
+cumbersome.  It may help if one views groups and rings as handicapped fields.
+
+The last two lines of the above code excerpt show how GMP and PBC define data
+types: they are arrays of length one so that when a variable is
+declared, space is automatically allocated for it on the stack.
+Yet when used as a argument to a function, a pointer is passed, thus there is
+no need to explicitly allocate and deallocate memory, nor reference and
+dereference variables.
+
+Each +element_t+ contains a field named +field+ to such a +field_t+ variable.
+The only other field is +data+, which stores any data needed for the
+implementation of the particular algebraic structure the element resides in.
+
+  struct element_s {
+    struct field_s *field;
+    void *data;
+  };
+
+When an +element_t+ variable is initialized, +field+ is set appropriately, and
+then the initialization specific to that field is called to complete the
+initialization. Here, a line of code is worth a thousand words:
+
+  void element_init(element_t e, field_ptr f) {
+    e->field = f;
+    f->init(e);
+  }
+
+Thus during a call to one of the `element_` functions, the +field+ pointer is
+followed then the appropriate routine is executed. For example, modular addition
+results when the input element is an element of a finite field, while
+polynomial addition is performed for elements of a polynomial ring and so on.
+
+  void element_add(element_t n, element_t a, element_t b) {
+    n->field->add(n, a, b);
+  }
+
+My design may seem dangerous because if a programmer inadvertently attempts
+to add a polynomial and a point on an elliptic curve, say, the code
+will compile without warnings since they have the same data type.
+
+However I settled on having a catch-all ``glorified +void *+'' +element_t+
+because I wanted to
+
+- extend a field an arbitrary number of times (though in practice, currently I
+  only need to extend a field twice at most),
+- switch fields easily, so for example a program that benchmarks addition in
+  polynomial rings can be trivially modified to benchmark addition in a group,
+  and
+- interchange different implementations of the same algebraic structure, for
+  example, compare Montgomery representation versus a naive implementation of
+  integer modulo rings.
+
+Additionally, defining `PBC_DEBUG` catches many type mismatches.
+
+In mathematics, groups, rings and fields should be distinguished, but for
+implmentation, it is simplest lump them together under the same heading.
+In any event, distinct data types may lead to a false sense of security.
+Fields of prime order with different moduli would still fall under the same
+data type, with unpleasant results if their elements are mistakenly mixed.
+
+I have vague plans to add flags to +field_t+ describing the capabilities of a
+particular +field_t+.  These flags would be set during initialization, and
+would indicate for example whether one can invert every nonzero element,
+whether there are one or two operations (that is, group versus ring), whether
+the field is an integer mod ring, polynomial ring, or polynomial mod ring, and
+so on. Once in place, more runtime checks can be performed to avoid illegal
+inversion and similar problems.
+
+Another option is to introduce data types for each of the four pairing-related
+algebraic structures, namely G1, G2, GT and Zr, as these are the only ones
+needed for implementing pairing-based cryptosystems.
+
+An alternative was to simply use +void *+ instead of +element_t+ and require
+the programmer to pass the field as a parameter, e.g. +element_add(a, b, c,
+F_13)+, but I decided the added annoyance of having to type this extra variable
+every time negated any benefits, such as obviating the need for the
++field+ pointer in +struct element_s+, even if one ignores
+the more serious problem that runtime type checking is considerably harder, if
+not impossible.
+
+I suppose one could write a preprocessor to convert one type of notation
+to the other, but I would like the code to be standard C.  (On the other hand,
+as Hovav Shacham suggested, it may be nice to eventually have a converter that
+takes human-friendly infix operator expressions like `a = (b + c) *
+d` and outputs the assembly-like `element_` equivalents.)
+
+=== Internal randomness ===
+
+Some algorithms require a quadratic nonresidue in a given field. These
+are computed lazily: The first time a quadratic nonresidue is requested, one is
+generated at random, using the same source of random bits as other PBC random
+functions. [Which reminds me, should I get rid of the +nqr+ field and instead
+have it as part of the +data+ field in struct field_s?]
+
+In `fieldquadratic.c`, a quadratic field extension is constructed with a square
+root of this randomly generated quadratic nonresidue in the base field.  Thus
+for a nondeterminstic source of random bits, the same field may be constructed
+differently on different runs.
+
+To construct the same field the same way every time, one must record the
+quadratic nonresidue generated from one run, and call `field_set_nqr()` every
+time this particular construction of a quadratic field extension is desired.
+Another use for this function is to save time by setting the quadratic
+nonresidue to some precomputed value.
+
+Similarly, for higher degree extensions, a random irreducible polynomial
+may be chosen to construct it, but this must be recorded if the same
+construction is later required.
+
+This happens behind the scenes in PBC.
+
+=== Type A internals ===
+
+Type A pairings are constructed on the curve y^2^ = x^3^ + x over the field F_q
+for some prime q = 3 mod 4.
+Both G1 and G2 are the group of points E(F_q), so this
+pairing is symmetric.  It turns out #E(F_q) = q + 1 and
+#E(F_q^2^) = (q + 1)^2^. Thus the embedding degree k is 2,
+and hence GT is a subgroup of F_q^2.  The order r is some prime
+factor of q + 1.
+
+Write q + 1 = r * h. For efficiency, r is picked to be a Solinas prime,
+that is, r has the form 2^a^ +- 2^b^ +- 1 for some integers 0 < b < a.
+
+Also, we choose q = -1 mod 12 so F_q^2^ can be implemented as F_q[i]
+(where i = sqrt(-1)) and since q = -1 mod 3, cube roots in F_q
+are easy to compute. This latter feature may be removed because I have
+not found a use for it yet (in which case we only need q = -1 mod 4).
+
++a_param+ struct fields:
+
+  exp2, exp1, sign1, sign0, r:
+    r = 2^exp2 + sign1 * 2^exp1 + sign0 * 1 (Solinas prime)
+  q, h:
+    r * h = q + 1
+    q is a prime, h is a multiple of 12 (thus q = -1 mod 12)
+
+Type A1 uses the same equation, but have different fields since the library
+is given r and cannot choose it.
+
++a1_param+ struct fields:
+
+  p, n, l:
+    p + 1 = n * l
+    p is prime, same as the q in a_param, n is the order of the group.
+
+=== Type B internals ===
+
+Unimplemented. Similar to type A. The curve y^2^ = x^3^ + 1 over the field F_q
+for some prime q = 2 mod 3, which implies cube roots in F_q are easy to
+compute, though we can achieve this for type A pairings by constraining q
+appropriately. I recommend requiring q = 3 mod 4 as well, so that -1 is
+a quadratic nonresidue.
+
+The lack of an x term simplifies some routines such as point doubling.
+
+It turns out we must choose between symmetry or efficiency due to the nature of
+a certain optimization.
+
+=== Type C internals ===
+
+Unimplemented. The supersingular curves y^2^ = x^3^ + 2x + 1 and
+y^2^ = x^3^ + 2x - 1 over a field of characteristic 3. Discussed at length
+by Boneh, Lynn, and Shacham, "Short signatures from the Weil pairing".
+Many optimizations can be applied to speed up these pairings; see
+Barreto et al., "Efficient algorithms for pairing-based cryptosystems", but
+sadly, an attack due to Coppersmith makes these curves less attractive.
+
+=== Type D internals ===
+
+These are ordinary curves of with embedding degree 6, whose orders are prime
+or a prime multiplied by a small constant.
+
+A type D curve is defined over some field F_q and has order h * r where
+r is a prime and h is a small constant. Over the field F_q^6^ its order is
+a multiple of r^2^.
+
+Typically the order of the curve E is around 170 bits, as is F_q, the base
+field, thus q^k^ is around the 1024-bit mark which is commonly considered
+good enough.
+
++d_param+ struct fields:
+
+  q   F_q is the base field
+  n   # of points in E(F_q)
+  r   large prime dividing n
+  h   n = h * r
+  a   E: y^2 = x^3 + ax + b
+  b
+  nk  # of points in E(F_q^k)
+  hk  nk = hk * r * r
+  coeff0 coefficients of a monic cubic irreducible over F_q
+  coeff1
+  coeff2
+  nqr quadratic nonresidue in F_q
+
+These were discovered by Miyaji, Nakabayashi and Takano,
+"New explicit conditions of elliptic curve traces for FR-reduction".
+
+=== Type E Internals ===
+
+The CM (Complex Multiplication) method of constructing elliptic curves
+starts with the Diophantine equation
+
+    DV^2 = 4q - t^2
+
+If t = 2 and q = D r^2^ h^2^ + 1 for some prime r (which we choose to
+be a Solinas prime) and some integer h, we find that this equation is easily
+solved with V = 2rh.
+
+Thus it is easy to find a curve (over the field F_q) with order q - 1.
+Note r^2^ divides q - 1, thus we have an embedding degree of 1.
+
+Hence all computations necessary for the pairing can be done in F_q alone.
+There is never any need to extend F_q.
+
+As q is typically 1024 bits, group elements take a lot of space to represent.
+Moreover, many optimizations do not apply to this type, resulting in a slower
+pairing.
+
++e_param+ struct fields:
+
+  exp2, exp1, sign1, sign0, r:
+    r = 2^exp2 + sign1 * 2^exp1 + sign0 * 1 (Solinas prime)
+  q, h
+    q = h r^2 + 1 where r is prime, and h is 28 times a perfect square
+  a, b
+    E: y^2 = x^3 + ax + b
+
+=== Type F internals ===
+
+Using carefully crafted polynomials, k = 12 pairings can be constructed.
+Only 160 bits are needed to represent elements of one group, and 320 bits
+for the other.
+
+Also, embedding degree k = 12 allows higher security short signatures.
+(k = 6 curves cannot
+be used to scale security from 160-bits to say 256-bits because finite
+field attacks are subexponential.)
+
++f_param+ struct fields:
+
+  q:
+    The curve is defined over Fq
+  r:
+    The order of the curve.
+  b:
+    E: y^2= x^3 + b
+  beta:
+    A quadratic nonresidue in Fq: used in quadratic extension.
+  alpha0, alpha1:
+    x^6 + alpha0 + alpha1 sqrt(beta) is irreducible: used in sextic extension.
+
+Discovered by Barreto and Naehrig, "Pairing-friendly elliptic curves of prime order".
+
+=== Type G Internals ===
+
+Another construction based on the CM method.
+
++g_param+ struct fields:
+
+  q, n, h, r:
+    h * r = n is the order of E(F_q)
+  a, b:
+    E: y^2 = x^3 + ax + b
+  nk:
+    #E(F_q^10)
+  hk:
+    hk * r^2 = nk
+  coeff:
+    array of coefficients of polynomial used for quintic extension.
+  nqr:
+    a quadratic nonresidue
+
++g_param+ struct fields:
+
+Discovered by Freeman, "Constructing pairing-friendly elliptic curves with embedding degree 10."
+
+=== Type I Internals ===
+
+Type I pairings is symmetric, constructed on a supersingular curve
+y^2^ = x^3^ - x + 1 over a ternary extension field F_{3^m^}.
+The embedding degree k is 6.
+Both G1 and G2 are the group of points E(F_{3^m^}).
+GT is a subgroup of F_{3^6*m^}. The group order is a prime number.
+
+parameters:
+
+  m, t:
+    The ternary extension field is F(3)[x]/(x^m^ + x^t^ + 2).
+  n:
+    the order of G1
+  n2:
+    n * n2 = number of points in E(F_{3^m^})
+
+Introduced by Barreto et al, "Efficient Pairing Computation on Supersingular
+Abelian Varieties", Designs, Codes and Cryptography, vol. 42, no. 3, pp. 239-271,
+Mar. 2007.
+
+=== Testing functions ===
+
+For testing, debugging, demonstrations and benchmarks.
+Declared in +pbc_test.h+:
+
+include::gen/test.txt[]
+
+=== Dynamic arrays ===
+
+The +darray_t+ data type manages an array of pointers of type +void \*+,
+allocating more memory when necessary.
+Declared in +pbc_darray.h+.
+
+include::gen/darray.txt[]
+
+=== Symbol tables ===
+
+The +symtab_t+ data type manages symbol tables where the keys are strings of
+type +char \*+ and the values are pointers of type +void \*+.
+
+At present, they are implemented inefficiently using dynamic arrays, but this
+will change if the need arises. They are only used when reading a +pbc_param_t+
+from a string. Declared in +pbc_symtab.h+.
+
+include::gen/symtab.txt[]
+
+=== Religious stances ===
+
+I chose C because:
+
+- GMP, which PBC requires and is also modeled on, is also written in C.
+- PBC is intended to be a low-level portable cryptographic library.  C is the
+  least common denominator. It should not be difficult to wrap PBC for other
+  languages.
+- Despite its drawbacks (I would appreciate operator overloading and
+  genericity, and to a lesser extent garbage collection), I've found few
+  languages I like better.  To quote Rob Pike, C is the desert island language.
+  (I also agree with his statement that OO languages conceptually provide
+  little extra over judicious use of function pointers in C.)
+
+With respect to indentation, I'm migrating the code to follow
+http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml[Google C++
+Style Guide] to avoid having to switch styles all the time.
+The code was originally written using my old style: 4-space indent with 1TBS
+(One True Brace Style).
+
+I'd like to have no library dependencies (except standard C libraries),
+but then I'd have to write a large integer library. Furthermore, I'd have to
+write it in assembly, and then port it.
+
+To avoid this, I use an existing library. I selected GMP because the library's
+focus is on multiprecision arithmetic and nothing else, and it aims to be as
+fast as possible on many platforms.  Another important factor is that GMP is
+released under a free license.
+
+On the other hand, GMP is written to deal with extremely large numbers, while I
+mostly only need integers that are roughly between 160 and 2048 bits. It is
+possible a library specializing in numbers of these sizes would be better for
+PBC.
+
+I'm fond of GMP's method for eliminating the need for the +&amp;+ and +*+
+operators most of the time by declaring a typedef on arrays of size 1.  I try
+to do the same with PBC for consistency, though this trick does have drawbacks.
+
+I would like to have GMP as the only library dependency, though I do not mind
+using other libraries so long as they are optional. For example, one of the
+test programs is much easier to use if compiled with the GNU readline library,
+but by default compiles without it and is still functional.
+
+I dislike the C preprocessor. I like to place platform-specific code in
+separate files and let the build system work out which one to use.  Integer
+constants can be defined with enum instead.  I intend to minimize the number of
++#include+ statements in header files for PBC's internal use as much as
+possible (they should be in the `.c` files instead), and later perhaps even
+remove those annoying +#ifndef+ statements too.
+I grudgingly accept some macros for PBC's debugging features.
+
+I liberally use nested functions, a GNU C extension. I find their expressiveness so indispensable that I'm willing to sacrifice portability for them.
+
+The
+http://www.gnu.org/software/libc/manual/html_node/Reserved-Names.html[GNU libc manual]
+states that data types ending in +_t+ should not be used because they are
+reserved for future additions to C or POSIX.  On the other hand, I want to stay
+consistent with GMP, and ending data types with +_t+ is common practice.
diff --git a/moon-abe/pbc-0.5.14/doc/macros.ad b/moon-abe/pbc-0.5.14/doc/macros.ad
new file mode 100644
index 00000000..0b108e2b
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/macros.ad
@@ -0,0 +1,9 @@
+[miscellaneous]
+newline=\n
+
+[blockdef-passthrough]
+delimiter=^@{4,}$
+subs=none
+
+[replacements]
+sigma=&sigma;
diff --git a/moon-abe/pbc-0.5.14/doc/makeover b/moon-abe/pbc-0.5.14/doc/makeover
new file mode 100644
index 00000000..39b807c1
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/makeover
@@ -0,0 +1,50 @@
+#!/bin/bash
+gawk '
+/<div class="toc">/ {
+    print $0
+    getline #TODO: check this is the <ul> line
+    print $0
+    print "<li><a href=\".\">PBC Library Manual</a></li>"
+    getline
+    while (!match($0, "</div>")) {
+	print $0
+	getline
+    }
+    print "</div>"
+    exit
+}
+' < manual/index.html > toc.tmp
+for a in manual/*.html
+do
+    if [ $a != "manual/index.html" ]
+    then
+#add " - PBC" to titles of all pages
+    sed '/<\/title>/ s/<\/title>/ - PBC&/' -i $a
+    sed '/<body/{n; r toc.tmp
+a <div class="content">
+} ' -i $a
+    sed '/^<\/body/i </div>' -i $a
+    fi
+done
+
+gawk '
+/<div class="book"/ {
+    i = 0
+    for(;;) {
+	getline
+	if (match($0, "<div")) i++;
+	else if (match($0, "</div")) {
+	    i--;
+	    if (i < 0) break;
+	}
+    }
+    sub("</div>","")
+}
+{ print }
+' < manual/index.html | sed '/<body/{n; r toc.tmp
+a <div class="content">
+r index.html
+a </div>
+} ' > tmp.tmp
+mv tmp.tmp manual/index.html
+rm toc.tmp
diff --git a/moon-abe/pbc-0.5.14/doc/miscfns.txt b/moon-abe/pbc-0.5.14/doc/miscfns.txt
new file mode 100644
index 00000000..5ea07a67
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/miscfns.txt
@@ -0,0 +1,43 @@
+== Other functions ==
+
+Random number generation, memory allocation, logging.
+
+[[randomref]]
+=== Random bits ===
+
+The first time PBC is asked to generate a random number,
+the library will try to open the file `/dev/urandom` as a
+source of random bits. If this fails, PBC falls back to a deterministic
+random number generator (which is of course completely useless for
+cryptography).
+
+It is possible to change the file used for random bits. Also, explicitly
+selecting the deterministic random number generator will
+suppress the warning.
+
+On Windows, by default, PBC uses the Microsoft Crypto API to generate random
+bits.
+
+include::gen/pbcrandom.txt[]
+
+=== Custom allocation ===
+
+Like GMP, PBC can be instructed to use custom memory allocation functions.
+This must be done before any memory allocation is performed,
+usually at the beginning of a program before any other PBC functions have
+been called.
+
+Also like GMP, the PBC wrappers around +malloc+
+and +realloc+ will print a message on standard error
+and terminate program execution if the calls fail.
+Replacements for these functions should act similarly.
+
+However, unlike GMP, PBC does not pass the number of bytes previously allocated
+along with the pointer in calls to +realloc+ and
++free+.
+
+include::gen/alloc.txt[]
+
+=== Logging ===
+
+include::gen/log.txt[]
diff --git a/moon-abe/pbc-0.5.14/doc/pairingfns.txt b/moon-abe/pbc-0.5.14/doc/pairingfns.txt
new file mode 100644
index 00000000..4ea4bf13
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/pairingfns.txt
@@ -0,0 +1,69 @@
+== Pairing functions ==
+
+An application should first initialize a pairing object. This causes PBC
+to setup curves, groups and other mathematical miscellany. After that,
+elements can be initialized and manipulated for cryptographic operations.
+
+Parameters for various pairings are included with the PBC library distribution
+in the `param` subdirectory, and some are suitable for cryptographic use. Some
+programs in the `gen` subdirectory may be used to generate parameters (see
+<<bundlechap>>). Also, see the PBC website for many more
+pairing parameters.
+
+Pairings involve three groups of prime order. The PBC library calls them G1,
+G2, and GT, and calls the order r. The pairing is a bilinear map that takes two
+elements as input, one from G1 and one from G2, and outputs an element of GT.
+
+The elements of G2 are at least as long as G1; G1 is guaranteed to be the
+shorter of the two. Sometimes G1 and G2 are the same group (i.e. the pairing
+is symmetric) so their elements can be mixed freely. In this case the
++pairing_is_symmetric+ function returns 1.
+
+Bilinear pairings are stored in the data type +pairing_t+. Functions that
+operate on them start with +pairing_+.
+
+=== Initializing pairings ===
+
+To initialize a pairing from an ASCIIZ string:
+
+  pairing_t pairing;
+  pairing_init_set_str(pairing, s);  // Where s is a char *.
+
+The string 's' holds _pairing parameters_ in a text format. The +param+
+subdirectory contains several examples.
+
+Alternatively, call:
+
+  pairing_t pairing;
+  pairing_init_pbc_param(pairing, param);
+
+where 'param' is an initialized `pbc_param_t` (see <<paramchap>>).
+
+include::gen/pairing_init.txt[]
+
+=== Applying pairings ===
+
+The function `pairing_apply` can be called to apply a bilinear map.  The order
+of the inputs is important. The first, which holds the output, must be from the
+group GT. The second must be from G1, the third from G2, and the fourth must be
+the +pairing_t+ variable that relates them.
+
+In some applications, the programmer may know that many pairings with the same
+G1 input will be computed. If so, preprocessing should be used to avoid
+repeating many calculations saving time in the long run.  A variable of type
++pairing_pp_t+ should be declared, initialized with the fixed G1 element, and
+then used to compute pairings:
+
+  pairing_pp_t pp;
+  pairing_pp_init(pp, x, pairing); // x is some element of G1
+  pairing_pp_apply(r1, y1, pp); // r1 = e(x, y1)
+  pairing_pp_apply(r2, y2, pp); // r2 = e(x, y2)
+  pairing_pp_clear(pp); // don't need pp anymore
+
+Never mix and match G1, G2, and GT groups from different pairings.
+
+include::gen/pairing_apply.txt[]
+
+=== Other pairing functions ===
+
+include::gen/pairing_op.txt[]
diff --git a/moon-abe/pbc-0.5.14/doc/paramfns.txt b/moon-abe/pbc-0.5.14/doc/paramfns.txt
new file mode 100644
index 00000000..74b1abff
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/paramfns.txt
@@ -0,0 +1,37 @@
+[[paramchap]]
+== Param functions ==
+
+Pairings are initialized from _pairing parameters_, which are objects of type
+`pbc_param_t`. Some applications can ignore this data type because
+`pairing_init_set_str()` handles it behind the scenes: it reads a string as a
+`pbc_param_t`, then initializes a pairing with these parameters.
+
+include::gen/param.txt[]
+
+[[paramgenchap]]
+=== Param generation ===
+
+These were used to prepare the sample parameters in the +param+ subdirectory.
+
+We label the pairing families with capital letters roughly in the order of
+discovery, so we can refer to them easily. Type A is fastest. Type D is a good
+choice when elements should be short but is slower. Type F has even shorter
+elements but is slower still. The speed differences are hardware-dependent, and
+also change when preprocessing is used. Type B and C are unimplemented.
+
+The +pbc_cm_t+ data type holds CM parameters that are used to generate type D
+and G curves.
+
+include::gen/cminfo.txt[]
+
+include::gen/aparam.txt[]
+
+include::gen/a1param.txt[]
+
+include::gen/dparam.txt[]
+
+include::gen/eparam.txt[]
+
+include::gen/fparam.txt[]
+
+include::gen/gparam.txt[]
diff --git a/moon-abe/pbc-0.5.14/doc/preface.txt b/moon-abe/pbc-0.5.14/doc/preface.txt
new file mode 100644
index 00000000..ec8a3373
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/preface.txt
@@ -0,0 +1,18 @@
+= PBC Library Manual 0.5.14 =
+Ben Lynn
+2006
+
+== Preface ==
+
+The PBC library is a free portable C library allowing the rapid prototyping of
+pairing-based cryptosystems. It provides an abstract interface to a cyclic
+group with a bilinear pairing, insulating the programmer from mathematical
+details. Knowledge of elliptic curves is optional.
+
+The PBC library is built on top of the GMP library, and the PBC API is strongly
+influenced by the GMP API. Accordingly, this manual tries to imitate the look
+and feel of the GMP manual.
+
+The PBC library homepage: http://crypto.stanford.edu/pbc/[http://crypto.stanford.edu/pbc/]
+
+The GMP library homepage: http://www.swox.com/gmp/[http://www.swox.com/gmp/]
diff --git a/moon-abe/pbc-0.5.14/doc/pretty.css b/moon-abe/pbc-0.5.14/doc/pretty.css
new file mode 100644
index 00000000..69502083
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/pretty.css
@@ -0,0 +1,97 @@
+body {
+    font-size: 90%;
+    font-family: verdana, arial, sans-serif;
+}
+
+tt, code, pre, .type {
+    font-family: andale mono, courier new, courier, monospace;
+    font-size: 90%;
+}
+
+/* Based on http://phrogz.net/CSS/columns3.html */
+div.toc {
+    float: left;
+    margin: 0;
+    padding: 0;
+    padding-top: 0.5em;
+    border: 0;
+    width: 13em;
+
+    background-color: #f9f9f9;
+    margin-right:1em;
+}
+
+div.content {
+    margin: 0;
+    padding: 0;
+
+    /* won't match if font is smaller in toc */
+    border-left: 13em solid #f9f9f9;
+    padding-left: 1em;
+}
+
+div.content:after {
+    content:' ';
+    clear:both;
+    display:block;
+    height:0;
+    overflow:hidden
+}
+
+div.footer {
+    clear:left;
+}
+
+div.toc ul {
+    list-style: none;
+    padding: 0;
+    margin: 0;
+}
+
+div.toc li ul a, li ul span.currentlink
+{
+    font-weight: normal;
+    font-size: 90%;
+    padding-left: 2em;
+}
+
+div.toc a, span.currentlink{
+    display:block;
+    text-decoration: none;
+    padding-left: 0.5em;
+    color: #0000aa;
+}
+
+span.currentlink {
+    text-decoration: none;
+    background-color: #aaaaf9;
+}
+
+div.toc a:visited {
+    color: #0000aa;
+}
+
+div.toc a:hover {
+    background-color: #f9f9aa;
+}
+
+.literallayout {
+    margin: 0;
+    border: 1px solid #aaaaaa;
+    background-color: #f9f9f9;
+    padding: 0.17em;
+    margin: 1em;
+    margin-right: 3em;
+}
+
+h1, h2, h3, h4, h5, h6 {
+    padding-bottom: 0.17em;
+    margin: 0;
+    font-weight: normal;
+    color: black;
+    border-bottom: 1px solid #aaaaaa;
+}
+
+h3, h4, h5, h6 {
+    border-bottom: 0;
+}
diff --git a/moon-abe/pbc-0.5.14/doc/quickstart.txt b/moon-abe/pbc-0.5.14/doc/quickstart.txt
new file mode 100644
index 00000000..2f94e46e
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/quickstart.txt
@@ -0,0 +1,69 @@
+== Installing PBC ==
+
+The PBC library needs http://www.swox.com/gmp/[the GMP library].
+
+This build system has been tested and works on Linux and Mac OS X with a
+fink installation.
+
+  $ ./configure
+  $ make
+  $ make install
+
+On Windows, the configure command requires a couple of options:
+
+  $ ./configure -disable-static -enable-shared
+
+By default the library is installed in `/usr/local/lib`.  On some systems, this
+may not be in the library path. One way to fix this is to edit
+`/etc/ld.so.conf` and run `ldconfig`.
+
+=== Simple Makefile ===
+
+For speed and simplicity, I use `simple.make` during development.
+Naturally it is less portable.
+
+  $ make -f simple.make
+
+PBC uses some GNU C extensions such as nested functions.
+
+[[pbcintro]]
+=== Quick start ===
+
+We shall use the following notation. For our purposes, the pairing is a
+bilinear map from two cyclic groups, G1 and G2 to a third group GT, where each
+group has prime order r.
+
+Run `pbc/pbc` and type:
+
+  g := rnd(G1);
+  g;
+
+The first line generates a random element g of the group G1,
+while the second prints out the value of g. (The syntax was influenced
+by `bc`, an arbitrary precision calculator.)
+Next, enter:
+
+  h := rnd(G2);
+  h;
+
+This assigns h to a random element of the group G2. Actually, the default
+pairing `pbc` uses is symmetric so G1 and G2 are in fact the same group, but in
+general they are distinct. To compute the pairing applied to g and h, type:
+
+  pairing(g,h);
+
+The order of both g and h is r. Let's generate two random numbers between
+1 and r:
+
+  a := rnd(Zr);
+  b := rnd(Zr);
+
+By bilinearity, the resulting output of both of these lines should be
+identical:
+
+  pairing(g^a,h^b);
+  pairing(g,h)^(a*b);
+
+This program has <<pbcref, other features>> but the commands shown here should
+be enough to quickly and interactively experiment with many pairing-based
+cryptosystems using real numbers.
diff --git a/moon-abe/pbc-0.5.14/doc/security.txt b/moon-abe/pbc-0.5.14/doc/security.txt
new file mode 100644
index 00000000..c59cf4ba
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/security.txt
@@ -0,0 +1,45 @@
+== Security issues ==
+
+Potential problems for the paranoid.
+
+*Truncated hashes*
+
+For points on an elliptic curve over the base field, +element_from_hash()+
+will truncate the input hash until it can represent an x-coordinate in that
+field. (PBC then computes a corresponding y-coordinate.) Ideally the hash
+length should be smaller than size of the base field and also the size of the
+elliptic curve group.
+
+Hashing to elements in field extensions does not take advantage of the fact
+that the extension has more elements than the base field. I intend to rewrite
+the code so that for a degree n extension code, PBC splits the hash into n
+parts and determine each polynomial coefficient from one ofthe pieces. At the
+moment every coefficient is the same and depends on the whole hash.
+
+This is harmless for the base field, because all the pairing types implemented
+so far use an integer mod ring as the base field, rather than an extension of
+some low characteristic field.
+
+*Zeroed memory*
+
+Unlike OpenSSL, there are no functions to zero memory locations used in
+sensitive computations. To some extent, one can use +element_random()+ to
+overwrite data.
+
+*PRNG determinism*
+
+On platforms without `/dev/urandom` PBC falls back on a deterministic
+pseudo-random number generator, except on Windows where it attempts to
+use the Microsoft Crypto API.
+
+Also, `/dev/urandom` differs from `/dev/random`. A quote from its manpage:
+
+____
+A  read  from  the  /dev/urandom device will not block waiting for more
+entropy.  As a result, if  there  is  not  sufficient  entropy  in  the
+entropy  pool,  the  returned  values are theoretically vulnerable to a
+cryptographic attack on the algorithms used by the  driver.   Knowledge
+of how to do this is not available in the current non-classified literature,
+but it is theoretically possible that such an attack may  exist.
+If this is a concern in your application, use /dev/random instead.
+____
diff --git a/moon-abe/pbc-0.5.14/doc/sigex.txt b/moon-abe/pbc-0.5.14/doc/sigex.txt
new file mode 100644
index 00000000..dcfc8d5e
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/doc/sigex.txt
@@ -0,0 +1,155 @@
+== Tutorial ==
+
+This chapter walks through how one might implement the
+Boneh-Lynn-Shacham (BLS) signature scheme using the PBC library.
+It is based on the file `example/bls.c`.
+
+We have three groups 'G1', 'G2', 'GT' of prime order 'r', and a bilinear map
+'e' that takes an element from 'G1' and an element from 'G2', and outputs an
+element of 'GT'. We publish these along with the system parameter 'g', which is
+a randomly chosen element of 'G2'.
+
+Alice wishes to sign a message.  She generates her public and private keys as
+follows.  Her private key is a random element 'x' of 'Zr', and her corresponding
+public key is 'g'^'x'^.
+
+To sign a message, Alice hashes the message to some element
+'h' of 'G1', and then outputs the signature 'h'^'x'^.
+
+To verify a signature sigma, Bob checks that
+'e'('h','g'^'x'^) = 'e'(sigma, 'g').
+
+We now translate the above to C code using the PBC library.
+
+=== BLS signatures ===
+
+First we include `pbc/pbc.h`:
+
+  #include <pbc.h>
+
+Next we initialize a pairing:
+
+  pairing_t pairing;
+  char param[1024];
+  size_t count = fread(param, 1, 1024, stdin);
+  if (!count) pbc_die("input error");
+  pairing_init_set_buf(pairing, param, count);
+
+Later we give pairing parameters to our program on standard input. Any file in
+the `param` subdirectory will suffice, for example:
+
+ $ bls < param/a.param
+
+We shall need several +element_t+ variables to hold the system parameters, keys
+and other quantities. We declare them and initialize them,
+....
+element_t g, h;
+element_t public_key, secret_key;
+element_t sig;
+element_t temp1, temp2;
+
+element_init_G2(g, pairing);
+element_init_G2(public_key, pairing);
+element_init_G1(h, pairing);
+element_init_G1(sig, pairing);
+element_init_GT(temp1, pairing);
+element_init_GT(temp2, pairing);
+element_init_Zr(secret_key, pairing);
+....
+generate system parameters,
+
+    element_random(g);
+
+generate a private key,
+
+    element_random(secret_key);
+
+and the corresponding public key.
+
+    element_pow_zn(public_key, g, secret_key);
+
+When given a message to sign, we first compute its hash, using some standard
+hash algorithm.  Many libraries can do this, and this operation does not
+involve pairings, so PBC does not provide functions for this step. For this
+example, and our message has already been hashed, possibly using another
+library.
+
+Say the message hash is "ABCDEF" (a 48-bit hash).  We map these bytes to an
+element h of G1,
+
+    element_from_hash(h, "ABCDEF", 6);
+
+then sign it:
+
+    element_pow_zn(sig, h, secret_key);
+
+To verify this signature, we compare the
+outputs of the pairing applied to the signature and system parameter,
+and the pairing applied to the message hash and public key.
+If the pairing outputs match then the signature is valid.
+
+....
+pairing_apply(temp1, sig, g, pairing);
+pairing_apply(temp2, h, public_key, pairing);
+if (!element_cmp(temp1, temp2)) {
+    printf("signature verifies\n");
+} else {
+    printf("signature does not verify\n");
+}
+....
+
+=== Import/export ===
+
+To be useful, at some stage the signature must be converted
+to bytes for storage or transmission:
+
+    int n = pairing_length_in_bytes_compressed_G1(pairing);
+    // Alternatively:
+    // int n = element_length_in_bytes_compressed(sig);
+    unsigned char *data = malloc(n);
+    element_to_bytes_compressed(data, sig);
+
+On the other end, the signature must be decompressed:
+
+    element_from_bytes_compressed(sig, data);
+
+Eliding +_compressed+ in the above code
+will also work but the buffer 'data' will be roughly twice as large.
+
+We can save more space by using the 'x'-coordinate of the signature only
+
+    int n = pairing_length_in_bytes_x_only_G1(pairing);
+    // Alternative:
+    //   int n = element_length_in_bytes_x_only(sig);
+    unsigned char *data = malloc(n);
+    element_to_bytes_compressed(data, sig);
+
+but then there is a complication during verification since two different
+points have the same 'x'-coordinate. One way to solve this problem is to
+guess one point and try to verify. If that fails, we try the other.
+It can be shown that the pairing outputs of the two points are inverses
+of each other, avoiding the need to compute a pairing the second time.
+(In fact, there are even better ways to handle this.)
+....
+int n = pairing_length_in_bytes_x_only_G1(pairing);
+//int n = element_length_in_bytes_x_only(sig);
+unsigned char *data = malloc(n);
+
+element_to_bytes_x_only(data, sig);
+
+element_from_bytes_x_only(sig, data)
+
+pairing_apply(temp1, sig, g, pairing);
+pairing_apply(temp2, h, public_key, pairing);
+
+if (!element_cmp(temp1, temp2)) {
+    printf("signature verifies on first guess\n");
+} else {
+    element_invert(temp1, temp1);
+    if (!element_cmp(temp1, temp2)) {
+	printf("signature verifies on second guess\n");
+    } else {
+	printf("signature does not verify\n");
+    }
+}
+....