package msp

import "github.com/cloudflare/redoctober/msp"

Package msp implements matrix operations for elements in GF(2^128).

Polynomial fields with coefficients in GF(2)

Index ¶

• Variables
• type Condition
• type FieldElem
• func NewFieldElem() FieldElem
• func (e FieldElem) Add(f FieldElem) FieldElem
• func (e FieldElem) AddM(f FieldElem)
• func (e FieldElem) Dup() FieldElem
• func (e FieldElem) Exp(i int) FieldElem
• func (e FieldElem) Invert() FieldElem
• func (e FieldElem) IsOne() bool
• func (e FieldElem) IsZero() bool
• func (e FieldElem) Mul(f FieldElem) FieldElem
• type Formatted
• func StringToFormatted(f string) (out Formatted, err error)
• func (f *Formatted) Compress()
• func (f Formatted) Ok(db UserDatabase) bool
• func (f Formatted) String() string
• type Layer
• type MSP
• func StringToMSP(pred string) (m MSP, err error)
• func (m MSP) DerivePath(db UserDatabase) (ok bool, names []string, locs []int, trace []string)
• func (m MSP) DistributeShares(sec []byte, db UserDatabase) (map[string][][]byte, error)
• func (m MSP) RecoverSecret(db UserDatabase) ([]byte, error)
• type Matrix
• func (e Matrix) Mul(f Row) Row
• func (e Matrix) Recovery() (Row, bool)
• func (e Matrix) Size() (int, int)
• type Name
• func (n Name) Ok(db UserDatabase) bool
• type NodeType
• func (t NodeType) Type() NodeType
• type Raw
• func StringToRaw(r string) (out Raw, err error)
• func (r Raw) Formatted() (out Formatted)
• func (r Raw) Ok(db UserDatabase) bool
• func (r Raw) String() string
• type Row
• func NewRow(s int) Row
• func (e Row) AddM(f Row)
• func (e Row) DotProduct(f Row) FieldElem
• func (e Row) Mul(f FieldElem) Row
• func (e Row) MulM(f FieldElem)
• func (e Row) Size() int
• type TraceElem
• type TraceSlice
• func (ts TraceSlice) Compact() (index []int, names []string, trace []string)
• func (ts TraceSlice) Len() int
• func (ts TraceSlice) Less(i, j int) bool
• func (ts *TraceSlice) Pop() interface{}
• func (ts *TraceSlice) Push(te interface{})
• func (ts TraceSlice) Swap(i, j int)
• type UserDatabase

Variables ¶

var (
	Modulus        FieldElem = []byte{135, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} // x^128 + x^7 + x^2 + x + 1
	ModulusSize    int       = 16
	ModulusBitSize int       = 128

	Zero FieldElem = []byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
	One  FieldElem = []byte{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
)

var ErrNotEnoughShares = errors.New("not enough shares to recover")

ErrNotEnoughShares is returned if there aren't enough shares to decrypt the secret.

Types ¶

type Condition ¶

type Condition interface {
	Ok(UserDatabase) bool
}

type FieldElem ¶

type FieldElem []byte

func NewFieldElem ¶

func NewFieldElem() FieldElem

NewFieldElem returns a new zero element.

func (FieldElem) Add ¶

func (e FieldElem) Add(f FieldElem) FieldElem

Add returns e+f.

func (FieldElem) AddM ¶

func (e FieldElem) AddM(f FieldElem)

AddM mutates e into e+f.

func (FieldElem) Dup ¶

func (e FieldElem) Dup() FieldElem

Dup returns a duplicate of e.

func (FieldElem) Exp ¶

func (e FieldElem) Exp(i int) FieldElem

Exp returns e^i.

func (FieldElem) Invert ¶

func (e FieldElem) Invert() FieldElem

Invert returns the multiplicative inverse of e.

func (FieldElem) IsOne ¶

func (e FieldElem) IsOne() bool

func (FieldElem) IsZero ¶

func (e FieldElem) IsZero() bool

func (FieldElem) Mul ¶

func (e FieldElem) Mul(f FieldElem) FieldElem

Mul returns e*f.

type Formatted ¶

type Formatted struct {
	Min   int
	Conds []Condition
}

func StringToFormatted ¶

func StringToFormatted(f string) (out Formatted, err error)

func (*Formatted) Compress ¶

func (f *Formatted) Compress()

func (Formatted) Ok ¶

func (f Formatted) Ok(db UserDatabase) bool

func (Formatted) String ¶

func (f Formatted) String() string

type Layer ¶

type Layer struct {
	Conditions []Condition
	Operators  []NodeType
}

type MSP ¶

type MSP Formatted

func StringToMSP ¶

func StringToMSP(pred string) (m MSP, err error)

func (MSP) DerivePath ¶

func (m MSP) DerivePath(db UserDatabase) (ok bool, names []string, locs []int, trace []string)

DerivePath returns the cheapest way to satisfy the MSP (the one with the minimal number of delegations).

ok: True if the MSP can be satisfied with current delegations; false if not. names: The names in the top-level threshold gate that need to be delegated. locs: The index in the treshold gate for each name. trace: All names that must be delegated for for this gate to be satisfied.

func (MSP) DistributeShares ¶

func (m MSP) DistributeShares(sec []byte, db UserDatabase) (map[string][][]byte, error)

DistributeShares takes as input a secret and a user database and returns secret shares according to access structure described by the MSP.

func (MSP) RecoverSecret ¶

func (m MSP) RecoverSecret(db UserDatabase) ([]byte, error)

RecoverSecret takes a user database storing secret shares as input and returns the original secret.

type Matrix ¶

type Matrix []Row

func (Matrix) Mul ¶

func (e Matrix) Mul(f Row) Row

Mul right-multiplies a matrix by a row.

func (Matrix) Recovery ¶

func (e Matrix) Recovery() (Row, bool)

Recovery returns the row vector that takes this matrix to the target vector [1 0 0 ... 0].

func (Matrix) Size ¶

func (e Matrix) Size() (int, int)

type Name ¶

type Name struct {
	// contains filtered or unexported fields
}

func (Name) Ok ¶

func (n Name) Ok(db UserDatabase) bool

type NodeType ¶

type NodeType int // Types of node in the binary expression tree.

const (
	NodeAnd NodeType = iota
	NodeOr
)

func (NodeType) Type ¶

func (t NodeType) Type() NodeType

type Raw ¶

type Raw struct {
	NodeType

	Left  Condition
	Right Condition
}

func StringToRaw ¶

func StringToRaw(r string) (out Raw, err error)

func (Raw) Formatted ¶

func (r Raw) Formatted() (out Formatted)

func (Raw) Ok ¶

func (r Raw) Ok(db UserDatabase) bool

func (Raw) String ¶

func (r Raw) String() string

type Row ¶

type Row []FieldElem

func NewRow ¶

func NewRow(s int) Row

NewRow returns a row of length s with all zero entries.

func (Row) AddM ¶

func (e Row) AddM(f Row)

AddM adds two vectors.

func (Row) DotProduct ¶

func (e Row) DotProduct(f Row) FieldElem

DotProduct computes the dot product of two vectors.

func (Row) Mul ¶

func (e Row) Mul(f FieldElem) Row

func (Row) MulM ¶

func (e Row) MulM(f FieldElem)

MulM multiplies the row by a scalar.

func (Row) Size ¶

func (e Row) Size() int

type TraceElem ¶

type TraceElem struct {
	// contains filtered or unexported fields
}

type TraceSlice ¶

type TraceSlice []TraceElem

func (TraceSlice) Compact ¶

func (ts TraceSlice) Compact() (index []int, names []string, trace []string)

Compact takes a trace slice and merges all of its fields.

index: Union of all locations in the slice. names: Union of all names in the slice. trace: Union of all the traces in the slice.

func (TraceSlice) Len ¶

func (ts TraceSlice) Len() int

func (TraceSlice) Less ¶

func (ts TraceSlice) Less(i, j int) bool

func (*TraceSlice) Pop ¶

func (ts *TraceSlice) Pop() interface{}

func (*TraceSlice) Push ¶

func (ts *TraceSlice) Push(te interface{})

func (TraceSlice) Swap ¶

func (ts TraceSlice) Swap(i, j int)

type UserDatabase ¶

type UserDatabase interface {
	ValidUser(name string) bool
	CanGetShare(name string) bool
	GetShare(name string) ([][]byte, error)
}

A UserDatabase is an abstraction over the name -> share map returned by the secret splitter that allows an application to only decrypt or request shares when needed, rather than re-build a partial map of known data.

Source Files ¶

formatted.go matrix.go msp.go number.go raw.go