# Need help in proving of disproving security of generic partially-blind-signature construction

I have a project where I need to use a linear partially blind signature scheme. I looked at Abe-Okamoto, but I can't easily make it linear. So I looked at Okamoto-Schnorr blind signatures (here and here), which is linear, and came up with a general construction that would suit it.

The idea for the partially-blind construction is that extra public information I is known to both the Signer and the User at the time of verification, and that this information should remain unblinded. To do that, this construction shifts the keys of the Signer by a value dependent on I, which then signs the message with this key. Since I is known to every party, the verifier can do the same shift to go from the original verification key to the one actually needed to verify the signature.

The intuition is that each signer has a globally recognized public key (and corresponding private key) out of which it can derive many other key pairs. Each signature is performed under a different key pair, and the relation between this and the main key pair is bound to the public information. If the signature checks out, then it should be because only the purported signer could have created that shifted key.

There is a possible attack in here. A malicious user may want to obtain a signature under key pair (sk1, pk1) and info I1, and then verify it later under key pair (sk2, pk2) and info I2. This is possible in a naive construction, since the way the shifted key (sk * H(I)) can potentially be arrived at from different combinations. To prevent this, I also modify the message that is actually signed, to include a record of the original key. It is my hope that this would be enough to prevent forgery of signatures. This is precisely where I need some help, though.

But without a proof, there's a good chance there may be something obviously wrong with this scheme. Please let me know if that is the case.

Construction:

Start with a DL-based fully-blind signature scheme (PGen, Gen, Sign, Verify), with this behaviour: (I'm using additive notation)

PGen() --> (G, G1...Gm, q):

• creates a group <G> generated by a generator G1, of order q
• G1 ... Gm are distinct generators of this group, whose relative discrete logs are not known

Gen(1^n) --> (sk, pk):

• sk is a vector of elements in a group G \subset Z_p*: x1, ..., xm
• pk is a linear combination of generators and the secret key: pk = Sum_i=1..m ai * xi * Gi, for some fixed ai (determined by the scheme. For example, in Schnorr-Okamoto, m = 2, a1 = a2 = -1)

Sign(sk | M; pk) --> (M, sig):

• this is an interaction between two parties, the Signer and the User
• the private input of the signer is sk
• the private input of the user is M
• both know the signer's public key (the verification key)

Verify(pk, M, sig) --> ACCEPT or REJECT: - returns ACCEPT if sig is a valid signature of M under key pk

The syntax of a partially-blind scheme is slightly different, as both the signing and the verification include a new parameter. Using the base scheme above, we construct a partially-blind signature scheme (PB_PGen, PB_Gen, PB_Sign, PB_Verify) in this way:

PB_PGen: - this is the same as PGen, with the addition of a choice of Hash function H that maps arbitrary strings into G.

PB_Gen: - this is the same as Gen

PB_Sign(sk; I | M; pk, I):

• private inputs are the same as in Sign.
• I is now a public input to both Signer and User
        - a = H(I)
- sk' = sk * a
- pk' = (sk * a)G = a * pk [if sk is a vector, sk * a denotes the multiplication of every element of the vector by a].
- return Sign(sk'; (pk || M), pk)


PB_Verify(pk, M, I, sig):

    - a = H(I)
- pk' = a * pk
- Return Verify(pk', pk || M, sig)


To prove security, I tried to prove both the partial-blindness and unforgeability with the Games defined in Abe-Okamoto's paper. I think I can prove partial-blindness more or less, but I don't have a clue on how to proceed with unforgeability. I would like to prove the security for the general construction, not a specific instantiation (for example, with Schnorr-Okamoto as the base scheme), but the whole thing about changing signer keys after the game has started confuses me.

For example, if I want to make a reduction for the unforgeability game, then I would do this:

• U* - attacker against the base fully-blind scheme
• W* - adversary that can break the partially-blind scheme

1. U* receives from its environment (sk, pk)
2. U* provides a key pair for W*. For example, it fixes some I* and sends ( sk / H(I*), pk / H(I*) )
3. W* makes signing queries and chooses for each Mi and Ii
4. U* would like to use its environment to respond to these queries, but the responses would happen under several different keys and there is a single value of Ii for which it will be able to reply directly with an answer from the outside.

This means that unless the domain of I is small, U* may never get a useful query from W*. Is there any trick I can use, for example changing keys after W* makes its choice, or having access to a signing oracle where it can choose the key? I don't know of situations where a proof would consider this key shifting and am unaware of how to proceed.