×

Methods and apparatus for verifying the cryptographic security of a selected private and public key pair without knowing the private key

  • US 6,411,715 B1
  • Filed: 11/10/1998
  • Issued: 06/25/2002
  • Est. Priority Date: 11/10/1997
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for a proving entity to demonstrate to a verifying entity the cryptographic security of a private key and a public key, wherein said keys comprise n prime numbers pi, wherein said i is an index variable ranging from 1 to n, the method comprising the steps of:

  • (a) determining, by said verifying entity, that a product N is the product of exactly n primes, wherein said product N is the product of said prime numbers pi;

    (b) selecting a base r, wherein said base r is an element of a first distribution;

    (c) selecting, by said proving entity, a plurality of n blinding random numbers ki, wherein said blinding random numbers ki are members of a second distribution;

    (d) publishing, by said proving entity, a plurality of n commitment numbers hi, each of said commitment numbers hi comprising said base r raised to an exponent Ei;

    (e) publishing, by said proving entity, a sum k, said sum k equal to the sum of said plurality of blinding random numbers ki;

    (f) determining, by said verifying entity, that the product of said plurality of commitment numbers hi equals a verification number X;

    (g) determining, by said verifying entity, that said sum k is less than n times the largest element in said second distribution;

    (h) publishing, by said verifying entity, a selection indicating an exponent selected from the group consisting of said plurality of exponents Ei;

    (i) publishing, by said proving entity, all of said plurality of exponents Ei except said selected exponent;

    (j) determining, by said verifying entity, that the value of said base r raised to an exponent Ei equals a commitment number hi; and

    (k) determining, by said verifying entity, that an exponent Ei is greater than or equal to a lower bound and less than or equal to an upper bound.

View all claims
  • 5 Assignments
Timeline View
Assignment View
    ×
    ×