Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
St. Petersburg Mathematical Journal
St. Petersburg Mathematical Journal
ISSN 1547-7371(online) ISSN 1061-0022(print)

 

Algebraic cryptography: New constructions and their security against provable break


Authors: D. Grigoriev, A. Kojevnikov and S. J. Nikolenko
Translated by: the authors
Original publication: Algebra i Analiz, tom 20 (2008), nomer 6.
Journal: St. Petersburg Math. J. 20 (2009), 937-953
MSC (2000): Primary 94A60, 68P25, 11T71
Published electronically: October 1, 2009
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Very few known cryptographic primitives are based on noncommutative algebra. Each new scheme is of substantial interest, because noncommutative constructions are secure against many standard cryptographic attacks. On the other hand, cryptography does not provide security proofs that might allow the security of a cryptographic primitive to rely upon structural complexity assumptions. Thus, it is important to investigate weaker notions of security.

In this paper, new constructions of cryptographic primitives based on group invariants are proposed, together with new ways to strengthen them for practical use. Also, the notion of a provable break is introduced, which is a weaker version of the regular cryptographic break. In this new version, an adversary should have a proof that he has correctly decyphered the message. It is proved that the cryptosystems based on matrix group invariants and a version of the Anshel-Anshel-Goldfeld key agreement protocol for modular groups are secure against provable break unless $ \mathrm{NP}=\mathrm{RP}$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in St. Petersburg Mathematical Journal with MSC (2000): 94A60, 68P25, 11T71

Retrieve articles in all journals with MSC (2000): 94A60, 68P25, 11T71


Additional Information

D. Grigoriev
Affiliation: CNRS, Laboratoire des Mathématiques, Université de Lille, 59655 Villeneuve d’Ascq, France
Email: Dmitry.Grigoryev@math.univ-lille1.fr

A. Kojevnikov
Affiliation: St. Petersburg Branch, Steklov Mathematical Institute, Russian Academy of Sciences, Fontanka 27, 191023 St. Petersburg, Russia
Email: arist@pdmi.ras.ru

S. J. Nikolenko
Affiliation: St. Petersburg Branch, Steklov Mathematical Institute, Russian Academy of Sciences, Fontanka 27, 191023 St. Petersburg, Russia
Email: sergey@logic.pdmi.ras.ru

DOI: http://dx.doi.org/10.1090/S1061-0022-09-01079-6
PII: S 1061-0022(09)01079-6
Keywords: Algebraic cryptography, cryptographic primitives, provable break
Received by editor(s): January 9, 2008
Published electronically: October 1, 2009
Additional Notes: The research was done during the stay at the Max-Planck-Institut für Mathematik, Bonn, Germany.
The second and third authors were supported in part by INTAS (YSF fellowship no. 05-109-5565) and by RFBR (grant nos. 05-01-00932 and 06-01-00502).
Article copyright: © Copyright 2009 American Mathematical Society