Patent Description:
However, as any user that deals with passwords knows, there is an inherent problem with using passwords. Users would like passwords that are easy to remember, but would also like passwords to remain secure. However, passwords that are easy to remember are also often easy to guess and are therefore unsecure. As a corollary, passwords that are difficult to guess are often difficult for users to remember.

Furthermore, modern computing systems can be employed to quickly determine shorter passwords (e.g., <NUM> digits in length) by simple brute force, by working through all of the possible permutations until the password for a resource is found. Another way to try to break a password is to perform password spraying by applying a few commonly used passwords to a large number of accounts. While almost all user accounts will not have used those commonly used passwords, there may be one or a few that do. For those that do, their password has been broken.

Password validation might employ complexity rules to ensure that passwords have a certain minimum level of complexity and are thus difficult to guess. Such might require passwords to be a minimum length, have a certain minimum number of different types of characters, be different than recently used passwords, and so forth. Often, a visually bright green indicator gives the user a visual indication that they have entered a sufficiently complex password. However, these complexity rules may be too simple, leaving it still rather easy to guess what the password is. In another conventional technique, a user may provide a password to a password validation service. The service will then compare the password against a list of bad passwords to see if the password is in that list. If the password is in that list, the password is not permitted, and the user may then alter the password or pick a new password.

<CIT> describes a method, apparatus, and system for evaluating a password. The method for evaluating a password includes the steps of: generating an encryption key and a decryption key for encrypting and decrypting information using a fully homomorphic encryption algorithm; receiving a password that is an evaluation target from a user and encrypting the password using the encryption key; and acquiring strength information of the encrypted password as an evaluation index of security of the encrypted password using the strength evaluation information prepared in advance while maintaining the encrypted state of the password.

At least some embodiments described herein relate to privately determining whether a password satisfies a constraint without having to divulge the password itself to a third party (e.g., a server or service) that evaluates the constraint, and without the third party even being aware of the result of the evaluation. As an example, a password may be validated by a third party as sufficiently secure (e.g., satisfies certain rules, is not a weak password, or is not a breached password) without that third party needing to actually know the password, nor even whether the password satisfies the constraint. Thus, users can keep passwords securely to themselves, while still being able to rely on a third party to validate that the password is safe to use.

After the user selects a password, private communication (e.g., private information retrieval or multi-party computation) is used to determine whether the selected password satisfies password constraints. For instance, the password might be encrypted (e.g., homomorphically), and then the encrypted password and a function definition (e.g., a homomorphic function definition) are then provided to the third party. The third party then performs the function and returns an already encrypted result. The third party generated the encrypted result directly, without having access to the result in the clear. Upon receiving the encrypted result, the user's computing system may then decrypt the result, to find out whether the password satisfies the constraints, and thus is sufficiently safe to use.

After the user selects a password, private information retrieval is used to determine whether the selected password satisfies password constraints. For instance, the password might be encrypted (e.g., homomorphically), and then the encrypted password and a function definition (e.g., a homomorphic function definition) are then provided to the third party. The third party then performs the function and returns an already encrypted result. The third party generated the encrypted result directly, without having access to the result in the clear. Upon receiving the encrypted result, the user's computing system may then decrypt the result, to find out whether the password satisfies the constraints, and thus is sufficiently safe to use.

<FIG> illustrates a network environment <NUM> in which the principles described herein may be practiced. The network environment <NUM> includes a third-party system <NUM> that communicates with user systems <NUM> (including user system <NUM>) over a network <NUM>. The third-party system <NUM> operates to validate whether passwords <NUM> selected by the users <NUM> satisfy one or more constraints without the third-party system <NUM> needing to know the passwords <NUM>, nor needing to know the results of the validation. The third-party system <NUM> might be a server computing system, which might be structured as described below for the computing system <NUM> of <FIG>. However, a server may not use a user interface, such as the user interface <NUM> of <FIG>. Alternatively, or in addition, the third-party system <NUM> might be a service such as a cloud computing service offered in a cloud computing environment. The user systems <NUM> may also each be any computing system, and may also be structured as described below for the computing system <NUM> of <FIG>.

In an example referred to herein as the "subject example", the user system <NUM> has a user 101A that has selected a password 102A, and will use the third-party system <NUM> to determine whether the selected password 102A satisfies a constraint. As an example, the password may be validated to ensure it is sufficiently strong and secure.

For instance, the user 101A might use the third-party system <NUM> to determine whether or not the password 102A satisfies complexity rules (e.g., is of sufficient length, has a minimum number of characters of particular types, and so forth). Alternatively, or in addition, the user 101A might use the third-party system <NUM> to determine whether or not the password 102A is within a list of passwords (such as a list of weak and easily guessable passwords, or a list of breached passwords).

Again, the user 101A uses the third-party system <NUM> to do this without risking providing the password 102A to the third-party system <NUM> in the clear. Furthermore, the third-party system <NUM> itself does not even have a feasible way of determining the result, even though the user system <NUM> can determine the result from information provided by the third-party system <NUM>.

<FIG> illustrates a flowchart of a method <NUM> for privately determining whether a password satisfies one or more constraints, in accordance with the principles described herein. The method <NUM> may be performed by the user system <NUM> of <FIG>, and thus will be described with respect to <FIG>. The user system <NUM> may be structured as described below for the computing system <NUM> of <FIG>. In that case, the method <NUM> may be performed by one or more processors (e.g., the hardware processing unit <NUM>) of the computing system <NUM> executing computer-executable instructions that are on one or more computer-readable media (e.g., memory <NUM>).

The method <NUM> includes an act of accessing a password selected by a user (act <NUM>). As an example, in <FIG>, the user system <NUM> accesses a password 102A selected by the user 101A. Then, the method <NUM> includes a step <NUM> for using private communication to determine whether the selected password satisfies one or more password constraints (step <NUM>). This step <NUM> may also be performed by the user system <NUM> using information obtained from the third-party system <NUM>. This step <NUM> is represented using dashed-lined borders to represent that it is a functional, result-oriented, step that includes corresponding acts that are further described herein.

<FIG> also illustrates a method <NUM> for privately determining whether a password satisfies one or more constraints, in accordance with the principles described herein. The method <NUM> is similar to the method <NUM> of <FIG>. However, in the case of the step of privately communicating (step <NUM>) being private information retrieval, step <NUM> shows further corresponding acts performed by the user system in order to perform the step <NUM> are illustrated within the dashed-lined box. Acts that are performed by the user system (e.g., the user system <NUM> of <FIG> in the subject example) are illustrated in the left column under the header "Client". However, the principles described herein are not limited to the private communication being handle by private information retrieval. For example, the private communication may instead by multi-party computation instead.

In addition, acts performed by the third-party system (e.g., the third-party system <NUM> of <FIG> in the subject example) are also illustrated and are included in the right column under the header "Server". The third-party system <NUM> may also be structured as described below for the computing system <NUM> of <FIG>. In that case, the acts listed in the right column of <FIG> may be performed by one or more processors (e.g., the hardware processing unit <NUM>) of the computing system <NUM> executing computer-executable instructions that are on one or more computer-readable media (e.g., memory <NUM>).

The method <NUM> also includes accessing the selected password (act <NUM>) which is the same as the act of accessing the selected password (act <NUM>) of <FIG>. In the subject example, the user system <NUM> accesses the password 102A that was selected by the user 101A. Remaining acts performed by the user system are performed as part of the step for using private information retrieval to determine whether the selected password satisfies password constraints (step <NUM>), which are illustrated inside the dashed-lined box.

The user system then encrypts the selected password (act <NUM>). In the subject example of <FIG>, the user system <NUM> encrypts the password 102A. In one embodiment, the encryption is homomorphic encryption, which is a form of encryption that allows computation on the encrypted data (in this case the encrypted password) so as to generate an encrypted result which, when decrypted, matches the result of the computation as if the computation had been performed on the original data (in this case, on the original unencrypted password 102A). However, the result might also be computed using private set intersection as well.

<FIG> illustrates an encryption process <NUM> in which an encryption component <NUM> encrypts the password 102A to generate the encrypted password <NUM>. If the user system <NUM> is structured as described below for the computing system <NUM> of <FIG>, the encryption component <NUM> may be as described below for the executable component <NUM> of <FIG>.

The password 102A is represented as a key because it can be seen in the clear. However, encrypted password <NUM> is represented as a blob with rightward diagonal fill lines, representing that encrypted password <NUM> obfuscates the actual password 102A. Accordingly, the third-party system, which will later access the encrypted passwords <NUM> cannot ascertain what the password 102A actually is. Thus, access to the encrypted password <NUM> does not imply access to the password 102A to systems (such as third-party system <NUM>) that do not have the ability to decrypt the password <NUM>.

The user system also defines a function to be performed by the third-party system on the encrypted password (act <NUM>). This function is a homomorphic function in that it conforms with a set of computations that, when performed on the homomorphically encrypted password, provides a result that, when decrypted, matches the result that would happen if the homomorphic function were performed directly on the plain data (e.g., the password 102A in unencrypted form) itself. As an example, the homomorphic function could be a homomorphic verification of complexity rules for the password. As another example, the homomorphic function could be a homomorphic lookup for the password within a list of passwords (e.g., a list of weak passwords, and/or a list of breached passwords).

The encrypting of the password (act <NUM>) and the defining of the function (act <NUM>) are illustrated as occurring one after the other. However, the principles described herein are not limited to that temporal relationship. For example, if the user system <NUM> only looks up whether the password is in a list of passwords, the function may be predetermined (act <NUM>) even well before the user selected the password (act <NUM>). That function might not even change as the user(s) selects one password after another for repeat performances of the method <NUM> to verify whether any number of passwords satisfies the constraints.

On the other hand, the user might verify a number of different constraints on a single password. For example, the user might first verify that a password is not in a list of weak passwords, then verify that a password satisfies complexity rules, and then verify that the password is not in a list of breached passwords. Thus, the method <NUM> after act <NUM> may be repeated multiple times for a single selected password. As an example, the list of weak passwords might be on a different third-party system than the list of breached passwords, causing the encrypted password to be sent (with different functions) to each of multiple third-party systems.

The user system then causes the encrypted password and a function definition of the defined function to be sent to a third-party system for performing the defined function on the encrypted password (act <NUM>). In the subject example of <FIG>, the user system <NUM> sends the encrypted password and the function over the network <NUM> to the third-party system <NUM>. <FIG> illustrates an example message <NUM> that may be sent as part of this act, which message includes the encrypted password <NUM> as well as a function definition <NUM>.

The third-party system receives the encrypted password and function definition (act <NUM>), performs the defined function on the encrypted password (act <NUM>), and sends the result back to the user system (act <NUM>). In the subject example, the third-party system <NUM> receives the message (e.g., message <NUM>) from the user system <NUM>, performs the defined function (specified by the function definition <NUM>) on the encrypted password <NUM>, and sends the result of that operation over the network <NUM> back to the user system <NUM>.

<FIG> illustrates a process <NUM> in which an operation component <NUM> interprets the function definition <NUM>, and performs the defined function on the encrypted password <NUM> to generate a result <NUM>. If the third-party system <NUM> is structured as described below for the computing system <NUM> of <FIG>, the operation component <NUM> may be as described below for the executable component <NUM> of <FIG>. The result <NUM> is again shown as a blob, though a different blob than was used to represent the encrypted password <NUM>. This represents that though an operation was performed, the result of the operation is still not clear without the ability to decrypt the result.

Thus, in the case of applying complexity rules, the third-party system <NUM> does not know the password, nor whether the password actually satisfies the complexity rules. In the case of looking up the password in a list, the third-party system <NUM> does not know the password, nor whether the password is in its list of passwords. Thus, the password remains safe, even from the third-party system, and there is no need to even have to trust the third-party system. For instance, even though the third-party system may have access to a list of passwords in the clear, and the encrypted password is checked against that list, the third-party system still cannot use the list of passwords to somehow guess what the password is.

The user system then receives the result of the operation (act <NUM>). In the subject example, the user system <NUM> receives the result (e.g., result <NUM>) of the defined function (e.g., defined by the function definition <NUM>) performed on the encrypted password (e.g., encrypted password <NUM>).

Now, in the case of homomorphic encryption being performed on the password, and in the case of the function falling within the set of operations that maintain the homomorphic properties, the user system only has to decrypt the result (act <NUM>) in order to determine whether the password satisfies the one or more constraints (act <NUM>). For example, <FIG> illustrates a process <NUM> in which a decryption component <NUM> decrypts the result <NUM> to obtain the plain text result <NUM>. If the user system <NUM> is structured as described below for the computing system <NUM> of <FIG>, the decryption component <NUM> may be as described below for the executable component <NUM> of <FIG>.

The decryption performed by the decryption component <NUM> may likewise follow the same homomorphic encryption scheme that the encryption component <NUM> used to encrypt the password. Thus, the plain text result <NUM> is a result that the defined function would produce if performed directly on the plain text password 102A.

Returning to <FIG>, the ellipsis <NUM> represents that the user systems <NUM> may include any number of user systems that employ the principles described herein (e.g., performing method <NUM> or the left column of method <NUM>) in order to validate passwords selected by their users. Likewise, the ellipsis <NUM> represents that there may be any number of third-party systems that operate within the environment <NUM> to employ the principles described herein. For instance, a third-party system may help validate passwords selected by users of any number of user systems. Furthermore, a single user system may be used by several third-party systems to validate whether a selected password satisfies constraints. The ellipsis 102B represents that a single user may validate any number of passwords using the principles described herein. The ellipsis 101B represents that a single user system may have any number of users that select passwords subject to the principles described herein, and that any number of user systems with any number of users may select passwords subject to the principles described.

Thus, the principles described herein allow a user to use a third-party system to check whether a password satisfies constraints without needing to disclose the password itself to the third-party system, and without the third-party system ever finding out whether the password satisfies the constraint. Accordingly, the principles described herein provide a secure way to perform validation of a selected password thereby allowing for stronger passwords to be chosen, thereby improving the security of resources that are guarded by those passwords.

In one embodiment, the result <NUM> is just a simple Boolean value representing whether or not the password satisfies the one or more constraints (e.g., whether or not the password is in the list of passwords and/or whether or not the password satisfies complexity rules). However, in order to improve latency, and network usage, and simplify the defined function, the result <NUM> might instead include an intermediate result that requires further processing by the user system prior to the final determination. As an example, the intermediate result might include a smaller list of passwords that the user system must check through to verify whether the password is in that smaller list. If the password is in that smaller list within the result, that means that the password was in the larger list maintained at the third-party system. Likewise, if the password is not in the smaller list, this means that the password was not in the larger list maintained at the third-party system. This option might perhaps be better employed when the smaller list includes only a list of weak passwords that are easy to guess, as opposed to a list of breached passwords that are sensitive to divulge to anyone.

In order to reduce latency in responding to request to validate a password, there may be some pre-processing that is performed between the third-party system and the user system. For instance, the third-party system and the user system may agree on communication patterns (such as network ports, maximum message size, whether messages are to be confirmed as received, and so forth) that are related to the basic processes of communication. In addition, the third-party system and the user system may agree on other matters that help the user system construct a function, such as how many passwords are within a list of passwords, what the library of available homomorphic operations is, and so forth.

Note that the performance of the methods <NUM> and <NUM> may be performed by a computing system. Accordingly, a computing system will now be described with respect to <FIG>. Computing systems may, for example, be handheld devices, appliances, laptop computers, desktop computers, mainframes, distributed computing systems, datacenters, or even devices that have not conventionally been considered a computing system, such as wearables (e.g., glasses, watches, bands, and so forth). In this description and in the claims, the term "computing system" is defined broadly as including any device or system (or combination thereof) that includes at least one physical and tangible processor, and a physical and tangible memory capable of having thereon computer-executable instructions that may be executed by a processor.

As illustrated in <FIG>, in its most basic configuration, a computing system <NUM> typically includes at least one hardware processing unit <NUM> and memory <NUM>. The memory <NUM> may be physical system memory, which may be volatile, non-volatile, or some combination of the two. The term "memory" may also be used herein to refer to non-volatile mass storage such as physical storage media. If the computing system is distributed, the processing, memory and/or storage capability may be distributed as well.

The computing system <NUM> has thereon multiple structures often referred to as an "executable component". For instance, the memory <NUM> of the computing system <NUM> is illustrated as including executable component <NUM>. The term "executable component" is the name for a structure that is well understood to one of ordinary skill in the art in the field of computing as being a structure that can be software, hardware, or a combination thereof. For instance, when implemented in software, one of ordinary skill in the art would understand that the structure of an executable component may include software objects, routines, methods that may be executed on the computing system, whether such an executable component exists in the heap of a computing system, or whether the executable component exists on computer-readable storage media.

In such a case, one of ordinary skill in the art will recognize that the structure of the executable component exists on a computer-readable medium such that, when interpreted by one or more processors of a computing system (e.g., by a processor thread), the computing system is caused to perform a function. Such structure may be computer-readable directly by the processors (as is the case if the executable component were binary). Alternatively, the structure may be structured to be interpretable and/or compiled (whether in a single stage or in multiple stages) so as to generate such binary that is directly interpretable by the processors. Such an understanding of example structures of an executable component is well within the understanding of one of ordinary skill in the art of computing when using the term "executable component".

The term "executable component" is also well understood by one of ordinary skill as including structures that are implemented exclusively or near-exclusively in hardware, such as within a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), or any other specialized circuit. In this description, the term "component" or "vertex" may also be used. As used in this description and in the case, this term (regardless of whether the term is modified with one or more modifiers) is also intended to be synonymous with the term "executable component" or be specific types of such an "executable component", and thus also have a structure that is well understood by those of ordinary skill in the art of computing.

While not all computing systems require a user interface, in some embodiments, the computing system <NUM> includes a user interface <NUM> for use in interfacing with a user. The user interface <NUM> may include output mechanisms 812A as well as input mechanisms 812B. The principles described herein are not limited to the precise output mechanisms 812A or input mechanisms 812B as such will depend on the nature of the device. However, output mechanisms 812A might include, for instance, speakers, displays, tactile output, holograms, virtual reality, and so forth. Examples of input mechanisms 812B might include, for instance, microphones, touchscreens, holograms, virtual reality, cameras, keyboards, mouse or other pointer input, sensors of any type, and so forth.

Embodiments described herein may comprise or utilize a special purpose or general-purpose computing system including computer hardware, such as, for example, one or more processors and system memory, as discussed in greater detail below. Such computer-readable media can be any available media that can be accessed by a general purpose or special purpose computing system. Thus, by way of example, and not limitation, embodiments can comprise at least two distinctly different kinds of computer-readable media: storage media and transmission media.

Computer-readable storage media include RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other physical and tangible storage medium which can be used to store desired program code means in the form of computer-executable instructions or data structures and which can be accessed by a general purpose or special purpose computing system.

A "network" is defined as one or more data links that enable the transport of electronic data between computing systems and/or components and/or other electronic devices. Transmissions media can include a network and/or data links which can be used to carry desired program code means in the form of computer-executable instructions or data structures and which can be accessed by a general purpose or special purpose computing system.

For example, computer-executable instructions or data structures received over a network or data link can be buffered in RAM within a network interface component (e.g., a "NIC"), and then eventually transferred to computing system RAM and/or to less volatile storage media at a computing system. Thus, it should be understood that readable media can be included in computing system components that also (or even primarily) utilize transmission media.

Computer-executable instructions comprise, for example, instructions and data which, when executed at a processor, cause a general-purpose computing system, special purpose computing system, or special purpose processing device to perform a certain function or group of functions.

Those skilled in the art will appreciate that the invention may be practiced in network computing environments with many types of computing system configurations, including, personal computers, desktop computers, laptop computers, message processors, hand-held devices, multi-processor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, mobile telephones, PDAs, pagers, routers, switches, datacenters, wearables (such as glasses or watches) and the like. The invention may also be practiced in distributed system environments where local and remote computing systems, which are linked (either by hardwired data links, wireless data links, or by a combination of hardwired and wireless data links) through a network, both perform tasks. In a distributed system environment, program components may be located in both local and remote memory storage devices.

Those skilled in the art will also appreciate that the invention may be practiced in a cloud computing environment, which is supported by one or more datacenters or portions thereof.

For instance, cloud computing is currently employed in the marketplace so as to offer ubiquitous and convenient on-demand access to the shared pool of configurable computing resources. Furthermore, the shared pool of configurable computing resources can be rapidly provisioned via virtualization and released with low management effort or service provider interaction, and then scaled accordingly.

A cloud computing model can be composed of various characteristics such as on-demand, self-service, broad network access, resource pooling, rapid elasticity, measured service, and so forth. A cloud computing model may also come in the form of various application service models such as, for example, Software as a service ("SaaS"), Platform as a service ("PaaS"), and Infrastructure as a service ("IaaS"). The cloud computing model may also be deployed using different deployment models such as private cloud, community cloud, public cloud, hybrid cloud, and so forth. In this description and in the claims, a "cloud computing environment" is an environment in which cloud computing is employed.

Claim 1:
A method (<NUM>, <NUM>) for privately determining whether a password (102A) satisfies one or more constraints, the method comprising:
accessing (<NUM>, <NUM>) a password (102A) selected by a user (101A);
encrypting (<NUM>, <NUM>) the selected password wherein encrypting the selected password comprises homomorphically encrypting the selected password;
defining (<NUM>) a function to be performed by a server on the encrypted password (<NUM>), wherein the function is a homomorphic function that, when performed on the encrypted password (<NUM>), provides a result that, when decrypted, matches a result that would happen if the homomorphic function were performed directly on the unencrypted selected password;
causing (<NUM>) the encrypted password (<NUM>) and a function definition (<NUM>) of the function to be sent to the server for performing the defined function on the encrypted password;
detecting (<NUM>) receipt of an encrypted result (<NUM>) of the function on the encrypted password;
decrypting (<NUM>, <NUM>) the received encrypted result received from the server; and
determining (<NUM>) from the decrypted result (<NUM>) whether the password satisfies a constraint.