Skip to main content
Bumped by Community user
Tweeted twitter.com/StackCrypto/status/1068520165959057408
Bumped by Community user
More specific title.
Source Link
kelalaka
  • 49.5k
  • 12
  • 118
  • 205

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE.

Theorem 5.1: There is an algorithm $\mathsf{GenTrap}(1^n,1^m,q)$ that, given any $n\geq 1, q\geq 2$ and $m=\mathcal{O}(n\log q)$, outputs a matrix $\mathbf{A}\in\mathbb{Z}^{n\times m}_q$ and a trapdoor $\mathbf{R}$ such that:

  1. $\mathbf{A}$ is indistinguishable from a uniformly chosen matrix; and
  2. there is an algorithm $\mathsf{Invert}$ that, given $\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}$ (with $\mathbf{s}\in\mathbb{Z}^{n}_q$, $\mathbf{e}\in\mathbb{Z}^m$ and $||\mathbf{e}||<q/\mathcal{O}(\sqrt{n\log q})$) and a trapdoor $\mathbf{R}$, outputs $\mathbf{s}$ and $\mathbf{e}.$

They mention that the results in the paper can be straightforwardly adapted to the ring setting (RLWERing-LWE), however, they don't give details on that. What would be an equivalent result to this one in the ring setting?

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE.

Theorem 5.1: There is an algorithm $\mathsf{GenTrap}(1^n,1^m,q)$ that, given any $n\geq 1, q\geq 2$ and $m=\mathcal{O}(n\log q)$, outputs a matrix $\mathbf{A}\in\mathbb{Z}^{n\times m}_q$ and a trapdoor $\mathbf{R}$ such that:

  1. $\mathbf{A}$ is indistinguishable from a uniformly chosen matrix; and
  2. there is an algorithm $\mathsf{Invert}$ that, given $\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}$ (with $\mathbf{s}\in\mathbb{Z}^{n}_q$, $\mathbf{e}\in\mathbb{Z}^m$ and $||\mathbf{e}||<q/\mathcal{O}(\sqrt{n\log q})$) and a trapdoor $\mathbf{R}$, outputs $\mathbf{s}$ and $\mathbf{e}.$

They mention that the results in the paper can be straightforwardly adapted to the ring setting (RLWE), however they don't give details on that. What would be an equivalent result to this one in the ring setting?

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE.

Theorem 5.1: There is an algorithm $\mathsf{GenTrap}(1^n,1^m,q)$ that, given any $n\geq 1, q\geq 2$ and $m=\mathcal{O}(n\log q)$, outputs a matrix $\mathbf{A}\in\mathbb{Z}^{n\times m}_q$ and a trapdoor $\mathbf{R}$ such that:

  1. $\mathbf{A}$ is indistinguishable from a uniformly chosen matrix; and
  2. there is an algorithm $\mathsf{Invert}$ that, given $\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}$ (with $\mathbf{s}\in\mathbb{Z}^{n}_q$, $\mathbf{e}\in\mathbb{Z}^m$ and $||\mathbf{e}||<q/\mathcal{O}(\sqrt{n\log q})$) and a trapdoor $\mathbf{R}$, outputs $\mathbf{s}$ and $\mathbf{e}.$

They mention that the results in the paper can be straightforwardly adapted to the ring setting (Ring-LWE), however, they don't give details on that. What would be an equivalent result to this one in the ring setting?

Adapting LWE Trapdoors for RLWERing-LWE

small format
Source Link
kelalaka
  • 49.5k
  • 12
  • 118
  • 205

In the paper MP12Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE.

Theorem 5.1: There is an algorithm $\mathsf{GenTrap}(1^n,1^m,q)$ that, given any $n\geq 1, q\geq 2$ and $m=\mathcal{O}(n\log q)$, outputs a matrix $\mathbf{A}\in\mathbb{Z}^{n\times m}_q$ and a trapdoor $\mathbf{R}$ such that: i) $\mathbf{A}$ is indistinguishable from a uniformly chosen matrix; and ii) there is an algorithm $\mathsf{Invert}$ that, given $\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}$ (with $\mathbf{s}\in\mathbb{Z}^{n}_q$, $\mathbf{e}\in\mathbb{Z}^m$ and $||\mathbf{e}||<q/\mathcal{O}(\sqrt{n\log q})$) and a trapdoor $\mathbf{R}$, outputs $\mathbf{s}$ and $\mathbf{e}.$

  1. $\mathbf{A}$ is indistinguishable from a uniformly chosen matrix; and
  2. there is an algorithm $\mathsf{Invert}$ that, given $\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}$ (with $\mathbf{s}\in\mathbb{Z}^{n}_q$, $\mathbf{e}\in\mathbb{Z}^m$ and $||\mathbf{e}||<q/\mathcal{O}(\sqrt{n\log q})$) and a trapdoor $\mathbf{R}$, outputs $\mathbf{s}$ and $\mathbf{e}.$

They mention that the results in the paper can be straightforwardly adapted to the ring setting (RLWE), however they don't give details on that. What would be an equivalent result to this one in the ring setting?

Link of the paper: https://eprint.iacr.org/2011/501

In the paper MP12 by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE.

Theorem 5.1: There is an algorithm $\mathsf{GenTrap}(1^n,1^m,q)$ that, given any $n\geq 1, q\geq 2$ and $m=\mathcal{O}(n\log q)$, outputs a matrix $\mathbf{A}\in\mathbb{Z}^{n\times m}_q$ and a trapdoor $\mathbf{R}$ such that: i) $\mathbf{A}$ is indistinguishable from a uniformly chosen matrix; and ii) there is an algorithm $\mathsf{Invert}$ that, given $\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}$ (with $\mathbf{s}\in\mathbb{Z}^{n}_q$, $\mathbf{e}\in\mathbb{Z}^m$ and $||\mathbf{e}||<q/\mathcal{O}(\sqrt{n\log q})$) and a trapdoor $\mathbf{R}$, outputs $\mathbf{s}$ and $\mathbf{e}.$

They mention that the results in the paper can be straightforwardly adapted to the ring setting (RLWE), however they don't give details on that. What would be an equivalent result to this one in the ring setting?

Link of the paper: https://eprint.iacr.org/2011/501

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE.

Theorem 5.1: There is an algorithm $\mathsf{GenTrap}(1^n,1^m,q)$ that, given any $n\geq 1, q\geq 2$ and $m=\mathcal{O}(n\log q)$, outputs a matrix $\mathbf{A}\in\mathbb{Z}^{n\times m}_q$ and a trapdoor $\mathbf{R}$ such that:

  1. $\mathbf{A}$ is indistinguishable from a uniformly chosen matrix; and
  2. there is an algorithm $\mathsf{Invert}$ that, given $\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}$ (with $\mathbf{s}\in\mathbb{Z}^{n}_q$, $\mathbf{e}\in\mathbb{Z}^m$ and $||\mathbf{e}||<q/\mathcal{O}(\sqrt{n\log q})$) and a trapdoor $\mathbf{R}$, outputs $\mathbf{s}$ and $\mathbf{e}.$

They mention that the results in the paper can be straightforwardly adapted to the ring setting (RLWE), however they don't give details on that. What would be an equivalent result to this one in the ring setting?

Source Link
P.B.
  • 516
  • 3
  • 9
Loading