Structure-Preserving Signatures and Cryptography Overview

Unified, Minimal and Selectively Randomizable Structure-Preserving Signatures Masayaki Abe, NTT Jens Groth, University College London Miyako Ohkubo, NICT Mehdi Tibouchi, NTT

Unified, Minimal and Selectively Randomizable Structure-Preserving Signatures Unified Type I Type II Type III Minimal Small signatures and low verification complexity Single group element public verification keys Selectively randomizable Strong existential unforgeability Randomizability

Mathematical structures in cryptography Cyclic prime order group G ?? ??= ??+? Useful mathematical structure ElGamal encryption Pedersen commitments Schnorr proofs

Pairing-based cryptography Groups G1,G2,G? with pairing ?:G1 G2 G? ?? ??= ??+? ? ??,??= ? ?,??? Additional mathematical structure One-round tripartite key exchange Identity-based encryption Short digital signatures NIZK proofs

Structure-preserving cryptography Preserve mathematical structure of pairing groups Communication consists of group elements in G1,G2 Use generic group operations Multiplication, membership testing, pairing Avoid structure-destroying operations No cryptographic hash-functions Modular design Structure-preserving building blocks easy to combine

Bilinear group setup ?,G1,G2,G?,?,?,? Gen(1?) Groups G1,G2,G? of prime order ? Bilinear map ?:G1 G2 G? ? ??,?? = ? ?,??? G1= ? , G2= ? , G?= ? ?,? Types Type I: G1= G2 and ? = ? Type II: G1 G2 but there is efficient ?:G2 G1 Type III: G1 G2 and no efficient homomorphism Asymmetric setting Most efficient Symmetric setting Conceptually simple

Structure-preserving signatures Setup describes bilinear group and random group elements in G1,G2 Verification key has group elements in G1,G2 Messages consist of group elements in G1,G2 Signatures consist of group elements inG1,G2 Verifier uses pairing product equations to check validity of signatures, e.g., ? ?,? = ? ?,? ? ?,? ? ?,? = ? ?,? ?(?,?)

Composition with other structure-preserving primitives Easy to compose structure-preserving signatures with other structure-preserving primitives ElGamal encryption is structure-preserving Can encrypt signature Groth-Sahai proofs are structure preserving Can give NIZK proof that message has been signed And vice versa Can sign ElGamal ciphertexts and Groth-Sahai proofs

Lower bounds for Type I and III pairings Theorem A structure-preserving signature scheme must have at least 2 verification equations A structure-preserving signature created by a signer that only uses generic group operations must be at least 3 group elements Holds even for Existential unforgeability under random message attack Single group element messages

Sketch of proof Cannot have a single verification equation Two signatures can be combined to forgery on third message Each message must have many potential signatures Signer using generic group operations must compute signature as linear combination of group elements from setup and message If signatures are (quasi-)unique then possible to create forgery as linear combination of two previous signatures A signature must have at least 3 group elements Suppose the signature has only 1 or 2 group elements Verification involves 2 equations in 1 or 2 unknowns For a given message we have at most 4 solutions This makes the signature scheme quasi-unique

New structure-preserving signature scheme Setup 1?: Return ?? = ?,G1,G2,G?,?,?,?,? ?,G1,G2,G?,?,?,? Gen(1?) ; ? G1 KeyGen ?? : Return ??,?? = (?,?) ? ?? ; ? = ?? Sign??,??(?): Return = (?,?,?) ? ?? 1 ? ; ? = ? ? ?? 1 ? ; ? = ?? ; ? = ? ? ?? Verify??,???, : Accept if and only if ? ?,? = ? ?,? ? ?,? ? ?,? = ? ?,? ?(?,?)

Security Theorem The signature scheme is strongly existentially unforgeable under adaptive chosen message attack in the generic group model Need 4 group elements to base security on non-interactive assumptions [AGHO11], so strong assumption necessary to get optimal size signatures

Optimal Signature: Verification: Prior art gave optimality in the asymmetric setting, but new in the symmetric setting Shows attacker s extra capability in the symmetric setting does not necessitate extra signature size For one-time signatures the picture is different Asymmetric setting: 1 verification equation possible Symmetric setting: 2 verification equations necessary 3 group elements 2 verification equations

Minimal verification key Setup: ?,G1,G2,G?,?,?,?,? Public verification key: ? Single group element in verification key Certification chains Use ?1 to sign ?2, use ?2 to sign ?3, etc. Symmetric setting Automorphic: Verification keys can be signed Asymmetric setting Can build certification chain by alternating between G2 and G1

Unified The signature scheme works in all types of bilinear groups, both symmetric and asymmetric Separation of elements and operations in G1,G2 ? ?,? = ? ?,? ? ?,? ? ?,? = ? ?,? ?(?,?) Therefore possible to use it even in asymmetric groups Security holds in all types of groups Even in the symmetric setting G1= G2, which enables the adversary to mix and match components

Unified Type I Type II Type III Conceptual simplicity A single signature scheme that works in all settings Resistance towards cryptanalysis Use scheme in the asymmetric setting Even if cryptanalysts discover an efficiently computable isomorphism ? between G1 and G2 the scheme may still be secure

Randomization Strong existential unforgeability Cannot forge signature on new message Cannot change signature on previously signed message Existential unforgeability + randomizability Cannot forge signature on new message Can randomize signature on previously signed message Perfect randomization when randomized signature looks like fresh random signature on the same message

Selective randomizability Signer can make randomization token for signature Randomization token makes it possible to randomize Without randomization token not possible to randomize Strong existential unforgeability under adaptive chosen message and token attack Adversary can get signatures with or without tokens Cannot forge signature on new message Cannot create new signature on previously signed message unless it has a randomization token

Selective randomizability Verify??,???,(?,?,?) : Accept if and only if ? ?,? = ? ?,? ? ?,? ? ?,? = ? ?,? ?(?,?) Randomization token 1 ? ? = ? Randomization with randomization token 1 ? ; ? = ?? ; ? = ??2?? 1 ? ? = ?

Summary ? ?,? = ? ?,? ? ?,? ? ?,? = ? ?,? ?(?,?) Minimal Signature: 3 group elements Verification key: 1 group element Verification: 2 equations Unified Type I Type II Type III Selectively randomizable Strong existential unforgeability Randomizable with token