Merge "ibe: Implementation of the Boneh-Boyen identity-based-encryption scheme."
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
+}
