# VRF & ASM ## VRF - [verifiable random function for random sortitioning](https://hackmd.io/@jkrvivian/H16hUsIEj) - [medium on algorand](https://medium.com/algorand/algorand-releases-first-open-source-code-of-verifiable-random-function-93c2960abd61) - [ietf draft VRF](https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-15#section-5.1) - [algorand impl](https://github.com/algorand/go-algorand/blob/master/crypto/vrf.go) - BLS signature for VRF? ### [VRF RFC draft-15](https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-15#section-5) #### 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](https://eprint.iacr.org/2020/096.pdf) 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](https://eprint.iacr.org/2020/096.pdf): - 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](https://eprint.iacr.org/2018/483.pdf) 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) 1. pk = \sum_{j in S} pk_i 2. 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](https://eprint.iacr.org/2022/018.pdf) 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(C) -- 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
229

Read more

Untitled

12/1/2022
VRF

Verifiable random function

11/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's public key to encrypt a secret message and receiver uses her private key to decrypt it. In modern (decentralized) protocols there's a third party -- verifier. Verifier acts as an arbiter, she verifies that both parties (sender and receiver) follow the protocol correctly. When there'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'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't, without revealing her private decryption key); proof of correct encryption, ie. that the sender has encrypted a valid message (and not some garbage).

6/30/2022
PVSS succinct proofs

How to aggregate PVSS proofs nicely

2/3/2022
Read more from Protocol Team
Published on HackMD