# A Redactable Blockchain Scheme Supporting Quantum-Resistance and Trapdoor Updates
## 2 Preliminaries
### Concepts of Lattices  
A lattice is defined as a discrete additive subgroup on \(\mathbb{R}^{m}\) and is usually represented by a line combination of a set of linearly independent vectors. The \(q\)-ary integer lattice defined on \(\mathbb{Z}_{q}\). is given as: \(\Lambda^{\perp}(\mathbf{B})=\{\mathbf{x}\in\mathbb{Z}^{n}:\mathbf{B}\mathbf{x}=0\;modq\}\), \(\Lambda^{\perp}_{u}(\mathbf{B})=\Big{\{}\mathbf{x}\in\mathbb{Z}^{n}:\mathbf{B}\mathbf{x}=\mathbf{u }\;modq,\mathbf{u}\in\mathbb{Z}_{q}^{m}\Big{\}}\), where the matrix \(\mathbf{B}=[\mathbf{b}_{1},\dots,\mathbf{b}_{n}]\in\mathbb{R}^{m\times n}\) is called basis of the lattice. The norm of matrix \(\mathbf{B}\) is denoted as the maximum norm of the column vector, i.e., \(\|\mathbf{B}\|=max_{i}\|\mathbf{b}_{i}\|\) (in addition, \(\left\|\cdot\right\|_{\infty}\) stands for infinite norm). The singular value of matrix \(\mathbf{B}\) is denoted as the maximum norm on the unit vector u, i.e., \(s_{1}(\mathbf{B})=max_{u}\|\mathbf{B}\mathbf{u}\|\). **Definition 1** (Learning with errors (LWE) [34]). : _LWE is a class of problems solving learning with error parity. For a positive integer \(n\) and a sufficiently large integer \(q\), then an instance of the LWE problem \(\big{(}\mathbb{Z}_{q},n,\chi\big{)}-L\text{WE}\) is to find the vector \(s^{\prime}\in\mathbb{Z}_{q}^{n}\) s.t. \(\mathbf{A}\in\mathbb{Z}^{m\times n}\), \(\|\mathbf{A}s^{\prime}-(\mathbf{A}s+\mathbf{e})\|\leq\beta\), \(\beta>0\) being the upper limit of the error, and \(\mathbf{s}\in\mathbb{Z}_{q}^{n}\) is the unknown vector in the LWE. Vector \(e\) comes from the noise distribution \(\chi\)._  
**Definition 2** (Inhomogeneous small integer solution (ISIS)). : _ISIS is the problem of solving the short vector on a lattice. Let \(n,\;m,q\) be positive integers. Given a uniform random matrix \(\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}\) and a random vector \(\mathbf{u}\in\mathbb{Z}_{q}^{n}\). If we find a vector \(\mathbf{v}\in\mathbb{Z}_{q}^{m}\) satisfying \(\mathbf{A}\mathbf{v}=\mathbf{u}\;mod\;q\) and \(\|\mathbf{v}\|\leq\beta\), we have solved an \(ISIS_{q,m,\beta}\)-instance problem._  
Gaussian sampling over lattices is proved to be a simple and effective tool for analyzing lattice complexity problems [35]. **Definition 3** (Discrete Gaussian distribution). : \(\rho_{s,e}(\mathbf{x})\) _denotes a Gaussian function centered at \(\mathbf{c}\) with \(s\) as the Gaussian parameter. Then, \(\forall\mathbf{x}\in\Lambda,\rho_{s,e}(\mathbf{x})=exp\Big{(}-\pi\|\mathbf{x}-\mathbf{c}\|^{2 }/s^{2}\Big{)}\) denote the Gaussian function on the lattice, and the Gaussian distribution on the lattice is denoted as \(\forall\mathbf{x}\in\mathbf{\Lambda},\;D_{\Lambda,s,e}\left(\mathbf{x}\right)=\frac{\rho _{s,e}(\mathbf{x})}{\rho_{s,e}(\mathbf{\Lambda})},\;\rho_{s,e}(\mathbf{\Lambda})=\sum_{x \in\Lambda}\rho_{s,e}(\mathbf{x})\)._  
In this paper, we use the Gaussian sampling lemma shown in Lemma 1. **Lemma 1**. : _Let \(\mathbf{y}\leftarrow_{\mathbb{R}}\chi^{m},x\leftarrow_{\mathbb{R}}\chi,\;\mathbf{d} \in\mathbb{Z}^{m}\). Then, the length of the product of the error \(y\) and the vector satisfies \(\left|\mathbf{d}^{\intercal}\mathbf{y}\right|\leq\left\|d\|q\alpha\omega\big{(} \sqrt{\log m}\big{)}+\left\|d\right\|\sqrt{m}/2\) with negligible probability. Then, \(\left|x\right|\leq q\alpha\omega\big{(}\sqrt{\log m}\big{)}+1/2\) with negligible probability._