這個問題是否基於離散多項式模(X3−1)(x3−1)(x^3-1)強的？
我們開始使用 Ring $ R=\left(\mathbb{Z}/p\mathbb{Z}\right)\left[x\right]/\left(x^{3}-1\right) $ , $ p $ 素數，即係數為模的二次多項式 $ p $ 模組 $ x^{3}-1 $ . 作為 $ x^{3}-1=\left(x-1\right)\left(x^{2}+x+1\right) $ ，我們選擇一個子集 $ R $ , $ S\subset R $ 和公共價值， $ z\in\mathbb{Z}/p\mathbb{Z},\ z\neq0 $ , $ P\in S,\ P\equiv-z\left(mod\ x-1\right) $ .
我們可以定義元素的轉置操作 $ S $ 作為交換 $ x $ 係數與 $ x^{2} $ 對應多項式之一，所以 $ \left(ax^{2}+bx+c\right)^{T}=bx^{2}+ax+c $ .
現在，我們定義一個函式 $ f:S\times S\mapsto S $ ， 作為 $ f\left(A,B\right)=\left(xA^{T}+z\right)\left(xB^{T}+z\right)-zx $ . 它的空元素是 $ -zx $ 和 $ f $ 是一個封閉的地圖 $ S $ ， 所以 $ A,B\in S,\ f\left(A,B\right)\in S $ .
接下來，我們定義一個系列如下：
$ A,B\in S,\ s_{0}=A,\ s_{1}=B,\ s_{n}=f\left(s_{n-2},s_{n-1}\right) $
對於系列的給定元素， $ s_{n} $ ， 一個值 $ r_{n}=f\left(s_{n},A\right) $
問題是
考慮到函式 $ f $ 不聯想，有多難，知道 $ B $ 和 $ r_{n} $ ，恢復秘密的價值 $ A $ . 作為尺寸的一個例子，讓我們說 $ n=256,\ p\sim2^{128} $ .
此問題可能導致這兩個文件中描述的密碼系統：
https://drive.google.com/open?id=1OGnFfooWASVCD1Iw_hVwvHYgqMGGE5nH
https://drive.google.com/open?id=1OeKh_ZJF-i7_KzWFRv8jodk3YkXe2qyv
這是同構：
$ ax^2 + bx + c $ （和 $ z $ ) 映射到 $ ax^2 + (b + z - z’)x + c $ （和 $ z’ $ )
這種變換唯一不明顯的是它保留了 $ f $ ， 就這樣 $ f(A, B) $ （和 $ z $ ) 是映射到的元素 $ f’(A’, B’) $ （和 $ z’ $ ， 和 $ f’, A’, B’ $ 是映射的版本 $ f, A, B $ )
然而，這並不難證明；我們注意到約束 $ ax^2 + bx + c = -z \pmod {x-1} $ 相當於 $ a + b + c = -z $ .
考慮到這一點，如果 $ A = ax^2 - (a+b+z)x + b $ （將線性項設置為與約束一致的值），如果 $ B = cx^2 - (c+d+z)x + d $ ， 然後 $ f(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z)x + (2ad+2bc+ac+bd) $
如果我們考慮這兩個元素的映射版本 $ A’ = ax^2 - (a+b+z’)x + b $ 和 $ B’ = cx^2 - (c+d+z’)x + d $ ，那麼映射版本的 $ f’ $ 將有 $ f’(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z’)x + (2ad+2bc+ac+bd) $
我們可以看到元素 $ f(A, B) $ 映射到元素 $ f’(A’, B’) $ ，因此保留了同構。