Algebraic Tori in Cryptography

[摘要] Communicating bits over a network is expensive.Therefore, cryptosystems that transmit as little data as possible are valuable.This thesis studies several cryptosystems that require significantly less bandwidth than conventional analogues.The systems we study, called torus-based cryptosystems, were analyzed by Karl Rubin and Alice Silverberg in 2003 [RS03].They interpreted the XTR [LV00] and LUC [SL93] cryptosystems in terms of quotients of algebraic tori and birational parameterizations, and they also presented CEILIDH, a new torus-based cryptosystem.This thesis introduces the geometry of algebraic tori, uses it to explain the XTR, LUC, and CEILIDH cryptosystems, and presents torus-based extensions of van Dijk, Woodruff, et al. [vDW04, vDGP⁺05] that require even less bandwidth.In addition, a new algorithm of Granger and Vercauteren [GV05] that attacks the security of torus-based cryptosystems is presented.Finally, we list some open research problems.

[发布机构] University of Waterloo

[效力级别] cryptography

[关键词] Mathematics;cryptography;compression;finite field;extension field;discrete logarithm problem;tori;torus;algebraic;Rubin;Silverberg;Granger;Vercauteren;XTR;LUC;CEILIDH