TY - JOUR
T1 - Asymptotically Optimal Communication for Torus-Based Cryptography
AU - Van Dijk, M.
AU - Woodruff, D.
PY - 2004
Y1 - 2004
N2 - We introduce a compact and efficient representation of elements of the algebraic torus. This allows us to design a new discretelog based public-key system achieving the optimal communication rate, partially answering the conjecture in [4]. For n the product of distinct primes, we construct efficient ElGamal signature and encryption schemes in a subgroup of F*qn in which the number of bits exchanged is only a φ(n)/n fraction of that required in traditional schemes, while the security offered remains the same. We also present a Diffie-Hellman key exchange protocol averaging only φ(n) log2 q bits of communication per key. For the cryptographically important cases of n = 30 and n = 210, we transmit a 4/5 and a 24/35 fraction, respectively, of the number of bits required in XTR [14] and recent CEILIDH [24] cryptosystems. © International Association for Cryptologic Research 2004.
AB - We introduce a compact and efficient representation of elements of the algebraic torus. This allows us to design a new discretelog based public-key system achieving the optimal communication rate, partially answering the conjecture in [4]. For n the product of distinct primes, we construct efficient ElGamal signature and encryption schemes in a subgroup of F*qn in which the number of bits exchanged is only a φ(n)/n fraction of that required in traditional schemes, while the security offered remains the same. We also present a Diffie-Hellman key exchange protocol averaging only φ(n) log2 q bits of communication per key. For the cryptographically important cases of n = 30 and n = 210, we transmit a 4/5 and a 24/35 fraction, respectively, of the number of bits required in XTR [14] and recent CEILIDH [24] cryptosystems. © International Association for Cryptologic Research 2004.
UR - http://www.scopus.com/inward/record.url?scp=33745131994&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-28628-8_10
DO - 10.1007/978-3-540-28628-8_10
M3 - Article
SN - 0302-9743
VL - 3152
SP - 157
EP - 178
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ER -