<p>Andrew Poelstra suggests that:</p>

<pre><code>R' = R + alpha*G + beta*G
</code></pre>

<p>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</p>

CC BY-SA 4.0
2019-02-14T17:28:43.427Z
2019-02-14T17:28:43.427Z
Ronald Smith
<p>Here, sipa proposes a standardization of schnorr signatures: <a href="https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki" rel="nofollow noreferrer">https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki</a></p>

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

<p>After implementing <code>sign()</code> and <code>verify()</code> according to that document, I attempted to implement blind signatures.</p>

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

<p>Here's my pseudocodey impl:</p>

<pre><code>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 // &lt;-- Fails 50% here
    return false if R.x !== r
    return true
}
</code></pre>

<p>Here's the test that will fail 50% of the time:</p>

<pre><code>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)
</code></pre>

<p>The spec's <code>sign()</code> uses <code>nonce = jacobi(y) === 1 ? nonce : curve.N - nonce</code> to force a quadratic residue <code>y</code>, and I would assume my test fails because 50% of the time it generates a non-residue <code>y</code>. 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.</p>

CC BY-SA 4.0
2019-02-15T04:21:39.687Z
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
<signature><schnorr-signatures>
Are sipa's standardized schnorr signatures incompatible with blind signatures?
cantaloa
# Are sipa's standardized schnorr signatures incompatible with blind signatures?

(Asked by: username_0 on 2019-02-14)

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.

**Tags:** signature, schnorr-signatures

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2019-02-14. Score: 1 | Accepted answer

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


---

