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.