sdiehl/aos-signature

Abe-Ohkubo-Suzuki Linkable Ring Signatures

A ring signature, also know as a Spontaneous Anonymous Group (SAG) or 1-out-of-n signature, convinces a verifier that a message is signed by any member in a group of n independent signers without allowing the verifier to identify who the signer was.

Abe-Ohkubo-Suzuki Ring Signatures

In their paper, "1-out-of-n Signatures from a Variety of Keys"[1], Abe, Ohkubo and Suzuki (AOS) present a method to construct a 1-out-of-n signature scheme that allows mixture use of different flavours of keys at the same time.

Linkable Spontaneous Anonymous Group (LSAG) Signature

Liu, et al.[2] add the property of linkability to ring signatures. Linkability means that two signatures by the same signer can be identified as such, but the signer remains anonymous. It adds the feature of claimability, which allows a signer to claim responsibility by providing proof of having generated a given signature.

A LSAG signature scheme satisfies three properties:

• Anonymity: A signer cannot be distinguished from a pool of t commitments (public keys).
• Spontaneity: No group secret, group manager of secret sharing setup stage.
• Linkability: Two signatures by the same signer can be linked.

A LSAG Signature Scheme over elliptic curves

It consists of two parts: signature generation and signature verification. Let L = {y₀, ..., y_t-1} be a list of t public keys. Let H:{0, 1}* -> Z_n where H is a cryptographic hash function and n is the order of the elliptic curve over a finite field F_q. For i ∈ {0, ..., t-1}, each user i has a distinct public key y_i and a private key x_i.

Signature Generation

Let k ∈ {0, ..., t-1} be the position of the prover's public key in the list L of public keys. Let x_k be its private key. The LSAG signature of a message m ∈ {0,1}* is generated by the following steps:

1. Compute h by encoding the hash of the public keys to a point in the curve, while hiding its discrete logarithm, and y = [x_k] * h. Both computations are the product of a scalar and a point in the curve.

2. Select u ∈ Z_n and compute the first challenge ch_k+1 = H(L, y, m, [u] * g, [u] * h)

3. For i in {k+1, ..., t-1, 0, ... k-1}, choose s_i ∈ Z_n and compute the remaining challenges: ch_i+1 = H(L, y, m, [s_i] * g + [ch_i] * y_i, [s_i] * h + [ch_i] * y)

4. With the last ch_k computed, calculate s_k = (u - x_k * ch_k) mod n

The signature is (ch₀, [s₀, ..., s_t-1], y).

Signature Verification

Given a message m, a signature of a message (ch₀, [s₀, ..., s_t-1], y) and a list of public keys L, an honest verifier checks a signature as follows:

1. For i in {0, ..., t-1} compute ch_i+1 = H(L, y, m, [s_i] * g + [ch_i] * y_i, [s_i] * h + [ch_i] * y), where h = [H(L)] * g.

2. Check whether c₀ is equal to H(L, y, m, [s_t-1] * g + [ch_t-1] * y_t-1, [s_t-1] * h + [ch_t-1] * y)

testSignature
  :: ECC.Curve
  -> Int
  -> ByteString
  -> IO Bool
testSignature curve nParticipants msg = do
  -- Generate public and private keys
  (pubKey, privKey) <- ECC.generate curve
  -- Generate random foreign participants
  extPubKeys <- genNPubKeys curve nParticipants
  -- Position of the signer's key in the set of public keys
  k <- fromInteger <$> generateBetween 0 (toInteger $ length extPubKeys - 1)
  -- List of public keys
  let pubKeys = insert k pubKey extPubKeys
  -- Sign message with list of public keys and signer's key pair
  signature <- sign pubKeys (pubKey, privKey) msg
  -- Verify signature
  pure $ verify pubKeys signature msg

References:

1. M. Abe, M. Ohkubo, K. Suzuki. "1-out-of-n Signatures from a Variety of Keys", 2002
2. K. Liu, K. Wei, S. Wong. "Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups", 2004

Notation:

1. [b] * P: multiplication of a point P and a scalar b over an elliptic curve defined over a finite field modulo a prime number

License

Copyright 2018-2020 Adjoint Inc

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

aos-signature's Issues

Key image can be computed from public key

As h = H(L) * g, yk = xk * g, and y = xk * h, we can transform y to y = xk * H(L) * g = H(L) * xk * g = H(L) * yk which means that y, the key image, can be computed from the public key (and the list of all public keys). This makes identifying the signer of a ring signature trivial, as you simply need to check if the key image matches each of the public keys.

To fix this, you need to use a function that computes a curve point directly from a hash. There are several potential algorithms for this, such as:

• https://tools.ietf.org/html/draft-irtf-cfrg-vrf-02#section-5.4.1
• https://tools.ietf.org/html/draft-sullivan-hash-to-curve-00

It also seems that I'm not the first person to find this issue in other implementations of the same algorithm: https://web.archive.org/web/20160218042108/shnoe.wordpress.com/2016/02/11/de-anonymizing-shadowcash-and-oz-coin/

aos-signature fails to build on GHC 8.6.1

aos-signature currently fails to build on GHC 8.6.1 with the following errors:

src/LSAG.hs:54:7: error:
    • Could not deduce (Control.Monad.Fail.MonadFail m)
        arising from a do statement
        with the failable pattern ‘(sK1 : sK2ToPrevSK)’
      from the context: MonadRandom m
        bound by the type signature for:
                   sign :: forall (m :: * -> *).
                           MonadRandom m =>
                           [ECDSA.PublicKey]
                           -> (ECDSA.PublicKey, ECDSA.PrivateKey)
                           -> ByteString
                           -> m (Integer, [Integer], ECC.Point)
        at src/LSAG.hs:(42,1)-(47,38)
      Possible fix:
        add (Control.Monad.Fail.MonadFail m) to the context of
          the type signature for:
            sign :: forall (m :: * -> *).
                    MonadRandom m =>
                    [ECDSA.PublicKey]
                    -> (ECDSA.PublicKey, ECDSA.PrivateKey)
                    -> ByteString
                    -> m (Integer, [Integer], ECC.Point)
    • In a stmt of a 'do' block:
        (sK1 : sK2ToPrevSK) <- replicateM (participants - 1)
                                 $ generateBetween 1 (n - 1)
      In the expression:
        do (sK1 : sK2ToPrevSK) <- replicateM (participants - 1)
                                    $ generateBetween 1 (n - 1)
           u <- generateBetween 1 (n - 1)
           let chK1 = genChallenge curve pubKeys y msg (gu u) (hu u)
           let reversedChKToChK1 = runChallenges k sK1 chK1 sK2ToPrevSK u y h
               chK = head reversedChKToChK1
           ....
      In a case alternative:
          Just k
            -> do (sK1 : sK2ToPrevSK) <- replicateM (participants - 1)
                                           $ generateBetween 1 (n - 1)
                  u <- generateBetween 1 (n - 1)
                  let chK1 = ...
                  ....
   |
54 |       (sK1:sK2ToPrevSK) <- replicateM (participants - 1) $ generateBetween 1 (n - 1)
   | 

cf. commercialhaskell/stackage#4119