
-------------------------------- 
RYDE: a Digital Signature scheme
--------------------------------


1. SUBMISSION OVERVIEW 
----------------------

Both reference implementation and optimized implementation provided for this 
submission are the same. The six parameters sets denoted respectively RYDE-128F, 
RYDE-128S, RYDE-192F, RYDE-192S, RYDE-256F and RYDE-256S are provided as explained 
in the supporting documentation. Each parameter set folder is organized as follows:

- bin/: Files generated during compilation
- doc/: Technical documentation of the scheme
- lib/: Third party libraries used 
- src/: Source code of the scheme  
- doxygen.conf: Documentation configuration file
- Makefile: Makefile


2. INSTALLATION INSTRUCTIONS 
----------------------------

2.1 Requirements

The following softwares and librairies are required: gcc and openssl.

2.2 Compilation Step

Let X denotes 128, 192 or 256 depending on the parameter set considered. RQC
can be compiled in three differents ways:

- Execute make rydeX to compile a working example of the scheme. Run bin/rydeX to
  execute the scheme.
- Execute make rydeX-kat to compile the NIST KAT generator. Run bin/rydeX-kat to
  generate KAT files.
- Execute make rydeX-verbose to compile a working example of the scheme in
  verbose mode. Run bin/rydeX-verbose to generate intermediate values.

During compilation, the following files are created inside the bin/build
folder:

- SimpleFIPS202.o: SHAKE implementation (from XKCP project)
- KeccakHash.o: SHAKE/SHA3 implementation (from XKCP project)
- KeccakSponge.o: Sponge construction required in SHAKE/SHA3 implementation 
  (from XKCP project)
- KeccakHashtimes4.o: SHAKE/SHA3 (4 in parallel) implementation (from XKCP project)
- KeccakSpongetimes4.o: Sponge construction required in SHAKE/SHA3 (4 in parallel) 
  implementation (from XKCP project)
- randombytes.o: NIST randombytes implementation
- seedexpander.o: SHAKE-based seed expander implementation
- rbc_elt.o: Functions to manipulate finite fields elements.
- rbc_mat.o: Functions to manipulate matrices.
- rbc_qpoly.o: Functions to manipulate q-polynomials.
- rbc_vec.o: Functions to manipulate vectors.
- rbc_vspace.o: Functions to manipulate vector spaces.
- mpc.o: Functions to perform the Multi-Party-Computation (MPC) using the Hypercube 
  technique.
- parsing.o: Functions to parse public key, secret key and signature of the scheme.
- tree.o: Functions to construct seed trees and partial trees.
- keypair.o: The RYDE key pair generation (either in normal mode or verbose mode).
- signature.o: The RYDE signing procedure (either in normal mode or verbose mode).
- verification.o: The RYDE verifying procedure (either in normal mode or verbose mode).
- sign.o: The RYDE DS scheme (either in normal mode or verbose mode).


3. DOCUMENTATION GENERATION 
---------------------------

3.1 Requirements

The following softwares are required: doxygen and bibtex.

3.2 Generation Step

- Run doxygen doxygen.conf to generate the code documentation
- Browse doc/html/index.html to read the documentation


4. ADDITIONAL INFORMATIONS 
--------------------------

4.1 Implementation overview

The RYDE scheme is defined in the api.h and parameters.h files and implemented in sign.c.
The latter is based on the MPC construction of [1] using the Hypercube techniques from [2], 
which is defined in mpc.h and implemented in mpc.c.
The files rbc.h, rbc_elt.h, rbc_mat.h, rbc_qpoly.h, rbc_vec.h, rbc_vspace.h, rbc_elt.c, 
rbc_mat.c, rbc_qpoly.c, rbc_vec.c and rbc_vspace.c provide the functions performing the 
various operations over finite fields required by the scheme.
As public key, secret key and signature can manipulated either with theirs mathematical 
representations or as bit strings, the files parsing.h and parsing.c provide functions to 
switch between these two representations.
Finally, the files hash_fips202.h and seedexpander_shake.h (inside the src/wrapper), 
randombytes.h, randombytes.c, along with the files in the XKCP folder (inside the lib/ folder),  
provides SHAKE and SHA3 implementations as well as the NIST random functions.

4.2 Finite field interface

RYDE is a rank-based scheme and as such heavily relies on finite field arithmetic.
We have provided an interface for finite fields (through files rbc.h, rbc_elt.h, mat.h, 
rbc_qpoly.h, rbc_vec.h and rbc_vspace.h) describing the various operations required by 
the scheme. 
In the context of our ffi interface, a finite field always describes an extension of a 
binary field namely a finite field of the form GF(2^m).

- rbc.h: Constants that defines the considered finite field ;
- rbc_elt.h: Functions to manipulate elements of GF(2^m) ;
- rbc_mat.h: Functions to manipulate matrices over GF(2^m);
- rbc_qpoly.h: Functions to manipulate q-polynomials over GF(2^m) ;
- rbc_vec.h: Functions to manipulate vectors over GF(2^m) ;
- rbc_vspace.h: Functions to manipulate subspaces of GF(2^m) ;

In our reference implementation, the considered fields are GF(2^31), GF(2^37) and GF(2^43) 
for RYDE-128, RYDE-192 and RYDE-256.

4.3 Public key, secret key, ciphertext and shared secret

The public key, secret key and signature are respectively composed of (h, y), (x) and 
(sm, m). 
In order to shorten the keys, the public key is stored as (seed1, y) and the secret key 
is stored as (seed2).


5. REFERENCES 
-------------

[1] Thibauld Feneuil. Building MPCitH-based Signatures from MQ, MinRank, Rank SD and PKP.
Cryptology ePrint Archive, Report 2022/1512, 2022.

[2] Carlos Aguilar-Melchor, Nicolas Gama, James Howe, Andreas Hülsing, David Joseph, 
Dongze Yue. The Return of the SDitH. Advances in Cryptology - EUROCRYPT 2023, LNCS 14008, 564-596.

