1
$\begingroup$

I want to try to implement a functional encryption scheme proposed in http://eprint.iacr.org/2011/410. The first problem I faced with is a TrapGen algorithm. In the paper theorem 3.1 states that:

Let $q, n, m \in \mathbb Z$ with $q \geq 2$ and $m \geq 6n\log q$. There is a p.p.t. algorithm $\mathrm{TrapGen}(q,n,m)$ that outputs a pair $(\mathbf A, \mathbf S) \in \mathbb Z^{n\times m}_q\times \mathbb Z^{m\times m}$ such that $\mathbf A$ is statistically close to uniform in $\mathbb Z^{n\times m}_q$ and $\mathbf S$ is a basis for $\Lambda _q^\bot (A)$, satisfying $\|\mathbf S\| = O(n\log q)$ and $\|\tilde{\mathbf S} \| = O(\sqrt {n\log q})$ with overwhelming probability in n.

Remark: $\tilde {\mathbf S}$ denotes the Gram-Schmidt orthogonalization of $\mathbf S$ and $\|\mathbf S\| = \max _i\|\mathbf s_i\|$.

I want to propose my own $\mathrm{TrapGen}$ algorithm which runs as follows:

  1. Choose $\mathbf A$ uniformly from $\mathbb Z_q^{n\times m}$
  2. Choose $\mathbf R\in \mathbb Z^{n\times m}$ from $\mathcal U_d(-c, c)$ for some $c>0$.

Let $\operatorname{Id}\colon \mathbb Z_q^{m-n\times m}\to \mathbb Z^{m-n\times m}$ be a natural identity map. Then on input $n, m, q$ algorithm outputs a pair $\left(\mathbf A,\left[(\operatorname{Id}(Ker(\mathbf A)) \|q\mathbf R\right]\right)$, where input values and $c$ should satisfy $\|\mathbf S\| = O(n\log q)$ with overwhelming probability.

Does my algorithm applicable for this scheme? If no, how can I correct it? Thanks in advance for any help!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Your algorithm will not work, because simply choosing uniformly random $\mathbf{A}$ over $\mathbb{Z}_q$ makes it computationally hard to find any short nonzero vector in $\Lambda^\perp(\mathbf{A})$ -- much less a full basis of short vectors.

The most efficient and implementation-friendly trapdoor generator is the one from Micciancio and Peikert, "Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller," EUROCRYPT '12, available here: http://www.cc.gatech.edu/~cpeikert/pubs/efftrap.pdf

That paper introduces a smaller and more usable notion of trapdoor, which is not a short basis of $\Lambda^\perp(\mathbf{A})$. The AFV inner product functional encryption scheme can be adapted to work directly with the new trapdoor notion, but that is beyond the scope of this answer.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Sorry, but I don't understand why it is hard to find a short vector. Suppose $\mathbf A$ is uniform then $\operatorname {Ker}(\mathbf A)$ is also uniform. The norm $\|\operatorname {Ker}(\mathbf A)\|\approx \sqrt mq$. With the restriction $n < m < (\frac {n\log q}{q})^2$, $\|\mathbf S\|$ satisfies $O(n\log q)$. $\endgroup$
    – vladkkkkk
    Commented Sep 4, 2014 at 20:57
  • $\begingroup$ Finding a short vector is the "Short Integer Solution" (SIS) problem, which is provably as hard as worst-case lattice problems. Your restriction $m < (n \log q / q)^2$ doesn't make sense because we need $q \gg n \log q$ for correctness purposes. Also, the estimate $\|\text{Ker}(\mathbf{A})\| \approx \sqrt{m} q$ only holds for sufficiently large $m$, which is in contradiction with your upper bound on $m$. $\endgroup$
    – Chris Peikert
    Commented Sep 4, 2014 at 21:02
  • $\begingroup$ Thanks a lot! I have read you presentation, there was an algorithm for generating random matrix $\mathbf A$ together with the short basis $\mathbf S$: choose at random $\overline{\mathbf A}\in \mathbb Z^{\overline n\times \overline m}_q$ and $\overline{\mathbf X}\in \{0, 1\}^{\overline m\times \overline m}$. Then $\mathbf A = \overline{\mathbf A} \| -\overline{\mathbf A}\cdot \overline{\mathbf X}$ and $\mathbf S = \overline{\mathbf X} \| \mathbf I$. Can I use this algorithm? Here $\|\mathbf S\| = \sqrt{\max _{i\leq m}(1 + \mathcal B(m/2, 1/2))}$. $\endgroup$
    – vladkkkkk
    Commented Sep 6, 2014 at 12:33
  • $\begingroup$ $S$ is not a short basis for the lattice, because it is not square. But $S$ can be used as a trapdoor as described in the paper I referenced. $\endgroup$
    – Chris Peikert
    Commented Sep 6, 2014 at 13:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .