CSIFISH — Proof of Concept Implementation

This repository contains a proof-of-concept (PoC) implementation of the CSI-Fish post-quantum isogeny-based digital signature scheme.

The CSI-Fish scheme is described in the paper:

CSI-FiSh: Efficient Isogeny based Signatures through Class Group Computations
Ward Beullens, Thorsten Kleinjung, Frederik Vercauteren (2019)
ePrint: 2019/498 :contentReference[oaicite:0]{index=0}

---

Overview

CSI-Fish is a signature scheme built atop the CSIDH class group action. It uses multiple public key curves (or a Merkle-committed set of curves) in a Fiat–Shamir-style construction to attain strong soundness with efficient signing and verification.

This PoC implements two variants of CSI-Fish:

• Simple Variant — a direct multi-public-key variant (no Merkle tree)
• Merkle Variant — a variant that commits to all public keys with a Merkle tree and only reveals needed ones during signing

---

Features

• Implemented for use inside SageMath (Sage + Python).
• Uses a CSIDH group action for key generation and signing.
• Supports multiple parameter sets via the PARAMS dictionary.
• Implements:
  • keygen() → generate secret/public keys.
  • Sign(message) → create a signature.
  • Verify(message, signature) → verify a signature.

---

Requirements

• SageMath ≥ 9.x
• Python 3 (bundled with SageMath)

---

Usage

Simple Variant

load('CSIFISH.sage')

csifish = CSIFISH(PARAMS["S2_1_t56"])

# Key Generation
key_simple = csifish.keygen()

# Signing
sig = csifish.Sign("hello")

# Verifying
assert csifish.Verify("hello", sig)
assert not csifish.Verify("helloo", sig)

Merkle Variant

load('CSIFISH.sage')

# Instantiate CSIFISH with parameters (Merkle variant)
csifish = CSIFISH(PARAMS["M2_8_t13"])

# Key generation
key_merkle = csifish.keygen()

# Signing
sig = csifish.Sign("hello")

# Verification
assert csifish.Verify("hello", sig)
assert not csifish.Verify("helloo", sig)

Parameter Sets

The scheme provides predefined parameter sets in the PARAMS dictionary.
The values are taken from the CSI-FiSh paper (ePrint 2019/498), Tables 3 and 4 (excluding benchmark times).

---

Simple Variant (no Merkle tree)

S	t	k	sk	pk	sig
2¹	56	16	16 B	128 B	1880 B
2²	38	14	16 B	256 B	1286 B
2³	28	16	16 B	512 B	956 B
2⁴	23	13	16 B	1 KB	791 B
2⁶	16	16	16 B	4 KB	560 B
2⁸	13	11	16 B	16 KB	461 B
2¹⁰	11	7	16 B	64 KB	395 B
2¹²	9	11	16 B	256 KB	329 B
2¹⁵	7	16	16 B	2 MB	263 B

---

Merkle Variant (with Merkle tree)

S	t	k	sk	pk	sig
2⁸	13	11	8 KB	32 B	1995 B
2¹⁰	11	7	32 KB	32 B	2086 B
2¹²	9	11	128 KB	32 B	2022 B
2¹⁵	7	16	1 MB	32 B	1953 B
2¹⁸	6	14	8 MB	32 B	1990 B

---

Field Descriptions

• S — number of secret keys (and corresponding public keys).
• t — number of rounds (parallel repetitions).
• k — auxiliary parameter used in challenge selection.
• sk — secret key size.
• pk — public key size.
• sig — signature size.