In pursuit of understanding a randomly found topic I was interested in learning the connection between integer programming and cryptography and found Lenstra Jr.'s Integer Programming and Cryptography. It is bit technical for my taste. Is there an easier reference to use for a novice to learn about what cryptography and linear/integer programming has to do with one another. And what are the ongoing works in this field ? Appreciate your time in answering this question.
1 Answer
It's Hendrik Lenstra [to distinguish from Arjen Lenstra, both have worked on cryptography].
And, I am afraid I don't know how much the technical details in that article can be omitted, in the sense that only notation is defined and straightforward relationships are explored.
For example, clearly, a knapsack problem is exactly equivalent to an integer linear program.
And the problem finding integral points within a set, as on page 15, if one exists, is related to problems in more recent cryptographic structures such as those used in lattice based cryptography.