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!

$\endgroup$

1 Answer 1

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.

$\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
    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$ 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
    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$ Sep 6, 2014 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.