D. J. Bernstein
Fighting patents

US patent 5347581, Naccache M'Raihi, DSS batch verification

Text of the patent
Filed 15 September 1993, so expires 15 September 2013. No reports of enforcement attempts.

Claim 1 covers the general concept of batch verification of digital signatures. However, this concept was already published in, e.g., "A scheme for batch verification of integrity assertions in a database system" (1984).

Claims 2, 4, and 5 are specific to one signature algorithm, DSS.

Claims 3, 6, and 7 cover a "cut and choose tree search" to locate invalid signatures in a batch.