The cryptographic security of truncated linearly related variables

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The cryptographic security of truncated linearly related variables

Full text

Pdf (674 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the seventeenth annual ACM symposium on Theory of computing table of contents

Providence, Rhode Island, United States

Pages: 356 - 362

Year of Publication: 1985

ISBN:0-89791-151-2

Authors

J Hastad	Department of Mathematics, MIT, Cambridge, MA
A Shamir	Department of Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 21, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/22145.22184 What is a DOI?

ABSTRACT

In this paper we describe a polynomial time algorithm for computing the values of variables x1, … xk when some of their bits and some linear relationships between them are known. The algorithm is essentially optimal in its use of information in the sense that it can be applied as soon as the values of the xi become uniquely determined by the constraints. Its cryptanalytic significance is demonstrated by two applications: breaking linear congruential generators whose outputs are truncated, and breaking Blum's protocol for exchanging secrets.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Manuel Blum, How to exchange (secret) keys, ACM Transactions on Computer Systems (TOCS), v.1 n.2, p.175-193, May 1983 [doi>10.1145/357360.357368]
	2	J.W.S. Cassels, "Geometry of Numbers", Springer Verlag 1959.
	3	A.M. Frieze, R. Hannah and J.C. Lagarias "Linear Congruential Generators do not Produce Random Sequences", FOCS 1984 480-484.
	4	S. Goldwa~ser, S. Micali and C. Rackoff "The Knowledge Complexity of Interactive Protocols". Unpublished manuscript.
	5	J. Hastad "On the Shortest Vector in Random Latrices". Manuscript in preparatiLon.
	6	Ravi Kannan, Improved algorithms for integer programming and related lattice problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.193-206, December 1983 [doi>10.1145/800061.808749]
	7	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	8	A.K. Lenstra, H.W. Lenstra aud L. Lovasz, "Factoring Polynomial,J With Integer coefficients", M~tem. atische Ar~nalen, 261, (1982), 513-534.
	9	J.E. Mazo and A.M. Odlyzko, Lattice points in High-dimensional spheres. Paper in prer~ation.
	10	Minkows~d "Di~kontinuitiitsbereieh f/ir Arithmetische ,~.quivalcnz", Journal fiir M~them~tik, 129, 1905, 220-274.
	11	J.B. Plumstead, "Inferring a Sequence Generated by a Linear Congruence", FOCS 1982, 153-159.

CITED BY 4

	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986
	Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985
	Joan Boyar, Inferring sequences produced by pseudo-random number generators, Journal of the ACM (JACM), v.36 n.1, p.129-141, Jan. 1989
	Soongohn Kim , Seoksoo Kim , Geuk Lee, Secure verifiable non-interactive oblivious transfer protocol using RSA and Bit commitment on distributed environment, Future Generation Computer Systems, v.25 n.3, p.352-357, March, 2009