Try   HackMD

VRF & ASM

VRF

VRF RFC draft-15

API

VRF=(Gen,Hash,Prove,Verify)
VRF.Gen() -> (sk, pk)
VRF.Prove(sk, alpha) -> prf
VRF.Hash(prf) -> rnd – deterministic in sk, alpha?
VRF.Verify(pk, alpha, prf) -> 2

Security Properties

Uniqueness

forall pk, alpha exists! prf: VRF.Verify(pk, alpha, prf) = 1
hard to find pk, alpha, (prf1, prf2: VRF.Verify(pk, alpha, prfi) = 1) such that VRF.Hash(prf1) != VRF.Hash(prf2)

  • full: Adv is allowed to choose any (bad, low entropy) pk
  • trusted: same as full, but Adv can't choose a bad pk (ie. Adv knows sk and pk=VRF.Gen(sk))
Collision resistance

forall pk, alpha1, alpha2 => VRF.Hash(VRF.Prove(pk, alpha1)) != VRF.Hash(VRF.Prove(pk, alpha2))
hard to find pk, (alpha1, alpha2, prf1, prf2: VRF.Verify(pk, alphai, prfi) = 1) such that VRF.Hash(prf1) == VRF.Hash(prf2)

  • full: Adv is allowed to choose any (bad, low entropy) pk
  • trusted collision resistance: same as full, but Adv can't choose pk (ie. Adv knows sk and pk=VRF.Gen(sk))
Pseudorandomness

If sk and prf are unknown then hash=VRF.Hash(prf) is indistinguishable from random for any alpha

  • full: Adv receive pk, choose alphai and observe prfi, choose alpha
  • selective: Adv choose alpha, receive pk, choose alphai, observe prfi
Unpredictability under malicious key gen

Similar to pseudorandomness property but with "good-enough" key gen (ie. with enough entropy)

ECVRF construction

Two variants: with or without key validation (KV).

ECVRF(sk, alpha) -> rnd

  1. DlEq{(G, sk G, KDF(alpha), sk KDF(alpha); sk): sk G = sk KDF(alpha)}
  2. rnd = Hash(sk KDF(alpha))

Properties (mostly follow from properties of ZKP, Hash, KDF):

  • full uniqueness (perfect binding, onewayness of KDF)
  • trusted/full(KV) collision resistance (collision resistance of KDF, Hash)
  • full pseudorandomness (hash pseudorandomness)
  • unpredictability(KV) (hash unpredict)

ECVRF.Gen(sk) -> pk

  1. return pk = KDF(sk)*G

ECVRF.Prove(sk, alpha, [salt]) -> prf

  1. x = KDF(sk); Y = x G
  2. H = encode_to_curve(salt, alpha)
  3. h = point_to_string(H)
  4. X = x H
  5. k = nonce_gen(sk, h)
  6. c = challenge_gen(Y, H, X, kG, kH)
  7. s = k + cx
  8. return prf = (X, c, s)

ECVRF.Hash(prf) -> Option<rnd>

  1. (X, c, s) = decode_prf(prf)?
  2. return Some rnd = H(suite_string | dom_sep(0x03) | point_to_string(cofactor * X) | dom_sep(0x00))

ECVRF.Verify(pk, alpha, prf, [salt], KV) -> 2 // KV: 2; validate keys or not

  1. Y = string_to_point(pk)?
  2. if KV then validate_key(Y)?
  3. (X, c, s) = decode_prf(prf)?
  4. H = encode_to_curve(salt, alpha)
  5. U = sG-cY
  6. V = sH-cX
  7. c ?= challenge_gen(Y, H, X, U, V)
  8. return true

ECVRF.encode_to_curve(salt, alpha) -> H – hash to curve
ECVRF.nonce_gen(sk, h) -> k – deterministic gen nonce scalar
ECVRF.challenge_gen(Y, H, X, U, V) -> c – transcript/hash
ECVRF.decode_prf(prf) -> Option<X, c, s> – parse/validate PK and scalars
ECVRF.validate_key(Y) -> 2 – for curve25519 there's a list of 8 bad points, so use lookup instead of cofactor*

  1. return cofactor*Y != O
Parameters

TODO:

  • RFC ciphersuites
  • salt
  • Hash
  • KDF
  • encode_to_curve
  • nonce_gen
  • challenge_gen
  • dom_sep
  • KV
  • E, G, cofactor / ristretto
  • string_to_point/point_to_string / Elligator

BLS

BLS.KeyGen(sk) -> pk = sk G_2
BLS.Sign(sk; m) -> sig = sk H(m)
BLS.Verify(pk; m) -> 2 = e(H(m), pk) =? e(sig, G_2)
BLS.VRF(sk; alpha) -> rnd = H(sk H(alpha))

BLS-dl

BLS is essentially DlEq proof.
Schnorr DlEq:

BLS-dl.KeyGen(sk) -> pk = sk G
BLS-dl.Sign(sk; m) -> sig

  1. r <-R Z_q, R = r G, X = r H(m), T = sk H(m)
  2. c = H(pk, R, X, m)
  3. s = r + c sk
  4. sig = (s,c,T) or (s, R, X, T)

BLS-dl.Verify(pk; m, (s,R,X,T)) -> 2

  1. c = H(pk, R, X, m)
  2. s G ?= R + c pk
  3. s H(m) ?= X + c T

BLS-dl.Verify(pk; m, (s,c,T)) -> 2

  1. R = s G - c pk
  2. X = s H(m) - c T
  3. c ?= H(pk, R, X, m)

Implementations

  • r2ishiguro: ECVRF with ed25519; uses random nonce
  • coniks-go: ECVRF with ed25519; uses det nonce, let efficient, doesn't use mixed scalar mul
  • algorand with libsodium fork (branch draft-irtf-cfrg-vrf-03): ECVRF with ed25519
  • Algorand, Ouroboros-Praos and Elrond; Harmony; HERB (see Galindo et al for references).

Distributed VRF

Pairing allows to verify DlEq without an explicit proof.
Schnorr requires an explicit proof for DlEq.

Standard way for DVRF:

  1. DKG - needs DlEq for partial secret sig verification
  2. DH: sk KDF(alpha) - needs DlEq to prove DH vs pk

Galindo et al:

  • Dfinity-DVRF - DKG (Schnorr/DlEq) + Gen (pairing-based/BLS)
  • DDH-DVRF - DKG (Schnorr/DlEq) + Gen (Schnorr/DlEq)
  • GLOW-DVRF - DKG (pairing-based) + Gen (Schnorr/DlEq)

Distributed Random Beacon

DRB vs VRF:

  • DRB has state that changes with time after each new beacon is generated
  • DRB has state transition given current beacon and proof
  • state_n = beacon_n || n

Accountable subgroup multisignature (ASM)

Boneh, Drijvers, Neven

BLS.Sign(sk,m) = sk H(m)
BLS.Verify(pk,sig,m) = e(H(m),pk) ?= e(sig,G)

aggregation: {sig_i} => sig=\sum_i sig_i
verify: e(sig,G) ?= \sum_i e(H(m_i),pk_i)
rogue-key attack (with m_1=m_2): pk_2(a) = aG - pk_1
defense: Prove KoSK, use different m_1!=m_2

Constructions: MSP, MSP-pop, AMSP, AMSP-pop, ASM, MSDL, MSDL-pop

MSP - BLS-based multisig

MSP.KeyGen(sk_i) -> pk_i = sk_i G_2
MSP.Agg({pk_i}) -> A_i = H(pk_i,{pk_j})
MSP.KeyAgg({pk_i}) -> apk = \sum_i A_i pk_i
MSP.Sign({pk_i}, sk_i, m) -> sig_i = (sk_i A_i) H(m)
MSP.SigAgg({sig_i}) -> sig = \sum_i sig_i
MSP.Verify(apk, m, sig) -> 2 = e(sig,G_2) ?= e(H(m), apk)
MSP.BatchVerify …

MSP-pop

Proof-of-possession variant of MSP. Simpler KeyAgg, but instead public keys are shared with PoP:

MSP-pop.KeyGen(sk_i) -> (pk_i, prf_i) = (sk_i G_2, sk_i H(pk_i))
MSP-pop.Agg({pk_i}) -> A_i = 1
MSP-KeyAgg({pk_i}) -> apk = \sum_i pk_i
…

AMSP - aggregate multi-signature scheme

AMSP := MSP
AMSP.Sign({pk_i}, sk_i, m) -> sig_i = (sk_i A_i) H(apk, m)
AMSP.Verify …
AMSP.BatchVerify …

AMSP-pop

Similar to MSP-pop.

ASM - accountable subset multisig

ASM.KeyGen := MSP.KeyGen
ASM.KeyAgg := MSP.KeyAgg
ASM.GroupSetup(sk_i, {pk_i}) -> mk_i

  1. for all j: send to j mk_{j,i}=(sk_i A_i) H(apk, j)
  2. mk_i = \sum_j mk_{i,j} // mk_i = AMSP.Sign(i)
    ASM.Sign({pk_i}, sk_i, mk_i, m) -> sig_i = mk_i + sk_i H(apk, m_i)
    ASM.SigAgg({pk_i}, S, {sig_j}) -> (pk, sig)
  3. pk = \sum_{j in S} pk_i
  4. sig = \sum_{j in S} sig_j
    ASM.Verify(apk, S, m, (pk, sig)) -> 2 = e(H(apk,m),pk)*e(\sum_{j in S} H(apk, j), apk) ?= e(sig, G_2)

MSDL - Schnorr-based multisig

MSDL.KeyGen = MSP.KeyGen
MSDL.Agg := MSP.Agg
MSDL.KeyAgg := MSP.KeyAgg
MSDL.Sign({pk_i}, sk_i, m) -> sig

  1. r_i <-R Z_q, R_i = r_i G, broadcast t_i = H(R_i)
  2. broadcast R_i, verify t_j ?= H(R_j)
  3. R = \sum_j R_j, c = H(R, apk, m), broadcast s_i = r_i + c sk_i A_i
  4. s = \sum_j s_j, sig = (R, s)
    MSDL.Verify …

MSDL-pop

Extra round in KeyGen?

Agirtas, Yayla

ASM Schemes

vASM - ASM with VSS-verifiable subgroup setup

Feldman VSS + PoP, subgroup unknown before signing

vASM.KeyGen(sk_i) -> pk_i = sk_i G_2
vASM.GroupSetup({pk_i}, S={1..n}, sk_i) -> (mk_i, C)

  1. f_i(x) = \sum_j a_{j,i} x^i <-R Z*_q[x], deg(f_i)=n-1, f_i(0) = sk_i, (coeffs are non-zero)
  2. C_i = {C_{j,i} = a_{j,i} G_2}
  3. for all j send to j (f_i(j),C_i)
  4. mk_i = \sum_{j in S} f_j(i), C = \sum_j C_j
  5. C_0 ?= \sum_{j in S} pk_j; mk_i G_2 ?= \sum_k i^k C_k
  6. return mk_i, C

vASM.Sign(mk_i, m) -> sig_i = mk_i H(m) // send to combiner
vASM.SigAgg(S, {sig_i}) -> sig = \sum_{i in S} sig_i
vASM.Verify(C, S, m, sig) -> 2 = e(sig, G_2) ?= e(H(m), \sum_k (\sum_{i in S} i^k) C_k)

vASM-dl - DL/Schnorr-based variant of vASM

vASM.Verify(C, S, m, sig) does DlEq verification:
Dl_{H(m)}(sig) ?= Dl_{G_2}(\sum_k (\sum_{i in S} i^k) C_k)

Let's make it explicit with Schnorr:

vASM-dl.KeyGen
vASM-dl.GroupSetup -> (mk_i, C) // Feldman DKG, mk_i G = f© – public key reconstructed from commitments C
vASM-dl.Sign(mk_i, r_i, m) -> sig_i

  1. T = mk_i H(m) // vASM.Sign
  2. R = r_i G, X = r_i H(m)
  3. c_i = H(apk, R, X, T, m) // c_i must be const => R_i=const, X_i=const, T_i=const
  4. s_i = r_i + c_i mk_i
  5. return sig_i = (s_i, R, X, T)
    vASM-dl.SigAgg(S, {sig_i}) -> sig = \sum_{i in S}

ASMwSA - ASM with subgroup authentication

Explicit Subgroup

ASMwSA.KeyGen := vASM.KeyGen
ASMwSA.Agg({pk_i}) -> A_i = H(pk_i, {pk_i})
ASMwSA.KeyAgg({pk_i}) -> apk = \sum_i A_i pk_i
ASMwSA.GroupSetup := ASM.GroupSetup?
ASMwSA.GroupSetup({pk_i}) -> m_{i,j} = (A_i sk_i) H(apk, j)
ASMwSA.Sign({m_{i,j}}, S, m, sk_i) -> sig_i

  1. mk_i = \sum_{j in S} m_{i,j}
  2. sig_i = mk_i + (A_i sk_i) H(apk, m)

ASMwSA.SigAgg({pk_i}, S, {sig_i}) -> (spk, sig) = (\sum_{i in S} A_i pk_i, \sum_{i in S} sig_i)
ASMwSA.Verify(apk, (spk, sig), S, m) -> 2 = e(sig, G_2) ?= e(H(apk,m) + \sum_{j in S} H(apk, j), spk)

ASMwCA - ASM with combiner authentication

Designated combiner, subgroup unknown before signing

ASMwCA.KeyGen := ASMwSA.KeyGen
ASMwCA.Agg := ASMwSA.Agg
ASMwCA.KeyAgg := ASMwSA.KeyAgg
ASMwCA.GroupSetup := ASMwSA.GroupSetup
ASMwCA.Sign({m_{i,j}}, S, m, sk_i) -> sig_i = m_{i,i} + (A_i sk_i) H(apk, m)
ASMwCA.SigAgg({m_{i,j}}, {pk_i}, S, {sig_i}) -> (spk, sig) = (\sum_{i in S} A_i pk_i, \sum_{i in S} (sig_i + \sum_{j in S} m_{i,j}))
ASMwCA.Verify(apk, (spk, sig), S, m) -> 2 = e(sig, G_2) ?= e(H(apk,m) + \sum_{j in S} H(apk, j), spk)

Aggregated ASM

Last changed by 
 
Protocol Team
Specing Iota Day and Night
0
405

Read more

Untitled

Dec 1, 2022
VRF

Verifiable random function

Nov 11, 2022
Publicly verifiable multi-user public key encryption

Introduction Public key encryption (PKE) is a standard tool used in many protocols with two parties -- sender and receiver. Sender uses receiver&apos;s public key to encrypt a secret message and receiver uses her private key to decrypt it. In modern (decentralized) protocols there&apos;s a third party -- verifier. Verifier acts as an arbiter, she verifies that both parties (sender and receiver) follow the protocol correctly. When there&apos;s a need for privacy a PKE scheme does not offer the verifier to do her job -- to get access to the encrypted message privacy property must be sacrificed. To overcome this issue there&apos;s publicly verifiable public key encryption (PVPKE). In such a scheme the sender encrypts a message and proves certain useful properties about it such that the verifier can verify the proof (ie. that the properties do actually hold for the encrypted message without decrypting it) and the receiver can decrypt the message as usual. Some useful properties about encrypted text might include the following: proof of decryptability, ie. that the receiver can indeed decrypt the message (and not claim that she can&apos;t, without revealing her private decryption key); proof of correct encryption, ie. that the sender has encrypted a valid message (and not some garbage).

Jun 30, 2022
PVSS succinct proofs

How to aggregate PVSS proofs nicely

Feb 3, 2022
Read more from Protocol Team
Published on HackMD