Initial commit

8 files changed, 466 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..3fdc49e
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,6 @@
+# SPDX-License-Identifier: CC0-1.0
+#
+# Copyright (C) 2024 W. Kosior <koszko@koszko.org>
+
+poly_mul
+*.o
diff --git a/.reuse/dep5 b/.reuse/dep5
new file mode 100644
index 0000000..b8585cb
--- /dev/null
+++ b/.reuse/dep5
@@ -0,0 +1,10 @@
+Format: https://www.debian.org/doc/packaging-manuals/copyright-format/1.0/
+Upstream-Name: Post-quantum blind signatures implementation
+Upstream-Contact: W. Kosior <koszko@koszko.org>
+Source: https://git.koszko.org/pq-blind-sigs-impl
+
+# Sample paragraph, commented out:
+#
+# Files: src/*
+# Copyright: $YEAR $NAME <$CONTACT>
+# License: ...
diff --git a/LICENSES/CC0-1.0.txt b/LICENSES/CC0-1.0.txt
new file mode 100644
index 0000000..0e259d4
--- /dev/null
+++ b/LICENSES/CC0-1.0.txt
@@ -0,0 +1,121 @@
+Creative Commons Legal Code
+
+CC0 1.0 Universal
+
+    CREATIVE COMMONS CORPORATION IS NOT A LAW FIRM AND DOES NOT PROVIDE
+    LEGAL SERVICES. DISTRIBUTION OF THIS DOCUMENT DOES NOT CREATE AN
+    ATTORNEY-CLIENT RELATIONSHIP. CREATIVE COMMONS PROVIDES THIS
+    INFORMATION ON AN "AS-IS" BASIS. CREATIVE COMMONS MAKES NO WARRANTIES
+    REGARDING THE USE OF THIS DOCUMENT OR THE INFORMATION OR WORKS
+    PROVIDED HEREUNDER, AND DISCLAIMS LIABILITY FOR DAMAGES RESULTING FROM
+    THE USE OF THIS DOCUMENT OR THE INFORMATION OR WORKS PROVIDED
+    HEREUNDER.
+
+Statement of Purpose
+
+The laws of most jurisdictions throughout the world automatically confer
+exclusive Copyright and Related Rights (defined below) upon the creator
+and subsequent owner(s) (each and all, an "owner") of an original work of
+authorship and/or a database (each, a "Work").
+
+Certain owners wish to permanently relinquish those rights to a Work for
+the purpose of contributing to a commons of creative, cultural and
+scientific works ("Commons") that the public can reliably and without fear
+of later claims of infringement build upon, modify, incorporate in other
+works, reuse and redistribute as freely as possible in any form whatsoever
+and for any purposes, including without limitation commercial purposes.
+These owners may contribute to the Commons to promote the ideal of a free
+culture and the further production of creative, cultural and scientific
+works, or to gain reputation or greater distribution for their Work in
+part through the use and efforts of others.
+
+For these and/or other purposes and motivations, and without any
+expectation of additional consideration or compensation, the person
+associating CC0 with a Work (the "Affirmer"), to the extent that he or she
+is an owner of Copyright and Related Rights in the Work, voluntarily
+elects to apply CC0 to the Work and publicly distribute the Work under its
+terms, with knowledge of his or her Copyright and Related Rights in the
+Work and the meaning and intended legal effect of CC0 on those rights.
+
+1. Copyright and Related Rights. A Work made available under CC0 may be
+protected by copyright and related or neighboring rights ("Copyright and
+Related Rights"). Copyright and Related Rights include, but are not
+limited to, the following:
+
+  i. the right to reproduce, adapt, distribute, perform, display,
+     communicate, and translate a Work;
+ ii. moral rights retained by the original author(s) and/or performer(s);
+iii. publicity and privacy rights pertaining to a person's image or
+     likeness depicted in a Work;
+ iv. rights protecting against unfair competition in regards to a Work,
+     subject to the limitations in paragraph 4(a), below;
+  v. rights protecting the extraction, dissemination, use and reuse of data
+     in a Work;
+ vi. database rights (such as those arising under Directive 96/9/EC of the
+     European Parliament and of the Council of 11 March 1996 on the legal
+     protection of databases, and under any national implementation
+     thereof, including any amended or successor version of such
+     directive); and
+vii. other similar, equivalent or corresponding rights throughout the
+     world based on applicable law or treaty, and any national
+     implementations thereof.
+
+2. Waiver. To the greatest extent permitted by, but not in contravention
+of, applicable law, Affirmer hereby overtly, fully, permanently,
+irrevocably and unconditionally waives, abandons, and surrenders all of
+Affirmer's Copyright and Related Rights and associated claims and causes
+of action, whether now known or unknown (including existing as well as
+future claims and causes of action), in the Work (i) in all territories
+worldwide, (ii) for the maximum duration provided by applicable law or
+treaty (including future time extensions), (iii) in any current or future
+medium and for any number of copies, and (iv) for any purpose whatsoever,
+including without limitation commercial, advertising or promotional
+purposes (the "Waiver"). Affirmer makes the Waiver for the benefit of each
+member of the public at large and to the detriment of Affirmer's heirs and
+successors, fully intending that such Waiver shall not be subject to
+revocation, rescission, cancellation, termination, or any other legal or
+equitable action to disrupt the quiet enjoyment of the Work by the public
+as contemplated by Affirmer's express Statement of Purpose.
+
+3. Public License Fallback. Should any part of the Waiver for any reason
+be judged legally invalid or ineffective under applicable law, then the
+Waiver shall be preserved to the maximum extent permitted taking into
+account Affirmer's express Statement of Purpose. In addition, to the
+extent the Waiver is so judged Affirmer hereby grants to each affected
+person a royalty-free, non transferable, non sublicensable, non exclusive,
+irrevocable and unconditional license to exercise Affirmer's Copyright and
+Related Rights in the Work (i) in all territories worldwide, (ii) for the
+maximum duration provided by applicable law or treaty (including future
+time extensions), (iii) in any current or future medium and for any number
+of copies, and (iv) for any purpose whatsoever, including without
+limitation commercial, advertising or promotional purposes (the
+"License"). The License shall be deemed effective as of the date CC0 was
+applied by Affirmer to the Work. Should any part of the License for any
+reason be judged legally invalid or ineffective under applicable law, such
+partial invalidity or ineffectiveness shall not invalidate the remainder
+of the License, and in such case Affirmer hereby affirms that he or she
+will not (i) exercise any of his or her remaining Copyright and Related
+Rights in the Work or (ii) assert any associated claims and causes of
+action with respect to the Work, in either case contrary to Affirmer's
+express Statement of Purpose.
+
+4. Limitations and Disclaimers.
+
+ a. No trademark or patent rights held by Affirmer are waived, abandoned,
+    surrendered, licensed or otherwise affected by this document.
+ b. Affirmer offers the Work as-is and makes no representations or
+    warranties of any kind concerning the Work, express, implied,
+    statutory or otherwise, including without limitation warranties of
+    title, merchantability, fitness for a particular purpose, non
+    infringement, or the absence of latent or other defects, accuracy, or
+    the present or absence of errors, whether or not discoverable, all to
+    the greatest extent permissible under applicable law.
+ c. Affirmer disclaims responsibility for clearing rights of other persons
+    that may apply to the Work or any use thereof, including without
+    limitation any person's Copyright and Related Rights in the Work.
+    Further, Affirmer disclaims responsibility for obtaining any necessary
+    consents, permissions or other rights required for any use of the
+    Work.
+ d. Affirmer understands and acknowledges that Creative Commons is not a
+    party to this document and has no duty or obligation with respect to
+    this CC0 or use of the Work.
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..b78f6c0
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,15 @@
+# SPDX-License-Identifier: CC0-1.0
+#
+# Copyright (C) 2024 W. Kosior <koszko@koszko.org>
+
+CC = gcc
+CFLAGS = -std=c11 -Wall -Wextra -Werror
+
+poly_mul: poly_mul.o
+	$(CC) -lflint -lgmp -o $@ $^
+
+# For fans of old librebooted ThinkPads — the FLINT build in some distros (at
+# least Guix) uses processor instructions not available in old Core 2 Duo
+# processors…  For mere testing it is enough tu run with QEMU emulation, tho.
+run_poly_mul: poly_mul
+	guix shell qemu -- qemu-x86_64 -cpu max $<
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..c89656e
--- /dev/null
+++ b/README.md
@@ -0,0 +1,23 @@
+# Post-quantum blind signatures implementation (in progress)
+
+This is a small university project with the goal of implementing Markus
+Rückert's lattice-based blind signature scheme from 2008[1].
+
+Please consider it a toy program — it's being developed with shortcuts
+(e.g. using a big scientific library (FLINT[2]) for efficient polynomial
+multiplication).  Also, there are possibly better BS algorithms by now.
+
+## How it works
+
+Well, the actual program is not there yet.  There's just some code to facilitate
+polynomial multiplication in a ring modulo X^m+1 over a modulo field with
+non-canonical range — [-(n-1)/2, (n-1)/2] rather than [0, n-1].  Interestingly,
+only modulo operations in the latter range seem to be directly supported in
+FLINT as of today.
+
+## Building
+
+Please consult the included Makefile :)
+
+- [1] https://eprint.iacr.org/2008/322
+- [2] https://flintlib.org/
diff --git a/README.md.license b/README.md.license
new file mode 100644
index 0000000..5c9c439
--- /dev/null
+++ b/README.md.license
@@ -0,0 +1,3 @@
+SPDX-License-Identifier: CC0-1.0
+
+Copyright (C) 2024 W. Kosior <koszko@koszko.org>
diff --git a/dev-shell b/dev-shell
new file mode 100755
index 0000000..615fa53
--- /dev/null
+++ b/dev-shell
@@ -0,0 +1,10 @@
+#!/bin/sh
+# SPDX-License-Identifier: CC0-1.0
+#
+# Copyright (C) 2024 W. Kosior <koszko@koszko.org>
+
+# It is so annoying to have some shell read garbage from script while you edit
+# it…  Why not load all of it to memory first?
+exec sh -c "$(awk '{if (after) print} /#{3}/{after=1}' "$0")" "$0" "$@"
+###
+guix shell gcc-toolchain flint make
diff --git a/poly_mul.c b/poly_mul.c
new file mode 100644
index 0000000..db45bfd
--- /dev/null
+++ b/poly_mul.c
@@ -0,0 +1,278 @@
+/*
+ * SPDX-License-Identifier: CC0-1.0
+ *
+ * Copyright (C) 2024 W. Kosior <koszko@koszko.org>
+ */
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#include <flint/flint.h>
+#include <flint/fmpz.h>
+#include <flint/fmpz_mod.h>
+#include <flint/fmpz_poly.h>
+
+/* Exponent for Mersenne prime, for testing. */
+#define TEST_MERSENNE_EXPONENT 7 /* 89 */
+
+void marsenne_prime_init(fmpz_t prime, const ulong exponent) {
+	fmpz_init(prime);
+
+	fmpz_ui_pow_ui(prime, 2, exponent);
+	fmpz_sub_ui(prime, prime, 1);
+}
+
+void init_read_poly(fmpz_poly_t poly, FILE * file) {
+	bool first = true;
+	fmpz_t coef;
+
+	fmpz_poly_init(poly);
+	fmpz_init(coef);
+
+	for (ulong exponent = 0;; exponent++) {
+		int separator_char;
+
+		if (first) {
+			first = false;
+		} else {
+			separator_char = getc(file);
+
+			if (separator_char == '\n')
+				break;
+
+			if (separator_char != ' ')
+				goto error;
+		}
+
+		if (fmpz_fread(file, coef) < 0)
+			goto error;
+
+		fmpz_poly_set_coeff_fmpz(poly, exponent, coef);
+	}
+
+	fmpz_clear(coef);
+	return;
+
+error:
+	fprintf(stderr, "Error reading polynomial.\n");
+	abort();
+}
+
+/*
+ * FLINT seems to assume all modulo operations are performed on integers in
+ * range [0, n-1].  Here we provide a facility for performing modulo operations
+ * on big integers in range [-(n-1)/2, (n-1)/2].
+ */
+
+struct mod_centered_0_ctx {
+	fmpz_t mod;
+	fmpz_t range_max;
+};
+
+typedef struct mod_centered_0_ctx mod_centered_0_ctx_t[1];
+
+void mod_c0_ctx_init(mod_centered_0_ctx_t ctx, fmpz_t mod) {
+	struct mod_centered_0_ctx *ctxp = ctx;
+
+	fmpz_init_set(ctxp->mod, mod);
+
+	fmpz_init(ctxp->range_max);
+	fmpz_sub_ui(ctxp->range_max, ctxp->mod, 1);
+	/* Bit-shifting is faster but FLINT lacks convenient API for it. */
+	fmpz_divexact_ui(ctxp->range_max, ctxp->range_max, 2);
+}
+
+void mod_c0_ctx_clear(mod_centered_0_ctx_t ctx) {
+	fmpz_clear(ctx[0].mod);
+	fmpz_clear(ctx[0].range_max);
+}
+
+void mod_c0(fmpz_t value, mod_centered_0_ctx_t ctx) {
+	fmpz_add(value, value, ctx[0].range_max);
+	fmpz_fdiv_r(value, value, ctx[0].mod);
+	fmpz_sub(value, value, ctx[0].range_max);
+}
+
+void mod_c0_ctx_init_set(mod_centered_0_ctx_t dst_ctx,
+			 mod_centered_0_ctx_t src_ctx) {
+	fmpz_init_set(dst_ctx[0].mod, src_ctx[0].mod);
+	fmpz_init_set(dst_ctx[0].range_max, src_ctx[0].range_max);
+}
+
+/*
+ * Here we provide a facility for performing operations in polynomial rings
+ * modulo X^m+1 over fields of integers modulo n shifted to range [-(n-1)/2,
+ * (n-1)/2].
+ */
+
+struct poly_ring_ctx {
+	mod_centered_0_ctx_t mod_ctx;
+	slong divisor_degree;
+};
+
+typedef struct poly_ring_ctx poly_ring_ctx_t[1];
+
+void poly_ring_ctx_init(poly_ring_ctx_t ctx, mod_centered_0_ctx_t mod_ctx,
+			slong divisor_degree) {
+	if (divisor_degree < 0)
+		abort();
+
+	mod_c0_ctx_init_set(ctx[0].mod_ctx, mod_ctx);
+	ctx[0].divisor_degree = divisor_degree;
+}
+
+void poly_ring_ctx_clear(poly_ring_ctx_t ctx) {
+	mod_c0_ctx_clear(ctx[0].mod_ctx);
+}
+
+/*
+ * Apply modulo operations to make poly a member of the ring designated by ctx.
+ */
+void poly_to_ring(fmpz_poly_t poly, poly_ring_ctx_t ctx) {
+	slong degree = fmpz_poly_degree(poly);
+	fmpz_t new_coef_value;
+
+	fmpz_init(new_coef_value);
+
+	for (slong coef_idx = 0;
+	     coef_idx < ctx[0].divisor_degree;
+	     coef_idx++) {
+		int sign = 1;
+		slong higher_coef_idx = coef_idx;
+
+		fmpz_poly_get_coeff_fmpz(new_coef_value, poly, coef_idx);
+
+		/*
+		 * Polynomial division by X^m+1 can be achieved by substituting
+		 * -1 for X^m.
+		 */
+		do {
+			fmpz const * higher_coef;
+
+			sign *= -1;
+			higher_coef_idx += ctx[0].divisor_degree;
+
+			if (higher_coef_idx > degree)
+				break;
+
+			higher_coef =
+				fmpz_poly_get_coeff_ptr(poly, higher_coef_idx);
+
+			(sign == 1 ? &fmpz_add : &fmpz_sub)
+				(new_coef_value, new_coef_value, higher_coef);
+		} while (true);
+
+		mod_c0(new_coef_value, ctx[0].mod_ctx);
+		fmpz_poly_set_coeff_fmpz(poly, coef_idx, new_coef_value);
+	}
+
+	if (degree >= ctx[0].divisor_degree)
+		fmpz_poly_realloc(poly, ctx[0].divisor_degree);
+
+	fmpz_clear(new_coef_value);
+}
+
+void poly_mul_in_ring(fmpz_poly_t res, fmpz_poly_t poly1, fmpz_poly_t poly2,
+		      poly_ring_ctx_t ctx) {
+	fmpz_poly_mul(res, poly1, poly2);
+	poly_to_ring(res, ctx);
+}
+
+int main(const int argc, const char* const* const argv) {
+	fmpz_t prime; /* integer for modulo operations */
+	mod_centered_0_ctx_t mod_ctx;
+
+	(void) argc;
+	(void) argv;
+
+	/*
+	 * Marsenne primes are used just for testing.  Cryptographic algorithm
+	 * will use different ones.
+	 */
+	marsenne_prime_init(prime, TEST_MERSENNE_EXPONENT);
+
+	printf("Prime used for modulo operations: ");
+	fmpz_fprint(stdout, prime);
+	putchar('\n');
+
+	mod_c0_ctx_init(mod_ctx, prime);
+
+	{ /* Experiment 1 — modulo addition */
+		fmpz_t num1, num2, num_sum;
+
+		fmpz_init_set_ui(num1, 55);
+		fmpz_init_set_ui(num2, 31);
+		fmpz_init(num_sum);
+
+		fmpz_fprint(stdout, num1);
+		printf(" + ");
+		fmpz_fprint(stdout, num2);
+		printf(" mod [-");
+		fmpz_fprint(stdout, mod_ctx[0].range_max);
+		putchar(',');
+		fmpz_fprint(stdout, mod_ctx[0].range_max);
+		printf("] = ");
+
+		fmpz_add(num_sum, num1, num2);
+		mod_c0(num_sum, mod_ctx);
+		fmpz_fprint(stdout, num_sum);
+		putchar('\n');
+
+		fmpz_clear(num1);
+		fmpz_clear(num2);
+		fmpz_clear(num_sum);
+	} /* End of experiment 1 */
+
+	{ /* Experiment 2 */
+		fmpz_poly_t poly1, poly2, poly_prod;
+		slong divisor_degree;
+		poly_ring_ctx_t poly_ring_ctx;
+
+		printf("Give first polynomial to multiply:\n");
+		init_read_poly(poly1, stdin);
+
+		printf("Read polynomial: ");
+		fmpz_poly_print_pretty(poly1, "x");
+		putchar('\n');
+
+		printf("Give second polynomial to multiply:\n");
+		init_read_poly(poly2, stdin);
+
+		printf("Read polynomial: ");
+		fmpz_poly_print_pretty(poly2, "x");
+		putchar('\n');
+
+		printf("Normal product of polynomials:\n");
+		fmpz_poly_init(poly_prod);
+		fmpz_poly_mul(poly_prod, poly1, poly2);
+		fmpz_poly_print_pretty(poly_prod, "x");
+		putchar('\n');
+
+		printf("Give the degree m of X^m+1 polynomial to be used as ");
+		printf("divisor in the ring:\n");
+		if (flint_scanf("%wd", &divisor_degree) < 1 ||
+		    divisor_degree < 1) {
+			fprintf(stderr, "Bad divisor.\n");
+			abort();
+		}
+		poly_ring_ctx_init(poly_ring_ctx, mod_ctx, divisor_degree);
+
+		printf("Product of polynomials in the ring:\n");
+		poly_mul_in_ring(poly_prod, poly1, poly2, poly_ring_ctx);
+		fmpz_poly_print_pretty(poly_prod, "x");
+		putchar('\n');
+
+		fmpz_poly_clear(poly1);
+		fmpz_poly_clear(poly2);
+		fmpz_poly_clear(poly_prod);
+
+		poly_ring_ctx_clear(poly_ring_ctx);
+	} /* End of experiment 2 */
+
+	mod_c0_ctx_clear(mod_ctx);
+	fmpz_clear(prime);
+
+	return EXIT_SUCCESS;
+}