The security of the birational permutation signature schemes
type: Item
instance of: scholarly article
title: The security of the birational permutation signature schemes
zbMATH Open document ID: 0905.94026
author: Don Coppersmith
author: Jacques Stern
author: Serge Vaudenay
published in: Journal of Cryptology
publication date: 1999-01-31T00:00:00Z
review text: The paper describes several attacks which can be applied to the family of signature schemes proposed by \textit{A. Shamir} [Advances in Cryptology -- CRYPTO'93, Santa Barbara, CA, Lect. Notes Comput. Sci. 773, 1-12 (1994; Zbl 0877.94041)]. Shamir's schemes were put forward as a possible alternative to the RSA signature scheme, employing polynomials of low degree and of several variables taking values in the ring \({\mathbb Z}_N\) with \(N\) large (e.g. one of the schemes under consideration is based on quadratic forms) and consequently having lower computational requirements, and they also improved on an earlier scheme [\textit{H. Ong, C. P. Schnorr} and \textit{A. Shamir}, A fast signature scheme based on quadratic equations, Proc. 16th ACM Symp. Theory of Computing, 208-216 (1984); see also Zbl 0571.94015)], which was broken in [\textit{J. M. Pollard} and \textit{C. P. Schnorr}, An efficient solution of the congruence \(x^2+ky^2=m\pmod n\), IEEE Trans. Inf. Theory IT-33, No. 5, 702-709 (1987; Zbl 0636.94008)]. The conclusion of the authors is that Shamir's schemes are vulnerable to the proposed attacks. Many proofs in the paper are based on the following `rule of the thumb,' supported by some mathematical arguments but still largely heuristic: if \(N\) is a large composite integer whose prime factorization is unknown, then in many situations one is free to treat the ring \({\mathbb Z}_N={\mathbb Z}/N{\mathbb Z}\) as a field, at least in the algorithmic aspects, through pretending that one is working in some \({\mathbb Z}_p\). Discovering the exact nature of the phenomenon behind this principle is a challenging problem for an interested model theorist.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11T71
zbMATH DE Number: 1053683
zbMATH Keywords: signature schemes
zbMATH Keywords: birational permutations
zbMATH Keywords: cryptanalysis
zbMATH Keywords: Shamir scheme
zbMATH Keywords: Galois theory
zbMATH Keywords: quadratic forms
reviewed by: Vladimir G. Pestov
MaRDI profile type: Publication
full work available at URL: s001459900028
OpenAlex ID: W2078581514
cites work: Q4341770
cites work: Q4023676
cites work: Q3496299
cites work: Q3803032
cites work: Q4343439
cites work: An efficient solution of the congruence&lt;tex&gt;x^2 + ky^2 = mpmod{n}&lt;/tex&gt;
cites work: A method for obtaining digital signatures and public-key cryptosystems
cites work: Q4341727
cites work: Q4343429
DOI: 10.1007/S001459900028
Recommended article: Q4341770
Recommended article: Q4341727
Recommended article: Cryptanalysis of the birational permutation signature scheme over a non-commutative ring
Recommended article: Q4418529
Recommended article: Public Key Cryptography – PKC 2004
Recommended article: Signcryption schemes with insider security in an ideal permutation model
Recommended article: The security of He and Kiesler's signature schemes
Recommended article: Erratum to: ``Cryptanalysis of the birational permutation signature scheme over a non-commutative ring''
Recommended article: On the security of the Courtois-Finiasz-Sendrier signature
Recommended article: Information Security and Cryptology - ICISC 2005
description: scientific article; zbMATH DE number 1053683