Exponential sums and lattice reduction: Applications to cryptography

We describe a rather surprising, yet powerful, combination of two famous number theoretic techniques: bounds of exponential sums and lattice reduction algorithms. This combination has led to a number of cryptographic applications, helping to make rigorous several heuristic approaches and provides a two edge sword to defend and attack. It can be used prove important security results arid also to create powerful attacks. The examples of the first group include results about the bit security of the Diffie-Hellman key exchange system, of the Shamir message passing scheme and of the XTR and LUC cryptosystems. The examples of the second group include attacks on the Digital Signature Scheme and its modifications which are provably insecure under certain conditions.