Join Log in
Score:1
Tarick Welling avatar Crypto

How is GGH's bad basis public key safe from gram–schmidt orthogonalization?

nl flag
Tarick Welling

I'm reading about lattice based cryptography. In my reading I read of gram–schmidt orthogonalization. Which allows for turning a bad basis into a good basis, or at least an orthogonal one.

Now I'm reading that in the GGH encryption scheme a good basis is used as private key and a bad basis is used as public key.

However my thought is that if the public key is known we can apply gram-schmidt orthogonalization to this bad basis to form a better one which would allow us to find the point that is being transferred.

How can this be safe? What am I missing in my thoughts?

It seems like that the problem is that with gram-schmidt we are having a $O(n!)$ computation because we need to do $n-1$ projections for every added dimensions. And as $O(n!)$ is worse than $O(2^n)$ we are still not in polynomial time with regards to our computation.

28
0 + 0
Chris Peikert avatar
in flag
Chris Peikert
The output of the GSO process is a set of orthogonal vectors, but they are typically not a *lattice basis*. When applied to a “bad” basis, the orthogonalized vectors typically have rapidly decreasing lengths. This prevents them from successfully recovering the nearest lattice point to the ciphertext point.
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.