Faster Batch Forgery Identification

Batch signature verification detects whether a batch of signatures contains any forgeries. Batch forgery identification pinpoints the location of each forgery. Existing forgery-identification schemes vary in their strategies for selecting subbatches to verify (individual checks, binary search, combinatorial designs, etc.) and in their strategies for verifying subbatches. This paper exploits synergies between these two levels of strategies, reducing the cost of batch forgery identification for elliptic-curve signatures.

• Publication year

  2012

• Venue

  International Conference on Cryptology in India

• Publication date

  2012-12-09

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-34931-7_26
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Progress in cryptology : AFRICACRYPT 2012 : 5th International Conference on Cryptology in Africa, Ifrane, Morocco, July 10-12, 2012 : proceedings

  2012cited by this paper
• Progress in Cryptology - AFRICACRYPT 2012

  2012cited by this paper
• Batch Verification of ECDSA Signatures

  2012influential reference
• Cryptographic Hardware and Embedded Systems - CHES 2011 - 13th International Workshop, Nara, Japan, September 28 - October 1, 2011. Proceedings

  2011cited by this paper
• High-speed high-security signatures

  2011cited by this paper
• Pairing-Based Cryptography - Pairing 2010

  2011cited by this paper
• Identification of Multiple Invalid Pairing-Based Signatures in Constrained Batches

  2010cited by this paper
• Information Theoretic Security

  2010cited by this paper
• Pairing-Based Cryptography - Pairing 2010 - 4th International Conference, Yamanaka Hot Spring, Japan, December 2010. Proceedings

  2010cited by this paper
• Group Testing and Batch Verification

  2009cited by this paper
• Public Key Cryptography – PKC 2009

  2009cited by this paper
• Identification of Multiple Invalid Signatures in Pairing-Based Batched Signatures

  2009cited by this paper
• Advances in Cryptology - ASIACRYPT 2008, 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008. Proceedings

  2008cited by this paper
• Twisted Edwards Curves Revisited

  2008cited by this paper
• Cryptography and Coding, 11th IMA International Conference, Cirencester, UK, December 18-20, 2007, Proceedings

  2007cited by this paper
• Finding Invalid Signatures in Pairing-Based Batches

  2007cited by this paper
• Curve25519: New Diffie-Hellman Speed Records

  2006cited by this paper
• Identi cation of Bad Signatures in

  2006influential reference
• Efficient signature generation by smart cards

  2004cited by this paper
• Traceable Signatures

  2004cited by this paper
• Advances in Cryptology - ASIACRYPT 2003

  2003cited by this paper
• Progress in Cryptology - INDOCRYPT 2000: First International Conference in Cryptology in India, Calcutta, India, December 10-13, 2000. Proceedings

  2001cited by this paper
• Low-Weight Binary Representations for Pairs of Integers

  2001cited by this paper
• Advances in Cryptology — CRYPTO ’94

  2001cited by this paper
• Public key cryptography : third International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Melbourne, Victoria, Australia, January 18-20, 2000 : proceedings

  2000cited by this paper
• Codes Identifying Bad Signature in Batches

  2000cited by this paper
• Advances in Cryptology — CRYPTO’ 99

  1999cited by this paper
• Fast Batch Verification for Modular Exponentiation and Digital Signatures

  1998cited by this paper
• Advances in cryptology-EUROCRYPT '98 : International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31-June 4, 1998 : proceedings

  1998cited by this paper
• Advances in Cryptology — EUROCRYPT'98

  1998cited by this paper
• Cryptography and Coding

  1995cited by this paper
• Advances in cryptology, EUROCRYPT '94 : Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 9-12, 1994 : proceedings

  1995cited by this paper
• Efficient Exponentiation using Procomputation and Vector Addition Chains

  1994cited by this paper
• More Flexible Exponentiation with Precomputation

  1994cited by this paper
• Can D.S.A. be Improved? Complexity Trade-Offs with the Digital Signature Standard

  1994cited by this paper
• Fast Exponentiation with Precomputation: Algorithms and Lower Bounds

  1993cited by this paper
• Fast Exponentiation with Precomputation (Extended Abstract)

  1992cited by this paper
• Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings

  1990cited by this paper
• Efficient Identification and Signatures for Smart Cards (Abstract)

  1989cited by this paper
• On the Evaluation of Powers and Monomials

  1980cited by this paper
• The minimum number of edges in graphs with prescribed paths

  1978cited by this paper
• 17th Annual Symposium on Foundations of Computer Science, Houston, Texas, USA, 25-27 October 1976

  1976cited by this paper
• On the evaluation of powers and related problems

  1976cited by this paper

• Speeding Up Multi-scalar Multiplications for Pairing-Based zkSNARKs

  2025cites this paper
• Fast elliptic curve scalar multiplications in SN(T)ARK circuits

  2025cites this paper
• Accelerating EdDSA Signature Verification with Faster Scalar Size Halving

  2025influential citation
• OPTIMSM: FPGA hardware accelerator for Zero-Knowledge MSM

  2025cites this paper
• Verifiable Secret Sharing Simplified

  2025cites this paper
• SZKP: A Scalable Accelerator Architecture for Zero-Knowledge Proofs

  2024cites this paper
• Elastic MSM: A Fast, Elastic and Modular Preprocessing Technique for Multi-Scalar Multiplication Algorithm on GPUs

  2024influential citation
• Concurrently Secure Blind Schnorr Signatures

  2024cites this paper
• Gypsophila: A Scalable and Bandwidth-Optimized Multi-Scalar Multiplication Architecture

  2024cites this paper
• High-speed batch verification for discrete-logarithm-based signatures via Multi-Scalar Multiplication Algorithm

  2024cites this paper
• Verifiable Random Function Schemes Based on SM2 Digital Signature Algorithm and its Applications for Committee Elections

  2024cites this paper
• Load-Balanced Parallel Implementation on GPUs for Multi-Scalar Multiplication Algorithm

  2024cites this paper
• On Computing the Multidimensional Scalar Multiplication on Elliptic Curves

  2024influential citation
• ZKFDT: A Fair Exchange Scheme for Data Trading Based on Efficient Zero-Knowledge Proofs

  2024cites this paper
• cuZK: Accelerating Zero-Knowledge Proof with A Faster Parallel Multi-Scalar Multiplication Algorithm on GPUs

  2023cites this paper
• Exploration of Algorithms for the Hardware Acceleration of Multi-Scalar Multiplication on FPGA

  2023cites this paper
• Adaptively Secure BLS Threshold Signatures from DDH and co-CDH

  2023cites this paper
• A New Paradigm for Verifiable Secret Sharing

  2023cites this paper
• Threshold Signatures from Inner Product Argument: Succinct, Weighted, and Multi-threshold

  2023cites this paper
• Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS

  2023cites this paper
• Fast batched asynchronous distributed key generation

  2023influential citation
• Fast Computation of Multi-Scalar Multiplication for Pairing-Based zkSNARK Applications

  2023cites this paper
• Speeding Up Multi-Scalar Multiplication over Fixed Points Towards Efficient zkSNARKs

  2023cites this paper
• GZKP: A GPU Accelerated Zero-Knowledge Proof System

  2023cites this paper
• Accelerating zk-SNARK with Group and Zone Optimization on GPU

  2023cites this paper
• A SM2 based efficient and lightweight batch verification approach for IC cards

  2023cites this paper
• Faster Montgomery multiplication and Multi-Scalar-Multiplication for SNARKs

  2023cites this paper
• EdMSM: Multi-Scalar-Multiplication for recursive SNARKs and more

  2022cites this paper
• Spurt: Scalable Distributed Randomness Beacon with Transparent Setup

  2022cites this paper
• A survey of elliptic curves for proof systems

  2022cites this paper
• On UC-Secure Range Extension and Batch Verification for ECVRF

  2022cites this paper
• PipeMSM: Hardware Acceleration for Multi-Scalar Multiplication

  2022cites this paper
• FPGA Acceleration of Multi-Scalar Multiplication: CycloneMSM

  2022cites this paper
• An Efficient Batch Verification Scheme for SM2 Signatures

  2021cites this paper
• Families of SNARK-friendly 2-chains of elliptic curves

  2021cites this paper
• Non-interactive half-aggregation of EdDSA and variants of Schnorr signatures

  2021cites this paper
• A modern signature scheme with message recovery: Abe-Okamoto signatures with EdDSA elements

  2020cites this paper
• Zecale: Reconciling Privacy and Scalability on Ethereum

  2020cites this paper
• Accelerating V2X Cryptography through Batch Operations

  2019cites this paper
• Fast Verification of Signatures With Shared ECQV Implicit Certificates

  2019cites this paper
• A new batch verification scheme for ECDSA$$^*$$∗ signatures

  2019cites this paper
• Doubly-Efficient zkSNARKs Without Trusted Setup

  2018cites this paper
• DIZK: A Distributed Zero Knowledge Proof System

  2018cites this paper
• Fast batch modular exponentiation with common-multiplicand multiplication

  2018cites this paper
• Bulletproofs: Short Proofs for Confidential Transactions and More

  2018cites this paper
• Simplified small exponent test for batch verification

  2017cites this paper
• Improved batch verification of signatures using generalized sparse exponents

  2015cites this paper
• Batch Verification of Elliptic Curve Digital Signatures

  2015influential citation
• New algorithms for batch verification of standard ECDSA signatures

  2014cites this paper
• Randomized Batch Verification of Standard ECDSA Signatures

  2014cites this paper
• Batch Verification of EdDSA Signatures

  2014cites this paper
• Faster Batch Verification of Standard ECDSA Signatures Using Summation Polynomials

  2014cites this paper
• Using Randomizers for Batch Verification of ECDSA Signatures

  2012cites this paper
• Batch Verification of ECDSA Signatures

  2012cites this paper