WO2010109060A1

WO2010109060A1 - Method and apparatus for providing off-line payment transactions with minimal data transfer

Info

Publication number: WO2010109060A1
Application number: PCT/FI2010/050199
Authority: WO
Inventors: Nadarajah Asokan; Jan-Erik Ekberg
Original assignee: Nokia Corporation
Priority date: 2009-03-26
Filing date: 2010-03-16
Publication date: 2010-09-30
Also published as: BRPI1014196A2; BRPI1014196A8; CN102369547A

Abstract

An approach is provided for facilitating purchases and other transactions using a network capable device but in an off-line manner. Relatively short-lived cryptographic keys and certificates stored on a user device (728) are utilized to minimize the amount of data used during authentication and verification of the transaction (732, 734, 736). Thus, the transaction may be completed without transmission or receiving of information over the network during the transaction.

Description

METHOD AND APPARATUS FOR PROVIDING OFF-LINE PAYMENT TRANSACTIONS WITH MINIMAL DATA TRANSFER

BACKGROUND

[0001] Many users of portable computing devices desire the convenience of paying for transactions and purchases through use of that device in order to have a convenient payment method and to alleviate the need to carry money or currency around. In order for such transactions to occur, it is beneficial for a certain level of trust to exist in the identity of the participants and their ability to pay for the purchases or transactions. Accordingly, complex cryptographic algorithms have been developed to provide the authentication and verification techniques useful for providing the desired trust for such transactions. However, these techniques typically involve transferring relatively large amounts of data and signatures during the transactions not only between the participants but also with an additional third party. As a result, performing such a transaction involves having a network communication channel available that has a relatively large bandwidth.

SOME EXEMPLARY EMBODIMENTS

[0002] Therefore, there is a need for an approach for allowing transactions between a customer's portable computing device and a merchant in an off-line manner for minimizing the need to communicate with a third party as well as minimizing the amount of data transferred between the customer and merchant devices.

[0003] An embodiment relates to a computer-readable storage medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to perform a number of functions. The processors at least perform the following: initiating receiving of one or more parameters for off-line payment, wherein the parameters relate to a predetermined time period; generating, based on the parameters, a public key and a private key that are valid for the predetermined time period; and signing transaction data associated with the off-line payment using the private key during the predetermined time period.

[0004] Another embodiment relates to an apparatus comprising a processor and a memory storing executable instructions that (1) as part of execution or as a result of execution at least or (2) as both part of execution and as a result of execution at least cause the apparatus to perform at least the following: initiating receiving of one or more parameters for off-line payment, wherein the parameters relate to a predetermined time period; generating, based on the parameters, a public key and a private key that are valid for the predetermined time period; and signing transaction data associated with the off-line payment using the private key during the predetermined time period.

[0005] Another embodiment relates to an apparatus comprising means for initiating receiving of one or more parameters for off-line payment, wherein the parameters relate to a predetermined time period; means for generating, based on the parameters, a public key and a private key that are valid for the predetermined time period; and means for signing transaction data associated with the offline payment using the private key during the predetermined time period.

[0006] Another embodiment relates to an apparatus comprising a processor and a memory storing executable instructions that if executed cause the apparatus to at least perform generating cryptographic parameters that relate to a predetermined time period; generating, using the cryptographic parameters, a first public key and a first private key that are valid for the predetermined time period which verify an identity of a party in an off-line transaction; and generating a first certificate related to the first public key and the first private key, which verify the cryptographic parameters for the party, wherein for a subsequent time period, different cryptographic information is generated.

[0007] Another embodiment relates to an apparatus comprising means for generating cryptographic parameters that relate to a predetermined time period; means for generating, using the cryptographic parameters, a first public key and a first private key that are valid for the predetermined time period which verify an identity of a party in an off-line transaction; means for generating a first certificate related to the first public key and the first private key, which verify the cryptographic parameters for the party, wherein for a subsequent time period, different cryptographic information is generated.

[0008] Yet another embodiment relates to a method that comprises generating cryptographic parameters that relate to a predetermined time period; generating, using the cryptographic parameters, a first public key and a first private key that are valid for the predetermined time period which verify an identity of a party in an off-line transaction; and generating a first certificate related to the first public key and the first private key, which verify the cryptographic parameters for the party, wherein for a subsequent time period, different cryptographic information is generated. [0009] Still other aspects, features, and advantages of the invention are readily apparent from the following detailed description, simply by illustrating a number of particular embodiments and implementations, including the best mode contemplated for carrying out the invention. The invention is also capable of other and different embodiments, and its several details can be modified in various obvious respects, all without departing from the spirit and scope of the invention. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not as restrictive, cryptographic information for each subsequent time period.

BRIEF DESCRIPTION OF THE DRAWINGS

[0010] The embodiments of the invention are illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings:

[0011] FIG. 1 is diagram of a communications system capable of providing off-line transaction, according to an exemplary embodiment;

[0012] FIG. 2A is a diagram of functional components of a device for performing off-line transactions, in accordance with one embodiment;

[0013] FIG. 2B is a diagram of one example of a user device performing an off-line transaction, in accordance with one embodiment;

[0014] FIG. 3 is a flowchart of a process for generating transaction credentials between a user device and a trusted service, in accordance with one embodiment;

[0015] FIG. 4 is a flowchart of a process for generating transaction credentials between a merchant and a trusted service, in accordance with one embodiment;

[0016] FIG. 5 is a flowchart of a process for performing an off-line transaction, in accordance with one embodiment;

[0017] FIG. 6 is a flowchart of a process for generating transaction credentials between a user device and a merchant, in accordance with one embodiment;

[0018] FIG. 7 is a ladder diagram of an example protocol for off-line transactions, in accordance with another embodiment;

[0019] FIG. 8 is a diagram of hardware that can be used to implement an embodiment of the invention;

[0020] FIG. 9 is a diagram of a chip set that can be used to implement an embodiment of the invention; and [0021] FIG. 10 is a diagram of a mobile station (e.g., handset) that can be used to implement an embodiment of the invention.

DESCRIPTION OF PREFERRED EMBODIMENT

[0022] A method and apparatus for facilitating off-line transactions and purchases are disclosed. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the embodiments of the invention. It is apparent, however, to one skilled in the art that the embodiments of the invention may be practiced without these specific details or with an equivalent arrangement. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the embodiments of the invention.

[0023] FIG. 1 is diagram of a communications system capable of providing off-line transactions, according to an exemplary embodiment. In the system 100, a user device 101a-101n is operated by a respective user to access various resources available over the network 103. In particular, the user device 10Ia-IOIn may rely on a trusted third party, such as a bank or financial institution, 107 to provide various services over the network 103. The user device 10Ia-IOIn can be any type of mobile terminal, fixed terminal, or portable terminal including mobile handsets, stations, units, devices, multimedia tablets, Internet nodes, communicators, desktop computers, laptop computers, Personal Digital Assistants (PDAs), or any combination thereof. It is also contemplated that the UEs 10Ia-IOIn can support any type of interface to the user (such as "wearable" circuitry, etc.). In the case of a mobile device such as a cellular telephone, a particular carrier may provide service such that the user device 10Ia-IOIn can have network access. Using this ability to access the network 103, the user device 10Ia-IOIn can communicate with other computers and systems. One example of such a system is a merchant 109. In particular, the merchant 109 may permit online transaction processing or off-line transaction processing.

[0024] When conducting transactions, such as purchases, between two entities there is typically an exchange of encrypted data and certificates so that the identity of the entities may be authenticated and so that the data exchanged may be verified. Accordingly, the trusted third party 107 is involved in generating the credentials used by both the user device 10Ia-IOIn and the merchant 109. The credentials include various keys and certificates 111 that are stored on each user device 10Ia-IOIn and keys and certificates 113 stored at the merchants location. During a transaction involving a user device 10Ia-IOIn and the merchant 109, these credentials can be used so that both parties can have confidence in the transaction. Also, because these credentials are stored locally, they do not have to be retrieved over a network connection during the transaction thereby allowing the transaction to take place off-line.

[0025] By way of example, the communication network 103 of system 100 includes one or more networks such as a data network (not shown), a wireless network (not shown), a telephony network (not shown), or any combination thereof. It is contemplated that the data network may be any local area network (LAN), metropolitan area network (MAN), wide area network (WAN), the Internet, or any other suitable packet-switched network, such as a commercially owned, proprietary packet- switched network, e.g., a proprietary cable or fiber-optic network. In addition, the wireless network may be, for example, a cellular network and may employ various technologies including enhanced data rates for global evolution (EDGE), general packet radio service (GPRS), global system for mobile communications (GSM), Internet protocol multimedia subsystem (IMS), universal mobile telecommunications system (UMTS), etc., as well as any other suitable wireless medium, e.g., microwave access (WiMAX), Long Term Evolution (LTE) networks, code division multiple access (CDMA), wireless fidelity (WiFi), satellite, mobile ad-hoc network (MANET), and the like.

[0026] FIG. 2A is a diagram of functional components of a device 101 for performing off-line transactions, in accordance with one embodiment. The user device 101 includes a data receiver 203 that is capable of receiving data in a variety of modes. For example, the data receiver 203 can receive input from a keypad or user interface of the device 101. Additional sources of data can include a camera built into the device 101, text from text messages that can be received by the device 101, and audio input that is received by a microphone of the device 101. The device 101 may also receive packet data that can be decoded and received by the data receiver 203.

[0027] Because the device 101 may be involved in transactions such as purchases, a signed data verifier 205 is included as well. The signed data verifier handles received data that may be encrypted or signed with a cryptographic key. In handling this data the signed data verifier 205 verifies that the data is properly signed or encrypted. If so, then the data can be further used in the transaction process. If not, then a user of the device 101 can be alerted and the transaction process can be terminated. In accordance with one embodiment, the user device 101 receives information from a trusted third party, or service, regarding short-lived key pairs that can be used for transactions. Thus, once such information is authenticated by the verifier 205, an epoch key generator is used to generate a key pair for a current epoch. For example, an epoch can be for a single day and the user device 101 will receive key information from the trusted service every day and will generate an epoch key pair every day.

[0028] In authenticating information and generating key pairs, both the signed data verifier 205 and the epoch key generator 207 rely on local storage 209 of keys and certificates that can be used in the encryption/decryption and signing/verification processes. Furthermore, the generation of a key pair utilizes various parameters depending on the cryptographic algorithm being used. Thus, the cryptographic parameters may be stored in the storage 209 as well.

[0029] Another type of information that may be received by the data receiver 203 includes data about a transaction. For example, the user device 101 may take a picture of a bar code that describes the transaction (e.g., item, quantity, price, merchant ID, date, etc.) or the user may use a keypad or other user interface of the device 101 to enter the transaction description. This data is then forwarded to a signed data generator 211. The signed data generator 211 signs the data with the user's credentials so that a party receiving the signed data can trust that the data identifies the correct user identity. The signed data may also include other information such as, for example, a limit to the amount of money this particular user has available or the age of the user so that certain age- restricted items cannot be purchased.

[0030] Once signed data is generated, it is then transmitted by the output data transmitter 213. The output data transmitter 213 can perform its function in a variety of different ways. If local networking is available between the user device 101 and the merchant (e.g., Bluetooth), then the data can be packetized and sent over the network. Alternatively, the signed data may be transmitted to the merchant by displaying a one dimensional or two dimensional barcode on a display screen of the device 101. The merchant would then scan or take a picture of that barcode as part of the transaction. Also, the signed output data may be transmitted as an audio signal out of a speaker of the device 101. Much like a modem signal, the output audio signal can be decoded by an appropriate device at the merchant location.

[0031] FIG. 2B is a diagram of one example of a user device 227 performing an off-line transaction, in accordance with one embodiment. The cellular telephone 227 includes a display screen 229 that can display a barcode or other encoded visual information. Or, for example, steganographic techniques can be utilized to encode information into an image that is displayed. As mentioned above, the encoded information may also by in the format of a multimedia file such as, for example, an audio file 231, that the device 227 is capable of playing. [0032] The encoded information in display 229, or the file 231, represents a transaction that is taking place with a merchant or vendor. In particular, the encoded information represents a description by the transaction that has been signed using a credential of the user of the device 227. This signed data can be captured by a merchant device 235 that has a media capture function 237 which could include taking a picture of the display 229 or receiving and decoding the audio file 231. The captured data is then forwarded to an cryptographic application 239 that verifies the identity and information that is encoded within the captured data. Once the merchant is satisfied with the veracity of the information, the transaction can be completed. It is well understood that there are a variety of ways, separate from the transaction, that the merchant can settle accounts and receive payments from an appropriate source of funds related to the user making the transaction.

[0033] FIG. 3 is a flowchart 300 of a process for generating transaction credentials between a user device and a trusted service, in accordance with one embodiment. As a first step, in step 301, the user and the service set up a long shared symmetrical key, Kc; this step is performed for each user so that each user has its own unique key. In the following diagrams and flowcharts, the terms "customer", "merchant" and "bank" are used to refer to the three parties that are involved in an offline transaction in accordance with an embodiment of the present invention. These terms are not intended to restrict implementations of the disclosed techniques and devices to only these specific types of entities but, instead, these terms are used to refer to the general roles of the entities within the transaction process. Also, consistent use of these terms will allow simple naming of keys based on these roles. For example, the subscript "C" in the example key Kc allows quick discernment that this is the customer's symmetric key being described.

[0034] Prior to setting up the key Kc in step 301, the customer and the bank have established an account so that the customer may draw on funds in the bank or can buy on credit extended by the bank which will be paid back by the customer. The key Kc allows the bank to encrypt data for the customer and for the customer to verify data received from the bank is truly from the bank. One example of the data sent by the bank is that for every epoch, the bank transmits parameters for generating key pairs for that epoch that are received in step 303 by the customer. An epoch can, for example, be one day or one week and represents the length of time before the bank will send out new parameters for the next epoch. One exemplary cryptography technique is elliptic curve cryptography in general, and specifically elliptical curve digital signal algorithm (ECDSA). The bit size of the public key believed to be needed for ECDSA is about twice the size of the security level, in bits. By comparison, at a security level of 80 bits, meaning an attacker requires about the equivalent of about 2⁸⁰ signature generations to find the private key, the size of a DSA public key is at least 1024 bits, whereas the size of an ECDSA public key would be 160 bits.

[0035] Based on the cryptography parameters received, the user device can then derive, in step 305, a short-lived key pair to be used for transactions during the current epoch. The key pair SKc' and PKc' can be derived based on the symmetrical key Kc and the cryptography parameters received in step 303. This short-lived key pair is a unique key pair for that customer during the epoch.

[0036] The bank also generates an epoch key pair that it uses during the epoch as well. This key pair SK_B' and PK_B ^l is used to sign and verify data exchanged by the bank during a current epoch. The bank uses SK_B ^l to create a user specific certificate valid for the epoch which the customer also receives a certificate Cc', in step 307. This epoch specific certificate can be presented by the customer during a transaction and the merchant can use PK_B ^l to verify the authenticity of the information within the certificate. For example, the certificate may identify the user by way of a cryptographic credential and may also indicate spending limits, available funds, or other information about the customer. This process of key pair generation and receiving certificates repeats every epoch. Although discussed above as a "push" operation controlled by the bank, the customer may also "pull" the information at the start of each epoch.

[0037] It is beneficial that the customer can verify that the epoch specific cryptography parameters received are really those chosen by the bank. Accordingly, the bank can send an authentication code Auth'c that is computed over the parameters using the shared key Kc. The code can be easily verified and can, for example, be small in size such as about 128 bits.

[0038] FIG. 4 is a flowchart 400 of a process for generating transaction credentials between a merchant and a trusted service, in accordance with one embodiment. As between the bank and the merchant, the bank shares a public key PK_B with any merchant, in step 401. This allows the merchant to verify data signed using the bank's private key SK_B. Every epoch, the bank signs its epoch public key PK_B ^l and sends the signed key to each merchant, in step 403, as a bank specific certificate C^l _B that can be verified using the key, PK_B, in step 405. The merchant is now able to process off-line transactions from customers that use the banks epoch public key, PK_B ^l, during the transaction. The bank also includes the epoch specific parameters (already sent to the customer) in the bank certificate C^l _B as well. Since C^l _B can be verified using the bank's long term public key PK_B, the merchant can verify that the epoch specific cryptography parameters are really those chosen by the bank, and that PKB' is a genuine short-term public key which the bank will use during the current epoch..

[0039] Now that the customer's device has the credentials from the bank and the epoch specific keys and the bank has the epoch specific information, a trusted transaction can take place between the merchant and the customer off-line without utilizing network messaging or resources. FIG. 5 is a flowchart 500 of a process for performing an off-line transaction, in accordance with one embodiment. While at the merchant, the customer and the merchant generate transaction data, in step 501. The transaction data describes the transaction such as the identity of the merchant, the items being purchased, the quantities of various items, the amount of the purchase, and other similar information. Alternatively, the transaction data may also be very simple and include the amount of the transaction and almost no other data. This transaction data is entered into the customer's device as described earlier such as by a keypad or other input mode.

[0040] Next, the customer signs the transaction data, in step 503, using their epoch-specific private key SKc'. The customer then send the merchant the signed transaction data and their epoch specific certificate Cc', in step 505. This information may be sent to the merchant via the display screen of the customer's device or as an audio file or other transmission means. As a result, the merchant receives this information, in step 507, and verifies its authenticity and accuracy. For example, the merchant can verify the certificate, Cc', using the banks epoch specific public key PK_B' and can verify, in step 509, the customer's signature using PKc' using the information from the, now verified, certificate Cc'. The transaction has completed after these verifications and the merchant can then commence efforts to receive the appropriate funds from the bank to cover the transaction.

[0041] In the above discussions, the size of the epoch specific keys is chosen based on the length of the epoch. The benefit is that the short-lived key pair is valid only during a given epoch and the length can be chosen so that it is secure during that period. After expiration of the epoch, breaking of the key pair provides no useful information.

[0042] FIG. 6 is a flowchart 600 of a process for generating transaction credentials between a user device and a merchant, in accordance with one embodiment. In the process of FIG. 4, the bank transmits the epoch cryptography parameters to the customer every epoch. This occurs whether the customer performs an off-line transaction during that epoch or not. One alternative is to have the merchant provide those parameters during the transaction but this assumes that a two-way communication takes place during the transaction. In step 601, during the transaction, the merchant sends the cryptography parameters to the customer who then can verify them as authentic, in step 603. Once verified, the customer can use the parameters to generate the short-lived key pair for the current epoch, in step 605.

[0043] If the merchant provides parameters to the customer, it might be possible for the merchant (depending on the algorithm that generates PK^l _c and SK^l _c) to fool the customer into using parameters that would leak Kc. This threat can be alleviated by having an epoch-dependent 2-step key generation (PK^l _c, SK^l _c = ^(parameters', f₂(K_c, t)) , whereby a bad choice of parameters reveals only information to break keys only for one epoch. Additionally, the frequency of input of epoch- specific parameters can be throttled in the terminal, or e.g. monitored so that during one epoch only on one value is accepted. Nevertheless if a customer's devices is fooled into using unauthentic parameters, leakage of SK^l _c is possible.

[0044] It is noted that various approaches can be utilized for the customer to verify the authenticity of the parameters. One approach is to have the merchant forward C'B to the customer so that the customer can authenticate the parameters but this has the drawback of increasing the bandwidth requirement for the merchant—customer channel. Another approach is to have the bank make a table of Auth'c values available for on-line lookup so that a merchant with an on-line connection can download the correct Auth' for a specific customer. Such a lookup server may be a directory server and need not have any access to any customer-specific secrets. This has the drawback of utilizing the availability of a bank—merchant channel at the time of transactions. An additional approach is to have the bank map the set of all Auth'c values to a bloom filter f* which is broadcast to all merchants at the start of every epoch and is transferred, along with the parameters, from the merchant to a customer on demand. The customer can construct its own Auth' value and check for membership in the received f*. This avoids the disadvantages of the previous approaches but has the drawback that the probability of correct verification of the parameters is lower then in the previous two approaches.

[0045] FIG. 7 is a ladder diagram of an example protocol for off-line transactions, in accordance with another embodiment. The parties in the diagram are the customer 702, the merchant 704, and the bank 706. The bank shares its public key PK_B 708 with all merchants 704 and a separate symmetric key Kc 710 with each customer. The customer's device has storage 712 for Kc and the merchant 704 has storage 714 for PKβ. The bank 706 has storage for the public key PK_B and the customer keys Kc. At the start of each epoch, the bank generates a variety of information 718. This information can include: (a) the cryptography parameters used for generating key pairs during the current epoch, (b) a bank short-lived key pair for the current epoch (PKB'), (C) a certificate, CB' generated by the bank signing the epoch information with its secret key, (d) the epoch key pairs for each customer, PK^l _c, SK^l _c (e) a customer certificate (Cc') for each customer generated by signing the epoch information with the banks short-lived public key, and (f) an authentication message (Auth'c) that allows the customer to verify the cryptography parameters sent by the bank.

[0046] A message 720 sent by the bank 706 to the merchant 704 includes the epoch cryptography parameters, the banks short-lived public key, PK_B ^l , and the bank certificate, C_B', of the current epoch information. A message 722 sent by the bank 706 to the customer includes the customer certificate Cc', and the authentication message Auth'c. In step 724, the merchant verifies the banks certificate and, in step 726, the device of the customer is used to verify the authentication message and to generate the short-lived key par for the epoch. As a result, the customer's device can store the certificate Cc' and the key pair PK^l _c, SK^l _c in storage 728 while the merchant 704 can store the information it received in storage 730.

[0047] The customer 702 and the merchant 704 can now perform an off-line transaction with assurances of the authenticity and validity of the transaction. The customer 702 signs the transaction data in step 732 and send it and the certificate Cc' in a message 734 to the merchant 704. As mentioned earlier, this message is not necessarily a network message but may include an image displayed on the customer's device or an audio file played by the customer's device. In step 736, the merchant 704 can verify the certificate using the bank's short-lived public key, PK_B', to obtain the customer's epoch public key PKc' . Then, the signed data can be verified using this key. As a result an off-line transaction occurred that did not utilize network communications, between the parties, or with a third party during the transaction.

[0048] A reasonable duration for an epoch can be 1 day. Assuming that the strongest possible attacker is capable of doing on the order of 2³⁰ (or more conservatively 2⁴⁰) operations during this period, an ECDSA in a 60 or 80 bit elliptic curve can be used. This results in signatures made with the short-lived keys that are 120 (or 160) bits long. Also, C'_B can be a standard signature (e.g., 512 bits with ECDSA). In an embodiment where the bank provides the cryptography parameters, the amount of data transferred via the various channels can be summarized, Table 1, as follows when using a b-bit elliptic curve:

Table 1

[0049] In an embodiment where the merchant provides the cryptography parameters, and assuming that the merchant forwards the information in its entirety to a customer who does not yet have the epoch-specific parameters, the merchant to the customer channel will transport 4b+512 bits, but periodic sending of these messages from the bank can be avoided altogether.

[0050] By way of variation, the bank can pre-generate the parameters for several epochs at once. It can then pre-calculate the short-lived keypairs for several epochs (both for the customers and for the bank itself) and generate short-lived certificates C'c for customers for several epochs. This has the advantage of reducing bank to customer communication. The bank can provide certificates for several epochs at once. The parameters for a particular epoch will only be revealed during that epoch. Therefore, releasing C'c early does not hamper the security.

[0051] This improvement is advantageously combined with the variation of a two way communication between merchant and customer whereby the epoch-specific, "global" parameters can be given to the customer by the merchant. Then, the epoch-specific communication between the client and the bank can be avoided entirely.

[0052] The processes described herein for manipulating the images returned from a search engine may be implemented via software, hardware (e.g., general processor, Digital Signal Processing (DSP) chip, an Application Specific Integrated Circuit (ASIC), Field Programmable Gate Arrays (FPGAs), etc.), firmware or a combination thereof. Such exemplary hardware for performing the described functions is detailed below.

[0053] FIG. 8 illustrates a computer system 800 upon which an embodiment of the invention may be implemented. Computer system 800 is programmed to carry out the inventive functions described herein and includes a communication mechanism such as a bus 810 for passing information between other internal and external components of the computer system 800. Information (also called data) is represented as a physical expression of a measurable phenomenon, typically electric voltages, but including, in other embodiments, such phenomena as magnetic, electromagnetic, pressure, chemical, biological, molecular, atomic, sub-atomic and quantum interactions. For example, north and south magnetic fields, or a zero and non-zero electric voltage, represent two states (0, 1) of a binary digit (bit). Other phenomena can represent digits of a higher base. A superposition of multiple simultaneous quantum states before measurement represents a quantum bit (qubit). A sequence of one or more digits constitutes digital data that is used to represent a number or code for a character. In some embodiments, information called analog data is represented by a near continuum of measurable values within a particular range.

[0054] A bus 810 includes one or more parallel conductors of information so that information is transferred quickly among devices coupled to the bus 810. One or more processors 802 for processing information are coupled with the bus 810.

[0055] A processor 802 performs a set of operations on information. The set of operations include bringing information in from the bus 810 and placing information on the bus 810. The set of operations also typically include comparing two or more units of information, shifting positions of units of information, and combining two or more units of information, such as by addition or multiplication or logical operations like OR, exclusive OR (XOR), and AND. Each operation of the set of operations that can be performed by the processor is represented to the processor by information called instructions, such as an operation code of one or more digits. A sequence of operations to be executed by the processor 802, such as a sequence of operation codes, constitute processor instructions, also called computer system instructions or, simply, computer instructions. Processors may be implemented as mechanical, electrical, magnetic, optical, chemical or quantum components, among others, alone or in combination.

[0056] Computer system 800 also includes a memory 804 coupled to bus 810. The memory 804, such as a random access memory (RAM) or other dynamic storage device, stores information including processor instructions. Dynamic memory allows information stored therein to be changed by the computer system 800. RAM allows a unit of information stored at a location called a memory address to be stored and retrieved independently of information at neighboring addresses. The memory 804 is also used by the processor 802 to store temporary values during execution of processor instructions. The computer system 800 also includes a read only memory (ROM) 806 or other static storage device coupled to the bus 810 for storing static information, including instructions, that is not changed by the computer system 800. Some memory is composed of volatile storage that loses the information stored thereon when power is lost. Also coupled to bus 810 is a non-volatile (persistent) storage device 808, such as a magnetic disk, optical disk or flash card, for storing information, including instructions, that persists even when the computer system 800 is turned off or otherwise loses power.

[0057] Information, including instructions, is provided to the bus 810 for use by the processor from an external input device 812, such as a keyboard containing alphanumeric keys operated by a human user, or a sensor. A sensor detects conditions in its vicinity and transforms those detections into physical expression compatible with the measurable phenomenon used to represent information in computer system 800. Other external devices coupled to bus 810, used primarily for interacting with humans, include a display device 814, such as a cathode ray tube (CRT) or a liquid crystal display (LCD), or plasma screen or printer for presenting text or images, and a pointing device 816, such as a mouse or a trackball or cursor direction keys, or motion sensor, for controlling a position of a small cursor image presented on the display 814 and issuing commands associated with graphical elements presented on the display 814. In some embodiments, for example, in embodiments in which the computer system 800 performs all functions automatically without human input, one or more of external input device 812, display device 814 and pointing device 816 is omitted.

[0058] In the illustrated embodiment, special purpose hardware, such as an application specific integrated circuit (ASIC) 820, is coupled to bus 810. The special purpose hardware is configured to perform operations not performed by processor 802 quickly enough for special purposes. Examples of application specific ICs include graphics accelerator cards for generating images for display 814, cryptographic boards for encrypting and decrypting messages sent over a network, speech recognition, and interfaces to special external devices, such as robotic arms and medical scanning equipment that repeatedly perform some complex sequence of operations that are more efficiently implemented in hardware.

[0059] Computer system 800 also includes one or more instances of a communications interface 870 coupled to bus 810. Communication interface 870 provides a one-way or two-way communication coupling to a variety of external devices that operate with their own processors, such as printers, scanners and external disks. In general the coupling is with a network link 878 that is connected to a local network 880 to which a variety of external devices with their own processors are connected. For example, communication interface 870 may be a parallel port or a serial port or a universal serial bus (USB) port on a personal computer. In some embodiments, communications interface 870 is an integrated services digital network (ISDN) card or a digital subscriber line (DSL) card or a telephone modem that provides an information communication connection to a corresponding type of telephone line. In some embodiments, a communication interface 870 is a cable modem that converts signals on bus 810 into signals for a communication connection over a coaxial cable or into optical signals for a communication connection over a fiber optic cable. As another example, communications interface 870 may be a local area network (LAN) card to provide a data communication connection to a compatible LAN, such as Ethernet. Wireless links may also be implemented. For wireless links, the communications interface 870 sends or receives or both sends and receives electrical, acoustic or electromagnetic signals, including infrared and optical signals, that carry information streams, such as digital data. For example, in wireless handheld devices, such as mobile telephones like cell phones, the communications interface 870 includes a radio band electromagnetic transmitter and receiver called a radio transceiver.

[0060] The term computer-readable medium is used herein to refer to any medium that participates in providing information to processor 802, including instructions for execution. Such a medium may take many forms, including, but not limited to, non-volatile media, volatile media and transmission media. Non-volatile media include, for example, optical or magnetic disks, such as storage device 808. Volatile media include, for example, dynamic memory 804. Transmission media include, for example, coaxial cables, copper wire, fiber optic cables, and carrier waves that travel through space without wires or cables, such as acoustic waves and electromagnetic waves, including radio, optical and infrared waves. Signals include man-made transient variations in amplitude, frequency, phase, polarization or other physical properties transmitted through the transmission media. Common forms of computer-readable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, any other magnetic medium, a CD-ROM, CDRW, DVD, any other optical medium, punch cards, paper tape, optical mark sheets, any other physical medium with patterns of holes or other optically recognizable indicia, a RAM, a PROM, an EPROM, a FLASH-EPROM, any other memory chip or cartridge, a carrier wave, or any other medium from which a computer can read.

[0061] FIG. 9 illustrates a chip set 900 upon which an embodiment of the invention may be implemented. Chip set 900 is programmed to carry out the inventive functions described herein and includes, for instance, the processor and memory components described with respect to FIG. 8 incorporated in one or more physical packages. By way of example, a physical package includes an arrangement of one or more materials, components, and/or wires on a structural assembly (e.g., a baseboard) to provide one or more characteristics such as physical strength, conservation of size, and/or limitation of electrical interaction.

[0062] In one embodiment, the chip set 900 includes a communication mechanism such as a bus 901 for passing information among the components of the chip set 900. A processor 903 has connectivity to the bus 901 to execute instructions and process information stored in, for example, a memory 905. The processor 903 may include one or more processing cores with each core configured to perform independently. A multi-core processor enables multiprocessing within a single physical package. Examples of a multi-core processor include two, four, eight, or greater numbers of processing cores. Alternatively or in addition, the processor 903 may include one or more microprocessors configured in tandem via the bus 901 to enable independent execution of instructions, pipelining, and multithreading. The processor 903 may also be accompanied with one or more specialized components to perform certain processing functions and tasks such as one or more digital signal processors (DSP) 907, or one or more application-specific integrated circuits (ASIC) 909. A DSP 907 typically is configured to process real-word signals (e.g., sound) in real time independently of the processor 903. Similarly, an ASIC 909 can be configured to performed specialized functions not easily performed by a general purposed processor. Other specialized components to aid in performing the inventive functions described herein include one or more field programmable gate arrays (FPGA) (not shown), one or more controllers (not shown), or one or more other special-purpose computer chips.

[0063] The processor 903 and accompanying components have connectivity to the memory 905 via the bus 901. The memory 905 includes both dynamic memory (e.g., RAM, magnetic disk, writable optical disk, etc.) and static memory (e.g., ROM, CD-ROM, etc.) for storing executable instructions that when executed perform the inventive steps described herein. The memory 905 also stores the data associated with or generated by the execution of the inventive steps.

[0064] FIG. 10 is a diagram of exemplary components of a mobile station (e.g., handset) capable of operating in the system of FIG. 1 , according to an exemplary embodiment. Generally, a radio receiver is often defined in terms of front-end and back-end characteristics. The front-end of the receiver encompasses all of the Radio Frequency (RF) circuitry whereas the back-end encompasses all of the base-band processing circuitry. Pertinent internal components of the telephone include a Main Control Unit (MCU) 1003, a Digital Signal Processor (DSP) 1005, and a receiver/transmitter unit including a microphone gain control unit and a speaker gain control unit. A main display unit 1007 provides a display to the user in support of various applications and mobile station functions. An audio function circuitry 1009 includes a microphone 1011 and microphone amplifier that amplifies the speech signal output from the microphone 1011. The amplified speech signal output from the microphone 1011 is fed to a coder/decoder (CODEC) 1013.

[0065] A radio section 1015 amplifies power and converts frequency in order to communicate with a base station, which is included in a mobile communication system, via antenna 1017. The power amplifier (PA) 1019 and the transmitter/modulation circuitry are operationally responsive to the MCU 1003, with an output from the PA 1019 coupled to the duplexer 1021 or circulator or antenna switch, as known in the art. The PA 1019 also couples to a battery interface and power control unit 1020.

[0066] In use, a user of mobile station 1001 speaks into the microphone 1011 and his or her voice along with any detected background noise is converted into an analog voltage. The analog voltage is then converted into a digital signal through the Analog to Digital Converter (ADC) 1023. The control unit 1003 routes the digital signal into the DSP 1005 for processing therein, such as speech encoding, channel encoding, encrypting, and interleaving. In the exemplary embodiment, the processed voice signals are encoded, by units not separately shown, using a cellular transmission protocol such as global evolution (EDGE), general packet radio service (GPRS), global system for mobile communications (GSM), Internet protocol multimedia subsystem (IMS), universal mobile telecommunications system (UMTS), etc., as well as any other suitable wireless medium, e.g., microwave access (WiMAX), Long Term Evolution (LTE) networks, code division multiple access (CDMA), wireless fidelity (WiFi), satellite, and the like.

[0067] The encoded signals are then routed to an equalizer 1025 for compensation of any frequency-dependent impairments that occur during transmission though the air such as phase and amplitude distortion. After equalizing the bit stream, the modulator 1027 combines the signal with a RF signal generated in the RF interface 1029. The modulator 1027 generates a sine wave by way of frequency or phase modulation. In order to prepare the signal for transmission, an up-converter 1031 combines the sine wave output from the modulator 1027 with another sine wave generated by a synthesizer 1033 to achieve the desired frequency of transmission. The signal is then sent through a PA 1019 to increase the signal to an appropriate power level. In practical systems, the PA 1019 acts as a variable gain amplifier whose gain is controlled by the DSP 1005 from information received from a network base station. The signal is then filtered within the duplexer 1021 and optionally sent to an antenna coupler 1035 to match impedances to provide maximum power transfer. Finally, the signal is transmitted via antenna 1017 to a local base station. An automatic gain control (AGC) can be supplied to control the gain of the final stages of the receiver. The signals may be forwarded from there to a remote telephone which may be another cellular telephone, other mobile phone or a land-line connected to a Public Switched Telephone Network (PSTN), or other telephony networks.

[0068] Voice signals transmitted to the mobile station 1001 are received via antenna 1017 and immediately amplified by a low noise amplifier (LNA) 1037. A down-converter 1039 lowers the carrier frequency while the demodulator 1041 strips away the RF leaving only a digital bit stream. The signal then goes through the equalizer 1025 and is processed by the DSP 1005. A Digital to Analog Converter (DAC) 1043 converts the signal and the resulting output is transmitted to the user through the speaker 1045, all under control of a Main Control Unit (MCU) 1003-which can be implemented as a Central Processing Unit (CPU) (not shown).

[0069] The MCU 1003 receives various signals including input signals from the keyboard 1047. The MCU 1003 delivers a display command and a switch command to the display 1007 and to the speech output switching controller, respectively. Further, the MCU 1003 exchanges information with the DSP 1005 and can access an optionally incorporated SIM card 1049 and a memory 1051. In addition, the MCU 1003 executes various control functions required of the station. The DSP 1005 may, depending upon the implementation, perform any of a variety of conventional digital processing functions on the voice signals. Additionally, DSP 1005 determines the background noise level of the local environment from the signals detected by microphone 1011 and sets the gain of microphone 1011 to a level selected to compensate for the natural tendency of the user of the mobile station 1001.

[0070] The CODEC 1013 includes the ADC 1023 and DAC 1043. The memory 1051 stores various data including call incoming tone data and is capable of storing other data including music data received via, e.g., the global Internet. The software module could reside in RAM memory, flash memory, registers, or any other form of writable storage medium known in the art. The memory device 1051 may be, but not limited to, a single memory, CD, DVD, ROM, RAM, EEPROM, optical storage, or any other non-volatile storage medium capable of storing digital data.

[0071] An optionally incorporated SIM card 1049 carries, for instance, important information, such as the cellular phone number, the carrier supplying service, subscription details, and security information. The SIM card 1049 serves primarily to identify the mobile station 1001 on a radio network. The card 1049 also contains a memory for storing a personal telephone number registry, text messages, and user specific mobile station settings.

[0072] While the invention has been described in connection with a number of embodiments and implementations, the invention is not so limited but covers various obvious modifications and equivalent arrangements, which fall within the purview of the appended claims. Although features of the invention are expressed in certain combinations among the claims, it is contemplated that these features can be arranged in any combination and order.

Claims

CLAIMSWHAT IS CLAIMED IS:

1. A computer-readable storage medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following: initiating receiving of one or more parameters for off-line payment, wherein the parameters relate to a predetermined time period; generating, based on the parameters, a public key and a private key that are valid for the predetermined time period; and signing transaction data associated with the off-line payment using the private key during the predetermined time period.

2. A computer-readable storage medium of claim 1, wherein the apparatus is caused to further perform: initiating receiving of a certificate related to the public key and the private key, wherein the certificate is valid during the predetermined period.

3. A computer-readable storage medium of claim 1 or 2, wherein the apparatus is caused to further perform: initiating receiving of the transaction data.

4. A computer-readable storage medium of claim 1 or 2 or 3, wherein the apparatus is caused to further perform: transmitting the signed transaction data during a transaction.

5. A computer-readable storage medium of claim 4, wherein a size of the signed transaction data is less than about 200 bits.

6. A computer-readable storage medium of claim 4, wherein transmitting includes displaying an image representing the signed transaction data.

7. A computer-readable storage medium of claim 4, wherein transmitting includes playing an audio- format file representing the signed transaction data.

8. A computer-readable storage medium according to any of claims 1 to 7, wherein a length of the public key and a length of the private key are related to a length of the predetermined time period.

9. A computer readable storage medium according to any of claims 1 to 8, wherein the apparatus is caused to further perform: initiating receiving of new one or more parameters for off-line payment, wherein the new parameters relate to a subsequent predetermined time period; and generating, based on the new parameters, a new public key and a new private key that are valid for the subsequent predetermined time period.

10. A computer readable storage medium according to any of claims 1 to 9, wherein the apparatus is caused to further perform: agreeing on a shared symmetrical key with a third party; and verifying the one or more parameters using the symmetrical key.

11. An apparatus comprising a processor and a memory storing executable instructions that (1) as part of execution or as a result of execution at least or (2) as both part of execution and as a result of execution at least cause the apparatus to perform at least the following: initiating receiving of one or more parameters for off-line payment, wherein the parameters relate to a predetermined time period; generating, based on the parameters, a public key and a private key that are valid for the predetermined time period; and signing transaction data associated with the off-line payment using the private key during the predetermined time period.

12. An apparatus of claim 11, wherein a length of the public key and a length of the private key are related to a length of the predetermined time period.

13. An apparatus of claim 11 or 12, wherein the apparatus is caused to further perform: transmitting the signed transaction data during a transaction, the signed transaction data including payment information for the transaction.

14. An apparatus of claim 11 or 12 or 13, wherein the apparatus is caused to further perform: initiating receiving of new one or more parameters for off-line payment, wherein the new parameters relate to a subsequent predetermined time period; and generating, based on the new parameters, a new public key and a new private key that are valid for the subsequent predetermined time period.

15. An apparatus comprising a processor and a memory storing executable instructions that (1) as part of execution or as a result of execution at least or (2) as both part of execution and as a result of execution at least cause the apparatus to perform at least the following: generating cryptographic parameters that relate to a predetermined time period; generating, using the cryptographic parameters, a first public key and a first private key that are valid for the predetermined time period which verify an identity of a party in an off-line transaction; and generating a first certificate related to the first public key and the first private key, which verify the cryptographic parameters for the party, wherein for a subsequent time period, different cryptographic information is generated.

16. An apparatus of claim 15, wherein the predetermined time period is about one day.

17. An apparatus of claim 15 or 16, wherein the apparatus is caused to further perform: initiating transmitting of the cryptographic parameters and the first certificate to a portable device of the party.

18. A method comprising: generating cryptographic parameters that relate to a predetermined time period; generating, using the cryptographic parameters, a first public key and a first private key that are valid for the predetermined time period which verify an identity of a party in an off-line transaction; and generating a first certificate related to the first public key and the first private key, which verify the cryptographic parameters for the party,

?? wherein for a subsequent time period, different cryptographic information is generated.

19. An method according to claim 18, wherein the predetermined time period is about one day.

20. An method according to any of claims 18 to 19, further including: initiating transmitting of the cryptographic parameters and the first certificate to a portable device of the party.

21. A method comprising: initiating receiving of one or more parameters for off-line payment, wherein the parameters relate to a predetermined time period; generating, based on the parameters, a public key and a private key that are valid for the predetermined time period; and signing transaction data associated with the off-line payment using the private key during the predetermined time period.

22. The method according to claim 21, further comprising: initiating receiving of a certificate related to the public key and the private key, wherein the certificate is valid during the predetermined period.

23. The method according to any of claims 21 to 22, further comprising: initiating receiving of the transaction data.

24. The method according to any of claims 21 to 23, further comprising: transmitting the signed transaction data during a transaction.

25. The method according to claim 24, wherein a size of the signed transaction data is less than about 200 bits.

26. The method according to claim 24, wherein transmitting includes displaying an image representing the signed transaction data.

27. The method according to claim 24, wherein transmitting includes playing an audio-format file representing the signed transaction data.

28. The method according to any of claims 21 to 27, wherein a length of the public key and a length of the private key are related to a length of the predetermined time period.

29. The method according to any of claims 21 to 28, further comprising: initiating receiving of new one or more parameters for off-line payment, wherein the new parameters relate to a subsequent predetermined time period; and generating, based on the new parameters, a new public key and a new private key that are valid for the subsequent predetermined time period.

30. The method according to any of claims 21 to 29, further comprising: agreeing on a shared symmetrical key with a third party; and verifying the one or more parameters using the symmetrical key.

31. A computer program that when executed causes an apparatus to perform the method according to any of claims 21 to 30.

32. An apparatus comprising means for performing the method of any of claims 21-30.