ibe: Implementation of the Boneh-Boyen identity-based-encryption scheme.
(Joint work with David Wu & Ankur Taly).
This patch adds a package that defines interfaces for
identity-based-encryption (IBE) and provides an implementation of those
interfaces using the Boneh-Boyen (BB1) scheme described in "Efficient
Selective Identity-Based Encryption Without Random Oracles" by Dan Boneh
& Xavier Boyen (http://crypto.stanford.edu/~dabo/papers/bbibe.pdf).
Specifically, the operations defined in Section 4.3 of that paper.
This code was originally implemented by David Wu, with some
restructuring and benchmarks added by the author of this patch.
Benchmark results on my 2015 MacBook Pro with a 3.1GHz Intel Core i7:
BenchmarkExtractBB1-4 100 20243772 ns/op (20ms)
BenchmarkEncryptBB-4 100 23291797 ns/op (23ms)
BenchmarkDecryptBB-4 30 38485444 ns/op (38ms)
Initial experimentation by David Wu suggests that using a more efficient
(C-based) implementation of the Naehric-Niederhagen-Schwabe pairing
library can improve performance by a factor of 10x. Incorporating that
and other missing features (like Marshaling/Unmarshaling functions to
help persist the PrivateKey and Params) is left for a future commit.
the Boneh-Boyen
Change-Id: I2ee4a55cfcd742d963ff3e79f717c188892b247c
diff --git a/ibe/.godepcop b/ibe/.godepcop
new file mode 100644
index 0000000..e1e57c2
--- /dev/null
+++ b/ibe/.godepcop
@@ -0,0 +1,3 @@
+<godepcop>
+ <pkg allow="golang.org/x/crypto/bn256"/>
+</godepcop>
diff --git a/ibe/bb1.go b/ibe/bb1.go
new file mode 100644
index 0000000..12ad391
--- /dev/null
+++ b/ibe/bb1.go
@@ -0,0 +1,203 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This file defines an implementation of the IBE interfaces using the
+// Boneh-Boyen scheme. The paper defining this algorithm (see comments for
+// SetupBB1) uses multiplicative groups while the bn256 package used in the
+// implementation here defines an additive group. The comments follow the
+// notation in the paper while the code uses the bn256 library. For example,
+// g^i corresponds to G1.ScalarBaseMult(i).
+
+package ibe
+
+import (
+ "crypto/rand"
+ "crypto/sha256"
+ "errors"
+ "fmt"
+ "golang.org/x/crypto/bn256"
+ "math/big"
+)
+
+var errBadCiphertext = errors.New("invalid ciphertext")
+
+const marshaledG1Size = 64
+
+// Setup creates an ibe.Master based on the BB1 scheme described in "Efficient
+// Selective Identity-Based Encryption Without Random Oracles" by Dan Boneh and
+// Xavier Boyen (http://crypto.stanford.edu/~dabo/papers/bbibe.pdf).
+//
+// Specifically, Section 4.3 of the paper is implemented.
+func SetupBB1() (Master, error) {
+ var (
+ m = &bb1master{params: new(bb1params)}
+ pk = m.params // shorthand
+ g0Hat = &(m.g0Hat) // shorthand
+ )
+
+ // Set generators
+ pk.g.ScalarBaseMult(big.NewInt(1))
+ pk.gHat.ScalarBaseMult(big.NewInt(1))
+
+ // Pick a random alpha and set g1 & g1Hat
+ alpha, err := random()
+ if err != nil {
+ return nil, err
+ }
+ pk.g1.ScalarBaseMult(alpha)
+ pk.g1Hat.ScalarBaseMult(alpha)
+
+ // Pick a random delta and set h and hHat
+ delta, err := random()
+ if err != nil {
+ return nil, err
+ }
+ pk.h.ScalarBaseMult(delta)
+ pk.hHat.ScalarBaseMult(delta)
+
+ // Pick a random beta and set g0Hat.
+ beta, err := random()
+ if err != nil {
+ return nil, err
+ }
+ alphabeta := new(big.Int).Mul(alpha, beta)
+ g0Hat.ScalarBaseMult(alphabeta.Mod(alphabeta, bn256.Order)) // g0Hat = gHat^*(alpha*beta)
+
+ pk.v = bn256.Pair(&pk.g, g0Hat)
+ return m, nil
+}
+
+type bb1master struct {
+ params *bb1params // Public params
+ g0Hat bn256.G2 // Master key
+}
+
+func (m *bb1master) Extract(id string) (PrivateKey, error) {
+ r, err := random()
+ if err != nil {
+ return nil, err
+ }
+
+ var (
+ ret = &bb1PrivateKey{params: m.params}
+ // A bunch of shorthands
+ d0 = new(bn256.G2)
+ g1Hat = &(m.params.g1Hat)
+ g0Hat = &(m.g0Hat)
+ hHat = &(m.params.hHat)
+ i = id2bignum(id)
+ )
+ // ret.d0 = g0Hat * (g1Hat^i * hHat)^r
+ d0.ScalarMult(g1Hat, i)
+ d0.Add(d0, hHat)
+ d0.ScalarMult(d0, r)
+ ret.d0.Add(d0, g0Hat)
+ ret.d1.ScalarBaseMult(r)
+ return ret, nil
+}
+
+func (m *bb1master) Params() Params { return m.params }
+
+type bb1params struct {
+ g, g1, h bn256.G1
+ gHat, g1Hat, hHat bn256.G2
+ v *bn256.GT
+}
+
+func (e *bb1params) Encrypt(id string, m *Plaintext, C *Ciphertext) error {
+ s, err := random()
+ if err != nil {
+ return err
+ }
+
+ var (
+ vs bn256.GT
+ tmpG1 bn256.G1
+ // Ciphertext C = (A, B, C1)
+ A = C[0:len(m)]
+ B = C[len(m) : len(m)+marshaledG1Size]
+ C1 = C[len(m)+marshaledG1Size:]
+ )
+ vs.ScalarMult(e.v, s)
+ pad := sha256.Sum256(vs.Marshal())
+ // A = m ⊕ H(v^s)
+ for i := range m {
+ A[i] = m[i] ^ pad[i]
+ }
+ // B = g^s
+ if err := marshalG1(B, tmpG1.ScalarBaseMult(s)); err != nil {
+ return err
+ }
+ // C1 = (g1^H(id) h)^s
+ tmpG1.ScalarMult(&e.g1, id2bignum(id))
+ tmpG1.Add(&tmpG1, &e.h)
+ tmpG1.ScalarMult(&tmpG1, s)
+ if err := marshalG1(C1, &tmpG1); err != nil {
+ return err
+ }
+ return nil
+}
+
+type bb1PrivateKey struct {
+ params *bb1params // public parameters
+ d0, d1 bn256.G2
+}
+
+func (k *bb1PrivateKey) Decrypt(C *Ciphertext, m *Plaintext) error {
+ var (
+ A = C[0:len(m)]
+ B, C1 bn256.G1
+ )
+ if _, ok := B.Unmarshal(C[len(m) : len(m)+marshaledG1Size]); !ok {
+ return errBadCiphertext
+ }
+ if _, ok := C1.Unmarshal(C[len(m)+marshaledG1Size:]); !ok {
+ return errBadCiphertext
+ }
+ // M = A ⊕ H(e(B, d0)/e(C1,d1))
+ var (
+ numerator = bn256.Pair(&B, &k.d0)
+ denominator = bn256.Pair(&C1, &k.d1)
+ hash = sha256.Sum256(numerator.Add(numerator, denominator.Neg(denominator)).Marshal())
+ )
+ for i := range m {
+ m[i] = A[i] ^ hash[i]
+ }
+ return nil
+}
+
+// random returns a positive integer in the range [1, bn256.Order)
+// (denoted by Zp in http://crypto.stanford.edu/~dabo/papers/bbibe.pdf).
+//
+// The paper refers to random numbers drawn from Zp*. From a theoretical
+// perspective, the uniform distribution over Zp and Zp* start within a
+// statistical distance of 1/p (where p=bn256.Order is a ~256bit prime). Thus,
+// drawing uniformly from Zp is no different from Zp*.
+func random() (*big.Int, error) {
+ for {
+ k, err := rand.Int(rand.Reader, bn256.Order)
+ if err != nil {
+ return nil, err
+ }
+ if k.Sign() > 0 {
+ return k, nil
+ }
+ }
+}
+
+func id2bignum(id string) *big.Int {
+ h := sha256.Sum256([]byte(id))
+ k := new(big.Int).SetBytes(h[:])
+ return k.Mod(k, bn256.Order)
+}
+
+// marshalG1 writes the marshaled form of g into dst.
+func marshalG1(dst []byte, g *bn256.G1) error {
+ src := g.Marshal()
+ if len(src) != len(dst) {
+ return fmt.Errorf("bn256.G1.Marshal returned a %d byte slice, expected %d: the BB1 IBE implementation is likely broken", len(src), len(dst))
+ }
+ copy(dst, src)
+ return nil
+}
diff --git a/ibe/bb1_test.go b/ibe/bb1_test.go
new file mode 100644
index 0000000..cbd5854
--- /dev/null
+++ b/ibe/bb1_test.go
@@ -0,0 +1,124 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package ibe
+
+import (
+ "bytes"
+ "crypto/rand"
+ "reflect"
+ "testing"
+)
+
+func TestBB1Correctness(t *testing.T) {
+ master, err := SetupBB1()
+ if err != nil {
+ t.Fatal(err)
+ }
+ const (
+ alice = "alice"
+ bob = "bob"
+ )
+ // Extract
+ aliceSK, err := master.Extract(alice)
+ if err != nil {
+ t.Fatal(err)
+ }
+ aliceSK2, err := master.Extract(alice)
+ if err != nil {
+ t.Fatal(err)
+ } else if reflect.DeepEqual(aliceSK, aliceSK2) {
+ t.Fatal("Two Extract operations yielded the same PrivateKey!")
+ }
+ bobSK, err := master.Extract(bob)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ // Encrypt
+ var (
+ m Plaintext
+ C, C2 Ciphertext
+ )
+ if n := copy(m[:], []byte("AThirtyTwoBytePieceOfTextThisIs!")); n != len(m) {
+ t.Fatalf("Test string must be %d bytes, not %d", len(m), n)
+ }
+ if err := master.Params().Encrypt(alice, &m, &C); err != nil {
+ t.Fatal(err)
+ }
+ if err := master.Params().Encrypt(alice, &m, &C2); err != nil {
+ t.Fatal(err)
+ }
+ if bytes.Equal(C[:], C2[:]) {
+ t.Errorf("Repeated encryptions of the identical plaintext should not produce identical ciphertext")
+ }
+
+ // Decrypt
+ decrypt := func(sk PrivateKey) (*Plaintext, error) {
+ var ret Plaintext
+ if err := sk.Decrypt(&C, &ret); err != nil {
+ return nil, err
+ }
+ return &ret, nil
+ }
+ if decrypted, err := decrypt(aliceSK); err != nil || !bytes.Equal(decrypted[:], m[:]) {
+ t.Errorf("Got (%v, %v), want (%v, nil)", decrypted, err, m[:])
+ }
+ if decrypted, err := decrypt(aliceSK2); err != nil || !bytes.Equal(decrypted[:], m[:]) {
+ t.Errorf("Got (%v, %v), want (%v, nil)", decrypted, err, m[:])
+ }
+ if decrypted, _ := decrypt(bobSK); bytes.Equal(decrypted[:], m[:]) {
+ t.Errorf("Decrypted message with a different PrivateKey")
+ }
+}
+
+var (
+ bb1 Master
+ bb1SK PrivateKey
+ benchmarkm Plaintext
+ bb1C Ciphertext
+)
+
+func init() {
+ var err error
+ if bb1, err = SetupBB1(); err != nil {
+ panic(err)
+ }
+ if bb1SK, err = bb1.Extract("alice"); err != nil {
+ panic(err)
+ }
+ if _, err := rand.Read(benchmarkm[:]); err != nil {
+ panic(err)
+ }
+ if err := bb1.Params().Encrypt("alice", &benchmarkm, &bb1C); err != nil {
+ panic(err)
+ }
+}
+
+func BenchmarkExtractBB1(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ if _, err := bb1.Extract("alice"); err != nil {
+ b.Fatal(err)
+ }
+ }
+}
+
+func BenchmarkEncryptBB(b *testing.B) {
+ p := bb1.Params()
+ var C Ciphertext
+ for i := 0; i < b.N; i++ {
+ if err := p.Encrypt("alice", &benchmarkm, &C); err != nil {
+ b.Fatal(err)
+ }
+ }
+}
+
+func BenchmarkDecryptBB(b *testing.B) {
+ var m Plaintext
+ for i := 0; i < b.N; i++ {
+ if err := bb1SK.Decrypt(&bb1C, &m); err != nil {
+ b.Fatal(err)
+ }
+ }
+}
diff --git a/ibe/ibe.go b/ibe/ibe.go
new file mode 100644
index 0000000..6045cb1
--- /dev/null
+++ b/ibe/ibe.go
@@ -0,0 +1,60 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package ibe implements identity-based encryption.
+//
+// This package defines interfaces for identity-based-encryption (IBE) and
+// provides specific implementations of those interfaces. The idea was first
+// proposed in 1984 by Adi Shamir in "Identity-Based Cryptosystems And
+// Signature Schemes"
+// (http://discovery.csc.ncsu.edu/Courses/csc774-S08/reading-assignments/shamir84.pdf)
+// and a construction based on the Bilinear Diffie-Hellman problem was
+// described in "Identity-Based Encryption from the Weil Paring" by Dan Boneh
+// and Matthew Franklin (http://crypto.stanford.edu/~dabo/papers/bfibe.pdf).
+//
+// As described in the those papers, an IBE scheme consists of four operations:
+//
+// (1) Setup: Which generates global system parameters and a master key.
+//
+// (2) Extract: Uses the master key and global system parameters to generate
+// the private key corresponding to an arbitrary identity string.
+//
+// (3) Encrypt: Uses the global system parameters to encrypt messages for a
+// particular identity.
+//
+// (4) Decrypt: Uses the private key (and global system parameters) to decrypt
+// messages. To be clear, the private key here is for the identity (sometimes
+// refered to as the "identity key" in literature) and not the master secret.
+//
+// This package defines 3 interfaces: one for Extract, one for Encrypt and one
+// for Decrypt and provides Setup function implementations for different IBE
+// systems (at the time of this writing, only for the Boneh-Boyen scheme).
+package ibe
+
+// Plaintext represents a plaintext message that can be encrypted.
+//
+// Typical use would be for plaintext to be a key used to encrypt arbitrary
+// messages.
+type Plaintext [32]byte
+
+// Ciphertext represents an encrypted plaintext.
+type Ciphertext [160]byte
+
+// Master is the interface used to extract private keys for arbitrary identities.
+type Master interface {
+ Extract(id string) (PrivateKey, error)
+ Params() Params
+}
+
+// Params represents the global system parameters that are used to encrypt
+// messages for a particular identity.
+type Params interface {
+ // Encrypt encrypts m into C for the identity id.
+ Encrypt(id string, m *Plaintext, C *Ciphertext) error
+}
+
+// PrivateKey is the interface used to decrypt encrypted messages.
+type PrivateKey interface {
+ Decrypt(C *Ciphertext, m *Plaintext) error
+}
