The comment at the beginning led us to find this [paper](https://eprint.iacr.org/2020/053). Obviously this challenge is an implementation of the scheme proposed by Jiahui Chen et al.

In Section 3.1, they pointed out an important property of the public key.

> Namely, Span_F P has a linearly independent set of n−a degree-one polynomials. Therefore, an attacker can generate a linearly independent set of n − a degree-one polynomials from the public key P.

So we can put aside the quadratic terms and solve the linear part directly.

steps as below

First, to get rid of quadratic terms, we can choose a basis s.t. the combinations of quadratic part get to zero.

(note that `sage` has a good implementation of polynomial system, which is helpful for algebraic cryptanalysis)

```python
polySeq = []
for i in range(n):
for j in range(n):
monomial = xs[i]*xs[j]
coefficients = [p_i.monomial_coefficient(monomial)
for p_i in P]
polySeq.append(vector(a_) * vector(coefficients))

polySeq = PolynomialSequence(polySeq)
basis = polySeq.groebner_basis()
```

Second, we use the basis to construct additional degree-one polynomials, and generate linear equations from cipher *d*.

```
basis_a * polynomials_pubkey = basis_a * cipher_d
```

At last, we combined them with quadratic equations from encryption (`pk(plain) = cipher`) and solve this system using Groebner basis algorithm. The solution is the plaintext.

for more details, refer to [exp.sage](https://github.com/Se-P3t/ctf-writeup/blob/master/2020/PlaidCTF/crypto_MPKC/exp.sage)

Original writeup (https://github.com/Se-P3t/ctf-writeup/tree/master/2020/PlaidCTF/crypto_MPKC).