qndleq

Documentation

Overview

Package qndleq provides zero-knowledge proofs of Discrete-Logarithm Equivalence (DLEQ) on Qn.

This package implements proofs on the group Qn (the subgroup of squares in (Z/nZ)*).

Notation

Z/nZ is the ring of integers modulo N.
(Z/nZ)* is the multiplicative group of Z/nZ, a.k.a. the units of Z/nZ, the elements with inverse mod N.
Qn is the subgroup of squares in (Z/nZ)*.

A number x belongs to Qn if

gcd(x, N) = 1, and
exists y such that x = y^2 mod N.

References

[DLEQ Proof] "Wallet databases with observers" by Chaum-Pedersen. https://doi.org/10.1007/3-540-48071-4_7

[Qn] "Practical Threshold Signatures" by Shoup. https://www.iacr.org/archive/eurocrypt2000/1807/18070209-new.pdf

Index

• func SampleQn(random io.Reader, N *big.Int) (*big.Int, error)
• type Proof
  • func Prove(random io.Reader, x, g, gx, h, hx, N *big.Int, secParam uint) (*Proof, error)
  • func (p Proof) Verify(g, gx, h, hx, N *big.Int) bool

Functions

func SampleQn

func SampleQn(random io.Reader, N *big.Int) (*big.Int, error)

SampleQn returns an element of Qn (the subgroup of squares in (Z/nZ)*). SampleQn will return error for any error returned by crypto/rand.Int.

Types

type Proof

type Proof struct {
	Z, C     *big.Int
	SecParam uint
}

func Prove

func Prove(random io.Reader, x, g, gx, h, hx, N *big.Int, secParam uint) (*Proof, error)

Prove creates a DLEQ Proof that attests that the pairs (g,gx) and (h,hx) have the same discrete logarithm equal to x.

Given g, h in Qn (the subgroup of squares in (Z/nZ)*), it holds

gx = g^x mod N
hx = h^x mod N
x  = Log_g(g^x) = Log_h(h^x)

Note: this function does not run in constant time because it uses big.Int arithmetic.

func (Proof) Verify

func (p Proof) Verify(g, gx, h, hx, N *big.Int) bool

Verify checks whether x = Log_g(g^x) = Log_h(h^x).