GooSigs are short (~1kB) signatures made using an RSA key that don't reveal which RSA key made the signature. (GooSigs are named for the fact that they build on Groups of unknOwn Order.)

This document describes GooSigs informally, and documents libGooPy, a reference implementation.

protocol.txt describes the mechanics of the protocol; more details are coming soon.

A GooSig can be thought of either as a signature or as a succinct, non-interactive, publicly-verifiable zero-knowledge proof of knowledge of an RSA secret key, where the verifier does not learn the corresponding public key.

Viewed as a zero-knowledge proof scheme:

• A Challenger chooses an RSA public key PK and uses it to compute a challenge, C. (Informally, C does not reveal PK.)

• A Prover who knows the secret key corresponding to PK publishes a statement T and a proof π. (Informally, neither T nor π reveal PK.)

• A Verifier can then check that π is a correct proof corresponding to the challenge C and the statement T.

(In other words: the Challenger knows that C corresponds to PK (i.e., that PK is the Prover's public key), but the Verifier does not learn PK.)

Viewed as a signature scheme:

• A Signer with GooSig public key (C,T) publishes a message M and signature σ.

• A Verifier checks that σ is a valid signature on M for the GooSig public key (C,T).

This repository contains a reference implementation of GooSig called libGooPy. libGooPy is written in Python, and aims to be compatible with CPython 2 and 3, PyPy, and PyPy3.

You can run a few tests with

python -m libGooPy [-a] [niters] 

-a enables all tests (otherwise only end-to-end tests run). niters sets the number of test iterations; 16 is the default.

libGooPy has a relatively simple interface: the GooSigSigner class implements a signer, the GooSigVerifier class a verifier.

__main__.py shows how this interface works:

• First, construct a GooSigSigner object and provide it with the factorization of the Signer's RSA modulus. You can optionally specify a group of unknown order when constructing; see below.

• Next, call GooSigSigner.sign() with the challenge C1, its opening s, and the message msg. The result is a signature.

• Finally, construct a GooSigVerifier object and call GooSigVerify.verify() on the challenge and signature.

You can optionally construct RSAGroupOps objects for the signer and verifier (otherwise a default one will be constructed for you). You must choose a group whose order is unknown to both the prover and the verifier! For this purpose, defs.py provides three RSA moduli with (to our knowledge) unknown factorizations: the RSA-2048 challenge, the RSA-617 (2048-bit) challenge, and the 4096-bit modulus from the (now defunct) AOL Root CA 2 public key (one of the oldest 4096-bit CA keys).

If you do not supply an RSAGroupOps object when constructing the GooSigSigner and GooSigVerifier objects, the default is to use the RSA-2048 challenge.

libGooPy is (C) 2018 Dan Boneh, Riad S. Wahby

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.