定義拉格朗日插值 $ x=0 $ 作為 $ \mathcal{L} = \sum_{i=1}^{t+1} y_{i} \cdot l_{i} $ 和 $ l_{i} $ 作為拉格朗日基多項式。如果我們為每個共享應用橢圓曲線生成器，這是否成立 $ y_{i} \times G \rightarrow Y_{i} $ ?

1. 將橢圓曲線版本定義為 $ \mathcal{L}{G} = \sum{i=1}^{t+1} Y_{i} \times l_{i} $
2. 使用一組共享作為秘密 $ \alpha $ 作為 $ S_{\alpha} = {i \in [1, t + 1] : (i, y_{i})} $ 和橢圓曲線點份額為 $ P_{\alpha} = {i \in [1, t + 1] : (i, y_{i} \times G)} $

我預計 $ \mathcal{L}(S_{\alpha}) \times G = \mathcal{L}{G}(P{\alpha}) = \alpha \times G $ 是相同的，任何同態屬性也一樣。

據我所知，我還沒有看到任何人在任何現有的實現中製定或在實踐中使用它。但數學似乎是正確的。我只是不想在不確定它是否有效的情況下開始實施它。

這是“一半的答案”，而我在考慮另一半:)

編輯：下面添加了另一半。

我發現對所有基於離散對數的密碼學最有用的數學模型是有限域上的向量空間。在許多方面，乘法群的實現和橢圓曲線的實現是同構的，儘管它可能會令人困惑，因為前者是乘法的，而後者是加法的。

例如，乘法組設置通常讓您選擇兩個素數 $ p, q $ 和 $ q $ 劃分 $ (p-1)/2 $ , 和嵌入函式 $ x \mapsto g^x \mod p $ 在哪裡 $ g $ 是乘法順序的一個元素 $ q $ 模組 $ p $ （例如 $ g^q \equiv 1 $ 模組 $ p $ ).

在橢圓曲線設置中，您有一個基點 $ P $ 有秩序的 $ q $ ，沒有小—— $ p $ 嵌入函式是 $ x \mapsto x \times P $ .

這裡重要的數學結構是嵌入函式的目標是一個向量空間（維度為 1） $ \mathbb F_p $ 在這個模型中，嵌入函式是線性的。這可以讓你做很多事情。

我知道有幾個項目在乘法組設置中完成了各種秘密共享工作，其中很多都與電子投票有關，所有這些都應該幾乎 1:1 移植到橢圓曲線設置中。事實上，我希望人們會這樣做。您確實可以在某些機構之間生成（Shamir）秘密共享密鑰，每個人都發布他們的本地公鑰，然後將全域選舉公鑰計算為線性組合（這就是拉格朗日正在做的事情） $ Y = \sum_i c_i \times Y_i $ 在哪裡 $ Y_i $ 是本地公鑰。

原則上你可以定義一個產品 $ \otimes $ 在目標空間（例如曲線）上通過 $ (x \times P) \otimes (y \times P) := (xy \mod q) \times P $ 因為嵌入函式是雙射的。這使得目標空間變成了一個環，並且應該具有你需要在那裡用多項式做事情的大部分屬性，回答 SO 的問題（我認為）。這裡的實際問題是，實際計算這個乘積相當於求解CDH。這在兩種情況下應該不是問題：（1）在安全證明中，您只想對事物進行推理，（2）在秘密共享方案中，想要計算該產品的各方持有必要的原像有限域。

編輯

它應該仍然可以正常工作。例如：

在有限域上，您可以 $ (k, n) $ 分享一個秘密 $ s $ 通過設置 $ a_0 = s $ , 採摘 $ a_1 … a_{k-1} $ 隨機創建共享 $ s_i = \sum_{t=0}^{k-1} a_t i^t $ . 從中恢復 $ k $ 分享 $ (i, s_i){t=1}^k $ 你計算 $ \sum{t=1}^k \lambda_t s_t $ 在哪裡 $ \lambda_t $ 是拉格朗日係數。

如果你的秘密 $ S $ 在曲線中，如果你可以選擇隨機曲線點 $ A_1 … A_{k-1} $ 然後您可以通過以下方式創建共享 $ S_i = \sum_{t=0}^{k-1} [i^t] A_t $ 在哪裡 $ [t]A $ 表示標量 t 和曲線點的標量乘法 $ A $ . 恢復公式為 $ S = \sum_{t=1}^k [\lambda_t] S_t $ . 這樣做的原因是 $ i^t $ 和 $ \lambda_t $ 是標量，所以你永遠不會乘以曲線點。

（您可以通過選擇隨機標量來創建隨機曲線點 $ r $ 和計算 $ [r]P $ . 創建一個你不知道 dlog 的隨機曲線點更難，但在這裡沒有必要。）

這裡發生的事情是，由於每個曲線點都有一個離散對數，我們可以定義 $ s $ 這樣 $ S = [s]P $ 和 $ a_1 … a_{k-1} $ 這樣 $ A_t = [a_t]P $ 在哪裡 $ P $ 是基點。使用線性，我們創建共享的方式是 $ S_i = \sum_{t=0}^{k-1} [i^t a_t] P $ 所以如果我們選擇 $ s_i $ 這樣 $ S_i = [s_i]P $ 然後為了恢復我們得到 $ \sum_{t=1}^k [\lambda_t s_t]P = [\sum_{t=1}^k \lambda_t s_t] P $ . 但是這裡括號中的係數正是有限域上秘密共享的恢復公式，所以我們恢復 $ [s]P = S $ 正如預期的那樣。

（順便說一句，這也是您如何愉快地推理在安全證明中獲取離散日誌的一個範例。）

引用自：https://crypto.stackexchange.com/questions/70756