Pregunta:
Estoy buscando un esquema en el que la firma pueda ser costosa (lenta), pero la verificación por lotes con diferentes firmantes sea lo más rápida posible.
ECDSA modificado permite la verificación por lotes para diferentes firmantes con una aceleración 4X [1].
¿Hay algún esquema de firma que pueda hacerlo mejor?
[1] Verificación rápida por lotes de firmas múltiples . Jung Hee Cheon y Jeong Hyun Yi
Respuesta:
No hay una respuesta simple, ya que la velocidad de procesamiento por lotes depende de una serie de parámetros.
En primer lugar, la velocidad de la firma y la velocidad del procesamiento por lotes son en gran medida independientes. Si tiene dos algoritmos de firma S1 y S2 que permiten la técnica de procesamiento por lotes B1, generalmente ambos permitirán la técnica de procesamiento por lotes B2. Si S1 es más rápido que S2 para la verificación individual, entonces S1 con B1 será más rápido que S2 con B1. De manera similar, si B1 es más rápido que B2 en S1, también lo será en S2.
Encontrar el Si+Bi más rápido es en gran medida una cuestión de encontrar el Si más rápido y el Bi más rápido de forma independiente. La respuesta de @Thomas está orientada a encontrar el Si más rápido y su punto es correcto: es probable que esto le proporcione la mayor aceleración, sin encontrar el Bi correcto.
Para encontrar el Bi más rápido, debe considerar algunas cosas:
- La verificación por lotes no es perfecta. Si su tolerancia de error es de $2^{-a}$, el algoritmo de verificación por lotes más rápido podría diferir para a=5 en lugar de a=20 o 60.
- ¿Qué sucede si hay una firma inválida? ¿Tira todo el lote o solo las firmas malas? La verificación por lotes solo detecta la presencia de firmas incorrectas, no las encuentra. Necesita un segundo algoritmo de prueba de grupo para encontrar las firmas incorrectas.
- ¿Cuántas malas firmas está anticipando? Por ejemplo, puede que no sea ninguno, pero debe verificarlos para asegurarse. Alternativamente, podría ser mucho. Un resultado conocido es que si más de 1/3 de las firmas son malas, la verificación individual será más rápida que cualquier técnica de procesamiento por lotes para encontrarlas.
- Los algoritmos de verificación secuencial más rápidos no son necesariamente los algoritmos de verificación paralela más rápidos.
Si está abordando el problema como alguien que busca una solución establecida en la literatura, entonces el documento que cita es esencialmente lo último en firmas de estilo DSA. No dudaría en usarlo.
Si es un investigador que está dispuesto a optimizar la verificación según los requisitos exactos de la aplicación, es probable que no encuentre una técnica existente que aborde exactamente lo que necesita y es posible que entretenga algunas de las "letras pequeñas" que he se describe en la adaptación de un enfoque específico a sus necesidades.