Abstract
This paper improves the Finiasz-Vaudenay construction of \(\mathcal{TCH}o\), a hardware-oriented public-key cryptosystem, whose security relies on the hardness of finding a low-weight multiple of a given polynomial, and on the decoding of certain noisy cyclic linear codes. Our improvement makes it possible to decrypt in polynomial time (instead of exponential time), to directly prove semantic security (instead of one-wayness), and to achieve pretty good asymptotic performances. We further build IND-CCA secure schemes using the KEM/DEM and Fujisaki-Okamoto hybrid encryption frameworks in the random oracle model. This can encrypt an arbitrary message with an overhead of about 5 Kb in less than 15 ms, on an ASIC of about 10 000 gates at 4 MHz.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Abe, M., Gennaro, R., Kurosawa, K.: Tag-KEM/DEM: A new framework for hybrid encryption. IACR ePrint archive 2005/027 (2005), Available at http://eprint.iacr.org/2005/027 Newer version in [2]
Abe, M., Gennaro, R., Kurosawa, K., Shoup, V.: Tag-KEM/DEM: A new framework for hybrid encryption and a new analysis of Kurosawa-Desmedt KEM (Older version in [1]). In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 128–146. Springer, Heidelberg (2005)
Aumasson, J.-P.: On the pseudo-random generator ISAAC. IACR ePrint archive 2006/438 (2006), Available at http://eprint.iacr.org/2006/438
Baignères, T., Junod, P., Vaudenay, S.: How far can we go beyond linear cryptanalysis? In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 432–450. Springer, Heidelberg (2004)
Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In (FOCS’97). Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p. 394. IEEE Computer Society, Los Alamitos (1997)
Canteaut, A., Chabaud, F.: A new algorithm for finding minimum-weight words in a linear code: Application to McEliece’s cryptosystem and to narrow-sense BCH codes of length 511. IEEE Transactions on Information Theory 44(1), 367–378 (1998)
Canteaut, A., Trabbia, M.: Improved fast correlation attacks using parity check equations of weight 4 and 5. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 573–588. Springer, Heidelberg (2000)
Cantor, D.G., Zassenhaus, H.: A new algorithm for factoring polynomials over finite fields. Mathematics of Computation 36(154), 587–592 (1981)
Chowdhury, S., Maitra, S.: Efficient software implementation of linear feedback shift registers. In: Pandu Rangan, C., Ding, C. (eds.) INDOCRYPT 2001. LNCS, vol. 2247, pp. 297–307. Springer, Heidelberg (2001)
Chowdhury, S., Maitra, S.: Efficient software implementation of LFSR and boolean function and its application in nonlinear combiner model. In: Zhou, J., Yung, M., Han, Y. (eds.) ACNS 2003. LNCS, vol. 2846, pp. 387–402. Springer, Heidelberg (2003)
Dai, W.: Crypto++ library, http://www.eskimo.com/~weidai/
Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Transactions on Information Theory 22(6), 644–654 (1976)
Ellis, J.H.: The possibility of secure non-secret digital encryption. GCHQ-CESG publication (1970)
Finiasz, M., Vaudenay, S.: When stream cipher analysis meets public-key cryptography (invited talk). In: The Proceedings of SAC 2006, Lecture Notes in Computer Science (to appear)
Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener, M.J. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537–554. Springer, Heidelberg (1999)
Gupta, K.C., Maitra, S.: Multiples of primitive polynomials over GF(2). In: Pandu Rangan, C., Ding, C. (eds.) INDOCRYPT 2001. LNCS, vol. 2247, pp. 62–72. Springer, Heidelberg (2001)
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryptosystem. In: Buhler, J.P. (ed.) Algorithmic Number Theory. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)
Jambunathan, K.: On choice of connection-polynominals for LFSR-based stream ciphers. In: Roy, B., Okamoto, E. (eds.) INDOCRYPT 2000. LNCS, vol. 1977, pp. 9–18. Springer, Heidelberg (2000)
Jenkins Jr., R.J.: ISAAC. In: Gollmann, D. (ed.) Fast Software Encryption. LNCS, vol. 1039, pp. 41–49. Springer, Heidelberg (1996)
Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation 48(177), 203–209 (1987)
Lee, P.J., Brickell, E.F.: An observation on the security of McEliece’s public-key cryptosystem. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 275–280. Springer, Heidelberg (1988)
Maitra, S., Gupta, K.C., Venkateswarlu, A.: Results on multiples of primitive polynomials and their products over GF(2). Theoretical Computer Science 341(1-3), 311–343 (2005)
McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep. Jet Prop. Lab. California Inst. Technol. Pasadena, CA, pp. 114–116 (January 1978)
Meier, W., Staffelbach, O.: Fast correlation attacks on stream ciphers. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 301–314. Springer, Heidelberg (1988)
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5), 1484–1509 (1997)
Shoup, V.: NTL: A library for doing number theory, http://shoup.net/ntl/
Vaudenay, S.: RFID privacy based on public-key cryptography (invited talk). In: Rhee, M.S., Lee, B. (eds.) ICISC 2006. LNCS, vol. 4296, pp. 1–6. Springer, Heidelberg (2006)
Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–304. Springer, Heidelberg (2002)
Zhuo, L., Prasanna, V.K.: High performance linear algebra operations on reconfigurable systems. In: Gschwind, T., Aßmann, U., Nierstrasz, O. (eds.) SC 2005. LNCS, vol. 3628, Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Aumasson, JP., Finiasz, M., Meier, W., Vaudenay, S. (2007). \(\mathcal{TCH}o\): A Hardware-Oriented Trapdoor Cipher. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds) Information Security and Privacy. ACISP 2007. Lecture Notes in Computer Science, vol 4586. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73458-1_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-73458-1_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73457-4
Online ISBN: 978-3-540-73458-1
eBook Packages: Computer ScienceComputer Science (R0)