Efficient Fully Structure-Preserving Signatures

Efficient Fully Structure-Preserving Signatures for Large Messages Jens Groth University College London

Overview Combined signature scheme Can issue randomizable signatures Can issue strongly unforgeable signatures Pairing-based signature scheme Structure-preserving Fully structure preserving Large messages Sign ? elements with 2 ? element signatures

Existential unforgeability Cannot forge signature on new message Randomizable ? ? ? ? Strongly unforgeable ? ?

Combined signature scheme Setup 1? ?? Generic combined signature scheme ?? = ??Rand,??Strong ?? = ??Rand,??Strong But increases key length KeyGen ?? (??,??) SignRand??,? ? VfyRand??,?,? 1/0 Rand ??,?,? ? SignStrong??,? ? VfyStrong??,?,? 1/0 Perfect randomizability Executing SignRand and then Rand has same distribution as SignRand

Combined existential unforgeability against adaptive chosen message attack ??,?? ?,Rand/Strong ? ? ,? Wins if either VfyRand? ,? = 1 and ? ?Rand VfyStrong? ,? = 1 and (? ,? ) ?Strong

Structure-preserving cryptography Groups G1,G2,G? with pairing ?:G1 G2 G? 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 ElGamal encryption, Groth-Sahai proofs, etc.

Structure-preserving signatures Setup describes bilinear group and group elements in G1,G2 Verification key adds group elements in G1,G2 Messages consist of group elements in G1,G2 Signatures consist of group elements inG1,G2 Verifier uses generic bilinear group operations to check signature

Fully structure-preserving signatures Secret keys consist of group elements in G1,G2 Can I get a certificate? Prove to me that you know the secret key. ??,? ???? NIZK proof of knowledge with respect to group elements, so helpful if secret key consists of group elements

Large messages Wish to sign ? elements Signature size plus verification key size must provably be ( ?) elements Structure preserving signature scheme for vectors Has disadvantage that public key is of size ? Certify a verification key for signing ? elements and use it ? times Has disadvantage that each signature is at least 3 group elements, so total size is 3 ? or more

Our contribution For ? = 1 they match optimal size of 3 elements and 2 verification equations Combined signature schemes Randomizable & strongly unforgeable signatures Secure in generic bilinear group model Asymmetric pairings (type III) Large messages of ? = ?? elements Verification key size Signature size Verification equations Abe et al. 2015 3? + 3? + 11 ? + 3? + 11 ? + 5 Structure-preserving ? 2 + ? ? + 1 Fully structure preserving 1 ? + ? + 1 ? + 1

Bilinear group setup ?,G1,G2,G?,? ,?,? Gen(1?) Type III: G1 G2 and no efficient isomorphisms Notation We will write ?1 for ??, ?2for ??, ?? for ? ?,?? We write group operations additively ??+ ? ??= ? + ??? We will write the pairing as a multiplication ?1?2= ??? This allows us define operations over vectors and matrices of group elements in a natural way ?1?2= ???

Randomizable structure-preserving signature ?? = ? G1 ? = 1 G1,1 + ? G2 Setup 1? ?,G1,G2,G?,?, 11, 12, ?2 ; ? ?? KeyGen ?? ??,?? ?? = ([?]1, ?1) SignRand??, ?2 ( ?1, ?2, ?2) ? ?? ?2=1 ? ?1 2+ ?2 ?2=1 ? ?,1 ?2+ ? ?2 VfyRand(??, ?2, ?1, ?2, ?2) Check ?1?2= 11?1 2+ ?112 Check ?1 ?2= ?,1 ? ? 1 ?? ?? = ?,? ?? ? ? ? ?? Randomization 1=1 ? ??1 ? ? 2= ? ?2 2= ? ?2 1?2+ ?1 ?2

Intuition ?1?2= 11?1 2+ ?112 ?1 ?2= ?,1 The first equation prevents a forgery from the verification key alone The second set of equations incorporate the message elements There are ? equations, each involving one column of ?. The role of the (?,1) is to scale each row vector of ? to prevent attacks with linear combinations within a column in a signature Each signature has its own randomness ? Makes it hard to use linear combinations of signatures 1?2+ ?1 ?2

Strong existential unforgeability Setup 1? ?,G1,G2,G?,?, 11, 12, ?2 ; ? ?? KeyGen ?? ??,?? ?? = ([?]1, ?1) SignStrong??, ?2 ( ?1, ?2, ?2) ? ?? ?2=1 ? ?1 2+ ?2 ?2=1 ? ?,1 ?2+ ? ?2+ ? ?21 VfyStrong(??, ?2, ?1, ?2, ?2) Check ?1?2= 11?1 2+ ?112 Check ?1 ?2= ?,1 ? ? 1 ?? ?? = ?,? ?? ? ? ? ?? 1?2+ ?1 ?2+ ?1?21

Fully structure-preserving signatures Why does the previous signature scheme not have signing keys with group elements? ?1, ?2, ?2 SignRand??, ?2 ? ?? ?2=1 ?1 2+ ?2 ? ?2=1 Do not know discrete logarithms of ?2 so need to know ? in order to compute ?2 Idea: Let the signer pick ? when signing ?,1 ?2+ ? ?2 ?

Fully structure-preserving signatures ?? = 1 G1 ? = ? G1,1 + ? G2 Setup 1? ?,G1,G2,G?,?, 11, 12, ?2, ?2 ?? = ?1 SignRand??, ?2 ( ?1, ?1, ?2, ?2) ? ?? ?2=1 ? ?1 2+ ? x2+ ?2 ?2=1 ? ?,1 ?2+ ? ?2 VfyRand(??, ?2, ?1, ?2, ?2) Check ?1?2= 11?1 2+ ?1 ?2+ ?112 Check ?1 ?2= ?,1 2) ? ? ?? = ( ?2, ? ?2, ? ?2, ?2 ? ?? ? 1;? ?? Randomization ? 1= ?1+ ? ?1 ? 1= ? 2= ?( ?2+ ? ?2) ? 1 ??1 2= ?( ?2+ ?,0 ?2) 1?2+ ?1 ?2

Fully structure-preserving signature scheme Setup 1? ?,G1,G2,G?,?, 11, 12, ?2, ?2 ?? = ?1 SignStrong??, ?2 ( ?1, ?1, ?2, ?2) ? ?? ?2=1 ? ?1 2+ ? ?2+ ?2 ?2=1 ? ?,1 ?2+ ? ?2+ ??21 VfyStrong(??, ?2, ?1, ?2, ?2) Check ?1?2= 11?1 2+ ?1 ?2+ ?112 Check ?1 ?2= ?,1 2) ? ? ?? = ( ?2, ? ?2, ? ?2, ?2 ? ?? ? 1;? ?? 1?2+ ?1 ?2+ ?1?21

Summary Combined signature schemes Randomizable & strongly unforgeable signatures Secure in generic bilinear group model Asymmetric pairings (type III) Large messages of ? = ?? elements Verification key size Signature size Verification equations Structure-preserving ? 2 + ? ? + 1 Fully structure preserving 1 ? + ? + 1 ? + 1