### New Number-Theoretic Cryptographic Primitives

Eric Brier, Houda Ferradi, 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. Given of their very unique design the proposed signature schemes seem to be overlooked missing species in the corpus of known signature algorithms.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. NutMiC 2019 | J. Math. Cryptol.
Keywords
$r$th-power residue symbol$r$th-order imprint$p^r q$ modulinumber theoryone-way functionsdigital signaturescryptographic primitives.
Contact author(s)
marc joye @ gmail com
History
2019-11-16: last of 12 revisions
See all versions
Short URL
https://ia.cr/2019/484

CC BY

BibTeX

@misc{cryptoeprint:2019/484,
author = {Eric Brier and Houda Ferradi and Marc Joye and David Naccache},
title = {New Number-Theoretic Cryptographic Primitives},
howpublished = {Cryptology ePrint Archive, Paper 2019/484},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/484}},
url = {https://eprint.iacr.org/2019/484}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.