Proof regarding a property of "$q$-ary" lattices

P_Gate

6/1/24, 8:55 PM

In this question we are dealing with "$q$-ary" lattices. I will give the definition available to me and I'm interested in proving the lemma. As a reference see the PDF on page 2 from Peikert's lectures.

Definition. Let $\mathbb{Z}_q := \{ 0, 1, \dots, q-1\}$. We define $ \Lambda^{\perp}(\mathbf{A}) := \left\{ \mathbf{z} \in \mathbb{Z^m} : \mathbf{Az = 0} \right\} $, where $\mathbf{A} \in \mathbb{Z}_q^{n \times m}$

Lemma. Let $\mathbf{H} \in \mathbb{Z}_{q}^{n \times n}$ be invertible. Then $\Lambda^{\perp}(\mathbf{HA}) = \Lambda^{\perp}(\mathbf{A}) $.

1 + 5

lattice-crypto

Daniel S

6/2/24, 7:51 AM

Looks good to me.

P_Gate

6/2/24, 8:14 AM

Thank's Daniel!

Don Freecs

6/3/24, 11:33 PM

it is correct you can close the question

Mark

6/5/24, 9:07 PM

Really the OP should factor out their proof from the question, and answer their own question with that answer.

Rodrigo de Azevedo

6/6/24, 6:51 AM

Didn't you post this question on Math SE?

Score:1

Crypto

P_Gate

6/5/24, 9:31 PM

Thanks for the comments confirming that my proof is correct. As suggested in the comments, I'm happy to answer the question myself.

Proof:

$\Lambda^{\perp}(\mathbf{HA}) \subset \Lambda^{\perp}(\mathbf{A}) $, let $\mathbf{z} \in \Lambda^{\perp}(\mathbf{HA})$ then $\mathbf{HAz = 0}$ and $H$ is invertible implies $\mathbf{H^{-1}HAz = 0}$ and this implies $\mathbf{z} \in \Lambda^{\perp}(\mathbf{A})$.

$\Lambda^{\perp}(\mathbf{A}) \subset \Lambda^{\perp}(\mathbf{HA}) $, let $\mathbf{z} \in \Lambda^{\perp}(\mathbf{A})$ then $\mathbf{Az = 0}$ and multiply by $\mathbf{H}$ implies $\mathbf{HAz = 0}$ and this implies $\mathbf{z} \in \Lambda^{\perp}(\mathbf{HA})$.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Proof regarding a property of "$q$-ary" lattices

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.