# aos-signature: An implementation of the AOS signatures

[ cryptography, library ] [ Propose Tags ]

An implementation of 1-out-of-n signatures from a variety of keys

Versions [faq] 0.1.0, 0.1.1 base (>=4.7 && <5), bytestring, cryptonite, memory, mtl, protolude (>=0.2), random [details] LicenseRef-Apache Adjoint Inc (info@adjoint.io) Cryptography https://github.com/adjoint-io/aos-signature#readme https://github.com/adjoint-io/aos-signature/issues head: git clone https://github.com/adjoint-io/aos-signature by sdiehl at Sat Nov 10 08:17:15 UTC 2018 LTSHaskell:0.1.1, NixOS:0.1.1, Stackage:0.1.1 723 total (59 in the last 30 days) (no votes yet) [estimated by Bayesian average] λ λ λ Docs available Last success reported on 2018-11-10

## Modules

[Index] [Quick Jump]

## Flags

NameDescriptionDefaultType
optimized

Perform compiler optimizations

DisabledAutomatic
static

DisabledAutomatic

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

#### Maintainer's Corner

For package maintainers and hackage trustees

[back to package description]

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.

### A LSAG Signature Scheme over elliptic curves

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

### 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<sub>k</sub> be its private key. The LSAG signature of a message m ∈ {0,1}* is generated by the following steps:

1. Compute h = [H(L)] * g, where g is the generator of the elliptic curve, and y = [x<sub>k</sub>] * h. Both computations are the product of a scalar and a point in the curve.

2. Select u ∈ Z<sub>n</sub> and compute the first challenge ch<sub>k+1</sub> = H(L, y, m, [u] * g, [u] * h)

3. For i in {k+1, ..., t-1, 0, ... k-1}, choose s<sub>i</sub> ∈ Z<sub>n</sub> and compute the remaining challenges: ch<sub>i+1</sub> = H(L, y, m, [s<sub>i</sub>] * g + [ch<sub>i</sub>] * y<sub>i</sub>, [s<sub>i</sub>] * h + [ch<sub>i</sub>] * y)

4. With the last ch<sub>k</sub> computed, calculate s<sub>k</sub> = (u - x<sub>k</sub> * ch<sub>k</sub>) mod n

The signature is (ch<sub>0</sub>, [s<sub>0</sub>, ..., s<sub>t-1</sub>], y).

### Signature Verification

Given a message m, a signature of a message (ch<sub>0</sub>, [s<sub>0</sub>, ..., s<sub>t-1</sub>], 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<sub>i+1</sub> = H(L, y, m, [s<sub>i</sub>] * g + [ch<sub>i</sub>] * y<sub>i</sub>, [s<sub>i</sub>] * h + [ch<sub>i</sub>] * y), where h = [H(L)] * g.

2. Check whether c<sub>0</sub> is equal to H(L, y, m, [s<sub>t-1</sub>] * g + [ch<sub>t-1</sub>] * y<sub>t-1</sub>, [s<sub>t-1</sub>] * h + [ch<sub>t-1</sub>] * 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

Copyright 2018 Adjoint Inc

you may not use this file except in compliance with the License.
You may obtain a copy of the License at

Unless required by applicable law or agreed to in writing, software
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and