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!



Functional Encryption for Inner Product Predicates
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.


