Digital Signing Using Multidimensional PRNGs

Using the private and public keys based on the PRNG generator matrix as shown in Shared Public Key using Multidimensional PRNGs, we can use these keys to 'sign' a message in a way that could only feasibly be done by the holder of the private key.

Based on the Schnorr signature algorithm, we adjust this algorithm slightly for use with our PRNG generating matrices. The public information is, ($p$, $bar M$, $bar M^x$). The integer $x$ is a private key known only the the signer.

The signing process

1. The signer creates a random number $k$ between $0$ and $p^d-1$
2. Calculate $r=bar M^k mod p$
3. Concatenate $r$ onto message and calculate hash function $h = Hash(Concatenate(r,msg))$. This hash function can be any good hash function, such as SHA-2 or others.
4. Calculate $s = (k-(x*h)) mod (p^d-1)$
5. The signature is the pair $(h, s)$

Verification process

The verifier knows the senders public key ($bar M$, $bar M^x$, $p$) the message $msg$ and and signature of the message $(h, s)$

1. Calculate $hat r=M^s . (M^x)^h mod p$
2. Preprend $hat r$ onto the message and calculate hash function $hat h = Hash(Concatenate(hat r,msg))$.
3. If $hat h = h$, then the signature is verified