An independent Python implementation of the MEBS (Matrix Equivalence Blind Signatures) scheme from:
Veronika Kuchta, Jason T. LeGrow, Edoardo Persichetti
Post-quantum (partially) blind signatures from matrix code equivalence
Cryptography and Communications, 2026
DOI: 10.1007/s12095-026-00879-x
MEBS is a post-quantum blind signature scheme built on the MEDS group action (Matrix Equivalence Digital Signatures). It is conceptually similar to the isogeny-based CSI-Otter scheme but avoids the need for a quadratic twist by including additional information in the public key and commitment phase.
Security notice: This is a research implementation. The toy parameters (
PARAMS_TOY) are not secure. UsePARAMS_NIST1for NIST Level I estimates, and read Section 7 of the paper before deploying anything.
A blind signature scheme lets a user obtain a signer's signature on a message without revealing the message to the signer. MEBS achieves this using the hardness of the Modified Inverse Matrix Code Equivalence (MIMCE) problem, which is believed to resist attacks by quantum computers.
The scheme is built from a 3-round interactive Sigma protocol between signer (Alice) and user (Bob):
Alice (sk, pk) Bob (pk, msg)
─────────────────────────────────────────────────────────
S1: commit ──── ρ_S1 (commitments) ────►
U1: blind
◄─── ρ_U (blinded chal) ────
S2: respond ──── ρ_S2 (responses) ────►
U2: unblind → σ
Verify(pk, msg, σ)
The security proof reduces one-more unforgeability to MIMCE under the Kastner–Loss–Xu framework in the random oracle model.
Requires Python 3.10+ and NumPy.
git clone https://github.com/<you>/PQBS-partial
cd PQBS-partial
pip install numpy pytestpython demo.pyMEBS – Matrix Equivalence Blind Signatures (Demo)
Parameters: m=4, n=4, k=2, p=127, kappa=5
[KeyGen] delta=0 (0.45s)
[S.1] Signer commitment sent (0.01s)
[U.1] User blinded challenge sent (0.01s)
msg=b'Hello, post-quantum world!'
[S.2] Signer response sent (0.00s)
[U.2] User unblinded signature (0.01s)
[Verify] Valid=True
[Verify] Wrong message valid=False (expected False)
[Verify] Tampered sig valid=False (expected False)
All checks passed!
from mebs import MEBS, PARAMS_TOY, PARAMS_NIST1
scheme = MEBS(PARAMS_TOY) # swap for PARAMS_NIST1 for larger parameters
# Key generation
pk, sk = scheme.keygen()
# --- Blind signing protocol ---
msg = b"my message"
# Round 1: signer commits
signer_state, rho_S1 = scheme.signer_commit(sk, pk)
# Round 2: user blinds the message
user_state, rho_U = scheme.user_blind(pk, msg, rho_S1)
# Round 3: signer responds
rho_S2 = scheme.signer_respond(sk, signer_state, rho_U, pk)
# User unblinds to obtain the signature
sigma = scheme.user_unblind(pk, user_state, rho_S2, msg)
# Verification (by anyone with the public key)
assert scheme.verify(pk, msg, sigma)| Name | m | n | k | p | κ | Security |
|---|---|---|---|---|---|---|
PARAMS_TOY |
4 | 4 | 2 | 127 | 5 | None – testing only |
PARAMS_NIST1 |
46 | 46 | 46 | 8191 | 30 | NIST Level I estimate |
The NIST Level I parameters follow the analysis of Gilchrist et al. (2025) cited in Section 7 of the paper. The bit security estimate uses the block Wiedemann XL algorithm runtime formula given in Equation (7).
mebs/
field.py Finite field matrix arithmetic (inversion, A^(c), symmetric sampling)
matrix_code.py MEDS group action (A,B)*C = ACB^T, RREF canonicalisation
hash_utils.py ROM hash H:{0,1}*→{-1,1}^κ and the ⊙ operation
params.py Parameter sets
mebs.py Full MEBS protocol (Fig. 10 of the paper)
tests/
test_mebs.py 15 unit tests (field, group action, hash, end-to-end)
demo.py Interactive demo
python -m pytest tests/ -vAll 15 tests should pass in under 2 seconds on toy parameters.
Group action. The MEDS group action is G = GL_m(F_p) × GL_n(F_p) acting on [m×n, k] matrix codes by (A, B) ∗ C = {ACB^T : C ∈ C}. Codes are represented by their generator matrices in RREF (plain reduced row echelon form, without column reordering). Column reordering — which is standard for [I|P] systematic form — is deliberately avoided: it disrupts the vectorised layout and breaks composition of group actions when one code is used as input to a subsequent action.
Notation A^(c). Following Section 2.5 of the paper, for c ∈ {−1, 1}:
- A^(1) = A
- A^(−1) = A^{−T} (inverse transpose)
Symmetric/antisymmetric matrices. Secret keys are drawn from S_k(F_p) = S_k^+(F_p) ∪ S_k^-(F_p), where symmetric matrices satisfy A^T = A and antisymmetric ones satisfy A^T = −A. Antisymmetric matrices have zero diagonal (required for char ≠ 2) and are only invertible for even k.
Hash function. The random oracle H is instantiated with SHA-256 expanded to κ bits via a counter-based XOF.
- Public key well-formedness proofs (Section 3 / Figures 6, 8): the NIZKs that prove (X^(1), X^(−1)) is a valid public key. In this implementation the signer is assumed honest for key generation.
- Partially blind signatures (Section 5 / Figure 14): the extension that lets signer and user agree on public auxiliary information
info. - Witness-extractable keyspace (Section 6): the modified keyspace using formally positive definite matrices that enables full witness extractability.
This is an independent implementation and is not affiliated with or endorsed by the authors of the paper. The paper is published under a Creative Commons Attribution 4.0 International License.
If you use this in research, please cite the original paper:
@article{kuchta2026mebs,
author = {Kuchta, Veronika and LeGrow, Jason T. and Persichetti, Edoardo},
title = {Post-quantum (partially) blind signatures from matrix code equivalence},
journal = {Cryptography and Communications},
year = {2026},
doi = {10.1007/s12095-026-00879-x}
}The implementation code in this repository is released under the MIT License.
The underlying paper is © The Author(s) 2026, published under CC BY 4.0.