Cryptology ePrint Archive: Report 2019/484

New Number-Theoretic Cryptographic Primitives

Eric Brier and Houda Ferradi and Marc Joye and David Naccache

Abstract: This paper introduces new $p^r q$-based one-way functions and companion signature schemes. The new signature schemes are interesting because they do not belong to the two common design blueprints, which are the inversion of a trapdoor permutation and the Fiat--Shamir transform.

In the basic signature scheme, the signer generates multiple RSA-like moduli $n_i = p_i^2 q_i$ and keeps their factors secret. The signature is a bounded-size prime whose Jacobi symbols with respect to the $n_i$'s match the message digest. The generalized signature schemes replace the Jacobi symbol with higher-power residue symbols. The case of 8th-power residue symbols is fully detailed along with an efficient implementation thereof.

Given of their very unique design the proposed signature schemes seem to be overlooked missing species in the corpus of known signature algorithms.

Category / Keywords: foundations / $r$th-power residue symbol; $r$th-order imprint; $p^r q$ moduli; number theory; one-way functions; digital signatures; cryptographic primitives.

Original Publication (in the same form): NutMiC 2019

Date: received 12 May 2019, last revised 18 May 2019

Contact author: houda ferradi at ens fr

Available format(s): PDF | BibTeX Citation

Version: 20190518:124819 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]