Abstract
Extractors are an important ingredient in designing key exchange protocols and secure pseudorandom sequences in the standard model. Elliptic and hyperelliptic curves are gaining more and more interest due to their fast arithmetic and the fact that no subexponential attacks against the discrete logarithm problem are known.
In this paper we propose two simple and efficient deterministic extractors for \(J(\mathbb{F}_q)\), the Jacobian of a genus 2 hyperelliptic curve H defined over \(\mathbb{F}_q\), where q = 2n, called the sum and product extractors.
For non-supersingular hyperelliptic curves having a Jacobian with group order 2m, where m is odd, we propose the modified sum and product extractors for the main subgroup of \(J(\mathbb{F}_q)\). We show that, if \(D\in J(\mathbb{F}_q)\) is chosen uniformly at random, the bits extracted from D are indistinguishable from a uniformly random bit-string of length n.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Beelen, P., Pellikaan, R.: The Newton Polygon of Plane Curves with Many Rational Points. Designs Codes and Cryptography 21, 41–67 (2000)
Chevassut, O., Fouque, P., Gaudry, P., Pointcheval, D.: The Twist-AUgmented Technique for Key Exchange. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 410–426. Springer, Heidelberg (2006)
Cohen, H., Frey, G.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC, New York (2006)
Farashahi, R.R.: Extractors for Jacobian of Hyperelliptic Curves of Genus 2 in Odd Characteristic. In: Galbraith, S.D. (ed.) Cryptography and Coding 2007. LNCS, vol. 4887, pp. 313–335. Springer, Heidelberg (2007)
Farashahi, R.R., Pellikaan, R.: The Quadratic Extension Extractor for (Hyper)Elliptic Curves in Odd Characteristic. In: Carlet, C., Sunar, B. (eds.) WAIFI 2007. LNCS, vol. 4547, pp. 219–236. Springer, Heidelberg (2007)
Farashahi, R.R., Pellikaan, R., Sidorenko, A.: Extractors for Binary Elliptic Curves. In: Workshop on Coding and Cryptography–WCC 2007. Designs, Codes and Cryptography, pp. 127–136. Codes and Cryptography, Open access (2007), http://www.springerlink.com/content/lm35kv103x34j754
Gaudry, P.: An Algorithm for Solving the Discrete Log Problem on Hyperelliptic Curves. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 3419–3448. Springer, Heidelberg (2000)
Gaudry, P.: Fast genus 2 arithmetic based on Theta functions. J. Math. Crypt. 1, 243–265 (2007)
Gaudry, P., Lubicz, D.: The arithmetic of characteristic 2 Kummer surfaces (2008), http://www.loria.fr/~gaudry/tmp/c2.pdf
Gürel, N.: Extracting bits from coordinates of a point of an elliptic curve, Cryptology ePrint Archive, Report 2005/324 (2005), http://eprint.iacr.org/
Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer, New York (2004)
Hess, F., Shparlinski, I.E.: On the Linear Complexity and Multidimensional Distribution of Congruential Generators over Elliptic Curves. Designs, Codes and Cryptography 35(1), 111–117 (2005)
Kaliski, J.B.S.: A Pseudo-random Bit Generator Based on Elliptic Logarithms. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 84–103. Springer, Heidelberg (1987)
Koblitz, N.: Hyperelliptic Cryptosystem. J. of Cryptology 1, 139–150 (1989)
Lange, T., Shparlinski, I.E.: Certain Exponential Sums and Random Walks on Elliptic Curves. Canad. J. Math. 57(2), 338–350 (2005)
Lange, T., Shparlinski, I.E.: Distribution of Some Sequences of Points on Elliptic Curves. J. Math. Crypt. 1, 1–11 (2007)
Lange, T., Stevens, M.: Efficient Doubling on Genus Two Curves over Binary Fields. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 170–181. Springer, Heidelberg (2004)
Luby, M.: Pseudorandomness and Cryptographic Applications. Princeton University Press, USA (1994)
Mumford, D.: Tata Lectures on Theta II. Progress in Mathematics 43 (1984)
Shaltiel, R.: Recent Developments in Explicit Constructions of Extractors. Bulletin of the EATCS 77, 67–95 (2002)
Shparlinski, I.E.: On the Naor-Reingold Pseudo-Random Function from Elliptic Curves. Applicable Algebra in Engineering, Communication and Computing—AAECC 11(1), 27–34 (2000)
Trevisan, L., Vadhan, S.: Extracting Randomness from Samplable Distributions. In: IEEE Symposium on Foundations of Computer Science, pp. 32–42 (2000)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Farashahi, R.R. (2008). Extractors for Jacobians of Binary Genus-2 Hyperelliptic Curves. In: Mu, Y., Susilo, W., Seberry, J. (eds) Information Security and Privacy. ACISP 2008. Lecture Notes in Computer Science, vol 5107. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70500-0_33
Download citation
DOI: https://doi.org/10.1007/978-3-540-70500-0_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69971-2
Online ISBN: 978-3-540-70500-0
eBook Packages: Computer ScienceComputer Science (R0)