Patent Description:
Current messaging systems have used many different types of data encryption in peer-to-peer communications to ensure data security and privacy. Most state-of-the-art methods include the transfer of at least some identity information about participants in a chat event to the server hosting the event. Accordingly, when the server is compromised by a malicious third party, large numbers of users of the chat server (millions, or even billions of people) may become victims of identity theft, data loss, or publication of sensitive, personal information.

<CIT> describes an identification method and server for validation of online identities which uses public keys and identities to provide secure access to personal identity information.

Lecture Notes in <NPL>am describes an end-to-end encryption based approach that uses the RSA public-key encryption algorithm, as well as the AES symmetric-key encryption algorithm.

<CIT> describes techniques for multi-agent messaging authorization.

According to a first aspect, there is provided a computer-implemented method according to claim <NUM> of the appended claims.

According to a second aspect, there is provided a system, comprising: a memory storing multiple instructions; and one or more processors configured to execute the instructions to cause the system to carry out the method of the first aspect.

According to a third aspect, there is provided a computer program product comprising instructions which, when the instructions are executed by one or more processors of a computer, cause the computer to carry out the method of the first aspect.

According to a fourth aspect, there is provided a computer readable storage medium comprising instructions which, when executed by one or more processors, cause the one or more processors to carry out the method of the first aspect.

These and other embodiments will become clear to one of ordinary skill in view of the following disclosure.

In the figures, elements having the same or similar reference numerals are related to the same or similar attributes or features, unless explicitly stated otherwise.

In the following detailed description, numerous specific details are set forth to provide a full understanding of the present disclosure. It will be apparent, however, to one ordinarily skilled in the art, that the embodiments of the present disclosure may be practiced without some of these specific details. In other instances, well-known structures and techniques have not been shown in detail so as not to obscure the disclosure.

The use of end-to-end encrypted messaging ensures that conversations between users remain private. However, it is desirable to ensure that these interactions occur with people whose identities are certified. To avoid being compromised by a malicious attack (e.g., by an impersonator, or to be robbed of one's own identity for spurious activity), users typically discover the necessary public keys to identify each other. In some configurations, identity verification is accomplished by scanning a quick-response (QR) code in person to validate recipient public keys or by depending on a service provider to generate the relevant public key associated with a communication partner. In some approaches, a service provider stores the public keys of individuals on a publicly accessible key directory server so that users can query this server for messaging individuals in their contact list. However, since the server can supply users with outdated or fabricated keys, this strategy is vulnerable to attacks on the server itself (e.g., the server becoming a malicious actor).

To resolve the above problems arising in the technical field of identity verification for group chats and calls, embodiments as disclosed herein include an efficient, verifiable directory including a cryptographic primitive which allows an identity provider to store an evolving set of label-value pairs, commit to this set, as well as respond (with crypto-graphic proofs) to queries about this committed set and its updates. Accordingly, embodiments as disclosed herein include a large-scale cryptographic construction that can support billions of users on reasonably-sized servers. To make the system efficient, some embodiments include a modified crypto-graphic building-block as an ordered zero-knowledge set, which augments the primitives to satisfy the functionality and security requirements, without degrading privacy. The zero-knowledge set includes functions that verify the identity of call participants without revealing private information critical to the participant, when the request for verification involves a third-party or non-registered user. This preserves the functionality of the architecture without compromising privacy, and increasing the efficiency (as less cryptographic transactions are used).

In addition to zero-knowledge functions, some embodiments include a compaction operation that reduces the data stored on the secured database. Accordingly, the compaction operation purges ancient and obsolete entries. In some embodiments, a secure compaction operation may loosen the constraints for using "append-only" data-structures, which provide quick storage and retrieval data access. In some embodiments, verifiable directories with compaction as disclosed herein may include subroutines having a tunable leakage parameter, which can be updated in accuracy and precision. In some embodiments, compaction operations may be used only for long term data storage and usage. In addition to constructing memory optimizations for verifiable directories, some embodiments include a modular and flexible data-layer application programming interface (API), which can implemented using a distributed database solution (or even a local, in-memory storage solution).

Some embodiments include an identity provider that keeps a local database linking each of a user identifier (e.g., phone numbers, names, aliases, name tags, and other identification values) to an associated public key. The identity provider periodically sends a commitment of its latest state to a distributed set of authorities (e.g., witnesses) that ensure its correct behavior. The witnesses store the latest commitment and also communicate with users to make sure the identity provider is not censoring or eclipsing them. The users may query the identity provider to look up the public key associated with a specific user identifier. Each user can additionally monitor the history of their own public key, to identify a malicious activity or error. The identity provider ensures that only permissioned users can perform particular actions.

<FIG> illustrates a network architecture <NUM> configured for device verification in group chat applications, according to some embodiments. Servers <NUM> and a database <NUM> are communicatively coupled with client devices <NUM> via a network <NUM>. Servers <NUM> may host a group chat application running in client devices <NUM>. Client devices <NUM> may be used by participants in the group chats (e.g., chats involving two or more participants). Client devices <NUM> may include smart phones, laptops, mobile devices, palm devices, and even desktops. In some embodiments, client devices <NUM> may include virtual reality or augmented reality (VR/AR) headsets and/or smart glasses, and the group chat conversation may include immersive reality elements. Network <NUM> can include, for example, any one or more of a local area network (LAN), a wide area network (WAN), the Internet, and the like. Further, network <NUM> can include, but is not limited to, any one or more of the following network topologies, including a bus network, a star network, a ring network, a mesh network, a star-bus network, tree or hierarchical network, and the like. Database <NUM> may store user identification protected by encrypted keys that may be distributed to each and all of the group chat participants.

<FIG> is a block diagram <NUM> illustrating an example server <NUM>, client device <NUM>, and database <NUM> from architecture <NUM>, according to some embodiments. Client device <NUM> and server <NUM> are communicatively coupled over network <NUM> via respective communications modules <NUM>-<NUM> and <NUM>-<NUM> (hereinafter, collectively referred to as "communications modules <NUM>"). Communications modules <NUM> are configured to interface with network <NUM> to send and receive information, such as data, requests, responses, and commands to other devices via network <NUM>. Communications modules <NUM> can be, for example, modems or Ethernet cards, and may include radio hardware and software for wireless communications (e.g., via electromagnetic radiation, such as radiofrequency -RF-, near field communications -NFC-, Wi-Fi, and Bluetooth radio technology). A user may interact with client device <NUM> via an input device <NUM> and an output device <NUM>. Input device <NUM> may include a mouse, a keyboard, a pointer, a touchscreen, a microphone, a joystick, a virtual joystick, and the like. In some embodiments, input device <NUM> may include cameras, microphones, and sensors, such as touch sensors, acoustic sensors, inertial motion units -IMUs- and other sensors configured to provide input data to a VR/AR headset. Output device <NUM> may be a screen display, a touchscreen, a speaker, and the like.

Client device <NUM> may include a memory <NUM>-<NUM> and a processor <NUM>-<NUM>. Memory <NUM>-<NUM> may include a group chat application <NUM>, configured to run in client device <NUM> and couple with input device <NUM> and output device <NUM>. Application <NUM> may be downloaded by the user from server <NUM> and may be hosted by server <NUM>. Execution of application <NUM> may be controlled by processor <NUM>-<NUM>. In some embodiments, client device <NUM> is a VR/AR headset and application <NUM> is an immersive reality application (e.g., an immersive group chat application). In some embodiments, client device <NUM> is a mobile phone that can collect a video or image of a participant in a group chat hosted by application <NUM>.

Server <NUM> includes a memory <NUM>-<NUM>, a processor <NUM>-<NUM>, a communications module <NUM>-<NUM>, and an API <NUM>. Hereinafter, processors <NUM>-<NUM> and <NUM>-<NUM>, and memories <NUM>-<NUM> and <NUM>-<NUM>, will be collectively referred to, respectively, as "processors <NUM>" and "memories <NUM>. " Processors <NUM> are configured to execute instructions stored in memories <NUM>.

In some embodiments, memory <NUM>-<NUM> includes a chat engine <NUM>, a storage engine <NUM>, and a verification engine <NUM>. A participant in a group chat may access chat engine <NUM> using client device <NUM>, through application <NUM>. Chat engine <NUM> may share or provide features and resources to application <NUM>, such as a messaging tool <NUM>, through API <NUM>. Messaging tool <NUM> is configured to collect and synchronize voice, text, and media feeds (e.g., video, images, screenshares, and the like) from each participant in a group chat and provide a chat feed to all participants.

Storage engine <NUM> includes a tree tool <NUM> that provides a data storage architecture in a publicly verifiable configuration. Tree tool <NUM> may also provide identity proofs to client devices <NUM> used by participants in group chats. In some embodiments, identity proofs are not encrypted, and may be readable/verifiable by anyone in the public. Identity proofs provide cryptographic proof of data stored in database <NUM>, such as a public key associated with client device <NUM>, which is necessary to sending messages to its user. While the identity proof is publicly visible, it cannot be modified by anyone in the public, and unauthorized edits to identity proofs cause identity validation to fail.

Verification engine <NUM> may include an encryption tool <NUM>, a verifiable random tool <NUM>, and a zero-knowledge tool <NUM>. Encryption tool <NUM> provides encrypted pairs including a public key and a private key for each identification value of registered users of chat application <NUM>. An identification value for a user may include an identification number for client device <NUM>, an identification number or a name tag associated with the user of client device <NUM>, or any combination thereof. The public key may be stored with the identification value according to a verifiable architecture (e.g., a Merkle tree) provided by tree tool <NUM>. The verifiable architecture may include further encryption steps executed by encryption tool <NUM>. Verifiable random tool <NUM> may generate a deterministic function executable by a holder of a private key having as input the associated public key, and produces an identification proof as an output. Zero-knowledge tool <NUM> includes a function that verifies an identification value for a third-party accessing verification engine <NUM> without revealing a privacy sensitive information about a user of chat engine <NUM>.

Accordingly, client device <NUM> may provide a data set <NUM> to server <NUM>, and server <NUM> may provide a data set <NUM> to client device <NUM>. Data set <NUM> may include an information value for client device <NUM> (or the user/owner thereof), or an updated information value, or a request for an information proof. Likewise, data set <NUM> may include an information proof, an encrypted pair of public and private keys, or either of these, or a script for a verifiable random function or a leakage function for a zero-knowledge identity authentication.

Database <NUM> may include a verifiable directory <NUM> storing identifications of users registered with chat engine <NUM>, each identification protected by an encrypted pair of keys also stored in verifiable directory <NUM>. Verifiable directory <NUM> may be created by storage engine <NUM> using tree tool <NUM> to store identification values and encrypted keys in a Merkle tree. Identification updates in verifiable directory <NUM> are instantiated by verifiable random tool <NUM> and zero-knowledge tool <NUM>. In some embodiments, an identification update may include a change of a name tag for a user of chat engine <NUM>, or the same user with the same identification value may want to register a new client device <NUM>. The new client device <NUM> may replace an old client device <NUM>, or may be added by the user to the same username for alternative use of group chat application <NUM>. Accordingly, the dimension and complexity of verifiable directory <NUM> grows linearly with the number of updates for labels in the directory.

In some embodiments, chat engine <NUM>, storage engine <NUM>, verification engine <NUM>, the tools contained therein, and at least part of database <NUM> may be hosted in a different server that is accessible by server <NUM> or client device <NUM>.

<FIG> is a block diagram <NUM> illustrating a first participant ("Alice") using client device <NUM>, initiating a call via a chat engine <NUM> in a server <NUM> with a second participant ("Bob," not shown) and requesting an identity proof of Bob from a verifiable directory <NUM>, according to some embodiments.

In step <NUM>, Alice requests chat engine <NUM> to initiate the chat with Bob. In step <NUM>, chat engine <NUM> transmits Bob's identity values to Alice. In step <NUM>, Alice requests verifiable directory <NUM> an identity proof for Bob. In step <NUM>, Alice receives the identity proof for Bob from verifiable directory <NUM>. When Alice verifies the identity proof, she starts the chat with Bob in step <NUM>.

While chat engine <NUM> and verifiable directory <NUM> are shown as being within the same server <NUM>, this is not necessarily the case, as embodiments consistent with the present disclosure may include each of chat engine <NUM> and verifiable directory <NUM> being in separate servers.

<FIG> is a block diagram <NUM> illustrating a change of identity from a first participant (e.g., Alice) in a call using a client device <NUM>-<NUM>, and a request from a second participant (e.g., Bob) to verifiable directory <NUM> in server <NUM>, to verify the change of identity, according to some embodiments. The call is handled by chat engine <NUM> in server <NUM>. Bob may use a separate client device <NUM>-<NUM> to participate in the call. Hereinafter, client devices <NUM>-<NUM> and <NUM>-<NUM> will be collectively referred to as "client devices <NUM>.

In step <NUM>, Alice submits a change of identity value to chat engine <NUM>. The change of identity value may include a change of name, a change of alias, or any other identification number or text, or even a change of client device (e.g., <NUM>-<NUM> replacing client device <NUM>, or retiring client device <NUM>, which may be lost or stolen, or simply adding a new client device <NUM>-<NUM> to make calls, e.g., a new laptop, a new desktop, palm device, and the like). In step <NUM>, Bob receives from chat engine <NUM> a notification about the change of identity submitted by Alice. In step <NUM>, Bob requests verifiable directory <NUM> to verify Alice's change of identity. In response, verifiable directory <NUM> sends Bob an identity proof for Alice that includes Alice's new identity in step <NUM>. Bob may authenticate the validity of the identity proof using a verifiable random function and a private key provided to Bob by server <NUM> (cf. encryption tool <NUM> and verifiable random tool <NUM>).

<FIG> illustrates a graphic code <NUM> provided to a call participant (e.g., Alice) on a chat application <NUM> in a mobile device <NUM>, for verifying an identity of a second participant (e.g., Bob) in the call, according to some embodiments. Alice may be running chat application <NUM> in a client device (e.g., a mobile phone). Chat application <NUM> may include an encryption widget <NUM> handled by an encryption tool in the server hosting application <NUM> (cf. encryption tool <NUM>). Alice may then scan graphic code <NUM> and authenticate Bob's identity to continue with or initiate the call.

<FIG> is a tree diagram <NUM> illustrating the architecture of a verifiable directory <NUM> storing identities values <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> (hereinafter, collectively referred to as "identity values <NUM>") for each of the users of a group chat application, according to some embodiments. Identity values <NUM> may be identity values by the users themselves or an identity provider (e.g., a government institution or some other authority). Diagram <NUM> may be a Merkle tree, configured in such a way that all the information may be compacted into a single hash <NUM> after one or two layers of hashing. A first layer includes hashes <NUM>-<NUM>, <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM> (hereinafter, collectively referred to as "first layer hashes <NUM>"), resulting from hashing identity values <NUM> with the public keys for each of the users. A second layer of hashes <NUM>-<NUM> and <NUM>-<NUM> (hereinafter, collectively referred to as "second layer hashes <NUM>") may include a pairwise hashing of first layer hashes <NUM> according to rules defined by a variable random function (cf. verifiable random tool <NUM>). Finally, a third layer of hashing <NUM> is achieved again by pairwise hashing second layer hashes <NUM> based on rules established by the variable random function. Notice how the complexity and size of the data structure is reduced by a factor of <NUM> for higher layers.

While diagram <NUM> is an illustrative example, it is understood that the hashing for every layer may be performed by triples, quadruples, and k-tuples in general, in which case the reduction in size takes place at a geometric pace by exponents of k, while the computation length increases logarithmically at base-k.

<FIG> illustrate throughput-latency charts 700A, 700B, and 700C (hereinafter, collectively referred to as "charts <NUM>") for different verifiable directory architectures in a group chat application, according to some embodiments. Charts <NUM> indicate throughput <NUM> (abscissae, e.g., updates per second, arbitrary scale) and latency <NUM> (ordinates, e.g., seconds, arbitrary scale) of tree architectures for a verifiable directory as disclosed herein (cf. diagram <NUM>, and verifiable directory <NUM>). Accordingly, data structures as disclosed herein achieve enough throughput to operate at a world-wide scale. In addition, low latency is obtained even under high network load, and with large community sizes. The database runs efficiently on inexpensive machines with low specifications, and is robust when some parts of the system inevitably crash-fail. Charts <NUM> correspond to five different regions: N. Virginia (us-east-<NUM>), N. California (us-west-<NUM>), Sydney (ap-southeast-<NUM>), Stockholm (eu-north-<NUM>), and Tokyo (ap-northeast-<NUM>). The witnesses are evenly distributed across those regions. Each machine provides up to 5Gbps of bandwidth, <NUM> virtual computation processing units (CPUs), with <NUM> physical core each, on a <NUM>, 4GB memory.

Chart 700A illustrates curves 710a-<NUM>, 710a-<NUM>, and 710a-<NUM> (hereinafter, collectively referred to as "curves 710a") for varying numbers of witnesses. The maximum throughput <NUM> is around <NUM> updates/s (chart 710a-<NUM>) while keeping latency <NUM> below <NUM> seconds. In some configurations, an update rate around <NUM> updates/s may be sufficient. Chart 700A also illustrates that performance does not vary with <NUM> (curve 710a-<NUM>), <NUM> (curve 710a-<NUM>), or even <NUM> (curve 710a-<NUM>) witnesses. Increasing the number of geo-distributed witnesses up to <NUM> doesn't impact the end-to-end performance of the system. Increasing the number of witnesses may eventually make the network to become the system bottleneck.

Chart 700B illustrates curves 710b-<NUM>, 710b-<NUM>, 710b-<NUM>, and 710b-<NUM> (hereinafter, collectively referred to as "curves 710b") when varying the batch size from <NUM><NUM> (710b-<NUM>), to <NUM><NUM> (710b-<NUM>), to <NUM><NUM> (710b-<NUM>), to <NUM><NUM>(710b-<NUM>) for <NUM> witnesses. The maximum throughput observed for batches sizes of <NUM><NUM> (710b-<NUM>) and <NUM><NUM> (710b-<NUM>) is respectively <NUM> updates/s and <NUM> updates/s. This is much lower than the <NUM> updates/s that can be achieved when configured with a batch size over <NUM><NUM> (710b-<NUM>). Small batch sizes allow the database to trade throughput for latency. A database configured with a batch size of <NUM><NUM> can process up to <NUM> updates/s in less than <NUM>, and setting the batch size to <NUM><NUM> allows the database to operate at a massive scale while robustly maintaining sub-second latency.

Chart 700C illustrates curves 710c-<NUM>, 710c-<NUM>, and 710c-<NUM> (hereinafter, collectively referred to as "curves 710c") when a committee of <NUM> witnesses suffers <NUM> (710c-<NUM>), <NUM> (710c-<NUM>), and <NUM> (710c-<NUM>) crash-faults (the maximum that can be tolerated in some embodiments). Accordingly, the database performance is not affected by crash-faults.

<FIG> is a flow chart illustrating steps in a method <NUM> for using a verifiable key directory in a group chat, according to some embodiments. In some embodiments, a processor executing instructions stored in a memory may cause a computer in a client device, a server or database, communicatively coupled through a network via communications modules (cf. client devices <NUM>, servers <NUM>, database <NUM>, network <NUM>, processors <NUM>, memories <NUM>, and communications modules <NUM>), to perform at least one or more of the steps in method <NUM>, as disclosed herein. The memory may include a group chat application hosted by a chat engine, and a verifiable directory created by a tree tool in a storage engine as disclosed herein (cf. application <NUM>, chat engine <NUM>, verifiable directory <NUM>, storage engine <NUM>, and tree tool <NUM>). The verifiable directory may be created using an encryption tool and provide identification proofs by accessing a verifiable random tool or a zero-knowledge tool in a verification engine, as disclosed herein (cf. encryption tool <NUM>, verifiable random tool <NUM>, and zero-knowledge tool <NUM> in verification engine <NUM>). In some embodiments, methods consistent with the present disclosure may include at least one or more of the steps in method <NUM> performed in a different order, simultaneously, quasi-simultaneously, or overlapping in time.

Step <NUM> includes requesting, with a first client device from a first participant, to initiate a chat with a second client device from a second participant.

Step <NUM> includes receiving, from a chat server, an identification for the second participant.

Step <NUM> includes requesting, from a verifiable directory, an identity proof of the second participant associated with the identification for the second participant, wherein the verifiable directory includes a list of encryption public-keys for client devices associated with each of multiple users in the chat server. In some embodiments, step <NUM> includes requesting an updated identity proof for the second participant when the identity proof is not decoded by the private key.

Step <NUM> includes verifying the identity proof of the second participant with a public key associated with the second client device. In some embodiments, step <NUM> includes identifying a source of an identity attack from at least one of the second participant and the chat server. In some embodiments, step <NUM> includes requesting, to the verifiable directory, to update an identity for the first participant or the second participant. In some embodiments, step <NUM> includes matching, in the first client device, an output of a verifiable random function with the public key associated with the second client device as an input, with the identity proof. In some embodiments, the identity proof is a graphic code and step <NUM> includes scanning the graphic code with the first client device.

Step <NUM> includes initiating the chat with the second participant when the identity proof of the second participant is verified. In some embodiments, step <NUM> includes terminating the chat when the identity proof is not decoded by the public key associated with the second client device.

<FIG> is a flow chart illustrating steps in a method <NUM> for creating a verifiable key directory in a group chat service, according to some embodiments. In some embodiments, a processor executing instructions stored in a memory may cause a computer in a client device, a server or database, communicatively coupled through a network via communications modules (cf. client devices <NUM>, servers <NUM>, database <NUM>, network <NUM>, processors <NUM>, memories <NUM>, and communications modules <NUM>), to perform at least one or more of the steps in method <NUM>, as disclosed herein. The memory may include a group chat application hosted by a chat engine, and a verifiable directory created by a tree tool in a storage engine as disclosed herein (cf. application <NUM>, chat engine <NUM>, verifiable directory <NUM>, storage engine <NUM>, and tree tool <NUM>). The verifiable directory may be created using an encryption tool and provide identification proofs by accessing a verifiable random tool or a zero-knowledge tool in a verification engine, as disclosed herein (cf. encryption tool <NUM>, verifiable random tool <NUM>, and zero-knowledge tool <NUM> in verification engine <NUM>). In some embodiments, methods consistent with the present disclosure may include at least one or more of the steps in method <NUM> performed in a different order, simultaneously, quasi-simultaneously, or overlapping in time.

Step <NUM> includes requesting, from an identity provider, an identification value for a user of a chat group service. In some embodiments, step <NUM> includes receiving, from the user of the chat group service, a request to verify the identification value.

Step <NUM> includes requesting, from a selected witness authority, a cross-validation of the identification value.

Step <NUM> includes generating an encrypted pair associated with the identification value upon receipt of the cross-validation of the identification value, the encrypted pair including a private key and a public key.

Step <NUM> includes storing the identification value and the public key in a database.

Step <NUM> includes transmitting the private key to the user of the chat group service. In some embodiments, step <NUM> includes receiving, from a participant in a group chat supported by the chat group service, a request for an identity proof of the user of the chat group service, and transmitting the private key to the participant in the group chat supported by the chat group service. In some embodiments, step <NUM> includes receiving, from the user of the chat group service, a request to modify the identification value into a new identification value, requesting, from the selected witness authority, a cross-validation of the new identification value, generating a new encrypted pair upon receipt of the cross-validation of the new identification value, the new encrypted pair including a new public key and a new private key, and updating the database to the new identification value associated with the new public key. In some embodiments, step <NUM> includes generating a new encrypted pair after a pre-selected period of time, the new encrypted pair including a new public key and a new private key, and updating the database to include the identification value associated with the new public key. In some embodiments, step <NUM> includes marking the identification value and the public key for deletion in the database; and deleting the identification value and the public key after a pre-selected period of time.

<FIG> is a block diagram illustrating an exemplary computer system <NUM> with which headsets and other client devices <NUM>, and method <NUM> and <NUM> can be implemented, according to some embodiments. In certain aspects, computer system <NUM> may be implemented using hardware or a combination of software and hardware, either in a dedicated server, or integrated into another entity, or distributed across multiple entities. Computer system <NUM> may include a desktop computer, a laptop computer, a tablet, a phablet, a smartphone, a feature phone, a server computer, or otherwise. A server computer may be located remotely in a data center or be stored locally.

Computer system <NUM> includes a bus <NUM> or other communication mechanism for communicating information, and a processor <NUM> (e.g., processors <NUM>) coupled with bus <NUM> for processing information. By way of example, the computer system <NUM> may be implemented with one or more processors <NUM>. Processor <NUM> may be a general-purpose microprocessor, a microcontroller, a Digital Signal Processor (DSP), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA), a Programmable Logic Device (PLD), a controller, a state machine, gated logic, discrete hardware components, or any other suitable entity that can perform calculations or other manipulations of information.

Computer system <NUM> can include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them stored in an included memory <NUM> (e.g., memories <NUM>), such as a Random Access Memory (RAM), a flash memory, a Read-Only Memory (ROM), a Programmable Read-Only Memory (PROM), an Erasable PROM (EPROM), registers, a hard disk, a removable disk, a CD-ROM, a DVD, or any other suitable storage device, coupled with bus <NUM> for storing information and instructions to be executed by processor <NUM>. The processor <NUM> and the memory <NUM> can be supplemented by, or incorporated in, special purpose logic circuitry.

The instructions may be stored in the memory <NUM> and implemented in one or more computer program products, e.g., one or more modules of computer program instructions encoded on a computer-readable medium for execution by, or to control the operation of, the computer system <NUM>, and according to any method well known to those of skill in the art, including, but not limited to, computer languages such as data-oriented languages (e.g., SQL, dBase), system languages (e.g., C, Objective-C, C++, Assembly), architectural languages (e.g., Java,. NET), and application languages (e.g., PHP, Ruby, Perl, Python). Instructions may also be implemented in computer languages such as array languages, aspect-oriented languages, assembly languages, authoring languages, command line interface languages, compiled languages, concurrent languages, curly-bracket languages, dataflow languages, data-structured languages, declarative languages, esoteric languages, extension languages, fourth-generation languages, functional languages, interactive mode languages, interpreted languages, iterative languages, list-based languages, little languages, logic-based languages, machine languages, macro languages, metaprogramming languages, multiparadigm languages, numerical analysis, non-English-based languages, object-oriented class-based languages, object-oriented prototype-based languages, offside rule languages, procedural languages, reflective languages, rule-based languages, scripting languages, stack-based languages, synchronous languages, syntax handling languages, visual languages, wirth languages, and xml-based languages. Memory <NUM> may also be used for storing temporary variable or other intermediate information during execution of instructions to be executed by processor <NUM>.

A computer program as discussed herein does not necessarily correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, subprograms, or portions of code).

Computer system <NUM> further includes a data storage device <NUM> such as a magnetic disk or optical disk, coupled with bus <NUM> for storing information and instructions. Computer system <NUM> may be coupled via input/output module <NUM> to various devices. Input/output module <NUM> can be any input/output module. Exemplary input/output modules <NUM> include data ports such as USB ports. The input/output module <NUM> is configured to connect to a communications module <NUM>. Exemplary communications modules <NUM> include networking interface cards, such as Ethernet cards and modems. In certain aspects, input/output module <NUM> is configured to connect to a plurality of devices, such as an input device <NUM> and/or an output device <NUM>. Exemplary input devices <NUM> include a keyboard and a pointing device, e.g., a mouse or a trackball, by which a consumer can provide input to the computer system <NUM>. Other kinds of input devices <NUM> can be used to provide for interaction with a consumer as well, such as a tactile input device, visual input device, audio input device, or brain-computer interface device. For example, feedback provided to the consumer can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the consumer can be received in any form, including acoustic, speech, tactile, or brain wave input. Exemplary output devices <NUM> include display devices, such as an LCD (liquid crystal display) monitor, for displaying information to the consumer.

According to one aspect of the present disclosure, headsets and client devices <NUM> can be implemented, at least partially, using a computer system <NUM> in response to processor <NUM> executing one or more sequences of one or more instructions contained in memory <NUM>. Such instructions may be read into memory <NUM> from another machine-readable medium, such as data storage device <NUM>. One or more processors in a multi-processing arrangement may also be employed to execute the sequences of instructions contained in memory <NUM>. In alternative aspects, hard-wired circuitry may be used in place of or in combination with software instructions to implement various aspects of the present disclosure. Thus, aspects of the present disclosure are not limited to any specific combination of hardware circuitry and software.

Various aspects of the subject matter described in this specification can be implemented in a computing system that includes a back end component, e.g., a data server, or that includes a middleware component, e.g., an application server, or that includes a front end component, e.g., a client computer having a graphical consumer interface or a Web browser through which a consumer can interact with an implementation of the subject matter described in this specification, or any combination of one or more such back end, middleware, or front end components. The communication network can include, for example, any one or more of a LAN, a WAN, the Internet, and the like. Further, the communication network can include, but is not limited to, for example, any one or more of the following network topologies, including a bus network, a star network, a ring network, a mesh network, a star-bus network, tree or hierarchical network, or the like. The communications modules can be, for example, modems or Ethernet cards.

Computer system <NUM> can include clients and servers. Computer system <NUM> can be, for example, and without limitation, a desktop computer, laptop computer, or tablet computer. Computer system <NUM> can also be embedded in another device, for example, and without limitation, a mobile telephone, a PDA, a mobile audio player, a Global Positioning System (GPS) receiver, a video game console, and/or a television set top box.

The term "machine-readable storage medium" or "computer-readable medium" as used herein refers to any medium or media that participates in providing instructions to processor <NUM> 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 data storage device <NUM>. Volatile media include dynamic memory, such as memory <NUM>. Transmission media include coaxial cables, copper wire, and fiber optics, including the wires forming bus <NUM>. Common forms of machine-readable media include, for example, floppy disk, a flexible disk, hard disk, magnetic tape, any other magnetic medium, a CD-ROM, DVD, any other optical medium, punch cards, paper tape, any other physical medium with patterns of holes, a RAM, a PROM, an EPROM, a FLASH EPROM, any other memory chip or cartridge, or any other medium from which a computer can read. The machine-readable storage medium can be a machine-readable storage device, a machine-readable storage substrate, a memory device, a composition of matter affecting a machine-readable propagated signal, or a combination of one or more of them.

To illustrate the interchangeability of hardware and software, items such as the various illustrative blocks, modules, components, methods, operations, instructions, and algorithms have been described generally in terms of their functionality. Whether such functionality is implemented as hardware, software, or a combination of hardware and software depends upon the particular application and design constraints imposed on the overall system.

As used herein, the phrase "at least one of" preceding a series of items, with the terms "and" or "or" to separate any of the items, modifies the list as a whole, rather than each member of the list (e.g., each item).

Phrases such as an aspect, the aspect, another aspect, some aspects, one or more aspects, an implementation, the implementation, another implementation, some implementations, one or more implementations, an embodiment, the embodiment, another embodiment, some embodiments, one or more embodiments, a configuration, the configuration, another configuration, some configurations, one or more configurations, the subject technology, the disclosure, the present disclosure, and other variations thereof and alike are for convenience and do not imply that a disclosure relating to such phrase(s) is essential to the subject technology or that such disclosure applies to all configurations of the subject technology.

A reference to an element in the singular is not intended to mean "one and only one" unless specifically stated, but rather "one or more. " The term "some" refers to one or more. Underlined and/or italicized headings and subheadings are used for convenience only, do not limit the subject technology, and are not referred to in connection with the interpretation of the description of the subject technology. Moreover, nothing disclosed herein is intended to be dedicated to the public, regardless of whether such disclosure is explicitly recited in the above description. §<NUM>, sixth paragraph, unless the element is expressly recited using the phrase "means for" or, in the case of a method claim, the element is recited using the phrase "step for.

While this specification contains many specifics, these should not be construed as limitations on the scope of what may be described, but rather as descriptions of particular implementations of the subject matter. Moreover, although features may be described above as acting in certain combinations and even initially described as such, one or more features from a described combination can in some cases be excised from the combination, and the described combination may be directed to a subcombination or variation of a subcombination.

The subject matter of this specification has been described in terms of particular aspects, but other aspects can be implemented and are within the scope of the following claims. For example, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. The actions recited in the claims can be performed in a different order and still achieve desirable results. As one example, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. Moreover, the separation of various system components in the aspects described above should not be understood as requiring such separation in all aspects, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

The title, background, brief description of the drawings, abstract, and drawings are hereby incorporated into the disclosure and are provided as illustrative examples of the disclosure, not as restrictive descriptions. It is submitted with the understanding that they will not be used to limit the scope or meaning of the claims. In addition, in the detailed description, it can be seen that the description provides illustrative examples and the various features are grouped together in various implementations for the purpose of streamlining the disclosure. The method of disclosure is not to be interpreted as reflecting an intention that the described subject matter requires more features than are expressly recited in each claim. Rather, as the claims reflect, inventive subject matter lies in less than all features of a single disclosed configuration or operation. The claims are hereby incorporated into the detailed description, with each claim standing on its own as a separately described subject matter.

Claim 1:
A computer-implemented method, comprising:
requesting (<NUM>), by a first client device from a first participant, to initiate a chat with a second client device from a second participant;
receiving (<NUM>), by the first client device from a chat server, an identification for the second participant;
requesting (<NUM>), by the first client device from a verifiable directory, an identity proof of the second participant associated with the identification for the second participant, wherein the verifiable directory includes a list of encryption public-keys for client devices associated with each of multiple users in the chat server;
verifying (<NUM>), by the first client device, the identity proof of the second participant with a public key associated with the second client device; and
initiating (<NUM>), by the first client device, the chat with the second participant when the identity proof of the second participant is verified;
wherein verifying the identity proof comprises matching, in the first client device, an output of a verifiable random function with the public key associated with the second client device as an input, with the identity proof; and
wherein the identity proof is a graphic code and verifying the identity proof comprises scanning the graphic code with the first client device.