Oblivious Issuance of Proofs and Blind Signatures Connections

Oblivious issuance of proofs Michele Orr , Stefano Tessaro, Greg Zaverucha, Chenzhi Zhu

Non-interactive proofs Poly-time recognizable ? ? ? {?: ?, ?,? ?} ?,? NP language ? ?(?)? Alice: ?,? ? Bob Can ? be issued obliviously ? ? Accept/Reject Other properties: zero- knowledge, knowledge soudness, WI, succinct, Completeness: accept ? if ?,? ? Soundness: reject ? if X ?(?)

Oblivious issuance Part of ? hidden from Alice ? ? ? {?: ?, ?,? ?} ?,? Obliviousness: ? (and part of ?) can t be linked to interaction Alice: ? Bob: ? ? ?(?)? One-more unforgeability: can t forge more proofs than # of interactions ? Completeness: accept ? if ?,? ? Verify ?,? 1/0 Why care? Soundness: reject ? if X ?(?) Other properties

Motivations: blind signatures [Cha82] Many applications: Bob: ??,? Alice: ?? E-cash [Cha82] One s VPN Private click measure Privacy Pass ? Blindness: (?,?)can t link to interaction ??? ??,?,? 0/1 Proof One-more unforgeability: can t forge more signatures than # of interactions

Connections with blind signatures Blind signatures and extensions Blind Schnorr signatures [CP93] Partially blind signatures [AO00] Obliviously issue PoK of DLog Blind signatures w/ arttributes [BL12] U-Prove/Brands credential [Bra00,PZ11] Certain proofs New constructions Oblivious issuance of proofs

Motivations: anonymous credentials [Cha85] Multi-show Keyed-verification [CMZ14] ? Cred Issuer: ?? ,?p Partial information Can we support unlinkable public verification? User: ??,? Issuer (verifier): ?? User: ??,? ? ? ,? Cred Cred Unlinkable multi-show Yes, with oblivious issuance of proofs! Pairing free Better efficiency Verifier: ?? No unlinkable public verification All practical schemes [CL04, ASM06, BCC+09] require pairings

Adding public verifiability Single-show AC [BL12,KL23] ? Preserve keyed- verification User: ??,? Cred Issuer: ?? ? ? ,? ,?p Same as before Minor changes to issuance only Unlinkable to issuance Unlinkable single-show Verifier: ??

Related works Unlinkable to ? due to ZK Meta proofs [DSY90] ?????? ?,? ?: ZKP of ?,?????? ???,?,? = 1 Randomizable proofs [BCC+09] Can we issue proofs obliviously for more general relations based on pairing-free groups? High cost Relies on pairings ? ? Rd Based on Groth-Sahai proofs [GS08] Blind Schnorr signatures [CP93] obliviously issue PoK of Dlog Not OMUF in concurrent setting (ROS attack [BLL+21]) Fixes [Abe01, FPS20, KLR21, CAH+22, KLRX22, TZ22, FW24] Pairing-free groups Specific relations

Contributions Syntax & security of oblivious issuance of proofs Pairing-free constructions for algebraic relations Relies on AGM+ROM New constructions: - Partially unique blind sigs - U-Prove with OMUF Adding unlinkable public verifiability: - 2HashDH OPRF - Keyed-verification AC

Rest of talk Syntax & security Algebraic relations Our constructions

Syntax Public Chosen by user freely Hidden from issuer ? ?,(?,?,?) Depending on (?,?) Statement

Syntax Security Free Mode Restricted Mode Hidden from issuer ? ?,(?,?,?) Chosen freely independent of ? ? ? {(?,?,?): ?, ?,(?,?,?) ?} User: ?, info info Issuer: ?,? ? Soundness: reject ? if (X,Y,Z) ?(?) X,Y,Z ?(?) ?, ?,? Obliviousness: (?,?,?)can t be linked to interaction Randomly sampled depending on info

One-more unforgeability (OMUF) ? ?,(?,?,?) $ ? ? Set of possible ?,? ?,? OMUF Issuer: ?,? Adversary: ? Soundness: Can t forge valid ? for ?,?,? ?(?) concurrent sessions OMUF: Can t forge + 1 distinct tuples ?1,?1,?1, ,(? +1,? +1,? +1) ?? valid for ?,??,?? ?(?)

Algebraic Relations Additive notation for group operations: ?1+ ?2 ?? ? ? = ? ,? = ? ? ,(? ??,? ??,? ?) : ?1= ?? 1,?, ,??= ?? ?,?,Z = ???? ? ? ?????, ?=? ? Capture common linear relations Can be proved by -protocols ? Example: ?????,? ?,(?,?,?) ? ?3:? = ??,? = ?? = ?????, =[?]

Our constructions

Starting: w/o obliviousness ?=? ?,?,?,? :? ?????,? Free mode: ? is chosen freely by verifier ? ? ?,?,? : ? = ? ,? = ? Issuer: ?,? User: ?,? Achieve obliviousness? ? ? ? ? $ ? ,? ? ? ? ?(?,?,?,?) -protocol [Cra97] for ?? ? ?? ? ?=? ? ? ? ? + ? ? ? (?,?) Soundness due to -protocol + Fiat-Shamir

Achieving obliviousness ?=? ?,?,?,? :? ?????,? Free mode: ? is chosen freely by verifier ? ? ?,?,? : ? = ? ,? = ? Random masks Hidden from issuer Issuer: ?,? User: ?,? ? ? ?,? ? 1 ? ? ? ? ? ?1 + ?? ? ? 1 ,? ? $ ? ? 1?2 ? ? ? ? ? ?,?,?,? ? ?(?,?,?,?) ? ?? Oblivious -protocol similar to blind Schnorr ? ? ? (? ,? 1? + ?) ? ? + ? ? Soundness of ? Perfectly oblivious if ? computed correctly Obliviousness in ROM

One-more unforgeability? ?=? ?,?,?,? :? ?????,? Free mode: ? is chosen freely by verifier ? ? ?,?,? : ? = ? ,? = ? Issuer: ?,? Adversary: ? ? ? ? ? $ ? ROS attack [BLL+21]: (1 + log ?) forgeries by log ? issuing ,? ? ? ? ? ?? ? ? ? ? + ? ? Linearity: ?1= ?1+ ?1 ? ?1+ ?2 = (?1+ ?2) + (?1+ ?2) ? ?2= ?2+ ?2 ?

Avoid ROS attack (w/o oblivious) ?=? ?,?,?,? :? ?????,? Free mode: ? is chosen freely by verifier ? ? ?,?,? : ? = ? ,? = ? Idea from [TZ22] Issuer: ?,? User: ?,? ? ? ? ? Commitment of ? ,? ?? ? ? ,? $ ?,? ? ?? $ ? ?,? ? ? ?,?,?,?,? ? ? ?,?,?,? ? ? ,?,? Binding of ? ? (?,?,?,?) ? (?,?) ? ? + (??) ? ? ? + ? ? Break linearity Soundness assuming DL Obliviousness assuming DL

One-more unforgeability ?=? ?,?,?,? :? ?????,? Free mode: ? is chosen freely by verifier ? ? Compute ? given wG,?2?, ,???+1? Theorem. (Free mode) For any AGM adversary ?, ??+1 ??? + ?( ??+ ?? ???? 2/?) ????? ??,?????,? ? 2????,? ??: # of issuing, ??: # of ? queries Due to: issuer sends w? in each issuing ?=? ?,?,?,? : Restrict mode: ? sampled according Info ?????, ? ? Compute ? ? given s.t. ? = 0 Theorem. (Restrict mode) For any AGM adversary ?, ???? ?? + ??? ????? + ?( ??+ ?? 2/?) ????? ??,?????, ? 2????,? Implied by DL for common

Conclusion & open problems Blind signatures Oblivious issuance of proofs for algebraic relations New constructions: - Partially unique blind sigs - U-Prove with OMUF More relations? Adding unlinkable public verification: - 2HashDH OPRF - Keyed-verification AC Other proofs, SNARKs? Other applications? Our paper: https://ia.cr/2023/1635

Thank you!