Anonymous Tokens and Hidden Metadata: Enhancing Security and Privacy

Anonymous Tokens with Hidden Metadata Bet l Durak Melissa Chase and Serge Vaudenay

Motivation and Applications 2

(One-Time) Anonymous Tokens Give me tokens Unforgeable tokens unlinkable Redeem the tokens Server (Issuer/Redeemer) Client Privacy Pass (PP) and Google Trust Tokens (TT) API Token generation with private-key primitives such as OPRFs. 3

Anonymous Tokens and Fraud Establish trust to the client? Server (Issuer/Redeemer) Client How does the server know the client is trustworthy? Human vs bot (CAPTCHA?) Legit vs malicious bot (?) Authentic/emulator vs hacked device (device attestation?) 4 Machine Learning

Anonymous Tokens with Hidden Metadata Give me tokens Tokens + {0,1} Redeem the tokens (accept if embedded bit is 1). Server (Issuer/Redeemer) Client If the device is malicious, release a token with bit 0 Deferred rejection during redemption. 5

Private Metadata Bit Token (PMBT) [KLOR 20] 6

PMBT Interface SetUp 1? ???,?? ; KeyGen ??? ??,?? pp t sk b query ClientQuery IssueToken st resp ClientFinal t Verify ??,(?,?) {????,?????} ReadBit ??,(?,?) {0,1, } Gives two different notions of validity of tokens. 7

PMBT Protocol [KLOR20] Client Input: ?0,?1,? ? $?? ? ? ? ? ? 1? Server ?? = ?0,?0, ?1,?1; ? {0,1} ?0 ?0?; ?1 ?1? ClientQuery ? $ 0,1? ? ? (?;? ) ? ??? + ??? ? IssueToken (?,? ) ? ? (?;? ) S ?? ? ?? ? (?,?) output:(t,?) ClientFinal ReadBit: If ? = ?0??? + ?0? AND ? ?1??? + ?1?, return 0; If ? ?0??? + ?0? AND ? = ?1??? + ?1?, return 1; Else, return Verify: return true 8

Cryptographic Primitives PMBT also uses OPRFs with an input tag ? from the client. Security and Privacy: OMUF: One-more unforgeability UNLINK: Unlinkability PMB: Privacy of the metadata bit (from the client) 9

PMB: Privacy of the Metadata Bit ????? (?,?????) IssueToken ??,?,????? ???? ???? ???? SetUp 1? (???,??) KeyGen ??? (??,??) returnA?????, ???????, ?? ?????,?? ????? ????? IssueToken ??,? ,????? ???? ???? ??? = Pr ?????? 1 ? = 1 Pr[?????? 1|? = 0] ??????? (?,?) bool Verify ??,?,? ???? 10

PMBT Weakness ????? (?1= 0,?1= ?(?1)) ?1= ?0?1+ ?0?1 (?1,?1) ????? T = ? ? ?(?1) ? = ?? ? + ?? ? (? ,? ) If {t ,? = (? + ?1,? + ?1)}is valid , the challenge bit is ? = 0; Otherwise, the challenge bit is ? = 1. 11

Problem? PMBT design OPRFs are deterministic: it is hard to make it CCA secure . ? is chosen solely by the client. We want a stronger security notion with an access to the Validity oracle. 12

Anonymous Tokens with Hidden Metadata (ATHM) 13

ATHM A new interface without an artificial Verify. ? is computed by both the client and the server. Relying on algebraic MACs instead of OPRFs. Stronger security notions. 14

ATHM Interface SetUp 1? ???,?? ; KeyGen ??? ??,?? pp sk b query ClientQuery IssueToken st resp ClientFinal t ReadBit ??,?,? {0,1, } No need to define Verify separately. 15

Privacy of the Metadata Bit ????? ???? (?,?????) IssueToken ??,?,????? ???? ???? SetUp 1? (???,??) KeyGen ??? (??,??) flag false returnA ?????, ??????, ?????, ?? ?????,?? ?????? (?,?) ???? ReadBit ??,?,? =? ???? ????? ????? (?,?) ????? If flag, then return flag true If flag, then abort {0,1, } ReadBit ??,?,? {0,1, } ???? IssueToken ??,? ,????? ???? 16

Algebraic MAC [CPZ18] ????,?,? ?,? ?,? Pick ? $ ? ? ? + ? ? + ? ? ? ?,? are the attributes (in ATHM) added by both the client and issuer. 17

ATHM Protocol Server ?? = ?,?,? ; ? {0,1} Z ?? Client (?,?? = ?) mask ?,?? $?? ? ??? + ?? ?? $?? ? $?? ? ? ?? V ? + ?? + ??? ? + ?? ? proof unmask (?,?,??,?) Verify ? ? $?? P ??; ? ?(? ??) ? ??+ ?? ? (?,?) output:(?,?) Re-randomize ReadBit: If Q = ? + ?? + ?? ?, return ?. Else, return P = ?? = ??? ? = ? ? ?? = ?? ?? + ??? + ???? + ? ???? = ???? + ????? + ??+ ?????? ? = ? + ?? + ?? ? 18

Security We have formally proven under GGM and ROM: One-More Unforgeability (OMUF). UNLINK security. PMB security. 19

Implementation Results Issuance Redemption Total PP 9x 1x 10x PMBT 27x 4x 31x ATHM 28x 2x 30x Machine spec Running time PMBT Intel(R) i7-1185G7 3.00GHz CPU 1.6 ms (no hardware acceleration) NA (with acceleration) ATHM Intel(R) i7-1185G7 3.00GHz CPU 1.3 ms (no hardware acceleration) 0.9 ms (with acceleration) 20

Full Version and Open Problems The extended paper is available at 2022/1622.pdf (iacr.org) Extension of protocols with other algebraic MACs. Variant with security proofs in DDH (without GGM). Public metadata integration. The implementation: https://github.com/microsoft/MacTok Future Research: Can the security of ATHM be proven without GGM assumption? Can algebraic MAC-based protocols be turned into publicly verifiable form without pairings? 21

References KLOR 20, Ben Kreuter, Tancr de Lepoint, Michele Orr , and Mariana Raykova. Anonymous Tokens with Private Metadata Bit, Crypto 2020. CPZ 18, Melissa Chase, Trevor Perrin, and Greg Zaverucha. Algebraic MACs and Keyed-Verification Anonymous Credentials, CCS 2018. 22

OMUF Security ????? (?,?????) Increment ?? IssueToken ??,?,????? ???? SetUp 1? (???,??) KeyGen ??? (??,??) Initialize ?0 0;?1 0 A?????, ????????,?? (?, ???? ??,?? ) if # ?? ??, then abort win if ReadBit ??,??,?? = ?, forall i ????? (?,?) ReadBit ??,?,? {0,1, } {0,1, } 23

UNLINK Security SetUp 1? (???,??) initialize Qquery,Qfinal ?1??? (??,?????1) ??????, ???????????1 (?, ????? ? Q,?????2) if ? ?????? ??????, then abort ?????? if ? ??????, then abort insert ? in ?????? ClientQuery pp (??????,???) ? ?????? A2 if #? < ?, then abort for all ? ? (??,??) ClientFinal(???,?????) ?????? if ? ?????? or ? ??????, then abort insert ? in ?????? if (??,??) = , then abort (?,?????) ? $? (?,?) ClientFinal ???,????? (?,?) pick a random permutation of ? of ? ?3 ?????2,(?? ,?? ), (?? ?,??(?)? ? ? ??? = Pr ??? 2 ?+ ???? win if ? == ? 24