[Cfrg] Bign

["Agievich Sergei V." <[e-mail]>]

Dear CFRG members,

In the course of the debates on the new signature scheme let me share
information about Bign, that is, a Schnorr-type signature scheme which
we developed a few years ago. In 2013 Bign was adopted as the
Belarusian standard STB 34.101.45 and now is widely used in our
(Republic of Belarus) government and commercial PKI systems.

I hope that our experience will be useful for CFRG. A sketch of our
design is provided below. You can find further details in the full
specification http://apmi.bsu.by/assets/files/std/bign-spec29.pdf
(unfortunately, in Russian only right now) and in the reference
implementation https://github.com/agievich/bee2 (bign.h, bign.c).

Parameters
----------

l \in {128, 192, 256} -- a security level;

q -- a 2l-bit prime number;

G -- a generator of an Abelian group <G> of order q. 
Let O be the unity (zero) of this group; 

H -- an external hash function {0,1}^* -> {0,1}^{2l};

OID(H) -- an octet string which uniquely identify H
(in fact, an ASN.1 object identifier);

h -- an internal hash function {0,1}^* -> {0,1}^l.

Binary words are interpreted as unsigned integers (under little-endian
conventions) and otherwise. Residues mod q and nonzero elements of <G>
are represented by 2l-bit words.

Private key
-----------

d -- a secret random / pseudorandom element of {1, 2,..., q - 1}. 

Public key
----------

Q = dG.

Message to be sign
------------------

X \in {0,1}^*.

Signing
-------

1 Choose k in random (or pseudorandom, see later) from {1, 2,..., q - 1}. 
2 R <- kG.
3 s0 <- h(OID(H) || R || H(X)).
4 s1 <- (k - H(X) - (s0 + 2^l)d) mod q.
5 s <- s0 || s1.
6 Return s.

Verification 
------------

1 If |s| != 3l return 0.
2 Parse s and extract s0 and s1: s = s0 || s1, |s0| = l, |s1| = 2l.
3 If s1 >= q return 0.
5 R <- (s1 + H(X))G + (s0 + 2^l)Q.
6 If R = O return 0.
7 If h(OID(h) || R || H(X)) != s0 return 0.
8 Return 1.

Design rationale
----------------

1 Short signatures. 

The most Schnorr-type signature schemes use 2l bits for s0 and 2l bits
for s1. We apply so-called Schnorr's compression and truncate s0 to l
bits. Truncation is not only shorten total length of signature but also
speed-up verification: it takes only 1.5 exponentiation in <G> and
closely approaches signing time (1 constant-time exponentiation).

We use similar short signatures in our instantiations of MQV / STS
protocols (see http://apmi.bsu.by/assets/files/std/bake-spec19.pdf) 
and in a Schnorr-type identity based signature scheme
(http://apmi.bsu.by/assets/files/std/bign-spec29.pdf, appendix B).

2 Pre-hashing. 

Instead of the classical direct-hashing during the calculation of s0: 
	s0 <- h(R || X),
we use the pre-hashing approach:
	s0 <- h(OID(H) || R || H(X)).
Pre-hashing protects against multiple-target preimage attacks based on
consecutive extensions of X and described recently by D. Bernstein.
Additionally, pre-hashing facilitates integration with existing APIs
and data formats.

3 Whitening. 

The second part of signature (s1) is whitened by Y = H(X). In such
manner we block the signature collisions. Such a collision can be
found by a malicious signatory in time about 2^{l/2}. Whitening makes
the overall signature s a safe checksum of expected strength 2^l.

4 Hashing of Q.

Let s be a valid signature of X under Q. An adversary can change Q by
Q' and s by s' so that s' will be the valid signature of X under Q'.

To protect against this attack we can hash Q during the calculation of s0:
 	s0 <- h(OID(H) || R || Y || Q).
But we reject such a solution because, in our opinion, hashing of Q
duplicates a standard proof-of-possession during public key
distribution: any signature scheme will be weak with weak key
distribution; hashing of Q is useless with strong key distribution.
                                                         
5 Deterministic signature.

The ephemeral public key k can be generated using either TRNG or PRNG.
In the latter case k is generated by the special deterministic
algorithm genk.

This algorithm takes q, d, OID(H), Y = H(X) and arbitrary additional
data t \in {0,1}^*.

Firstly, OID(H), d and t are hashed using a function 
h_{256}: {0,1}^* -> {0,1}^{256}. This function is an extension of h 
(in fact, h is a restriction of h_{256}). The resulting hash value 
	\theta <- h_{256}(OID(H) || d || t)
is used as a key to encrypt Y:
	k <- Encr_1(Y, \theta).
Encryption is continued
	k <- Encr_2(k, \theta), 
	k <- Encr_3(k, \theta), ...
until k \in {1, 2, ..., q - 1}.

Here {Encr_i, i = 1, 2,...} is a family of symmetric encryption
functions: Encr_i(B, theta) is a result of encryption of B \in
{0,1}^{2l} under the key \theta \in {0,1}^{256}. Fortunately, we had
standardized a keywrap encryption mode which was transformed into
{Encr_i}.

Due to repeating encryptions genk isn't a constant-time algorithm. But
in practical settings q is very close to 2^{2l} and chances for even
second encryption are enough small.

We didn't use the constant-time constructions like
"wide-hash-then-reduce-mod-q" because of their quite heaviness.

6 Sign + transport.

In our standard STB 34.101.45 the pair (d, Q) can be used not only in
the signature algorithms but also for key transport (encryption) of
ElGamal type.

We consider the tandem "sign + transport" controlled by a single key pair as
a very useful cryptographic primitive. For example, we can imagine a key-centric
architecture like Bitcoin in which addresses -- public keys -- support both 
data authenticity and confidentiality. 

Best regards,
Sergey Agievich
Research Institute for Applied Problems of Mathematics and Informatics
Belarusian State University