帶符號位的單標量乘法
我想知道是否有一種“簡單”的無計時方式來計算 $ y $ - 座標 $ r G $ , 對於一個秘密標量 $ r $ 和 $ G $ 橢圓曲線的生成器。
對於標量乘法，我們有幾種選擇：1) 使用蒙哥馬利階梯，它提供 $ x $ - 座標，但什麼也沒告訴你 $ y $ -協調; 2) 其他方法，例如 Edwards 曲線上的乘加法。
蒙哥馬利梯子很可愛，因為要獲得對定時攻擊非常安全的東西並不難，所以對於 ECDH 來說，這是一個顯而易見的選擇。但是，簽名方案要求您知道 $ y $ -coordinate，這會導致非常繁瑣的實現要求，例如視窗化標量-mul 的無時間表查找。
我的問題是是否有中間選擇：使用蒙哥馬利 $ x $ - 座標，以及一些其他方法來獲得的符號 $ y $ -座標，然後可以由驗證者使用，避免需要實現時間安全的雙標量-mul操作。我正在考慮在蒙哥馬利曲線上進行某種“僅差分符號”操作。
特別是，我知道“符號”的選擇是任意的：任何一半大小的子集 $ Z_p $ 可以指定為“正”集 $ y $ -座標。有了這個符號定義的自由選擇，有沒有選擇使符號 $ r G $ 易於確定，使用“簡單”算法？
使用 $ x $ - 僅座標，給定一個點 $ G = (x_0,y_0) $ 在橢圓曲線上 $ y^2 = x^3 + ax + b $ 和一個標量 $ r $ ，蒙哥馬利階梯輸出 $ x $ - 座標 $ rG $ . 然而，仔細觀察算法會發現計算中使用的另一個累加器包含 $ x $ - 座標 $ (r+1)G $ . 讓 $ x_1 $ 這 $ x $ - 座標 $ rG $ 和 $ x_2 $ 這 $ x $ - 座標 $ (r+1)G $ , 我們有
$ y_1 = \dfrac{2b+(a+x_0x_1)(x_0+x_1)−x_2(x_0−x_1)^2}{2y_0} $
是個 $ y $ - 座標 $ rG $ . 給定 $ y_1 $ , 它的符號很容易得到。
參見例如 Éric Brier 和 Marc Joye，Weierstraß 橢圓曲線和側通道攻擊。在 D. Naccache 和 P. Paillier，Eds.，公鑰密碼學，卷。《電腦科學講義》第2274頁，第 335-345 頁，Springer-Verlag，2002 年。