Practical lattice based signatures and key exchange with strong security reduction I am looking for practical lattice-based signatures and key exchange with strong security reductions.

Specifically:


Provable security under the relevant standard assumptions.
Fast in software while resistant to timing attacks
At least 128 bits of security
Your best bet at the moment are probably the lattice-based key exchange described in the "Post-quantum key exchange – a new hope" paper. You can also find different implementations. C code can be found on Peter Schwabe's homepage.

For signatures, if you want to use lattices, you will end-up with BLISS or BLISS-B both of which are implemented by various people. 

However, a word of warning. While there exist parameter proposals and especially the "new hope" paper is even very conservative regarding the parameter choice, both schemes use ideal lattices. The parameter estimates assume that there exists no significantly better attack for ideal lattices than for random lattices. While this is true at the moment, it is unclear if this will be the case in the long run. As always, there are several researchers that believe it will stay that way and several that believe faster algorithms will be found. 

A second issue is that implementation security of these schemes was not really studied so far and is hence not understood.

Anyway, combining these with ECC for example will definitely improve your security.