How to exploit the intractability of exact TSP for cryptography. (English) Zbl 0939.94528
Preneel, Bart (ed.), Fast software encryption. 2nd international workshop, Leuven, Belgium, December 14-16, 1994. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 1008, 298-304 (1995).
Summary: We outline constructions for both pseudo-random generators and one-way hash functions. These constructions are based on the exact TSP (XTSP), a special variant of the well-known traveling salesman problem. We prove that these constructions are secure if the XTSP is infeasible. Our constructions are easy to implement, appear to be fast, but require a large amount of memory.
For the entire collection see [Zbl 0829.68005].
For the entire collection see [Zbl 0829.68005].
MSC:
| 94A60 | Cryptography |
