Electronic ticket system

• US 6,690,794 B1
• Filed: 07/10/1998
• Issued: 02/10/2004
• Est. Priority Date: 07/14/1997
• Status: Expired due to Fees

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Kamei, Mitsuhisa, Nakatsuyama, Hisashi, Terao, Taro
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): Song, Hosuk
• Application Number:
  US09/113,170
• Time in Patent Office: 2,041 Days
• Field of Search: 705/75-77, 705/5, 705/65-66, 713/185, 713/186, 713/189, 713/194, 235/384, 235/375, 235/380, 235/382, 380/51, 380/22
• US Class Current: 380/22
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3213 using tickets or tokens, e.g. Kerberos network architectures or network communication protocols for entities authentication using tickets in a packet data network H04L63/0807
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

An electronic ticket system for virtually preventing forgery, copying and other unauthorized uses of electronic tickets; for proving to a third party the contents of an electronic ticket contested between a user and an issuing party; and for protecting users'"'"' anonymity upon ticket use. The system comprises a ticket creating and issuing device, a ticket proving device, and a ticket verification device. A ticket creating unit in the ticket creating and issuing device creates specifications of a ticket representing a predetermined service or product in response to a ticket creating request. A ticket issuing unit of the ticket creating and issuing device, in reply to a ticket issuing request, issues the corresponding ticket using as input a ticket identifier, a proving identifier, a ticket specification identifier, and ticket added information. The ticket proving device gets a ticket issued by the ticket issuing unit and communicates with the ticket verification device to prove the possession of the ticket. The ticket verification device has a ticket verifying procedure and, on getting the ticket identifier created by the ticket creating unit, communicates with the ticket proving device to verify the ticket.

Claims

1. An electronic ticket system comprising a ticket issuing device, a verification device and a proving device, wherein said ticket issuing device comprises:

ticket characteristic information hold means for holding at least ticket public information and ticket secret information;

proving device unique identifying information hold means for holding proving device unique identifying information;

proving device identifying information hold means for holding proving device identifying information in association with said proving device unique identifying information; and

ticket issuing means for creating a ticket made of digital information by combining at least said ticket secret information and said proving device unique identifying information;

wherein said verification device comprises;

authenticating information generating means for generating a value used in an interactive proof; and

interactive verification means for verifying interactively whether said proving device has calculated said ticket secret information, and

wherein said proving device comprises;

proving device unique identifying information hold means;

ticket hold means; and

interactive proof means for proving interactively knowledge about said ticket secret information on the basis of at least said proving device unique identifying information and said ticket.

2. The electronic ticket system according to claim 1, wherein said ticket issuing device has ticket characteristic information creating means for creating ticket characteristic information.

3. The electronic ticket system according to claim 1, wherein said ticket issuing device has proving device identifying information hold means for holding proving device identifying information in association with said proving device unique identifying information.

4. The electronic ticket system according to claim 1, wherein at least said ticket public information and said ticket secret information constitute ticket characteristic information.

5. The electronic ticket system according to claim 4, wherein said ticket public information is made of a finite Abelian group, and said ticket secret information constitutes a annhilator area of said finite Abelian group.

6. The electronic ticket system according to claim 4, wherein said ticket secret information is an integer, and said ticket public information is a finite group, an element of said finite group, an order of said element, and a multiple of the element and secret information.

7. The electronic ticket system according to claim 1, wherein said proving device has internal state hold means for holding a variable internal state.

8. The electronic ticket system according to claim 7, wherein at least part of said variable internal state held by said internal state hold means of said proving device is protected against external attempts at modifying.

9. The electronic ticket system according to claim 7, wherein, during said interactive verification and said interactive proof, redundant information is transmitted at least once with respect to proof of knowledge about secret information.

10. The electronic ticket system according to claim 8, wherein said proving device has ticket counting means for holding information indicating an initialized internal state.

11. The electronic ticket system according to claim 10, wherein said proving device transmits at least once to said verification device information acquired from the internal state information of said proving device.

12. The electronic ticket system according to claim 11, wherein information acquired from that internal state information of said proving device which cannot be modified externally is transmitted at least once from said proving device to said verification device.

13. The electronic ticket system according to claim 8, wherein said internal state hold means of said proving device holds, in association with said ticket, an internal state indicating the validness of said ticket in a way that protects said internal state against external attempts at modifying;

and

wherein, if said internal state indicating the validness of said ticket takes a specific value, the corresponding ticket is judged to be invalid and information indicating invalidness of said ticket is transmitted during said interactive proof.

14. The electronic ticket system according to claim 13, wherein said verification device transmits information at least once to said proving device;

and

wherein, in accordance with the transmitted information from said verification device, said proving device changes the internal state which is associated with said ticket and which indicates the validness of said ticket, in order to either invalidate a valid ticket or validate an invalid ticket.

15. The electronic ticket system according to claim 8, wherein said internal state hold means of said proving device associates said ticket with an internal state acting as a ticket counter, said internal state being held so as to be protected against external attempts at modifying;

wherein, during said interactive proof, an arithmetic operation is executed by use of said internal state acting as said ticket counter; and

wherein, if said arithmetic operation results in a specific value, the corresponding ticket is judged to be invalid and information indicating the invalidness of said ticket is transmitted during said interactive proof.

16. The electronic ticket system according to claim 15, wherein said verification device transmits information at least once to said proving device;

and

wherein, in accordance with the transmitted information from said verification device, said proving device sets said internal state which is associated with said ticket and which acts as said ticket counter.

17. The electronic ticket system according to claim 1, wherein said proving device has a proving procedure execution unit capable of executing a plurality of interactive verifying procedures;

and

wherein part of ticket characteristic information in said ticket characteristic information hold means is used to select an appropriate proving procedure from among said plurality of interactive verifying procedures in order to carry out said interactive proof.

18. The electronic ticket system according to claim 1, wherein said proving device has a proving procedure execution unit capable of executing a program in which at least part of steps constituting an interactive verifying procedure is described;

and

wherein said program is extracted from part of ticket characteristic information in said ticket characteristic hold means in order to carry out said interactive proof.

19. The electronic ticket system according to claim 1, wherein said verification device holds one of three kinds of information:

information communicated between said verification device and said proving device during said interactive verification, part of the communicated information, and information generated by performing an arithmetic operation on said communicated information either as a whole or in part.

20. The electronic ticket system according to claim 1, wherein said verification device holds a combination of two kinds of information:

information used by said verification device to generate information to be transmitted to said proving device during said interactive verification; and

information acquired by said proving device having executed computation on the transmitted information from said verification device, the acquired information being returned from said proving device to said verification device.

21. The electronic ticket system according to claim 1, wherein said verification device includes verification device unique identifying information hold means for holding verification device unique identifying information, and ticket hold means for holding a ticket, said verification device further utilizing information acquired from said ticket during said interactive verification.

22. The electronic ticket system according to claim 1, wherein said proving device calculates proof information using a predetermined method based on authenticating information, said ticket public information, said ticket, ticket added information, and said proving device unique identifying information.

23. The electronic ticket system according to claim 22, wherein, given that D stands for said ticket secret information, that (n, E) denotes said ticket public information, that λ

(n) represents the maximum order of numbers modulo n, such that ED≡

1 mod λ

(n), that L indicates said ticket added information, that said proving device unique identifying information constitutes a secret one-way function d_U(L, n), and that said ticket t is defined as t;

=D−

d_U(L, n), said proving device, upon receipt of authenticating information C, calculates proof information R by obtaining a product of C^tC{circumflex over ( )}d_U(L, n) mod n.

24. The electronic ticket system according to claim 22, wherein, given that D stands for said ticket secret information, that (n, E) denotes said ticket public information, that ED≡

1 mod λ

(n), that L indicates said ticket added information, that said proving device unique identifying information constitutes a secret value, that f(d_U, L, n) is a one-way function, and that said ticket t is defined as t;

=D−

f(d_U, L, n), said proving device, upon receipt of authenticating information C, calculates proof information R by obtaining a product of C^tC{circumflex over ( )}f(dU, L, n) mod n.

25. The electronic ticket system according to claim 22, wherein, given that x stands for said ticket secret information, that p denotes a prime number, that G represents a finite group of which discrete logarithm problems are difficult to solve, that g stands for an element of the order p of said finite group G, that said ticket public information is given as (p, G, g, y), such that y=g^x, that L denotes said ticket added information, that said proving device unique identifying information constitutes a secret one-way function d_U(L, y), and that said ticket t is defined as t:

=x−

d_U(L, y), said proving device, upon receipt of authenticating information C, calculates proof information R by obtaining a product of C^tC{circumflex over ( )}d_U(L, y).

26. The electronic ticket system according to claim 22, wherein, given that x stands for said ticket secret information, that said ticket public information is given as (p, G, g, y), such that y=g^x, that L denotes said ticket added information, that said proving device unique identifying information constitutes a secret value d_U, that f(d_U, L, y) is a one-way function, and that said ticket t is defined as t:

=x−

f(d_U, L, y), said proving device, upon receipt of authenticating information C, calculates proof information R by obtaining a product of C^tC{circumflex over ( )}f(d_U, L, y).

27. The electronic ticket system according to claim 22, wherein said verification device judges whether said proof information is correct from said authenticating information, said proof information and said ticket public information, said verification device further extracting information from said proof information if said proof information is judged to be correct.

28. The electronic ticket system according to claim 27, wherein said verification device, given authenticating information C, proof information R and ticket public information (n, E), compares said authenticating information C with said proof information R to the power of E modulo n;

and

wherein said verification device judges said proof information R to be correct if R^E mod n=C∥

M, where M represents a bit string and denotes a bit concatenation of C and M, said bit string M being furnished as information extracted from said proof information R if said proof information R is judged to be correct.

29. The electronic ticket system according to claim 27, wherein said verification device, given authenticating information C, proof information R, ticket public information (n, E) and a value M which is smaller than a predetermined limit I, judges said proof information R to be correct if said proof information R to the power of E^M modulo n is equal to said authenticating information C, said value M being furnished as said information extracted from said proof information R if said proof information R is judged to be correct.

30. The electronic ticket system according to claim 27, wherein said proving device has output information hold means, said proving device further calculating said proof information by use of output information held in said output information hold means and of said authenticating information when calculating with said ticket secret information.

31. The electronic ticket system according to claim 30, wherein said proving device has output information hold means for holding output information M, said proving device further calculating said proof information as

32. The electronic ticket system according to claim 30, wherein said proving device has output information hold means for holding output information, said proving device further updating said authenticating information by use of said output information held in said output information hold means before calculating with said ticket secret information.

33. The electronic ticket system according to claim 32, wherein said proving device has output information hold means for holding output information M, said proving device further updating said authenticating information into

34. The electronic ticket system according to claim 22, wherein said proving device calculates said ticket secret information using a predetermined method based on said ticket, said ticket added information and said proving device unique identifying information, said proving device further generating said proof information by performing on said authenticating information an arithmetic operation involving said ticket secret information.

35. The electronic ticket system according to claim 34, wherein, given that D stands for said ticket secret information, that L denotes said ticket added information, that said proving device unique identifying information constitutes a decryption key d_U of a cryptosystem, that E_U represents an encryption corresponding to said proving device unique identifying information, and that said ticket is defined as t:

=E_U(D∥

L), said proving device calculates said ticket secret information D and said ticket added information L by decrypting said ticket by use of said decryption key d_U.

36. The electronic ticket system according to claim 34, wherein, given that D stands for said ticket secret information, that L denotes said ticket added information, that said proving device unique identifying information constitutes a decryption key d_U of a cryptosystem, that E_U represents an encryption corresponding to said proving device unique identifying information, that h(L) stands for a one-way function, and that said ticket is defined as t:

=E_U(D∥

h(L)), said proving device calculates said ticket secret information D by decrypting said ticket t using said decryption key d_U and then calculates the one-way function value h(L) of said ticket added information L, whereby integrity of said ticket added information L is verified.

37. The electronic ticket system according to claim 34, wherein, given that D stands for said ticket secret information, that L denotes said ticket added information, that said proving device unique identifying information constitutes a decryption key d_U of a cryptosystem, that E_U represents a code corresponding to said proving device unique identifying information, that h(L) stands for a one-way function, and that said ticket is defined as t:

=(E_U(D), h(d_U∥

D∥

L)), said proving device calculates said ticket secret information D by decrypting a first component of said ticket t using said decryption key d_U, and verifies integrity of said ticket added information L by comparing a second component of said ticket t with the one-way function value h(d_U∥

D∥

L).

38. The electronic ticket system according to claim 22, wherein said proving device has second authenticating information generating means for generating second authenticating information, said proving device further checking to see whether second proof information is correct from said second authenticating information, said second proof information and said ticket added information, the internal state of said proving device being updated if said second proof information is judged to be correct.

39. The electronic ticket system according to claim 38, wherein said ticket added information L includes at least part of information ν

∥

ε

for verifying said verification device, said proving device further judging said second proof information ρ

to be correct if said second authenticating information χ and

said second proof information ρ

satisfy

40. The electronic ticket system according to claim 38, wherein said ticket added information L includes at least part of η

, said proving device further judging said second proof information ρ

to be correct if said second authenticating information g^s and said second proof information ρ

satisfy

41. The electronic ticket system according to claim 38, wherein said proving device has input information hold means, said proving device further extracting input information from said second proof information if said second proof information is judged to be correct, the extracted information being placed into said input information hold means.

42. The electronic ticket system according to claim 41, wherein said ticket added information L comprises at least part of information ν

∥

ε

, said proving device further judging said second proof information ρ

to be correct if said second authenticating information χ

, said second proof information ρ and

a given bit string μ

satisfy

43. The electronic ticket system according to claim 41, wherein said ticket added information L comprises at least part of information ν

∥

ε

, said proving device further judging said second proof information ρ

to be correct if said second authenticating information χ

, said second proof information ρ

, and a value μ

which is smaller than a predetermined limit I satisfy

44. The electronic ticket system according to claim 22, wherein said proving device has input information hold means for holding input information and internal state hold means for holding an internal state, said internal state being updated on the basis of said input information placed in said input information hold means.

45. The electronic ticket system according to claim 22, wherein said proving device checks to see whether said proof information is correctly generated on the basis of said authenticating information and said ticket added information.

46. The electronic ticket system according to claim 22, wherein said proving device checks to see whether said proof information is correctly generated on the basis of an internal state of said proving device and said ticket added information.

47. The electronic ticket system according to claim 22, wherein said proving device has output information hold means, and calculates output information on the basis of an internal state of said proving device and said ticket added information, the calculated output information being placed into said output information hold means.

48. The electronic ticket system according to claim 22, wherein said verification device generates second proof information based on second authenticating information and secret information representing a privilege.

49. The electronic ticket system according to claim 48, wherein, given that δ

stands for said secret information representing said privilege, that the corresponding public information is given as (ν

, ε

), and that ε

δ

↑

1 mod λ

(ν

), said verification device generates said second proof information ρ

based on said second authenticating information χ

as

ti ρ

;

=χ

^δ

mod ν

.

50. The electronic ticket system according to claim 48, wherein, given that ξ

stands for said secret information representing said privilege, that the corresponding public information is given as (p, g, q, η

), and that η

=g^ξ

mod p, said verification device generates said second proof information ρ

based on said second authenticating information χ

as

51. The electronic ticket system according to claim 48, wherein said verification device has input information hold means, said verification device further calculating said second proof information based on input information held in said input information hold means and on said second authenticating information when calculating with said secret information representing said privilege.

52. The electronic ticket system according to claim 51, wherein, given that δ

stands for said secret information representing said privilege, that the corresponding public information is given as (ν

, ε

), and that ε

δ

≡

1 mod λ

(ν

);

said verification device generates said second proof information ρ

based on said input information μ

held in said input information hold means and on said second authenticating information χ

as

53. The electronic ticket system according to claim 48, wherein said verification device has input information hold means, said verification device further updating said second authenticating information by use of input information held in said input information hold means before calculating with said secret information representing said privilege.

54. The electronic ticket system according to claim 53, wherein said verification device has input information hold means for holding input information μ

, said verification device further updating said second authenticating information χ

into χ

∥

μ

.