Low-overhead secure information processing for mobile gaming and other lightweight device applications

• US 7,340,058 B2
• Filed: 04/27/2001
• Issued: 03/04/2008
• Est. Priority Date: 04/09/2001
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Pointcheval, David, Young, Adam Lucas, Jakobsson, Bjorn Markus
• Primary Examiner(s): Sheikh; Ayaz
• Assistant Examiner(s): Abrishamkar; Kaveh
• Application Number:
  US09/844,121
• Publication Number:
  US 20020147044A1
• Time in Patent Office: 2,503 Days
• Field of Search: 713/200, 713/201, 713/193, 705/67, 380/251
• US Class Current: 380/251
• CPC Class Codes: A63F 13/71 using secure communication between game devices and game servers, e.g. by encrypting game data or authenticating players
• CPC Class Codes: A63F 2300/204 the platform being a handheld device
• CPC Class Codes: A63F 2300/401 Secure communication, e.g. using encryption or authentication
• CPC Class Codes: A63F 2300/406 Transmission via wireless network, e.g. pager or GSM
• CPC Class Codes: A63F 2300/50 characterized by details of game servers
• CPC Class Codes: A63F 2300/532 using secure communication, e.g. by encryption, authentication
• CPC Class Codes: G06Q 20/325 using wireless networks
• CPC Class Codes: G06Q 20/3674 involving authentication
• CPC Class Codes: G07F 17/32 for games, toys, sports, or amusements
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

Cryptography-based methods and apparatus for secure information processing are disclosed that are particularly efficient in terms of the computational resources required, and thus implementable in mobile telephones, personal digital assistants (PDAs) or other lightweight processing devices. A setup procedure is performed to permit interactions of a designated type, e.g., secure mobile gaming interactions, to be carried out between participants, e.g., one or more players and a casino. A given participant initiates a particular interaction with another participant by sending to that participant initiation information based at least in part on one or more results of the setup procedure. The other participant in turn sends response information back to the given participant, and the interaction then continues with one or more rounds each involving one or more decisions committed to by each participant. Transcripts of the interaction can be used to determine rights of the first and second participants in a publicly verifiable manner, with the rights being based upon particular results of the interaction. The invention may be configured to permit arbitrary disconnection of the lightweight devices, and provides the advantages of public verifiability, fairness and robustness. Although the invention is particularly well suited for use in secure mobile gaming applications, it is also applicable to other secure information processing applications, including contract signing and fair exchange of digital signatures.

Claims

1. A method for performing secure information processing operations utilizing a plurality of processing devices, the method comprising the steps of:

performing a setup procedure to permit interactions of a designated type to be carried out between a first participant associated with at least a first one of the processing devices and a second participant associated with at least a second one of the processing devices;

initiating in the first processing device a particular interaction with the second participant, by sending designated initiation information to the second processing device associated with the second participant, the particular interaction being configured based at least in part on one or more results of the setup procedure;

receiving as part of the interaction response information from the second processing device associated with the second participant; and

sending as part of the interaction additional information from the first processing device to the second processing device based at least in part on the received response information;

wherein the interaction is configured such that the information exchanged between the first and second processing devices can be used to determine rights of the first and second participants in a publicly verifiable manner, the rights being based upon particular results of the interaction;

wherein the interaction comprises a number of consecutive rounds of one or more decisions by each of the first participant and the second participant;

wherein the interaction is characterized by a first free structure associated with the first participant and a second free structure associated with the second participant, each of the tree structures comprising a plurality of nodes, each of at least a subset of the nodes comprising a block of data that determines randomness contributed to a corresponding round of the interaction by the corresponding participant, wherein associated with each of at least a subset of the nodes are decision preimage values that encode possible decisions to be made in the interaction.

2. The method of claim 1 wherein the receiving and sending steps are repeated one or more times in accordance with specifications of the particular interaction.

3. The method of claim 1 wherein the first processing device comprises at least one lightweight device configured to communicate over a network with the second processing device.

4. The method of claim 1 wherein the particular interaction comprises secure mobile gaming interaction in which the first participant corresponds to a player and the second participant corresponds to a casino.

5. The method of claim 4 wherein the first processing device comprises a lightweight processing device associated with the player and the second processing device comprises at least one server associated with the casino.

6. The method of claim 1 wherein the particular interaction comprises secure mobile gaming interaction involving two or more players in which the first participant corresponds to a first player and the second participant corresponds to a second player.

7. The method of claim 1 wherein the particular interaction comprises secure contact signing interaction in which the first participant corresponds to a first party to the contract and the second participant corresponds to a second party to the contract.

8. The method of claim 1 wherein the particular interaction comprises secure digital signature exchange interaction in which the first participant corresponds to a first party to the digital signature exchange and the second participant corresponds to a second party to the digital signature exchange.

9. The method of claim 1 wherein security of the particular interaction is based at least in part on a secure probabilistic symmetric cipher (E,D) having semantic security operating in conjunction with a one-way hash function h for which collisions are intractable to find, and a commitment function C, wherein the commitment function C provides the public verifiability of designated portions of the interaction.

10. The method of claim 1 wherein the interaction is configured such that if at least one of the first and second processing devices is disconnected during the interaction, the interaction may upon reconnection of the device be continued from a designated point at or prior to the disconnection without the participants being able to alter any partial results of the interaction attributable to a portion of the interaction up to the designated point.

11. The method of claim 4 wherein the secure mobile gaming interaction comprises at least one game played by the player with the casino, the game comprising a number of consecutive rounds of one or more moves by each of the player and the casino, each of the rounds allowing the player and the casino to commit to at least one decision.

12. The method of claim 11 wherein the game is characterized by a player game tree structure associated with the player and a casino game tree structure associated with the casino, each of the game tree structures comprising a plurality of nodes, each of at least a subset of the nodes comprising a block of data that determines randomness contributed to a corresponding round of the game by the corresponding player or casino, wherein associated with each of at least a subset of the game nodes are decision preimage values that encode possible decisions to be made in the game.

13. The method of claim 12 wherein the setup procedure comprises at least the following steps:

(a) the player selecting n random numbers d_i1, . . . , d_in, for each node i of the player game free structure, and a random number r_i uniformly at random for each node, wherein each node i corresponds to a particular round of the game;

(b) the player computing for each node i a corresponding game node value game_i=<

h(D_i1, . . . , D_in), R_i>

, where D_ij=h(d_ij), R_i=C(r_i), h denotes a hash function, C denotes a commitment function, and preimage_i=(d_i1, . . . , d_in, r_i) denotes a decision preimage value for game_i;

(c) the player computing for each node i a value which is a function of one or more of;

(i) values associated with one or more of its children nodes;

(ii) its corresponding game node value game_i; and

(iii) a descriptor that identifies the game type;

(d) both the player and the casino storing information of the form agreement_{(casino,player)} comprising a root value of the player game free structure, a root value of the casino game tree structure, a hash value on a game function ƒ

_game, and associated digital signatures by the player and the casino.

14. The method of claim 12 wherein the secure mobile gaming interactions are implemented in accordance with a game-playing protocol comprising at least the following steps:

(a) the player initiating the game by sending a value r_player,cnt to the casino, where cnt corresponds to a counter;

(b) the casino verifying that r_player,cnt is a correct preimage to R_player,cnt, and halting the protocol if it is not the correct preimage;

(c) the casino and the player taking turns making moves in which the casino sends to the player decision preimages encoding its move, the player is presented with one or more corresponding choices via an interface at the first processing device, and a given choice selected by the player is translated into one or more preimages that are subsequently sent to the casino;

(d) step (c) being repeated one or more times in accordance with the rules of the game;

(e)the casino sending a value r_casino,cnt to the player, which is verified correspondingly by the player;

(f) evaluating a game function ƒ

_games on the disclosed portions of the player and casino preimages, presenting a corresponding output to the player and the casino, and sending appropriate payment transcripts to at least one financial institution; and

(g) the player and the casino each updating the counter cnt, along with other state information associated with a current state of the game.

15. An apparatus for use in performing secure information processing operations, the apparatus comprising:

a memory; and

a processor coupled to the memory, the memory and processor being elements of a first processing device associated with a first participant, the processor being operative;

(i) to perform a setup procedure to permit interactions of a designated type to be carried out between the first participant and a second participant associated with at least a second processing device;

(ii) to initiate a particular interaction with the second participant, by sending designated initiation information to the second processing device associated with the second participant, the particular interaction being configured based at least in part on one or more results of the setup procedure;

(iii) receiving as part of the interaction response information from the second processing device associated with the second participant, and (iv) sending as part of the interaction additional information from the first processing device to the second processing device based at least in part on the received response information;

wherein the interaction is configured such that the information exchanged between the first and second processing devices can be used to determine rights of the first and second participants in a publicly verifiable manner, the rights being based upon particular results of the interaction;

wherein the interaction comprises a number of consecutive rounds of one or more decisions by each of the first participant and the second participant;

wherein the interaction is characterized by a first tree structure associated with the first participant and a second tree structure associated with the second participant, each of the tree structures comprising a plurality of nodes, each of at least a subset of the nodes comprising a block of data that determines randomness contributed to a corresponding round of the interaction by the corresponding participant, wherein associated with each of at least a subset of the nodes are decision preimage values that encode possible decisions to be made in the interaction.

16. The apparatus of claim 15 wherein receiving and sending operations (iii) and (iv) are repeated one or more times in accordance with specifications of the particular interaction.

17. The apparatus of claim 15 wherein the first processing device comprises at least one lightweight device configured to communicate over a network with the second processing device.

18. The apparatus of claim 15 wherein the particular interaction comprises secure mobile gaming interaction in which the first participant corresponds to a player and the second participant corresponds to a casino.

19. The apparatus of claim 18 wherein the first processing device comprises a lightweight processing device associated with the player and the second processing device comprises at least one server associated with the casino.

20. The apparatus of claim 15 wherein the particular interaction comprises secure mobile gaming interaction involving two or more players in which the first participant corresponds to a first player and the second participant corresponds to a second player.

21. The apparatus of claim 15 wherein the particular interaction comprises secure contract signing interaction in which the first participant corresponds to a first party to the contract and the second participant corresponds to a second party to the contract.

22. The apparatus of claim 15 wherein the particular interaction comprises secure digital signature exchange interaction in which the first participant corresponds to a first party to the digital signature exchange and the second participant corresponds to a second party to the digital signature exchange.

23. The apparatus of claim 15 wherein security of the particular interaction is based at least in part on a secure probabilistic symmetric cipher (E, D) having semantic security operating in conjunction with a one-way hash function h for which collisions are intractable to find, and a commitment function C, wherein the commitment function C provides the public verifiability of designated portions of the interaction.

24. The apparatus of claim 15 wherein the interaction is configured such that if at least one of the first and second processing devices is disconnected during the interaction, the interaction may upon reconnection of the device be continued from a designated point at or prior to the disconnection without the participants being able to alter any partial results of the interaction attributable to a portion of the interaction up to the designated point.

25. The apparatus of claim 18 wherein the secure mobile gaming interaction comprises at least one game played by the player with the casino, the game comprising a number of consecutive rounds of one or more moves by each of the player and the casino, each of the rounds allowing the player and the casino to commit to at least one decision.

26. The apparatus of claim 25 wherein the game is characterized by a player game tree structure associated with the player and a casino game tree structure associated with the casino, each of the game tree structures comprising a plurality of nodes, each of at least a subset of the nodes comprising a block of data that determines randomness contributed to a corresponding round of the game by the corresponding player or casino, wherein associated with each of at least a subset of the game nodes are decision preimage values that encode possible decisions to be made in the game.

27. An article of manufacture comprising a machine-readable storage medium for storing one or more programs for use in performing secure information processing operations utilizing a plurality of processing devices, wherein the one or more programs when executed implement the steps of:

performing a setup procedure to permit interactions of a designated type to be carried out between a first participant associated with at least a first one of the processing devices and a second participant associated with at least a second one of the processing devices;

initiating in the first processing device a particular interaction with the second participant, by sending designated initiation information to the second processing device associated with the second participant, the particular interaction being configured based at least in part on one or more results of the setup procedure;

receiving as part of the interaction response information from the second processing device associated with the second participant; and

sending as part of the interaction additional information from the first processing device to the second processing device based at least in part on the received response information;

wherein the interaction is configured such that the information exchanged between the first and second processing devices can be used to determine rights of the first and second participants in a publicly verifiable manner, the rights being based upon particular results of the interaction;

wherein the interaction comprises a number of consecutive rounds of one or more decisions by each of the first participant and the second participant;

wherein the interaction is characterized by a first tree structure associated with the first participant and a second free structure associated with the second participant, each of the tree structures comprising a plurality of nodes, each of at least a subset of the nodes comprising a block of data that determines randomness contributed to a corresponding round of the interaction by the corresponding participant, wherein associated with each of at least a subset of the nodes are decision preimage values that encode possible decisions to be made in the interaction.

28. A method for performing secure information processing operations utilizing a plurality of processing devices including at least a first processing device associated with a first participant and a second processing device associated with a second participant, the method comprising the steps of:

receiving from the first processing device in the second processing device designated initiation information initiating a particular interaction between the first participant and the second participant, the particular interaction being configured based at least in part on one or more results of a setup procedure, the setup procedure being performed by the first participant associated with the first processing device and permitting the particular interactions to be carried out between the first participant and the second participant;

sending as part of the interaction response information from the second processing device associated with the second participant; and

receiving as part of the interaction additional information sent from the first processing device to the second processing device based at least in part on the response information;

wherein the interaction is configured such that the information exchanged between the first and second processing devices can be used to determine rights of the first and second participants in a publicly verifiable manner, the rights being based upon particular results of the interaction;

wherein the interaction comprises a number of consecutive rounds of one or more decisions by each of the first participant and the second participant;

wherein the interaction is characterized by a first tree structure associated with the first participant and a second tree structure associated with the second participant, each of the tree structures corn rinsing a plurality of nodes, each of at least a subset of the nodes comprising a block of data that determines randomness contributed to a corresponding round of the interaction by the corresponding participant, wherein associated with each of at least a subset of the nodes are decision preimage values that encode possible decisions to be made in the interaction.