Source: http://www.google.com/patents/US7890763?dq=oakley+D523,461
Timestamp: 2017-03-29 21:47:00
Document Index: 346201119

Matched Legal Cases: ['application No. 20050005125', 'application No. 20050005125', 'application No. 20050005125', 'application No. 20050193048', 'application No. 20050193048', 'application No. 20050193048', 'application No. 20070028114', 'application No. 20070028114', 'application No. 20070028114']

Patent US7890763 - Method of identifying invalid digital signatures involving batch verification - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsMethod of identifying invalid digital signatures involving batch verification by receiving digital messages, digital signatures, and signer identifiers, computing Z0 as a function of the received information, and determining if the digital signatures are valid. If so, stopping. If not, assigning a signature...http://www.google.com/patents/US7890763?utm_source=gb-gplus-sharePatent US7890763 - Method of identifying invalid digital signatures involving batch verificationAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS7890763 B1Publication typeGrantApplication numberUS 11/901,109Publication dateFeb 15, 2011Filing dateSep 14, 2007Priority dateSep 14, 2007Fee statusPaidPublication number11901109, 901109, US 7890763 B1, US 7890763B1, US-B1-7890763, US7890763 B1, US7890763B1InventorsLaurie E. Law, Brian J. MattOriginal AssigneeThe United States Of America As Represented By The Director, National Security Agency, Sparta, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (30), Non-Patent Citations (4), Referenced by (10), Classifications (14), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetMethod of identifying invalid digital signatures involving batch verification
Three methods of verifying a batch of digital signatures is disclosed in a paper by Mihir Bellare et al, entitled “Fast Batch Verification for Modular Exponentiation and Digital Signatures,” Advances in Cryptography—Eurocrypt 98 Proceedings, LCNS, Vol. 1403, pp. 236-250, Springer-Verlag, 1998. One of these methods is known as the “small exponents test.” The first step of the method is receiving a number of digital messages, digital signatures, and signer identifiers, where the digital signatures were generated using a generator g. The second step of the method is computing first and second numeric values corresponding to the digital messages, digitals signatures, and signer identifiers. The third step of the method is selecting a number of random numbers equal to the number of digital signatures. The fourth step of the method is associating each random number with a digital signature. The fifth step of the method is multiplying each first numeric value by its corresponding random number. The sixth step of the method is summing the products of the fifth step. The seventh step of the method is raising each second numeric value to a power, where the power is the corresponding random number. The eighth step of the method is multiplying the results of the seventh step. The ninth step of the method is raising g to the result of the sixth step. The tenth step of the method is comparing the results of the eighth and ninth steps. If the results are equal then the batch is valid and all of the digital signatures therein are valid. Otherwise, the batch is invalid and at least one digital signature therein is invalid.
If a batch of digital signatures is invalid then it is often necessary to identify the invalid digital signatures that caused the batch to fail. The naïve method is to perform an individual verification test on each digital signature in the batch. This requires as many verification tests as there are digital signatures in the batch, which may be too time consuming for many applications that require large numbers of digital signatures.
Divide-and conquer approaches (also know as “cut-and-choose” approaches) that reduce the number of verifications tests required to identify invalid digital signatures in an invalid batch are disclosed in a paper by J. Pastuszak et al., entitled “Identification of Bad Signatures in Batches,” Public Key Cryptography—PKC 2000, LCNS 1751, pp. 28-45, Springer-Verlag, 2000. That is, a verification test is performed on the original batch. If the batch is valid then stop. Otherwise, divide the batch into smaller batches. Then, perform a verification test on each smaller batch, eliminating the smaller batches that are valid, and further dividing the smaller batches that were invalid. Eventually, this technique will lead to the individual digital signatures that caused the original batch to fail the verification test. If each batch to be divided is halved, the divide-and-conquer approach becomes a binary search. In most cases, divide-and-conquer methods identify invalid digital signature more quickly than the naïve method. However, in some applications, identifying invalid signatures is still too time consuming. Therefore, a faster method of identifying invalid signatures is needed. The present invention is such a method.
In an article entitled “An Identity-Based Signature from Gap Diffie-Hellman Groups,” by J. Cha and J. Cheon, Public Key Cryptography—PKC 2003, LCNS, Vol. 2567, pp. 18-30, Springer-Verlag, 2003, an identity-based digital signature method that employs bilinear pairings is disclosed. The method can be described as follows. G1 and G2 are groups which have prime order r, meaning that there are exactly r elements in each group. The bilinear pairing e is a map from G1×G2 into a third group G3. This pairing has the properties that for an integer i and elements M,M1 and M2 in G1 and elements N, N1 and N2 in G2, e(iM,N)=e(M,iN)=e(M,N)i, e(M1+M2,N)=e(M1,N)+e(M2,N), and e(M,N1+N2)=e(M,N1) e(M,N2). H(m,U) is a cryptographic hash function that maps a bit string m and a point U in G1 to an integer between 1 and r.
In an article entitled “A New ID-Based Signature with Batch Verification,” by J. Cheon et al., Cryptology ePrint Archive, Report 2004/131, 2004, http://eprint.iacr.org/, a batch verification method for an identity-based digital signature is disclosed. This method uses partially aggregate digital signatures, which are shorter than those in a typical batch of digital signatures. However, using such digital signatures does not provide sufficient information to identify individual invalid digital signatures in a batch.
U.S. Pat. No. 5,347,581, entitled “VERIFICATION PROCESS FOR A COMMUNICATION SYSTEM,” discloses a method of batch verification of digital signatures and tree searching for invalid digital signatures. However, U.S. Pat. No. 5,347,581 does not disclose an efficient method for pruning the tree as does the present invention. U.S. Pat. No. 5,347,581 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,245,718, entitled “LOW BANDWIDTH ZERO KNOWLEDGE AUTHENTICATION PROTOCOL AND DEVICE,” discloses a method of verifying a batch of identities by calculating a product of the public keys of the identities in question. However, U.S. Pat No. 7,245,718 does not disclose a method for identifying invalid signatures in an invalid batches as does the present invention. U.S. Pat. No. 7,245,718 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application No. 20050005125, entitled “APPARATUS AND METHOD FOR GENERATING AND VERIFYING ID-BASED BLIND SIGNATURE BY USING BILINEAR PAIRINGS,” discloses a device for and method of batch verification of digital signatures using a process similar to that of U.S. Pat. 5,347,581. U.S. patent application No. 20050005125 does not disclose a method of identifying invalid digital signatures in invalid batches as does the present invention. U.S. patent application No. 20050005125 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application No. 20050193048, entitled “METHOD TO GENERATE, VERIFY AND DENY AN UNDENIABLE SIGNATURE,” discloses a method of batch verification involving a challenge parameter, a challenge value generated from the challenge parameters, and a commitment value. The present invention does not employ challenge parameters, a challenge value, and a commitment value as does U.S. patent application No. 20050193048. U.S. patent application No. 20050193048 is hereby incorporated by reference into the specification of the present invention.
U.S. patent application No. 20070028114, entitled “VERIFICATION OF IDENTITY BASED SIGNATURES,” discloses a method of batch verification of digital signatures by aggregating elements of the signatures. U.S. patent application No. 20070028114 does not disclose a method of identifying invalid digital signatures in invalid batches as does the present invention. U.S. patent application No. 20070028114 is hereby incorporated by reference into the specification of the present invention.
In a second alternate method, the invalid digital signatures are identified using a “divide-and-conquer” method with fewer verifications than in the prior art.
The preferred method can be applied to several pairing-based digital signatures, including the Cha-Cheon pairing-based digital signature method described earlier. When the preferred method is applied to the Cha-Cheon method, Bk=rk(Uk+H(mk,Uk)·Qk), Dk=Vk and R=−T.
The first alternative method can be applied to several pairing-based digital signatures, including the Cha-Cheon pairing-based digital signature method described earlier. When the first alternative method is applied to the Cha-Cheon method, Bk=rk(Uk+H(mk,Uk)·Qk), Dk=Vk and R=−T.
FIG. 3 is a second alternative embodiment of the present invention. The second alternative embodiment is a “divide-and-conquer” method of identifying invalid digital signatures involving batch verification. It uses the Z value computed during batch verification to eliminate some of the verifications required by “divide-and-conquer” methods in the prior art, resulting in a faster method.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4309569 *Sep 5, 1979Jan 5, 1982The Board Of Trustees Of The Leland Stanford Junior UniversityMethod of providing digital signaturesUS4759063 *Aug 22, 1983Jul 19, 1988Chaum David LBlind signature systemsUS4964164 *Aug 7, 1989Oct 16, 1990Algorithmic Research, Ltd.RSA computation method for efficient batch processingUS5214702 *May 13, 1992May 25, 1993Fischer Addison MPublic key/signature cryptosystem with enhanced digital signature certificationUS5263085 *Nov 13, 1992Nov 16, 1993Yeda Research & Development Co. Ltd.Fast signature scheme based on sequentially linearized equationsUS5347581Sep 15, 1993Sep 13, 1994Gemplus DeveloppementVerification process for a communication systemUS5600725 *Aug 17, 1994Feb 4, 1997R3 Security Engineering AgDigital signature method and key agreement methodUS6910130 *Nov 29, 2000Jun 21, 2005Hideki ImaiSystem for and method of unconditionally secure digital signatureUS7113594 *Aug 13, 2002Sep 26, 2006The Board Of Trustees Of The Leland Stanford UniversitySystems and methods for identity-based encryption and related cryptographic techniquesUS7245581Mar 16, 2001Jul 17, 2007Rohde & Schwarz Gmbh & Co. KgMethod and apparatus for normalizing amplitudes of orthogonal frequency division multiplex (OFDM) signalsUS7337322 *Oct 23, 2006Feb 26, 2008Ntt Docomo Inc.Hierarchical identity-based encryption and signature schemesUS7533270 *Apr 15, 2003May 12, 2009Ntt Docomo, Inc.Signature schemes using bilinear mappingsUS7725724 *Nov 12, 2004May 25, 2010Zte CorporationDigital signature method based on braid groups conjugacy and verify method thereofUS7739509 *Jan 25, 2005Jun 15, 2010Silverbrook Research Pty LtdAuthentication of an object using a signature partUS7814315 *Nov 30, 2006Oct 12, 2010Red Hat, Inc.Propagation of certificate revocation informationUS20020044648 *Mar 22, 2001Apr 18, 2002Benjamin AraziMethods and systems for efficient chained certificationUS20030188167 *Jan 13, 2003Oct 2, 2003Fuji Xerox Co., Ltd.Group signature apparatus and methodUS20040123110 *Sep 29, 2003Jun 24, 2004Information And Communications University Educational FoundationApparatus and method for ID-based ring structure by using bilinear pairingsUS20050005125Dec 2, 2003Jan 6, 2005Information And Communications University Educational FoundationApparatus and method for generating and verifying ID-based blind signature by using bilinear paringsUS20050154878 *Jan 10, 2005Jul 14, 2005David EngbergSignature-efficient real time credentials for OCSP and distributed OCSPUS20050154879 *Jan 10, 2005Jul 14, 2005David EngbergBatch OCSP and batch distributed OCSPUS20050193048Feb 13, 2004Sep 1, 2005Serge VaudenayMethod to generate, verify and deny an undeniable signatureUS20050193204 *Jan 10, 2005Sep 1, 2005David EngbergCommunication-efficient real time credentials for OCSP and distributed OCSPUS20070028114Sep 28, 2006Feb 1, 2007Mccullagh NoelVerification of identity based signaturesUS20080222418 *Jan 17, 2006Sep 11, 2008Yuichi FutaSignature Generation Device and Signature Verification DeviceUS20080226066 *Aug 3, 2007Sep 18, 2008Samsung Electronics Co., Ltd.Apparatus for batch verification and method using the sameUS20080320557 *Mar 12, 2008Dec 25, 2008Keisuke HakutaBatch verification device, program and batch verification methodUS20090112956 *Mar 31, 2006Apr 30, 2009Seoul National University Industry FoundationFast Batch Verification Method And Apparatus There-ofUS20100287378 *Jun 18, 2010Nov 11, 2010Adobe Systems IncorporatedSignatures for multiple encodingsJP2000047582A * Title not available* Cited by examinerNon-Patent CitationsReference1J. Cha et al.; "An Identity-Based Signature from Gap Diffie-Hellman Groups", Public Key Cryptography-PKC 2003, LCNS, vol. 2567, pp. 18-30, Springer-Verlag, 2003.2J. Cheon et al. "A New ID-based Signature with Batch Verification", Cryptology ePrint Archive, Report 2004/131, 2004, http://eprint.iacr.org/.3J. Pastuszak et al.; "Identification of Bad Signatures in Batches", Public Key Cryptography-PKC 2000, LCNS 1751, pp. 28-45, Springer-Verlag, 2000.4M. Bellare et al.;"Fast Batch Verification for Modular Exponentiation . . . "; Advances in Cryptography-Eurocrypt 98 Proc., LCNS, vol. 1403, pp. 236-250, Springer-Verlag, 1998.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8068614 *Sep 28, 2007Nov 29, 2011Intel CorporationMethods and apparatus for batch bound authenticationUS8285996 *Sep 28, 2006Oct 9, 2012Dublin City UniversityVerification of identity based signaturesUS8732472Apr 12, 2013May 20, 2014Kaspersky Lab ZaoSystem and method for verification of digital certificatesUS8874920 *Dec 19, 2008Oct 28, 2014Texas Instruments IncorporatedVerifying cryptographic signature from stored primitives of previously received signatureUS9037849Apr 30, 2013May 19, 2015Cloudpath Networks, Inc.System and method for managing network access based on a history of a certificateUS9577828Mar 25, 2015Feb 21, 2017Electronics And Telecommunications Research InstituteBatch verification method and apparatus thereofUS20070028114 *Sep 28, 2006Feb 1, 2007Mccullagh NoelVerification of identity based signaturesUS20090086981 *Sep 28, 2007Apr 2, 2009Kumar Mohan JMethods and Apparatus for Batch Bound AuthenticationUS20090217050 *Dec 19, 2008Aug 27, 2009Texas Instruments IncorporatedSystems and methods for optimizing signature verification time for a cryptographic cacheUS20110184586 *Jan 18, 2011Jul 28, 2011Tomoyuki AsanoPower management apparatus, and method of registering electronic appliances* Cited by examinerClassifications U.S. Classification713/176, 713/177, 705/75, 713/157International ClassificationG06Q20/00, H04L29/06, H04L9/32Cooperative ClassificationH04L2209/608, H04L9/3247, H04L2209/68, H04L9/3073, G06Q20/401European ClassificationH04L9/32S, G06Q20/401Legal EventsDateCodeEventDescriptionSep 14, 2007ASAssignmentOwner name: NATIONAL SECURITY AGENCY, MARYLANDEffective date: 20070912Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:LAW, LAURIE E.;REEL/FRAME:019877/0154May 21, 2014FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services