I'm proposing a cryptosystem as defined below:

  • Private Key: $(R, A, R^{-1})$, where $R = \left(\mathbf{r_1}, \cdots, \mathbf{r_n}\right)$ is full-rank, with $n \geq 4$, even; $A = \left(a_1\mathbf{e_1}, \cdots, a_n\mathbf{e_n} \right)$ and $a_i \neq 0$;
  • Public Key: $B = RAR^{-1}$;
  • Plaintext: $P \in \mathbb{F}_p^{n\times n}$ represents an ordered basis over $\mathbb{F}_p^n$;
  • Ciphertext: $C = PBP^{-1}$;
  • Decription: $VR^{-1}$, where $V = \left(\mathbf{v_1}, \cdots, \mathbf{v_n}\right)$, where $C\mathbf{v_i} = a_i\mathbf{v_i}$;
  • Document: $d \in \mathbb{F}_p$;
  • Signature: $s = \Pi_{i = 1}^{n/2} (x-a_{\pi(i)}^d) \in \mathbb{F}_p[x]$, where $\pi(\cdot) \in S_n$;
  • Verification: $s | b_d$, where $b_d = det\left(B^d-xI\right) \in \mathbb{F}_p[x]$;


  • $\mathbb{F}_p$ refers to the finite field of order $p$;
  • $\mathbb{F}_p[x]$ refers to the set of polynomials over $\mathbb{F}_p$;
  • $\left(\mathbf{m_1},\cdots,\mathbf{m_n}\right)$ signifies a matrix having $\mathbf{m_i}$ as its $i$th column vector;
  • $\mathbf{e_i}$ refers to the $i$th canonical vector of $\mathbb{F}_p$;
  • $p|q$ means '$p$ divides $q$';
  • $S_n$ is the symmetric group of $n$ elements;

Is it original? Is the premise of soundess based on hardness of factorization of polynomials over finite fields valid?

References: White Paper



Browse other questions tagged or ask your own question.