Suppose you are given an inner product on a vector space and given a set of linearly independent vectors, and that you have been promised that the lattice they span has an orthonormal basis. Can you (quickly) figure out what that basis is?


Note that this may be much easier than finding the shortest vector in a general lattice, since (for instance) you know ahead of time exactly how long the shortest vector actually is.


Motivation: Suppose you wanted to use Brauer's induction theorem to compute the character table of a big group. After computing enough induced characters, you can check (by calculating a suitable determinant) that you have a set of representations generating the Grothendieck group. You know ahead of time that the irreducible representations form an orthonormal basis - so it's natural to ask whether you can use this information to quickly figure out what the characters actually are.



Lattice reduction on an orthonormal lattice?
I believe there is no known algorithm for the case of orthonormal lattices. I have seen this mentioned as an open question a couple of times. The only known algorithms are unfortunately those for general lattices, mainly LLL and its extension BKZ. 


The fact that the length of the shortest vector is known is not necessarily a strong indication that the problem is easy. A similar situation occurs with other families of lattices, especially so-called ideal lattices, which are lattices obtained through the canonical embedding of ideals in number fields (see, e.g., "Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors", Peikert and Rosen, STOC 2007). And just like in the case of orthonormal lattices, the best known algorithms are the generic ones, despite the extra structure.


