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:
- Choose $\mathbf A$ uniformly from $\mathbb Z_q^{n\times m}$
- 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 and $\mathbf 1$ be a matrix with all entries equal to $1$. Then on input $n, m, q$ algorithm outputs a pair $\left(\mathbf A,\left[(\operatorname{Id}(Ker(\mathbf A)) - \frac q2 \mathbf 1)\|q\mathbf R\right]\right)$$\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!