dlog

Documentation

Overview

Package dlog includes algorithms for computing discrete logarithms.

FE schemes instantiated from the Discrete Diffie-Hellman assumption (DDH) all rely on efficient algorithms for calculating discrete logarithms.

Index

• Variables
• type Calc
  • func NewCalc() *Calc
  • func (*Calc) InBN256() *CalcBN256
  • func (*Calc) InZp(p, order *big.Int) (*CalcZp, error)
• type CalcBN256
  • func (c *CalcBN256) BabyStepGiantStep(h, g *bn256.GT) (*big.Int, error)
  • func (c *CalcBN256) BabyStepGiantStepStd(h, g *bn256.GT) (*big.Int, error)
  • func (c *CalcBN256) Precompute(maxBits int) error
  • func (c *CalcBN256) WithBound(bound *big.Int) *CalcBN256
  • func (c *CalcBN256) WithNeg() *CalcBN256
• type CalcZp
  • func (c *CalcZp) BabyStepGiantStep(h, g *big.Int) (*big.Int, error)
  • func (c *CalcZp) WithBound(bound *big.Int) *CalcZp
  • func (c *CalcZp) WithNeg() *CalcZp

Variables

var MaxBound = new(big.Int).Exp(big.NewInt(2), big.NewInt(48), nil)

MaxBound limits the interval of values that are checked when computing discrete logarithms. It prevents time and memory exhaustive computation for practical purposes. If Calc is configured to use a boundary value > MaxBound, it will be automatically adjusted to MaxBound.

Types

type Calc

type Calc struct{}

Calc represents a discrete logarithm calculator.

func NewCalc

func NewCalc() *Calc

NewCalc generates a new discrete logarithm calculator.

func (*Calc) InBN256

func (*Calc) InBN256() *CalcBN256

InBN256 builds parameters needed to calculate a discrete logarithm in a pairing BN256 group.

func (*Calc) InZp

func (*Calc) InZp(p, order *big.Int) (*CalcZp, error)

InZp builds parameters needed to calculate a discrete logarithm in Z_p group.

type CalcBN256

type CalcBN256 struct {
	Precomp map[string]*big.Int
	// contains filtered or unexported fields
}

CalcBN256 represents a calculator for discrete logarithms that operates in the BN256 group.

func (*CalcBN256) BabyStepGiantStep

func (c *CalcBN256) BabyStepGiantStep(h, g *bn256.GT) (*big.Int, error)

BabyStepGiantStep uses the baby-step giant-step method to compute the discrete logarithm in the BN256.GT group. If c.neg is set to true it searches for the answer within [-bound, bound]. It does so by running two goroutines, one for negative answers and one for positive. If c.neg is set to false only one goroutine is started, searching for the answer within [0, bound].

func (*CalcBN256) BabyStepGiantStepStd

func (c *CalcBN256) BabyStepGiantStepStd(h, g *bn256.GT) (*big.Int, error)

BabyStepGiantStepStd implements the baby-step giant-step method to compute the discrete logarithm in the BN256.GT group.

It searches for a solution <= bound. If bound argument is nil, the bound is automatically set to the hard coded MaxBound.

The function returns x, where h = g^x in BN256.GT group where operations are written as multiplications. If the solution was not found within the provided bound, it returns an error.

func (*CalcBN256) Precompute

func (c *CalcBN256) Precompute(maxBits int) error

Precompute precomputes small steps for the discrete logarithm search. The resulting precomputation table is of size 2^maxBits.

func (*CalcBN256) WithBound

func (c *CalcBN256) WithBound(bound *big.Int) *CalcBN256

WithBound sets a bound for the calculator of the discrete logarithm.

func (*CalcBN256) WithNeg

func (c *CalcBN256) WithNeg() *CalcBN256

WithNeg sets that the result should be searched also among negative integers.

type CalcZp

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

CalcZp represents a calculator for discrete logarithms that operates in the Zp group of integers modulo prime p.

func (*CalcZp) BabyStepGiantStep

func (c *CalcZp) BabyStepGiantStep(h, g *big.Int) (*big.Int, error)

BabyStepGiantStep uses the baby-step giant-step method to compute the discrete logarithm in the Zp group. If c.neg is set to true it searches for the answer within [-bound, bound]. It does so by running two goroutines, one for negative answers and one for positive. If c.neg is set to false only one goroutine is started, searching for the answer within [0, bound].

func (*CalcZp) WithBound

func (c *CalcZp) WithBound(bound *big.Int) *CalcZp

WithBound sets a bound for the calculator of the discrete logarithm.

func (*CalcZp) WithNeg

func (c *CalcZp) WithNeg() *CalcZp

WithNeg sets that the result should be searched also among negative integers.