MEDS

Matrix Equivalence Digital Signature

This repository provides the reference implementation of the PQC signature scheme MEDS as submitted to the NIST PQC Signature standardization process.

The website accompanying the MEDS submission is meds-pqc.org.

The submission document with the MEDS specification can be found here.

C Reference Implementation

The reference implementation in directory ref/ can be compiled using the provided Makefile.

The Python script ref/params.py requires python-tabulate:

   pip install tabulate

We provide three programs: test to run at test of key generation, signing, and verification, bench for benchmarking the implementation using several rounds, and KAT_test for computing known answer tests.

The test can be compiled and run by

   make RUN

the benchmark using

   make BENCH

and the KAT test using

   make KAT

The default parameter set is the toy parameter set. Another parameter set can be selected using PARAM, e.g.:

   make RUN PARAM=MEDS9923

A list of available parameter sets can be obtained by:

   ./params.py -l

To run all targets, add _ALL to RUN, BENCH, and KAT, e.g.:

   make RUN_ALL

When the code is compiled with DEBUG defined, exhaustive step-by-step debugging is produced and written to stderr.

The code package of the MEDS NIST submission with dedicated directories for each parameter set can be generated by

   ./NIST.sh

Sage Reference Implementation

The Sage reference implementation in directory sage-ref/ requires PyCryptodome for SHAKE.

Install PyCryptodome by:

   sage --pip install PyCryptodome

A toy example of MEDS can be run using the following command:

   ./meds.sage

A list of the MEDS instances for the parameter set can be obtained with the following command:

   ./meds.sage -l

A specific parameter set can be run by:

   ./meds.sage [PARAMETER SET]

The Sage version can be compared to the C version using the KAT files and the script KAT_check.sage. There is a make target to easily generate and compare KAT files, e.g.:

   make KAT PARAM=MEDS9923
   make KAT_ALL

Requirements:

Tested with SageMath version 9.6.

The Python code files require Python version 3.8 or newer.

Africacrypt 2023

The source code accompanying the Africacrypt 2023 paper:

• Tung Chou, Ruben Niederhagen, Edoardo Persichetti, Tovohery Hajatiana Randrianarisoa, Krijn Reijnders, Simona Samardjiska, and Monika Trimoska: "Take your MEDS: Digital Signatures from Matrix Code Equivalence". Progress in Cryptology - AfricaCrypt 2023. Lecture Notes in Computer Science, Springer, 2023.

is in branch Africacrypt.