Privacy-protected transfer of electronic information

• US 5,604,805 A
• Filed: 02/09/1996
• Issued: 02/18/1997
• Est. Priority Date: 02/28/1994
• Status: Expired due to Term

• Current Assignee: Brands Stefan, Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Stefanus A. Brands
• Inventors: Brands, Stefanus A.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/598,871
• Time in Patent Office: 375 Days
• Field of Search: 380/25, 380/28, 380/30
• US Class Current: 380/30
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: G06Q 20/06 Private payment circuits, e.g. involving electronic currency used among participants of a common payment scheme
• CPC Class Codes: G06Q 20/381 Currency conversion
• CPC Class Codes: G07F 7/1016 Devices or methods for securing the PIN and other transaction-data, e.g. by encryption arrangements for secret communication, see H04L9/00
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3257 using blind signatures

Abstract

Cryptographic apparatus and means are disclosed for each of three types of participants in an electronic system for privacy-protected transfer of certified information. This invention reveals protocols that improve efficiency and security in such systems, and allows a variety of useful extensions in functionality without difficulty. This is achieved by a restrictive blind signature protocol in combination with a testing protocol. The restrictive blind signature protocol allows the certifying party to encode data into certified information that it provides to a receiving party, such that it cannot be altered or modified by the receiving party. The testing protocol enables parties to prove a variety of characteristics about the encoded data in their certified information.

Claims

1. A method for a first party to demonstrate to a second party a property of a vector of numbers, (u₁, . . . , u_k), where k≧

1 and each of u₁, . . . , u_k, is a number in a ring, _v, where v is a positive number, the method comprising the steps of;

generating k numbers, Z₁, . . . , Z_k, each of which is a number in a group, _n *, where n is a product of at least two distinct prime numbers;

computing by the first party, A=Z₁^u.sbsp.1 . . . Z_k^u.sbsp.k u_k+1^v, where u_k+1 is a number in _n *;

transmitting by the first party to the second party, a signal representative of A; and

demonstrating that the first party has access to a vector of numbers, (a₁, . . . , a_l ;

a_l+1), such that Y₁^a.sbsp.1 . . . Y_l^a.sbsp.l a_l+1^v is equal to a product of powers of numbers in the set, {A, Z₁, . . . , Z_k }, where l≦

0 and each of the numbers, Y₁, . . . , Y_l, is a product of powers of numbers in the set, {Z₁, . . . , Z_k }.

2. A method as in claim 1, wherein the step of demonstrating that the first party has access to the vector of numbers, (a₁, . . . , a_l ;

a_l+1), comprises the steps of;

generating by the first party, a vector of substantially random numbers, (b₁, . . . , b_l ;

b_l+1), where b₁, . . . , b_l are numbers in _v and b_l+1 is a number in _n *;

computing by the first party, B=Y₁^b.sbsp.l . . . Y_l^b.sbsp.l b_l+1^v ;

transmitting by the first party to the second party, a signal representative of B;

computing by the first party, l response numbers, r₁, . . . , r_l, in response to a challenge number, c, in _v, such that r_i =ca_i +b_i mod v for 1≦

i≦

l;

computing by the first party, a response number, r_l+1, in _n *, such that r_l+1 =(Π

_i=1^l Y_i^ca.sbsp.i^+b.sbsp.i^div v)·

a_l+1^c b_l+1 ; and

transmitting by the first party to the second party, signals representative of the l+1 response numbers.

3. A method for a first party to demonstrate to a second party a property of a vector of numbers, (u₁, . . . , u_k), where k≧

2 and each of u₁, . . . , u_k, is a number in a ring, _q, where q is a prime number, the method comprising the steps of;

generating k numbers, e₁, . . . , e_k, each of which is a number in a group, G_q, of order q;

computing by the first party, A=e₁^u.sbsp.1 . . . e_k^u.sbsp.k ;

transmitting by the first party to the second party, a signal representative of A; and

demonstrating that the first party has access to a vector of numbers, (a₁, . . . , a_l), such that g₁^a.sbsp.1 . . . g_l^a.sbsp.l is equal to a product of powers of numbers in the set, {A, e₁, . . . , e_k }, where l≧

1 and each of the numbers, g₁, . . . , g_l, is a product of powers of numbers in the set, {e₁, . . . , e_k }.

4. A method as in claim 3, wherein the step of demonstrating that the first party has access to the vector of numbers, (a₁, . . . , a_l), comprises the steps of:

generating by the first party, a vector of substantially random numbers, (b₁, . . . , b_l), where b₁, . . . , b_l are numbers in _q ;

computing by the first party, B=g₁^b.sbsp.1 . . . g_l^b.sbsp.l ;

transmitting by the first party to the second party, a signal representative of B;

computing by the first party, l response numbers, r₁, . . . , r_l, in response to a challenge number, c, in _q, such that r_i =ca_i +b_i mod q for 1≦

i≦

l; and

providing by the first party to the second party, signals representative of the l response numbers.

5. An apparatus for a first party to demonstrate to a second party a property of a vector of numbers, (u₁, . . . , u_k), where k≧

1 and each of u₁, . . . , u_k, is a number in a ring, _v, where v is a positive number, the apparatus comprising;

first processing means for use by the first party;

second processing means for use by the second party;

interface means between the first processing means and the second processing means;

means for generating k numbers, Z₁, . . . , Z_k, each of which is a number in a group, _n *, where n is a product of at least two prime distinct numbers;

means within the first processing means for computing A=Z₁^u.sbsp.1 . . . Z_k^u.sbsp.k u_k+1^v, where u_k+1 is a number in _n *;

means within the first processing means for transmitting to the second processing means, a signal representative of A; and

means within the first processing means for demonstrating access to a vector of numbers, (a₁, . . . , a_l ;

a_l+1), such that Y₁^a.sbsp.l . . . Y_l^a.sbsp.l a_l+1^v is equal to a product of powers of numbers in the set, {A, Z₁, . . . , Z_k }, where l≧

0 and each of the numbers, Y₁, . . . , Y_l, is a product of powers of numbers in the set, {Z₁, . . . , Z_k }.

6. An apparatus as in claim 5, wherein the means within the first processing means for demonstrating that it has access to the vector of numbers, (a₁, . . . , a_l ;

a_l+1), comprises;

means for generating a vector of substantially random numbers, (b₁, . . . , b_l ;

b_l+1), where b₁, . . . , b_l are numbers in _v and b_l+1 is a number in _n *;

means for computing, B=Y₁^b.sbsp.1 . . . Y_l^b.sbsp.l b_l+1^v ;

means for transmitting to the second processing means, a signal representative of B;

means for computing l response numbers, r₁, . . . , r_l, in response to a challenge number, c, in _v, such that r_i =ca_i +b_i mod v for 1≦

i≦

l;

means for computing a response number, r_l+1, in _n *, such that r_l+1 =(Π

_i=1^l Y_i^ca.sbsp.i^+b.sbsp.i^div v)·

a_l+1^c b_l+1 ; and

means for transmitting to the second processing means, signals representative of the l+1 response numbers.

7. An apparatus for a first party to demonstrate to a second party a property of a vector of numbers, (u₁, . . . , u_k), where k≧

2 and each of u₁, . . . , u_k, is a number in a ring, _q, where q is a prime number, the apparatus comprising;

first processing means for use by the first party;

second processing means for use by the second party;

interface means between the first processing means and the second processing means;

means for generating k numbers, e₁, . . . , e_k, each of which is a number in a group, G_q, of order q;

means within the first processing means for computing, A=e₁^u.sbsp.1 . . . e_k^u.sbsp.k ;

means within the first processing means for transmitting to the second processing means, a signal representative of A; and

means within the first processing means for demonstrating access to a vector of numbers, (a₁, . . . , a_l), such that g₁^a .sbsp.l . . . g_l^a.sbsp.l is equal to a product of powers of numbers in the set, {A, e₁, . . . , e_k }, where l≧

1 and each of the numbers, g₁, . . . , g_l, is a product of powers of numbers in the set, {e₁, . . . , e_k }.

8. An apparatus as in claim 7, wherein the means within the first processing means for demonstrating to the second processing means access to the vector of numbers, (a₁, . . . , a_l), comprises:

means for generating a vector of substantially random numbers, (b₁, . . . , b_l), where b₁, . . . , b_l are numbers in _q ;

means for computing, B=g₁^b.sbsp.1 . . . g_l^b.sbsp.l ;

means for transmitting to the second processing means, a signal representative of B;

means for computing l response numbers, r₁, . . . , r_l, in response to a challenge number, c, in _q, such that r_i =ca_i +b_i mod q for 1≦

i≦

l; and

means for transmitting to the second processing means, signals representative of the l response numbers.