Methods and apparatus for deriving, communicating and/or verifying ownership of expressions

Methods and apparatus for generating, communicating, and/or verifying ownership of expressions are described. Various embodiments are well suited for use in a wireless peer to peer communications systems in which expressions are communicated, e.g., broadcast, in discovery intervals. A first communications device generates an expression from a first public key and an additional input, said first public key corresponding to a private key known to said first communications device. The first device transmits the generated expression on a communications channel used for discovery. A second communications device receives the transmitted expression from the first device. The second device transmits a request signal to the first device associated with the expression; and receives from the first device a signed communication signed using a private key known to said first communications device. The second device uses information from the signed communication to determine if said first communication device owns said expression.

FIELD

Various embodiments relate to communications, and more particularly, to methods and apparatus which can be used for generating, communicating, and/or verifying ownership of expressions.

BACKGROUND

In a wireless communications system, a communication device may wish to advertise information to be available to other devices in its local vicinity, e.g., presence information, identification information, location information, service information, requests, offers, etc. The information may be advertised for other devices to discover and take subsequent action. For example, based on a detected identifier corresponding to information or an item of interest, a device which detected the discovery information of interest may attempt to establish a connection with the device which transmitted the discovery information of interest. In wireless peer to peer communications systems lacking centralized control, there is a need for devices to be able to recognize the presence of other devices of interest in their vicinity, and the implementation of discovery channels to be used for such a purpose can be beneficial.

In addition to be able to communicate discovery information in a reliable manner, there is a need to provide a mechanism for protection from malicious nodes which may attempt to perform spoofing. Based on the above discussion, there is a need for methods and apparatus to provide confirmation with regard to information communicated on a discovery communications channel. In particular, there is a need for methods and apparatus which allow a receiving device to confirm that received information corresponds to a particular node in a manner that allows the receiving node to be sure that the particular node had control over or authorized the communication of the received information, e.g., communicated expression.

SUMMARY

Methods and apparatus for generating expressions, communicating expressions, and/or verifying that a node had control over or authorized the communication of a received expression are described. Verifying that a particular node had control over or authorized communication of a particular expression is sometimes referred to as determining or verifying that the particular node owns the expression. Accordingly, in various embodiments expressions are communicated in a manner that allows ownership of a received expression to be verified, e.g., via one or more communications with a node believed to be the owner of the expression. The owner of a received expression may be the node which transmitted the expression but, in the case of a retransmission or communication through an intermediate node, the owner of an expression may be different from the node from which an expression was received. Various described methods and apparatus are well suited for use in a wireless peer to peer communications system in which expressions are communicated, e.g., broadcast, in discovery intervals.

An exemplary method of operating a first communications device to communicate information, in accordance with some embodiments, comprises: generating an expression from a first public key and an additional input, said first public key corresponding to a private key known to said first communications device; and transmitting the generated expression on a communications channel used for discovery. An exemplary first communications device, in accordance with some embodiments, comprises at least one processor configured to: generate an expression from a first public key and an additional input, said first public key corresponding to a private key known to said first communications device; and transmit the generated expression on a communications channel used for discovery. The exemplary first communications device further comprises memory coupled to said at least one processor.

An exemplary method of operating a first communications device to verify ownership of an expression, in accordance with some embodiments, comprises: transmitting a signal to a second communications device associated with the expression; receiving from the second communications device a signed communication signed using a private key known to said second communications device; and determining if said second communication device owns said expression. In some such embodiments, said step of determining if said second communications device owns said expresses includes: determining if said expression was generated using a first public key and verifying that the signed communication was generated by a private key corresponding to said first public key. An exemplary first communications device, in accordance with some embodiments, comprises at least one processor configured to: transmit a signal to a second communications device associated with the expression; receive from the second communications device a signed communication signed using a private key known to said second communications device; and determine if said second communication device owns said expression. In some such embodiments, being configured to determine if said second communication device owns said expression includes being configured to: determine if said expression was generated using a first public key; and verify that the signed communication was generated by a private key corresponding to said first public key. The exemplary first communications device also includes memory coupled to said at least one processor.

DETAILED DESCRIPTION

FIG. 1is a drawing of an exemplary wireless communications system100, e.g., a peer to peer wireless communications system, in accordance with an exemplary embodiment. Exemplary wireless communications system100includes a plurality of wireless communications devices (wireless communications device1102, wireless communications device2104, wireless communications device3106, wireless communications device4108, wireless communications device5110, wireless communications device6112, wireless communications device7114, . . . , wireless communications device N116. Some of the wireless communications devices of system100, e.g., device3106and device6112, are coupled to other network nodes and/or the Internet via backhaul network120. Some of the wireless communications devices of system100are mobile devices, e.g., devices (102,104,108,110,114,116). Exemplary communications system100also includes a key server node118which includes both a wireless interface and a wired network interface.

The wireless communications devices (102,104,106,108,110,112,114,116) support peer to peer communications and implement a peer to peer timing structure including discovery intervals. A first wireless communications device, e.g., device1102, may, and sometimes does, generate an expression using a public key and additional input, and then transmit the generated expression during the discovery interval. The expression may convey, e.g., information including one of: device identification information, user identification information, a service advertisement, a service request, a merchandise advertisement, a merchandise request, an offer, group identification information, location information, device capability information, or other information that may be of interest to other peer to peer devices.

A second wireless communication device, e.g., device2104, which may have monitoring for discovery interval signals, may receive the transmitted expression, and may desire to verify ownership of the detected expression. The second communications device receives a signed communication using a private key known to the first communications device. The second device determines if the first communications device owns the expression. In some embodiments, the determining includes determining if the received expression was generated using a first public key and verifying that the received signed communication was generated by a private key corresponding to the first public key.

Determining if the received expressed was generated using a first public key, in some embodiments, includes generating a test value based on information received in the signed communication and comparing the test value to the received expression. Verifying that the received signed communication was generated by a private key corresponding to the first public key, in some embodiments, includes performing a signature verification operation, e.g., using a standard public-private key verification method.

FIG. 2is a flowchart200of an exemplary method of operating a first communications device to communicate information in accordance with various exemplary embodiments. Operation starts in step202where the first communications device is powered on and initialized and proceeds to one of steps204,206, and208, e.g., depending upon the particular embodiment. In step204the first communications device receives a certificate from a certificate authority, wherein said certificate includes a private key and one of a device or user identifier. In step206the first communications device internally generates a certificate, wherein said certificate includes a private key and one of a device or user identifier. In step208the first communications device retrieves from memory, included in said first communications device, a certificate which has been included in said memory by a manufacturer of said first communications device, wherein said certificate includes a private key and one of a device or user identifier. Operation proceeds from one of steps204,206, and208to step210.

In step210the first communications device obtains a first public key from said certificate. Operation proceeds from step210to step212. In step212the first communications device generates an expression from said first public key and an additional input, said first public key corresponding to said private key known to said first communications device. The additional input, in some embodiments, is one of a random number and a time dependent input.

In some embodiments, step212includes sub-step214. In some embodiments, step212includes sub-step216. Returning to sub-step214, in sub-step214the first communications device performs a one-way hash operation using said first public key and said addition input as inputs to the one-way hash operation, an output of said hash operation being the generated expression. Returning to sub-step216, in sub-step216the first communications device performs a one-way hash operation using said first public key, a second public key and said additional input as inputs to the one-way hash operation, an output of the hash operation being said generated expression. Sub-step216includes sub-step218in which the first communications device uses said second public key corresponding to a second member of a group in addition to said first public key to derive said expression, wherein said device or user identifier to which the first public key corresponds is a member of said group.

Operation proceeds from step212to step220. In step220the first communications device transmits the generated expression on a communications channel used for discovery. In some embodiments, the communications channel used for discovery corresponds to discovery time intervals in a peer to peer communications system. In various embodiments, transmitting includes wirelessly transmitting said expression using a wireless transmitter.

In some embodiments, the output of the hash operation is limited to a predetermined number of bits, and step220includes step222. In step222the first communications device transmits different portions of said generated expression in different peer discovery time periods. Operation proceeds from step220to step224. In step224the first communications device receives a signal from a second communications device, e.g., a request for a signed communication from the second communications device. Operation proceeds from step224to step226, in which the first communications device signs a communication using said private key. In some embodiments, said signed communication includes at least one of: i) said public key and ii) said device or user identifier. The signed communication, in some embodiments, further includes hash information, said hash information including a hash function used to perform said hash operation and at least one input to said hash operation used to generate said expression. In various embodiments, the signed communication includes a plurality of public keys used to generate said expression. In some embodiments, the signed communication includes each of the parameters used to generate said expression as well as the detailed description of the mathematical function used for the hash used to generate said expression. The signed communication, in some embodiments, further includes hash information, said hash information including information used to identify or derive a hash function used to perform said hash operation and at least one input to said hash operation used to generate said expression. Then in step228the first communications device sends the signed communication to said second communications device.

FIG. 3is a drawing of an exemplary first communications device300, in accordance with an exemplary embodiment. Exemplary communications device300is, e.g., one of the wireless communications devices ofFIG. 1. Exemplary communications device300may, and sometimes does, implement a method in accordance with flowchart200ofFIG. 2.

Communications device300includes a processor302and memory304coupled together via a bus309over which the various elements (302,304) may interchange data and information. Communications device300further includes an input module306and an output module308which may be coupled to processor302as shown. However, in some embodiments, the input module306and output module308are located internal to the processor302. Input module306can receive input signals. Input module306can, and in some embodiments does, include a wireless receiver and/or a wired or optical input interface for receiving input. Output module308may include, and in some embodiments does include, a wireless transmitter and/or a wired or optical output interface for transmitting output.

Processor302is configured to generate an expression from a first public key and an additional input, said first public key corresponding to a private key known to said first communications device. Processor302is further configured to transmit the generated expression on a communications channel used for discovery. In some embodiments, said communications channel used for discovery corresponds to discovery time intervals in a peer to peer communications system. In various embodiments, processor302is configured to wirelessly transmit said expression as part of being configured to transmit said expression. The additional input, in some embodiments, is one of a random number and a time dependent input value.

Processor302, in some embodiments, is configured to perform a one-way hash operation using said first public key and said additional input as inputs to the one-way hash operation, an output of said hash operation being said generated expression, as part of being configured to generate an expression. In some embodiments, the output of said hash operation is limited to a predetermined number of bits; and processor302is configured to transmit different portions of said expression in different peer discovery time periods, as part of being configured to transmit the generated expression.

Processor302, in some embodiments, is configured to obtain said first public key from a certificate including said private key and one of a device or user identifier. Processor302, in various embodiments, is further configured to receive said certificate from a certificate authority. Processor302, in some embodiments, is configured to internally generate said certificate. In some embodiments, said certificate is stored in memory included in said first communications device by a manufacturer of said first communications device; and processor302is configured to retrieve said stored certificate from memory.

Processor302is further configured to: receive a signal from a second communications device; sign a communication using said private key; and send the signed communication to said second communications device. Said communication, in some embodiments, includes at least one of: i) said public key and ii) said device or user identifier. The signed communication, in various embodiments, further includes: hash information, said hash information including a hash function used to perform said hash operation and at least one input to said hash operation used to generate said expression.

In some embodiments, said device or user identifier to which the first public key corresponds is a member of a group; and processor302is configured to use a second public key corresponding to a second member of said group in addition to said first public key to derive said expression, as part of being configured to generate an expression. In some such embodiments, processor302is configured to perform a one-way hash operation using said first and second public keys and said additional input as inputs to the one-way hash operation, an output of said hash operation being said generated expression, as part of being configured to generate an expression.

FIG. 4is an assembly of modules400which can, and in some embodiments is, used in the first communications device300illustrated inFIG. 3. The modules in the assembly400can be implemented in hardware within the processor302ofFIG. 3, e.g., as individual circuits. Alternatively, the modules may be implemented in software and stored in the memory304of the first communications device300shown inFIG. 3. While shown in theFIG. 3embodiment as a single processor, e.g., computer, it should be appreciated that the processor302may be implemented as one or more processors, e.g., computers. When implemented in software the modules include code, which when executed by the processor, configure the processor, e.g., computer,302to implement the function corresponding to the module. In some embodiments, processor302is configured to implement each of the modules of the assembly of modules400. In embodiments where the assembly of modules400is stored in the memory304, the memory304is a computer program product comprising a computer readable medium comprising code, e.g., individual code for each module, for causing at least one computer, e.g., processor302, to implement the functions to which the modules correspond.

Completely hardware based or completely software based modules may be used. However, it should be appreciated that any combination of software and hardware (e.g., circuit implemented) modules may be used to implement the functions. As should be appreciated, the modules illustrated inFIG. 4control and/or configure the first communications device300or elements therein such as the processor302, to perform the functions of the corresponding steps illustrated in the method flowchart200ofFIG. 2.

Assembly of modules400includes one or more of modules404,406and408. Module404is a module for receiving a certificate from a certificate authority, wherein said certificate includes a private key and one of a device or user identifier. Module406is a module for internally generating a certificate, wherein said certificate include a private key and one of a device or user identifier. Module408is a module for retrieving from memory, included in said first communications device, a certificate which had been included in said memory by a manufacturer of said first communications device, wherein said certificate includes a private key and one of device or user identifier.

Assembly of modules400further includes: a module410for obtaining a first public key from said certificate, a module412for generating an expression from said first public key and an additional input, said first public key corresponding to said private key known to said first communications device and a module420for transmitting the generated expression on a communications channel used for discovery. In some embodiments, the additional input is one of a random number and a time dependent input value. In various embodiments, the communications channel used for discovery corresponds to discovery time intervals in a peer to peer communications system.

In some embodiments, module412includes module414for performing a one-way hash operation using said first public key and said additional input as inputs to the one-way hash operation, an output of said hash operation being the generated expression. In various embodiments, assembly of modules412includes module416for performing a one-way hash operation using said first public key, a second public key and said additional input as inputs to the one-way hash operation, an output of the one-way hash operation being said generated expression. In some embodiments, module416includes module418for using a second public key corresponding to a second member of a group in addition to said first public key to derive said expression, wherein said device or user identifier to which the first public key corresponds is a member of said group.

In various embodiments, module420includes module421for wirelessly transmitting said expression. Module420, in some embodiments, includes module422for transmitting different portions of said generated expression in different peer discovery time periods. In some such embodiments, the output of the hash operation is limited to a predetermined number of bits.

Assembly of modules400further includes a module424for receiving a signal from a second communications device, a module426for signing a communication using said private key and a module428for sending the signed communications to said second communications device. In various embodiments, the communication includes at least one of: i) said public key and ii) said device or user identifier. In some embodiments, the signed communications further includes hash information, said hash information including a hash function and at least one input to the hash operation used to generate the expression. In some embodiments, the signed communications further includes hash information, said hash information including information used to identify or derive a hash function and at least one input to the hash operation used to generate the expression.

FIG. 5is a flowchart500of an exemplary method of operating a first communications device to verify ownership of an expression. Operation starts in step502, where the first communications device is powered on and initialized and proceeds to step504. In step504the first communications device receives said expression from a second communications device. In some embodiments, step504includes sub-step506in which the first communications device receives different portions of said expression in different peer discovery time periods. In some such embodiments, the output of the hash expression is limited to a predetermined number of bits. Operation proceeds from step504to step508.

In step508the first communications device transmits a signal, e.g., a request for a signed communication, to the second communications device associated with the expression. Operation proceeds from step508to step510. In step510the first communications device receives from the second communications device a signed communication signed using a private key known to said second communications device. In some embodiments, a first public key, which corresponds to the private key, is included in the signed communication. In various embodiments, the signed communication includes a plurality of public keys to be used to generate a test value. The signed communication, in various embodiments, includes hash information, said hash information indicating a one-way hash function to be used to generate a test value. The signed communication, in various embodiments, includes hash information, said hash information indicating information used to identify or derive a one-way hash function to be used to generate a test value. In some embodiments, the signed communication includes each of the parameters used to generate a test value as well as the detailed description of the mathematical function used for the hash used to generate the test value.

In some embodiments, operation proceeds from step510to step512, while in other embodiments, operation proceeds from step510to step514. Returning to step512, in step512the first communications device uses an identifier included in said signed communication to retrieve said first public key, said identifier being one of a device and user identifier. In various embodiments, the first public key is retrieved from memory of the first communication device. In some embodiments, the first public key is retrieved from another source, e.g., a public key server. Operation proceeds from step512to step514.

In step514the first communications device determines if said second communications device owns said expression. Step514includes step516and step528. In step516, the first communications device determines if said expression was generated using a first public key. Step516includes steps518and526. In step518the first communications device generates a test value from said first public key and additional input, said additional input being one of a random number and a time dependent input.

In some embodiments, step518includes one of step520and522. In step520the first communications device performs a one-way hash operation using said first public key and said additional input as inputs to the one way hash operation, and output of the hash operation being said test value. In step522the first communications device performs a one-way hash operation using said first public key, a second public key and said additional input as inputs to the one-way hash operation, an output of the one way hash operation being said test value. Step522includes step524in which the first communications device uses said second public key corresponding to a second member of a group in addition to said first public key to generate said test value, wherein a device of user identifier to which the first public key corresponds is a member of said group.

Operation proceeds from step518to step526in which the first communications device compares the test value to said expression to determine if they match, a match indicating that said expression was generated using said first public key. Operation proceeds from step516to step528. In step528the first communications device performs an operation to verify that the signed communication was generated by a private key corresponding to said first public key, e.g., the first communications device performs a signature verification using a standard public-private key verification method.

In some embodiments, in which the second communications device is a member of said group, the exemplary method may, and sometimes does, includes a step in which the first communications device transmits a signal to the second member of said group and a step in which in the first communications device receives from the second member of said group a second signed communication signed using a second private key known to the second member of the group, e.g., the second private key corresponding to the second public key. In some such embodiments, the test value is generated using information recovered from both the signed communication and the second signed communication. In some embodiments, multiple test values are generated and tested against the received expression, e.g., a first test value using information recovered from the signed communication from the second communications device and a second test value using information recovered from the second signed communication from the second member of said group. In various embodiments in which a second signed communication is received from the second member of said group, the first communication device also performs an operation to verify that the second signed communication was generated by a second private key corresponding to the second public key.

FIG. 6is a drawing of an exemplary first communications device600, in accordance with an exemplary embodiment. Exemplary communications device600is, e.g., one of the wireless communications devices ofFIG. 1. Exemplary communications device600may, and sometimes does, implement a method in accordance with flowchart400ofFIG. 4.

Communications device600includes a processor602and memory604coupled together via a bus609over which the various elements (602,604) may interchange data and information. Communications device600further includes an input module606and an output module608which may be coupled to processor602as shown. However, in some embodiments, the input module606and output module608are located internal to the processor602. Input module606can receive input signals. Input module606can, and in some embodiments does, include a wireless receiver and/or a wired or optical input interface for receiving input. Output module608may include, and in some embodiments does include, a wireless transmitter and/or a wired or optical output interface for transmitting output.

Processor602is configured to: transmit a signal to a second communications device associated with an expression; receive from the second communications device a signed communication signed using a private key known to said second communications device; and determine if said second communication device owns said expression. Processor602is configured to: determine if said expression was generated using a first public key and verify that the signed communication was generated by a private key corresponding to said first public key, as part of being configured to determine if said second communication device owns said expression.

Processor602is further configured to: generate a test value from said first public key and an additional input, said additional input being one of a random number and a time dependent input value; and compare the test value to said expression to determine if they match, a match indicating that said expression was generated using said first public key, as part of being configured to determine if said expression was generated using a first public key.

In some embodiments, said first public key may be, and sometimes is, included in said signed communication, and processor602is further configured to recover the first public key from the signed communication. Processor602, in some embodiments, is further configured to: use an identifier included in said signed communication to retrieve, e.g., from memory or another source such as a public key server, said first public key, said identifier being one or a device and user identifier.

In some embodiments, processor602is further configured to: perform a one-way hash operation using said first public key and said additional input as inputs to the one-way hash operation, an output of said hash operation being said test value, as part of being configured to generate said test value. In various embodiments, the output of said hash operation is limited to a predetermined number of bits; and processor602is further configured to receive different portions of said expression in different peer discovery time periods, as part of being configured to receive the expression.

In some embodiments, said signed communication further includes: hash information, said hash information indicating a one-way hash function to be used to generate said test value. In some such embodiments, processor602is configured to recover the hash information from the signed communication.

In some embodiments, a device or user identifier to which the first public key corresponds may be, and sometimes is, a member of a group; and processor602is configured to use a second public key corresponding to a second member of said group in addition to said first public key to generate said test value, as part of being configured to generate a test value. In some such embodiments, processor602is configured to perform a one-way hash operation using said first and second public keys and said additional input as inputs to the one-way hash operation, an output of said hash operation being said test value, as part of being configured to generate a test value.

FIG. 7is an assembly of modules700which can, and in some embodiments is, used in the first communications device600illustrated inFIG. 6. The modules in the assembly700can be implemented in hardware within the processor602ofFIG. 6, e.g., as individual circuits. Alternatively, the modules may be implemented in software and stored in the memory604of the first communications device600shown inFIG. 6. While shown in theFIG. 6embodiment as a single processor, e.g., computer, it should be appreciated that the processor602may be implemented as one or more processors, e.g., computers. When implemented in software the modules include code, which when executed by the processor, configure the processor, e.g., computer,602to implement the function corresponding to the module. In some embodiments, processor602is configured to implement each of the modules of the assembly of modules700. In embodiments where the assembly of modules700is stored in the memory604, the memory604is a computer program product comprising a computer readable medium comprising code, e.g., individual code for each module, for causing at least one computer, e.g., processor602, to implement the functions to which the modules correspond.

Completely hardware based or completely software based modules may be used. However, it should be appreciated that any combination of software and hardware (e.g., circuit implemented) modules may be used to implement the functions. As should be appreciated, the modules illustrated inFIG. 7control and/or configure the first communications device600or elements therein such as the processor602, to perform the functions of the corresponding steps illustrated in the method flowchart500ofFIG. 5.

Assembly of modules700includes a module704for receiving said expression from a second communications device, a module708for transmitting a signal, e.g, a request for a signed communication, to the second communications device associated with the expression, a module710for receiving from the second communications device a signed communication signed using a private key known to said second communications device, and a module714for determining if said second communications device owns said expression. In various embodiments, a first public key corresponding to the first private key is included in the signed communication received by module710. In some embodiments, the signed communication received by module710includes hash information, said hash information indicating a one-way hash function to be used to generate a test value.

In some embodiments, assembly of modules700further includes a module712for using an identifier included in said signal communication to retrieve, e.g., from memory or another source such as a public key server, a first public key, said identifier being one of a device and user identifier.

In some embodiments, module704includes a module706for receiving different portions of said expression in different peer discovery time periods. In some embodiments, the output of the hash operation is limited to a predetermined number of bits, and module706receives different portions of said expression in different peer discovery time periods.

Module714includes a module716for determining if said expression was generated using a first public key and a module728for performing an operation to verify that the signed communication was generated by a private key corresponding to said first public key. Module716includes a module718for generating a test value from said first public key and an additional input, said additional input being one of a random number and a time dependent variable, and a module726for comparing the test value to said expression to determine if they match, a match indicating that said expression was generated using said first public key.

In some embodiments, module718includes one or more of module720for performing a one-way hash operation using said first public key and said additional input as inputs to the one-way hash operation, an output of said hash operation being said test value and a module722for performing a one-way hash operation using said first public key, a second public key and said additional input as inputs to the one-way hash operation, an output of the one-way hash operation being said test value. Module722includes a module724for using said second public key corresponding to a second member of a group in addition to said first public key to generate said test value, wherein a device or user identifier to which the first public key corresponds is a member of said group.

In some embodiments, assembly of modules700further includes a module730for transmitting a signal, e.g., a request for a signed communication, to second member of said group, and a module732for receiving from the second member of said group a second signed communication signed using a second private key known to the second member of the group. The second private key known to the second member of the group is, e.g., the private key corresponding to the second public key. In some such embodiments, module714uses information recovered from both said first signed communications and said second signed communication in generating a test value to compare to the received expression. In various embodiments, module714for determining if said second communication device owns said expression further includes a module734for performing an operation to verify that the second signed communication was generated by a second private key corresponding to the second public key.

FIG. 8is a drawing800illustrating some exemplary signaling exchanged and intermediary results in regard to generating, communicating and verifying ownership of an expression in accordance with one embodiment. Drawing800illustrates two exemplary wireless peer to peer communications devices (device A802, device B804). Devices802,804are, e.g., any of the wireless communications devices of system100ofFIG. 1. Devices802,804may implement one or more methods in accordance with flowchart200ofFIG. 2and/or flowchart500ofFIG. 5. Devices802,804may be implemented in accordance with one of more of elements described inFIGS. 3,4,6and/or7.

Device A802includes a certificate806which includes a public key (PKA), a corresponding private key A, and identification information. The identification information is, e.g., one of a device or user identifier. Device A802desires to transmit discovery information; therefore, device A802generates an expression812. The expression is generated by device A802as a function of its public key PKA808and additional input. In some embodiments generating the expression includes performing a one-way hash operation using PKAand the additional input to the one-way hash operation, and an output of the one-way hash operation is the generated expression. Device A802generates a discovery signal814to convey the generated expression812. Device A802transmits its discovery signal814over a discovery communications channel816in the air link resources of the peer to peer recurring timing-frequency structure being implemented. Device B804, which has been monitoring for discovery signals from other devices, detects device A discovery signal as indicated by arrow818. Device B804recovers the detected expression as indicated by block820.

Device B804would like to verify that device A802has ownership of the expression. Device B804generates a request for a signed communication822and transmits request signal824to device A802over non-discovery control channel826. In some embodiments, the non-discovery control channel826is one of: a paging channel, a link establishment channel, and a post link establishment control channel. Device A802receives the request signal as indicated by arrow828and recovers the received request for signed communication as indicated by block830. In response, device A802generates a communication832using one or more of: hash information834, PKA808, and ID information838as inputs. The ID information838is, e.g., a device and/or user identifier. The hash information834includes, e.g., information including a hash function used to perform the hash operation used to generate generated expression812and at least one input used to generate expression812. As another example, the hash information834includes, e.g., information used to identify a hash function used to perform the hash operation used to generate generated expression812and at least one input used to generate expression812.

Device A802then signs the generated communication832using its private key A840resulting in generated signed communication842. Device A802generates and transmits a signal844conveying the generated signed communication over non-discovery control channel846. In some embodiments, the non-discovery control channel846is one of: a paging response channel, a link establishment channel, and a post link establishment control channel. Device B804receives the signal carrying the signed communication as indicated by received signal848. Device B804recovers the received signed communication as indicated by block850. Device B804uses information communicated by the received signed communication to generate a test value as indicated by block852. The generated test value is compared to the detected expression820and a comparison matching result854is obtained. In this case, device A802owns the expression which was transmitted, and the private key used to generate the signed communication matched the public key originally used to generate the transmitted expression. In this case the generated test value852matches the detected expression820. Device B804also performs a signature verification as indicated by block856, e.g., using standard public private key verification methods.

FIG. 9is a drawing900illustrating some exemplary signaling exchanged and intermediary results in regard to generating, communicating and verifying ownership of an expression in accordance with one embodiment. Drawing900illustrates two exemplary wireless peer to peer communications devices (device A902, device B904). Devices902,904are, e.g., any of the wireless communications devices of system100ofFIG. 1. Devices902,904may implement one or more methods in accordance with flowchart200ofFIG. 2and/or flowchart500ofFIG. 5. Devices902,904may be implemented in accordance with one of more of elements described inFIGS. 3,4,6and/or7.

Device A902includes a certificate906which includes a public key (PKA), a corresponding private key A, and identification information. The identification information is, e.g., one of a device or user identifier. Device A902is a member of group including device C and device D. Device A902includes a public key for device C (PKC)903and a public key for device D (PKD)905. Device A902desires to transmit discovery information; therefore, device A902generates an expression912. The expression is generated by device A902as a function of its public key PKA908, PKC903, PKD910and additional input. In some embodiments the generating the expression includes performing a one-way hash operation using PKA, PKC, PKDand the additional input to the one-way hash operation, and an output of the one-way hash operation is the generated expression. Device A902generates a discovery signal914to convey the generated expression912. Device A902transmits its discovery signal914over a discovery communications channel916in the air link resources of the peer to peer recurring timing-frequency structure being implemented. Device B904, which has been monitoring for discovery signals from other devices, detects the device A discovery signal as indicated by arrow918. Device B904recovers the detected expression as indicated by block920.

Device B904would like to verify that device A902has ownership of the expression. Device B904generates a request for a signed communication922and transmits request signal924to device A902over non-discovery control channel926. In some embodiments, non-discovery control channel926is one of: a paging channel, a link establishment channel, and a post link establishment control channel. Device A902receives the request signal as indicated by arrow928and recovers the received request for signed communication as indicated by block930. In response, device A902generates a communication932using one or more of: hash information934, PKA908, PKC903, PKD905, and ID information938as inputs. The ID information938is, e.g., a device and/or user identifier. The hash information934includes, e.g., information including a hash function used to perform the hash operation used to generate generated expression912and at least one input used to generate expression912. As another example, the hash information934includes, e.g., information used to identify a hash function used to perform the hash operation used to generate generated expression912and at least one input used to generate expression912.

Device A902then signs the generated communication932using its private key A940resulting in generated signed communication942. Device A902generates and transmits a signal944conveying the generated signed communication over non-discovery control channel946. In some embodiments, the non-discovery control channel946is one of: a paging response channel, a link establishment channel, and a post link establishment control channel. Device B904receives the signal carrying the signed communication as indicated by received signal948. Device B904recovers the received signed communication as indicated by block950.

Device B904uses information communicated by the received signed communication950to generate a test value as indicated by block952. The generated test value is compared to the detected expression920and a comparison matching result954is obtained. In this case, device A902owns the expression which was transmitted, and the private key used to generate the signed communication matched the public key originally used to generate the transmitted expression. In this case the generated test value952matches the detected expression920. Device B904also performs a signature verification on the received signed communication from device A902as indicated by block956, e.g., using standard public private key verification methods.

FIG. 10is a drawing1000illustrating some exemplary signaling exchanged and intermediary results in regard to generating, communicating and verifying ownership of an expression in accordance with one embodiment, wherein said generated expression is based on group information and wherein signed communications are received from two group members as part of the verification. Drawing1000illustrates three exemplary wireless peer to peer communications devices (device A902, device B904, device C1002). Devices902,904,1002are, e.g., any of the wireless communications devices of system100ofFIG. 1. Devices902,904,1002may implement one or more methods in accordance with flowchart200ofFIG. 2and/or flowchart500ofFIG. 5. Devices902,904may be implemented in accordance with one of more of elements described inFIGS. 3,4,6and/or7.

Device A902includes a certificate906which includes a public key (PKA), a corresponding private key A, and identification information. The identification information is, e.g., one of a device or user identifier. Device A902is a member of group including device C and device D. Device A902includes a public key for device C (PKC)903and a public key for device D (PKD)905. Device C1002includes a certificate including public key C, private key C1003, and ID information. Device C1002also includes public key A and public key D. Device A902desires to transmit discovery information; therefore, device A902generates an expression912. The expression is generated by device A902as a function of public key PKA908, PKC903, PKD905and additional input910. In some embodiments generating the expression includes performing a one-way hash operation using PKA, PKC, PKDand the additional input to the one-way hash operation, and an output of the one-way hash operation is the generated expression. Device A902generates a discovery signal914to convey the generated expression912. Device A902transmits its discovery signal914over a discovery communications channel916in the air link resources of the peer to peer recurring timing-frequency structure being implemented. Device B904, which has been monitoring for discovery signals from other devices, detects device A discovery signal as indicated by arrow918. Device B904recovers the detected expression as indicated by block920.

Device B904would like to verify that device A902has ownership of the expression. Device B904generates a request for a signed communication922and transmits request signal924to device A902over non-discovery control channel926. In some embodiments, non-discovery control channel926is one of: a paging channel, a link establishment channel, and a post link establishment control channel. Device A902receives the request signal as indicated by arrow928and recovers the received request for signed communication as indicated by block930. In response, device A902generates a communication932using one or more of: hash information934, PKA908, PKC903, PKD905, and ID information938as inputs. The ID information938is, e.g., a device and/or user identifier. The hash information934includes, e.g., information including a hash function used to perform the hash operation used to generate generated expression912and at least one input used to generate expression912. As another example, the hash information934includes, e.g., information used to identify a hash function used to perform the hash operation used to generate generated expression912and at least one input used to generate expression912.

Device A902then signs the generated communication932using its private key A940resulting in generated signed communication942. Device A902generates and transmits a signal944conveying the generated signed communication over non-discovery control channel946. In some embodiments, the non-discovery control channel946is one of: a paging response channel, a link establishment channel, and a post link establishment control channel. Device B904receives the signal carrying the signed communication as indicated by received signal948. Device B904recovers the received signed communication as indicated by block950.

In response to detected expression920, device B904also generates a request for a signed communication from another member of the group to which device A902belongs. In this example, device B904generates request for a signed communication to device C1004. For example, device C1002may happen to be in the local vicinity of device B904at this time and is available to assist in verification. Device B904and transmits request signal1006carrying request1004to device C1002over non-discovery control channel1008. Device C1002receives the request signal as indicated by arrow1010and recovers the received request for signed communication. In response, device C1002generates a communication using one or more of: hash information, PKA, PKB, PKC, and ID information as inputs.

Device C1002then signs the generated communication using its private key C1003corresponding to its public key C PKC, resulting in generated signed communication1012. Device C1002generates and transmits a signal1014conveying the generated signed communication over non-discovery control channel1016. Device B904receives the signal carrying the signed communication as indicated by received signal1018. Device B904recovers the received signed communication as indicated by block1020.

Device B904uses information communicated by the received signed communication950and/or received signed communication1020to generate a test value as indicated by block952. The generated test value is compared to the detected expression920and a comparison matching result954is obtained. In this case, device A902owns the expression which was transmitted, and the private key used to generate the signed communication matches the public key originally used to generate the transmitted expression. In this case the generated test value952matches the detected expression920. Device B904also performs a signature verification on the received signed communication from device A902as indicated by block956, e.g., using standard public private key verification methods. In addition, device B904also performs a signature verification on the received signed communication from device C1002as indicated by block1022, e.g., using standard public private key verification methods.

Various embodiments are directed to methods and apparatus which allow deriving a set of expressions from a certificate. The set of expressions, in some embodiments, is tightly bound to unique parameters in the certificate, e.g., the public key, which validity, can be verified by checking the signature(s) on the certificate (i.e., signed by at least one certificate authority (CA)), and its ownership verified by checking the signature of the message carrying the certificate. There are two main advantages behind deriving expressions from a certificate:1. It is very difficult, if not impossible, to impersonate the expression's owner since the first step towards verifying the expression(s) is to validate the certificate. This means that the malicious node has to provide a proof of ownership of the private-public key pair, which in turn means that it has to possess the private key which is used to sign the message carrying the certificate.2. Verifying the set of expressions becomes a straightforward and cheap operation. In some embodiments, the set of expressions is validated by validating the certificate and checking the public key ownership. In some embodiments, if both tests yield positive results, then the expressions are easily checked via a simple one, or a few, one-way hash function(s).

A third advantage for using a certificate to derive an expression is that a certificate can also be, and in some embodiments is, self-generated. In such scenario, the certificate verification is reduced to a proof of ownership of the public key, i.e., one signature only. Such a scenario may apply, and in some embodiments is used, in situations where a certificate authority (CA) is not available and/or accessible.

A fourth advantage for using a certificate to derive an expression, is the possibility to use more than one certificate to derive a particular expression. Such a procedure may be referred to as “chaining” as it allows a predefined set of people, each having his/her own private-public key pair, to own a particular expression.

In addition to using the PK to generate the expression(s), in some embodiments, there are other important parameters, which can be used for the same purpose. For example, the HIT (i.e., hash (PK)) is a 128-bit parameter which can be inserted in the one-way hash function together with other random values. In this case, the expression would be the result of the hash. It should be noted that the certificate usually carries the HIT as the owner's identity (or at least one identity).

Another important parameter is the hash of the certificate itself, e.g., the first 128 bits.

It is also possible to derive a parameter(s) from the certificate from which, the expression(s) can be derived. In fact, as long as the ownership of such parameter(s) can be proved then it can be used. Such virtual layering between the certificate and the expression can be useful for privacy purposes (i.e., case of group expression) as the sender will not have to disclose a priori its identities (i.e., mainly not its public key) before checking the certificate of the other peer (e.g., when pairing).

A common feature in the above set of parameters is that each of them can be verified upon validating the certificate and the signature, i.e., ownership of the private-public key pair.

A generic way to create an expression is to apply the following equation:
(Y)=First[m,Hash(M|RAN)]  (1)
Where:First (size, input) indicates truncation of the “input” data so that only the first “size”, i.e., m, bits remain to be used.Hash( ) is a one-way hash functionM is a parameter to be validated by the receiver. It can represent the sender's public key, a HIT, a hash of the certificate, etc.“|” indicates a bytewise concatenationRAN is a random 128-bit parameter
Note: it follows immediately from (1) that an unlimited number of (Y) can be derived from PK. Such feature enables the sender to derive as much expressions as needed without weakening the level of its security.

Various embodiments are directed to communications systems, e.g., peer to peer wireless communications systems. An expression can be, and in some embodiments is, derived from a device certificate. In some peer to peer communications systems, expressions play a key role in announcing both presence and proximity and also to advertise specific information.

However, sending (X, Y) to a set of receivers does not preclude a malicious sender from spoofing the pair of parameters at some stage in an attempt to confuse a set of receivers or to uncover relationship(s) in case of social networks.

Our motivation is to provide a mechanism that allows a receiver of an expression to easily validate that said expression belongs to the device transmitting it, i.e., to prevent spoofing of expressions by devices that do not own them.

Various aspects of an exemplary peer to peer protocol will be described. An expression (E) can be described as a couple of parameters (X, Y) where (X) is the information itself and (Y) is a shared key. The shared key is used to enhance the privacy of the advertising node, by incorporating it together with the current time in the hash of (X). For this purpose, the couple (X, Y) is distributed out of band to a set of receivers together with an identifier, e.g., the sender's host identity tag (HIT), which is obtained from hashing its public key (PK). Each receiver binds the pair(s) (X, Y) to the corresponding HIT. It follows that each of the receivers should be able to verify with a high degree of confidence the sender's identity prior to accepting the pair (X, Y).

It becomes clear from the above that the shared key (Y) plays a critical role in enhancing the sender's own privacy by enabling him/her to be identifiable and traceable to the set of receivers only. For a receiver outside the designed set, the advertised information will not provide any hint about the sender's identity nor the possibility to correlate between different advertisements (i.e., except in particular cases).

The suggested solution, in some embodiments, includes deriving (Y) from the sender device's certificate (e.g., the device's public key or other parameter in the certificate).

In some communications systems, e.g., some peer to peer communications systems, the following steps are used to establish communications between devices:1) Discovery: During this process, devices discover each other, e.g., by transmitting and monitoring for “expressions”.2) Pairing: Once devices discover each other, the process of pairing is used to establish a secure communication channel between the devices.3) Link establishment and higher layer. Once pairing is done, the high layers are initiating to allow data exchange.

Some exemplary embodiments are well suited to allow devices to prove the fact that they own a certain expression transmitted in Discovery phase, during the Pairing phase. In some embodiments, this is achieved by deriving the expression used in Discovery phase from a Certificate belonging to the source device.

Now the expression Y can be proven to belong to the source of that expression by providing the other device with the Certificate of the source and a signature that validates the ownership of said certificate.

Deriving expression (Y) from the sender's PK can be done in the following way:
(Y)=First[m,Hash(PK|RAN)]  (2)
Where:First (size, input) indicates truncation of the “input” data so that only the first “size”, i.e., m, bits remain to be used.Hash( ) is a one-way hash functionPK is the sender's public key“|” indicates a bytewise concatenationRAN is a random 128-bit parameter
Note: it follows immediately from equation (2) that an unlimited number of expression (Y) can be derived from public key (PK). Such feature enables the sender to derive as much expressions as needed without weakening the level of its security.

After deriving expression (Y), the sender shares it with its selected group of receivers together with its HIT. As mentioned earlier, it is important to sign any payload which carries such parameters. Otherwise, the receiver(s) should reject it. Each receiver binds (Y) to the sender's HIT and can start using it to derive fresh advertisements, which are supposed to be sent or to be used when paging the sender (i.e., the sender may decide not to advertise at all).

When a receiver (R) initiates a session with the sender, a security association between the two peers is established prior to exchanging any data packet. The validation of expression (Y) can occur when validating the sender's certificate. The certificate provides receiver (R) with a proof of ownership of PK. In parallel with the certificate validation, the sender can disclose the RAN parameter, which in turn enables receiver (R) to re-compute expression (Y) from the certified PK and RAN.

Deriving expression (Y) from public key (PK) prevents spoofing attack against (Y) since the malicious node has to prove also ownership of PK itself, which is supposed to be substantially difficult to achieve.

In some embodiments, the RAN(s) is (are) sent along with expression (Y) and the HIT. Note that while the HIT should be related to PK, the message carrying each of these parameters may be signed with another private key. In such case, the verification of PK enables the receiver (R) to implicitly validate immediately each of the expression (Y) that are bound to PK.

The techniques of various embodiments may be implemented using software, hardware and/or a combination of software and hardware. In some embodiments, modules are implemented as physical modules. In some such embodiments, the individual physical modules are implemented in hardware, e.g., as circuits, or include hardware, e.g., circuits, with some software. In other embodiments, the modules are implemented as software modules which are stored in memory and executed by a processor, e.g., general purpose computer. Various embodiments are directed to apparatus, e.g., stationary wireless nodes, mobile nodes such as mobile access terminals of which cell phones are but one example, access point such as base stations including one or more attachment points, servers, and/or communications systems. Various embodiments are also directed to methods, e.g., method of controlling and/or operating wireless communications devices including mobile and/or stationary nodes, access points such as base stations, server nodes and/or communications systems, e.g., hosts. Various embodiments are also directed to machine, e.g., computer, readable medium, e.g., ROM, RAM, CDs, hard discs, etc., which include machine readable instructions for controlling a machine to implement one or more steps of a method.

In various embodiments nodes described herein are implemented using one or more modules to perform the steps corresponding to one or more methods, for example, generating an expression from a first public key and an additional input, said first public key corresponding to a private key known to said first communications device; and transmitting the generated expression on a communications channel used for discovery.

Thus, in some embodiments various features are implemented using modules. Such modules may be implemented using software, hardware or a combination of software and hardware. Many of the above described methods or method steps can be implemented using machine executable instructions, such as software, included in a machine readable medium such as a memory device, e.g., RAM, floppy disk, etc. to control a machine, e.g., general purpose computer with or without additional hardware, to implement all or portions of the above described methods, e.g., in one or more nodes. Accordingly, among other things, various embodiments are directed to a machine-readable medium including machine executable instructions for causing a machine, e.g., processor and associated hardware, to perform one or more of the steps of the above-described method(s). Some embodiments are directed to a device, e.g., communications device, including a processor configured to implement one, multiple or all of the steps of one or more methods of the invention.

In some embodiments, the processor or processors, e.g., CPUs, of one or more devices, e.g., communications devices such as wireless terminals are configured to perform the steps of the methods described as being performed by the communications device. Accordingly, some but not all embodiments are directed to a device, e.g., communications device, with a processor which includes a module corresponding to each of the steps of the various described methods performed by the device in which the processor is included. In some but not all embodiments a device, e.g., communications device, includes a module corresponding to each of the steps of the various described methods performed by the device in which the processor is included. The modules may be implemented using software and/or hardware.

While various features are described in the context of an OFDM system, at least some of the methods and apparatus of various embodiments are applicable to a wide range of communications systems including many non-OFDM and/or non-cellular systems.

Numerous additional variations on the methods and apparatus of the various embodiments described above will be apparent to those skilled in the art in view of the above description. Such variations are to be considered within the scope. The methods and apparatus may be, and in various embodiments are, used with CDMA, orthogonal frequency division multiplexing (OFDM), GSM and/or various other types of communications techniques which may be used to provide wireless communications links, e.g., WAN wireless communications links, between access points and wireless communications device such as mobile nodes and wireless communications. The methods and apparatus may be, and in various embodiments are, used with CDMA, orthogonal frequency division multiplexing (OFDM), GSM and/or various other types of communications techniques which may be used to provide wireless communications links, e.g., direct peer to peer wireless communications links, between wireless communications devices including peer to peer interfaces. In some embodiments a wireless communications device including both a wide area network interface and a peer to peer network interface uses different communications techniques for the different interfaces, e.g., one of CDMA and GSM based techniques for the WAN interface and OFDM based techniques for the peer to peer interface. In some embodiments the access points are implemented as base stations which establish communications links with mobile nodes using CDMA, GSM and/or OFDM. In various embodiments the mobile nodes are implemented as notebook computers, personal data assistants (PDAs), or other portable devices including receiver/transmitter circuits and logic and/or routines, for implementing the methods.