3

Here, sipa proposes a standardization of schnorr signatures: https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

For example, sign() returns Sig{R,s} which can be encoded with 64 bytes (R.x || s) where R.y can be disambiguated via quadratic residue.

After implementing sign() and verify() according to that document, I attempted to implement blind signatures.

However, verifying my unblinded signature fails 50% of the time because of the line return false if jacobi(R.y) !== 1 in verify(), enclosed below.

Here's my pseudocodey impl:

type Signature = { Rx: int, s: int }
type Unblinder = { alpha: int, Rx: int }
type BlindedMessage = { challenge: int }
type BlindedSignature = { s: int }

fn blindMessage(nonce: Point, signer: Point, message: bytes): (Unblinder, BlindedMessage) {
    R = nonce
    P = signer
    alpha = rand()
    beta = rand()
    R' = R + alpha*G + beta*P
    // challenge
    c' = int(hash(R'.x || P || message)) % curve.n
    // blinded challenge
    c = c' + beta
    return (Unblinder(alpha, R'.x), BlindedMessage(c))
}

fn blindSign(signer: privkey, nonce: privkey, blindedMessage: BlindedMessage): BlindedSignature {
    c = blindedMessage.challenge
    x = signer
    k = nonce

    s = k + c*x
    return BlindedSignature(s)
}

fn unblind(unblinder: Unblinder, blindedSig: BlindedSignature): Signature {
    Rx = unblinder.Rx
    s = blindedSig.s + unblinder.alpha
    return Signature(Rx, s)
} 

// implemented according to sipa's spec
fn verify(pubkey: Point, message: bytes, sig: Signature): bool {
    pk = pubkey
    m = message
    P = pubkey

    (r, s) = sig
    e = int(hash(r || P || m)) % curve.n
    R = s*G - e*P

    return false if isInfinitePoint(R)
    return false if jacobi(R.y) !== 1 // <-- Fails 50% here
    return false if R.x !== r
    return true
}

Here's the test that will fail 50% of the time:

noncePriv = rand()
signerPriv = rand()
noncePub = noncePriv * curve.G
signerPub = signerPriv * curve.G
message = hash('my message')

// blind
(unblinder, blindedMessage) = blindMessage(noncePub, signerPub, message)

// sign
blindedSig = blindSign(signerPriv, noncePriv, blindedMessage)

// unblind 
sig = unblind(unblinder, blindedSig)

// verify
verified = verify(signerPub, message, sig)

assert(verified)

The spec's sign() uses nonce = jacobi(y) === 1 ? nonce : curve.N - nonce to force a quadratic residue y, and I would assume my test fails because 50% of the time it generates a non-residue y. However, I was unable to figure out where and how to apply this in my blind-related code. None of my efforts had an effect on my 50% pass rate.

  • 3
    Just for the benefit of random people that land on this question: A blind signature constructed this way is insecure if the blind-signer is willing to make multiple blind signatures at the same time. Blind signing must be secured against a one more signature attack based on wagner's algorithm. – G. Maxwell Feb 15 at 4:21
0

Andrew Poelstra suggests that:

R' = R + alpha*G + beta*G

should be put in a loop .. whenever R.x is not a quadratic residue. You can change beta and this should give you compat with sipa's scheme with no security, privacy loss or blind-sig-linkability loss

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.