Recientemente he estado trabajando en un algoritmo para la descomposición de un escalar para la multiplicación simultánea de w-NAF (forma no adyacente). El objetivo final es acelerar la multiplicación de puntos en curvas elípticas y así reducir el tiempo de multiplicación de puntos.
El algoritmo más simple para la multiplicación de la curva elíptica es el doble y sumar, ver (2), en el que la idea es usar la representación binaria del escalar que queremos multiplicar. Está claro que el costo del algoritmo depende directamente de la longitud del escalar, lo que hace que la multiplicación de puntos para un escalar de 256 bits sea bastante costosa.
Algoritmo doble y agregado
Existen otros algoritmos de multiplicación de puntos que utilizan representación NAF o w-NAF que hacen que el promedio de los valores distintos de 0 sea menor que en el algoritmo de doble y suma, por lo que la complejidad computacional es más lenta. Pero aún así, para los escalares largos, el costo del algoritmo es alto.
En la Sección 3.5 de (1) se describe un algoritmo para acelerar la multiplicación de puntos. La idea principal es muy simple, descomponer un escalar que necesitamos multiplicar en dos escalares con un menor número de bits. De esta manera, en lugar de hacer una multiplicación por un escalar de 256 bits, solo tenemos que calcular dos multiplicaciones paralelas de 128 bits. Tenga en cuenta que la multiplicación de un solo escalar no se puede paralelizar, ya que el algoritmo depende del estado.
Más precisamente, suponga que tenemos una multiplicación de puntos kP, donde P es un punto de una curva elíptica E yk es un escalar más pequeño que el orden de grupo n. Entonces existen dos escalares k₁, k₂ en (0, …, n-1), que tienen aproximadamente la mitad de la longitud de bits de k, de modo que
y
El factor λ es la solución de la ecuación de un endomorfismo ɸ sobre E.
Descomponiendo el escalar k
La idea del algoritmo es la siguiente: que f sea una función sobre ℤxℤ tal que para cada vector v = (a, b) en ℤxℤ,
Entonces solo necesitamos encontrar u = (k₁, k₂) en ℤxℤ tal que f (u) = k. De esta manera
Vamos a construirte. Hay dos partes para este objetivo:
1- Primero necesitamos encontrar dos vectores v₁ = (a₁, b₁), v₂ = (a₂, b₂) en ℤxℤ de manera que:
v₁ y v₂ son independientes sobre ℝ; f (v₁) = f (v₂) = 0; ambos tienen una pequeña norma euclidiana, esto significa a₁² + b₁²≈n, y lo mismo para v₂. Esta condición garantiza que cada componente k₁, k₂ sea medio bit largo que k.
2- Como v₁, v₂ son independientes sobre ℝ, sabemos que existen α₁, α₂ en ℚ de modo que (k, 0) = α₁v₁ + α₂v₂.
Supongamos que c₁ = (α₁), c₂ = (α₂) sea el número entero más cercano a α₂ y α₂, y consideremos v = c₁v₁ + c₂v₂. Entonces la ecuación u = (k, 0) -v satisface f (u) = f (k, 0) -f (v) = k, que era lo que necesitábamos. Finalmente, la descomposición de k viene dada por
Pero, ¿cómo encontramos los vectores v₁ y v₂? Para este propósito, utilizamos el algoritmo euclidiano extendido (1) para n y λ. Este algoritmo produce una secuencia de ecuaciones.
donde s₀ = 1, t₀ = 0, r₀ = ny s₁ = 0, t₁ = 1, r₁ = λ. Los restos rᵢ son estrictamente decrecientes y no negativos, al igual que los valores absolutos de sᵢ y tᵢ. Además, por cada i> = 1,
Deje que r the sea el resto más pequeño de tal manera que rₗ> = √n, entonces elegiremos como vectores v₁ y v₂
Si escribimos v₁ = (a₁, b₁) y v₂ = (a₂, b₂) entonces tenemos c₁ = (b₂k / n), c₂ = (- b₁k / n). El vector v es la suma v = c₁v₁ + c₂v₂ y u = (k, o) -v es
Esto concluye el algoritmo ya que los componentes de u son la descomposición de k.
Como se mencionó al principio de esta publicación, este algoritmo hace que la multiplicación de puntos sea mucho más eficiente al reducir su costo computacional. En Witnet, necesitamos realizar aritmética de curva elíptica costosa dentro de Ethereum para verificar las pruebas de elegibilidad y, por lo tanto, cada optimización es clave para reducir el costo del uso del protocolo. Esta técnica de descomposición escalar es definitivamente un gran candidato para ayudarnos a construir un software más eficiente.