FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
COMPLETE SPECIFICATION (See Section 10 and Rule 13)
Title of the invention:
METHOD AND SYSTEM FOR PRESERVING PRIVACY OF PASSWORD WHILE CHECKING PASSWORD STRENGTH
Applicant
Tata Consultancy Services Limited A company Incorporated in India under the Companies Act, 1956
Having address:
Nirmal Building, 9th floor,
Nariman Point, Mumbai 400021,
Maharashtra, India
Preamble to the description
The following specification particularly describes the invention and the manner in which it is to be performed.

TECHNICAL FIELD
[001] The embodiments herein generally relate to the field of password strength meters. More particularly, but not specifically, the present disclosure provides a method and system for preserving privacy of a password while checking password strength using a password strength meter.
BACKGROUND
[002] Passwords are most widely used means of authentication. Different services provide various ways of authentication, passwords being the most common one. Since users have to use so many passwords on a daily basis, they tend to keep easier passwords with minor changes across different accounts so that they can remember them easily. However, keeping passwords with meaningful words or words such as names etc. can make it easy for an attacker to get access to or crack the password and steal user’s identity. Hence users have to make sure the passwords they create are strong so that the passwords are not susceptible to stealing by attackers.
[003] A password strength meter is useful for users to assess the strength of the passwords they create before they go on to use it for authentication. A password strength meter gives a score for the input password given by the users which indicates the probability of the password being cracked by the attacker. A password strength meter service is provided by servers online (or can be done by an individual as well), which have a database of passwords which are either known to be weak or passwords which have been leaked in some password database breach. Using this database of passwords, a server can come up with a model for identifying or measuring strength of other passwords. However, as these passwords are sensitive for users, they are private to users and should not be revealed to even the password strength meters. One leaked password might give away the pattern which users use to create many other passwords. Hence, a password strength meter has to be queried in privacy preserving manner to make sure server doesn’t learn

anything about user’s password.
[004] There are several methods to ensure privacy of the query namely k-anonymity, differential privacy, other forms of private information retrieval (PIR). Few of the methods use fully homomorphic encryption (FHE) based password strength meters which are provably secure. FHE enables computations on encrypted data wherein the encrypted passwords can be sent to the password strength meter in a privacy preserving manner. There are several password strength meters in the prior art based on Markov model, Context free grammar (CFG) and machine learning. However, in FHE domain, privacy preserving search is an expensive operation in terms of time and memory.
SUMMARY
[005] The following presents a simplified summary of some embodiments of the disclosure to provide a basic understanding of the embodiments. This summary is not an extensive overview of the embodiments. It is not intended to identify key/critical elements of the embodiments or to delineate the scope of the embodiments. It’s sole purpose is to present some embodiments in a simplified form as a prelude to the more detailed description that is presented below.
[006] In view of the foregoing, an embodiment herein provides a system for preserving privacy of a password while checking password strength using a password strength meter has been provided. The system comprises an input/output interface, one or more hardware processors and a memory. The input/ output interface configured to provide the password to a client for checking the strength, wherein the password having a password string. The memory in communication with the one or more hardware processors, wherein the one or more first hardware processors are configured to execute programmed instructions stored in the memory, to: extract one or more n-grams from the password string, wherein n is a number of characters in one or more substrings present in the password string; encrypt the extracted one or more n-grams using a fully homomorphic encryption (FHE) technique; send the encrypted one or more n-grams to the password strength

meter present on a server, wherein the password strength meter is using a Markov model based technique; search each n-gram from amongst the one or more n-grams in their respective information score tables to get an information score if n is less than or equal to 2, wherein the information score tables are made for each of the n-grams, the information score tables comprise of n-grams and their guessing information scores; split n-grams into 3-grams if n is more than 2, wherein the splitting is done based on a structure of the n-gram, and the division results in generation of derived tables having n-grams and their guessing information scores; search n-grams in the derived tables to get the information scores if n is more than 2; adding information scores of n-grams obtained/ searched from the information score tables and the derived tables to get a final score; send the final score to the client; and decrypt the final score using a FHE private key to get a final information score, wherein the final information score is indicative of the strength of the password.
[007] In another aspect, the embodiment herein also provides the system comprising using a probabilistic context free grammar (PCFG) technique for measuring strength of password, wherein the PCFG technique comprises: providing the password to the client for checking the strength; extracting the structure of the password string; encrypting variables present in the password string; sending the encrypted variables and the structure of the password string to the password strength meter; creating a set of variable tables corresponding to the variables present in the password string; creating a set of intermediate 1-gram, 2-gram and 3-grams tables for each variable table of the set of the variable tables; searching one or more variable information scores in corresponding intermediate 1-gram, 2-gram and 3-grams tables derived from variable tables; retrieving a plurality of structure information scores in a structure lookup table; and adding the structure information scores and the one or more variable information scores to get the final information score of the password strings, wherein the final information score is indicative of the strength of the password.
[008] In another aspect, the embodiment here provides a method for preserving privacy of a password while checking password strength using a

password strength meter has been provided. Initially, the password is provided to a client for checking the strength, wherein the password having a password string. Further, one or more n-grams are extracted from the password string, wherein n is a number of characters in one or more substrings present in the password string. The extracted one or more n-grams are then encrypted using a fully homomorphic encryption (FHE) technique. Further, the encrypted one or more n-grams are sent to the password strength meter present on a server, wherein the password strength meter is using a Markov model based technique. In the next step, each n-gram is searched from amongst the one or more n-grams in their respective information score tables to get an information score if n is less than or equal to 2, wherein the information score tables are made for each of the n-grams, the information score tables comprise of n-grams and their guessing information scores. Further, n-grams is split into 3-grams if n is more than 2, wherein the splitting is done based on a structure of the n-gram, and the division results in generation of derived tables having n-grams and their guessing information scores. In the next step, n-grams are searched in the derived tables to get the information scores if n is more than 2. The information scores of n-grams searched from the information score tables and the derived tables are then added to get a final score. The final score is then sent to the client. And finally, the final score is decrypted using a FHE private key to get a final information score, wherein the final information score is indicative of the strength of the password.
[009] In another embodiment, the method further comprising using a prob-abilistic context free grammar (PCFG) technique for measuring password strength. Initially, the password is provided to the client for checking the strength. The struc-ture of the password string is then extracted. Further, variables present in the pass-word string are extracted. In the next step, the encrypted variables and the structure of the password string are sent to the password strength meter. Further, a set of variable tables are created corresponding to the variables present in the password string. A set of intermediate 1-gram, 2-gram and 3-grams tables are also created for each variable table of the set of the variable tables. In the next step, one or more variable information scores are searched in corresponding intermediate 1-gram, 2-

gram and 3-grams tables derived from variable tables. Further a plurality of struc¬ture information scores are retrieved in a structure lookup table. And finally, the structure information scores and the one or more variable probabilities are added to get the final information score of the password strings, wherein the final infor¬mation score is indicative of the strength of the password.
[010] In yet another aspect, one or more non-transitory machine readable information storage mediums comprising one or more instructions which when executed by one or more hardware processors causes preserving privacy of a password while checking password strength using a password strength meter has been provided. Initially, the password is provided to a client for checking the strength, wherein the password having a password string. Further, one or more n-grams are extracted from the password string, wherein n is the number of characters in substrings present in the password string. The extracted one or more n-grams are then encrypted using a fully homomorphic encryption (FHE) technique. Further, the encrypted one or more n-grams are sent to the password strength meter present on a server, wherein the password strength meter is using a Markov model based technique. In the next step, each n-grams is searched out of the one or more of n-grams in their respective information score tables to get an information score if n is less than or equal to 2, wherein the information score tables are made for each of the n-grams, the information score tables comprise of n-grams and their guessing information scores. Further, n-grams is split into 3-grams if n is more than 2, wherein the splitting is done based on a structure of the n-gram, and the division results in generation of derived tables having n-grams and their guessing information scores. In the next step, n-grams are searched in the derived tables to get the information scores for n is more than 2. The information scores of n-grams obtained/searched from the information score tables and the derived tables are then added to get a final score. The final score is then sent to the client. And finally, the final score is decrypted using a FHE private key to get a final information score, wherein the final information score is indicative of the strength of the password.

[011] It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.
BRIEF DESCRIPTION OF THE DRAWINGS
[012] The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together with the description, serve to explain the disclosed principles.
[013] FIG. 1 shows a block diagram of a system for preserving privacy of a password while checking password strength using a password strength meter according to an embodiment of the present disclosure.
[014] FIG. 2 shows a flowchart of a method for preserving privacy of a password while checking password strength using a password strength meter utilizing Markov model based technique according to an embodiment of the present disclosure.
[015] FIG. 3 shows a flowchart of a method for preserving privacy of a password while checking password strength using a password strength meter utilizing PCFG based technique according to some embodiments of the present disclosure.
[016] FIG. 4 shows a schematic diagram illustrating an example of n-gram based Markov model based password strength meters according to some embodiments of the present disclosure.
[017] FIG. 5 shows a schematic diagram illustrating an example of PCFG model based password strength meters according to some embodiments of the present disclosure.
[018] FIG. 6 shows the behaviour of client and server in the optimized Markov model along with an example according to some embodiments of the present disclosure.
[019] FIG. 7 shows behaviour of the client and server in the optimized PCFG model along with an example according to some embodiments of the present disclosure.

DETAILED DESCRIPTION
[020] Exemplary embodiments are described regarding the accompanying drawings. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. Wherever convenient, the same reference numbers are used throughout the drawings to refer to the same or like parts. While examples and features of disclosed principles are described herein, modifications, adaptations, and other implementations are possible without departing from the spirit and scope of the disclosed embodiments.
[021] There are certain password strength meters are available in the prior art which use guessing models to analyze strengths of passwords i.e., greater the guessing probability, lesser the strength of a password. Websites or applications can provide these password strengths analyzing services or simply password strength meters as a service to the users to query strength of their passwords. Websites can use these password strength analyzing techniques to devise password creation strategies that can enforce better password choices by the users.
[022] However, one concern with the password strength meter services is that they need access to the passwords to analyze the strength. When a password strength meter or a server on which it is hosted is malicious, there is a high risk of privacy as the service knows what password the user is querying. And these passwords can sometimes involve personal information of the users that can be exploited by malicious adversaries. Therefore, it is important to ensure privacy for these queries. Privacy preserving password strength meters that can compute password strength while preserving privacy of the users are essential.
[023] Most widely studied password strength meters in the prior art are based on Markov Model and probabilistic context free grammar (PCFG) model. These probabilistic models compute the password strengths efficiently with remarkable accuracy. Markov model computes password strength based on substring probabilities that constitute a password. PCFG models are based on probabilistic grammar which consists of set of rules that compose structures and variables and predicts password strength based on their probabilities. FHE enables

computations on encrypted data wherein the encrypted passwords can be sent to the password strength meter in a privacy preserving manner. However, a major limitation of FHE is inefficiency to search over large datasets.
[024] Referring now to the drawings, and more particularly to FIG. 1 through FIG. 7, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments and these embodiments are described in the context of the following exemplary system and/or method.
[025] According to an embodiment of the disclosure, a system 100 for preserving privacy of a password while checking password strength using a password strength meter is shown in a block diagram of FIG. 1. The system 100 is configured to provide a privacy preserving password strength meters utilizing Markov model and a probabilistic context free grammar (PCFG) model using fully homomorphic encryption (FHE) technique for efficient password strength analysis. The FHE technique enables computations on encrypted data, which is an important capability in this context to perform strength analysis on an encrypted password.
[026] The privacy preserving password strength meters enable users to securely evaluate strength of their passwords. The aim is to provide end-to-end query privacy for the users by leveraging FHE based password strength meter that requires users to send encrypted password to the server for strength analysis and obtain encrypted password strength scores back. The FHE based protocol is built on top of existing n-grams based Markov models and PCFG models with some modification to improve efficiency. The operation of the protocol is search over a dictionary of key-value pairs (a sub-string and corresponding guessing information score). Search space optimization have been utilized to increase the efficiency of password strength analysis. Further, an empirical analysis have also been provided of how this optimization introduce trade-offs in terms of security and provide an alternative mechanism of including honey passwords to mitigate this. Furthermore, a privacy preserving index search approach is also provided that significantly improves the search functionality.

[027] It may be understood that the system 100 comprises one or more computing devices 102, such as a laptop computer, a desktop computer, a notebook, a workstation, a cloud-based computing environment and the like. It will be under¬stood that the system 100 may be accessed through one or more input/output inter¬faces 104, collectively referred to as I/O interface 104 or user interface 104. Exam¬ples of the I/O interface 104 may include, but are not limited to, a user interface, a portable computer, a personal digital assistant, a handheld device, a smartphone, a tablet computer, a workstation and the like. The I/O interface 104 are communica¬tively coupled to the system 100 through a network 106.
[028] In an embodiment, the network 106 may be a wireless or a wired network, or a combination thereof. In an example, the network 106 can be imple-mented as a computer network, as one of the different types of networks, such as virtual private network (VPN), intranet, local area network (LAN), wide area net-work (WAN), the internet, and such. The network 106 may either be a dedicated network or a shared network, which represents an association of the different types of networks that use a variety of protocols, for example, Hypertext Transfer Proto-col (HTTP), Transmission Control Protocol/Internet Protocol (TCP/IP), and Wire-less Application Protocol (WAP), to communicate with each other. Further, the net-work 106 may include a variety of network devices, including routers, bridges, serv-ers, computing devices, storage devices. The network devices within the network 106 may interact with the system 100 through communication links.
[029] The system 100 may be implemented in a workstation, a mainframe computer, a server, and a network server. In an embodiment, the computing device 102 further comprises one or more hardware processors 108, one or more memory 110, hereinafter referred as a memory 110 and a data repository 112, for example, a repository 112. The memory 110 is in communication with the one or more hard¬ware processors 108, wherein the one or more hardware processors 108 are config¬ured to execute programmed instructions stored in the memory 110, to perform var¬ious functions as explained in the later part of the disclosure. The repository 112 may store data processed, received, and generated by the system 100.

[030] The system 100 supports various connectivity options such as BLUETOOTH®, USB, ZigBee and other cellular services. The network environ-ment enables connection of various components of the system 100 using any com-munication link including Internet, WAN, MAN, and so on. In an exemplary em-bodiment, the system 100 is implemented to operate as a stand-alone device. In another embodiment, the system 100 may be implemented to work as a loosely coupled device to a smart computing environment. The components and function-alities of the system 100 are described further in detail.
[031] In operation, a flow diagram of a method 200 for preserving privacy of a password while checking password strength using a password strength meter according to some embodiments of the present disclosure is shown in FIG. 2. The method 200 depicted in the flow chart may be executed by a system, for example, the system, 100 of FIG. 1. In an example embodiment, the system 100 may be em-bodied in a computing device.
[032] Operations of the flowchart, and combinations of operation in the flowchart, may be implemented by various means, such as hardware, firmware, processor, circuitry and/or other device associated with execution of software in-cluding one or more computer program instructions. For example, one or more of the procedures described in various embodiments may be embodied by computer program instructions. In an example embodiment, the computer program instruc-tions, which embody the procedures, described in various embodiments may be stored by at least one memory device of a system and executed by at least one pro¬cessor in the system. Any such computer program instructions may be loaded onto a computer or other programmable system (for example, hardware) to produce a machine, such that the resulting computer or other programmable system embody means for implementing the operations specified in the flowchart. It will be noted herein that the operations of the method 200 are described with help of system 100. However, the operations of the method 200 can be described and/or practiced by using any other system.
[033] Initially at step 202, the password is provided to a client for checking the strength via the input/output interface 104 or user interface 104, wherein the

password having a password string. The user interface 104 is accessible to the user via smartphones, laptop or desktop configuration thus giving the user the freedom to interact with the system 100 from anywhere anytime. The user interface 104 may include a variety of software and hardware interfaces, for example, interfaces for peripheral device(s), such as a keyboard, a mouse, an external memory, a camera device, and a printer. The user interface 104 can facilitate multiple communications within a wide variety of networks and protocol types, including wired networks, for example, local area network (LAN), cable, etc., and wireless networks, such as Wireless LAN (WLAN), cellular, or satellite.
[034] Further at step 204, one or more n-grams are extracted from the password string, wherein n is the number of characters in substrings present in the password string.
[035] At step 206, the extracted one or more n-grams are encrypted using a fully homomorphic encryption (FHE) technique. The FHE technique is explained as follows: FHE enables computations on encrypted data without the need for decryption. For a set of ciphertexts corresponding to a set of plaintexts, using FHE, one can evaluate an arbitrary function on these ciphertexts without revealing the plaintexts. FHE supports addition and multiplication as primitive operations:
Enc (a + b) = Enc (a) + Enc (b)
Enc (a * b) = Enc (a) * Enc (b)
[036] These primitive operations can be used to realize arbitrary functions in FHE. Formally, Given a set of ciphertexts C1, . . .Cn for plaintext messages m1 . . .mn respectively encrypted with a key, one can evaluate an arbitrary function say f(m1 . . .mn) without compromising privacy of plaintext messages. A public key FHE scheme ξ can be described as follows:
: (KeyGenξ, Encξ, Decξ, Evalξ) where KeyGenξ, Encξ, Decξ denote the key generation, encryption and decryption functions of ξ respectively and are identical to that of the usual public key encryption schemes. Evalξ is the evaluation algorithm used for computations on encrypted data.
[037] This algorithm takes as input a polynomial expression P and a set of

ciphertexts c = {C0, C1,….., Cn}which are needed to compute �. The input output of Evalξ satisfies following equation:
Dec(Evalξ(P, c, pk), sk) = P(Decξ(c, sk))
[038] In the above expression pk denotes public key and sk denotes private key. To improve the efficiency of homomorphic operations, one can leverage homomorphic batching technique. In batching, plaintext messages m1,m2,… ….,mn are batched into a single ciphertext. On this batched ciphertext, operations can be performed on component wise m’s and can be executed in parallel. Packing significantly improves performance and reduces space complexity.
[039] FHE schemes are predominantly built on hardness of lattice, learning with error (LWE) or ring learning with error (RLWE) assumptions. Based on these hard problems, some of the commonly used FHE schemes are Brakerski-Gentry-Vaikuntanathan (BGV), Brakerski/Fan-Vercauteren (BFV), Cheon-Kim-Kim-Song (CKKS), Fan-Vercauteren (FV). Open source implementations were built on these FHE schemes, where most prominent ones include Homomorphic Encryption library (HElib), SEAL open source homomorphic encryption library, HEAAN open source homomorphic encryption library, PALISADE open-source cross platform software library, TFHE and nGraph-HE. CKKS was chosen scheme out of these schemes as it has support for floating point arithmetic. The libraries HElib, SEAL and HEAAN support CKKS scheme, however, we choose HEAAN because it supports for floating point arithmetic over encrypted packed ciphertexts which is important for privacy preserving indexing.
[040] Further at step 208, the encrypted one or more n-grams are sent to the password strength meter present on a server 114, wherein the password strength meter is using a Markov model based technique. For any string, the password of a particular character depends on the previous characters in that string. The Markov Model based technique utilizes these conditional probability to compute the guessing probability of the whole string. This probability can be interpreted as the probability with which an attacker can guess the password and ca be used as a metric to measure the password strength.

[041] Given a string represented as a sequence of characters s1 . . . sm, the guessing probability of the string is given by:

Information scores were computed from probabilities to score strength of a password as
H = - log (P)
[042] In FHE, multiplication of ciphertexts is expensive and complexity of a computation is determined by the multiplicative depth of the computation. Hence, reducing the multiplicative depth makes the computation efficient. Using probabilities for scoring will increase multiplication depth since all probabilities have to be multiplied to get the final score of the password. However, using information scores is efficient since it requires adding (instead of multiplication) all the information scores for n-grams or variables to compute overall score of a password. Moreover, the probabilities can be very small values and can incur additional scaling overheads for processing in FHE. Also, floating-point arithmetic in FHE can only serve efficiently up to a certain precision. Beyond a threshold, error increases significantly resulting in inaccurate guessing probabilities for passwords. Hence, information score is a more appropriate metric for password strength analysis in encrypted domain.
[043] A client server model was assumed in which client delegates a password strength computation to a server. This computation is evaluated by series of lookups and additions from the score tables pre-computed and stored on the server. For any given string x, the scores of the corresponding sub-strings (n-gram, a sub-string of length n) are fetched and added to result in the guessing score of the password x. The server stores n-grams tables as a key value pairs of n-grams and corresponding scores. An n-gram based Markov model is built where each n-gram has an associated score, which is generated based on the frequency of that n-gram in the passwords from the breached dataset. For instance, for n=1 the password string is simply divided into characters. For n=2, password string is divided into every combination of contiguous pair of characters, and so on. The server generates

n-grams for each of the entry, up to some suitable value of n. We store these n-grams and their associated scores in a look up table. When user sends a password for calculating the strength, the password string is first divided into n-grams. Each n-gram is then searched in the respective table and their corresponding scores are added to get the final score which is indicative of the strength of the password provided by the user.
[044] Further at step 210 of flowchart 200, each n-grams out of the one or more of n-grams is searched in their respective information score tables to get an information score if n is less than or equal to 2, wherein the information score tables are made for each of the n-grams, the information score tables comprise of n-grams and their guessing information score. The n-gram based Markov model was built where n-gram has an associated information score, which is generated based on the frequency of that n-gram in the passwords. At step 212 of flowchart 200, n-grams were split into 3-grams if n is more than 2, the division results in generation of derived tables having n-grams and their guessing information score. At step 214 of flowchart 200, the n-grams are then searched in the derived tables to get the infor-mation score for n is more than 2. Further at step 216, the information score of n-grams obtained/searched from the information score tables and the derived tables are added to get a final score.
[045] For example, for n=1 the password string is simply divided into characters. For n=2, password string is divided into every contiguous pair of characters, and so on. The server generates n-grams for each of the entry, up to some suitable value of n. These n-grams and their associated information scores are stored in a look up table. When user sends a password for calculating the strength, the password string is first divided into n-grams. Each n-gram is then searched in the respective table, for instance 1-grams will be searched in the table containing all the 1-grams, and their corresponding information score values are added to get the final score which is indicative of the strength of the password provided by the user. Note that a database of breached passwords is used to build this model. FIG. 4 shows a schematic diagram illustrating an example of n-gram based Markov model based password strength meters according to some embodiment of the

present disclosure.
[046] Further at step 218, the final score is sent to the client. And finally at step 220, the final score is decrypted using a FHE private key to get a final information score, wherein the final information score is indicative of the strength of the password.
[047] According to an embodiment of the disclosure, the system 100 can also use a probabilistic context free grammar (PCFG) technique for measuring password strength. A method 300 utilizing the PCFG technique is shown in flowchart of FIG. 3. Initially, at step 302 the password is provided to the client for checking the strength. At step 304, the structure of the password string is extracted. Further at step 306, variables present in the password string are extracted. At step 308, the encrypted variables and the plain structure of the password string is sent to the password strength meter. At step 310, a set of variable tables is created corresponding to the variables present in the password string. At step 312, a set of intermediate 1-gram, 2-gram and 3-grams tables are also created for each variable table of the set of the variable tables.
[048] At step 314, one or more variable information scores are searched in corresponding intermediate 1-gram, 2-gram and 3-grams tables derived from variable tables. Further at step 316, the structure information scores are retrieved in a structure lookup table. And finally at step 318, the structure information score and the one or more variable information scores are added to get the final information score of the password strings, wherein the final information score is indicative of the strength of the password. In an example, the strength of the password can be categorized as one of a very weak password, a weak password, a medium passwords, a strong password or a very strong password.
[049] The PCFG technique is probability context free grammar which contains set of terminals, non-terminals, start symbols, rules and corresponding probabilities. Terminals are the indivisible parts of the grammar and are the building blocks. A non-terminal can be defined as a combination of non-terminals and terminals. Start symbols represent the initial state of a grammar. Rules have two components separated by an arrow. The LHS of the rule can be a start symbol or a

non-terminal. RHS is combination of non-terminals and terminals. Each rule is associated with a count which indicates number of times the rule has appeared in a given dataset. Rules are categorized based on LHS, meaning rules which have same LHS are in one bucket. Probability of the rule is its count divided by the total count of the bucket in which it appears
[050] During training, when a password appears it is first converted to a structure which contains meta-information about the password like how many characters are there, how many digits/special characters are there and in what order. The non-terminals are used to represent the type like character/ digit/special character followed by a number which indicates count. For example, password is “password123”, here structure will be L8D3. L8 is a non-terminal indicating lowercase alphabets followed by its count, i.e., 8. Next non-terminal is D3 which represents digits followed by its count which is 3. This structure of the password is now assigned to a start symbol as “S- > L8D3” and this is added as rule to the grammar with count as 1. Then a new rule is added to grammar to define the non-terminal L8 as “L8- > password” and a rule for non-terminal D3 as “D3- > 123” with count as 1 for both. Now server processes the passwords in similar way and if the structure is already there in the grammar then the count is simply incremented, otherwise a new rule is added in the grammar. Once the server is completed with all the entries in the database, the rules with the same LHS are bucketed as one table. The probability for each entry in the table is calculated as its respective count divided by total of counts of all the entries in the table. Thus, server obtains the final grammar which acts as a model for calculating strength of the password. When the user wants to query a password for its strength, the structure is first identified for the given password. Now for start symbol and each non-terminal the corresponding probability values are required to compute the strength. FIG. 5 shows a schematic diagram illustrating an example of PCFG model based password strength meters according to some embodiment of the present disclosure.
[051] According to an embodiment of the disclosure, the system 100 can also be configured to use the probabilities along with the PCFG technique or the Markov model based technique instead of information scores to compute the

strength of the password. However the use of information score is more efficient in the FHE domain as compared to the probabilities.
[052] According to an embodiment of the disclosure, the system 100 is configured to provide privacy preserving search as explained below. The privacy preserving search function can be denoted by PPSearch (φ, Enc(σ)): Privacy preserving search function exhaustively searches for a given encrypted string Enc(σ) in unencrypted look up table φ and outputs corresponding encrypted information score Enc(pσ). Here, Dec(pσ) is either 0 or 1. Each entry x in look up table φ, is encoded as a bit string {x1 . . . xi} where l is the number of bits used to encode an entry. The input Enc(σ) is encoded as an encrypted bit string {Enc(y1) . . . Enc(yi)}. The privacy preserving can formalize search function as follows: For each entry x in table φ, when compared with encoded encrypted bit string {Enc(y1) . . . Enc(yi)}, the comparison output is:

The encrypted information score of matched entry can be given by:

As iterate exhaustively is needed through the entire table, the complexity of privacy preserving search is worst case, O(n), where n is size of the list.
[053] According to an embodiment of the disclosure, privacy preserving index search has also been introduced. The privacy preserving index search retrieves value at index i in the table of key-value pairs φ (string, information score), without actually comparing the target key with keys in the table. The order of keys in the table is assumed to be public (or shared to the client) and values are private to the server. On client side, for alphabet of size Σ, all possible combination strings of length Σ! are generated. A value corresponding to each element of the vector is set to either 0 or 1 (1 in the index that has the target key to be searched, 0 otherwise). This vector is then encrypted into a batched ciphertext and send it to the server. On server side, this batched ciphertext is multiplied with probabilities vector

in the table. The resultant vector will have the required probability at the target position and the other position will have encryptions of zero. The target probability can be retrieved by rotating the packed ciphertext. Consider n-grams and their corresponding information scores in the table below for alphabet ∑ = {�, �, �}:

abc acb bca bac cab cba Enc (p1)

Enc (p2)

Enc (p3)

Enc (p4)

Enc (p5)

Enc (p6)
To retrieve probability of n-gram acb, a packed ciphertext is formed as follows:
Enc(0) Enc(1) Enc(0) Enc(0) Enc(0) Enc(0)
This packed ciphertext is multiplied with the packed score ciphertext to obtain:

Enc(p2) can be fetched into first slot of the packed ciphertext by performing rotations.
[054] According to an embodiment of the disclosure, the client delegates a password strength computation to the server to determine strength of the password in encrypted form. The computation takes as input an encrypted password and outputs resultant password information score. On server side, the n-gram tables {Øi, pi} where i∈N with Øi representing exhaustive set of all n-grams and �� representing of corresponding scores stored in plaintext format.
[055] Note that for n-gram tables n > 3, were sub-divided into 3gram tables

based on the structure of n-gram to get a set of independent tables {Øit ....Øm} where m represents number of unique 3-gram structures in a table. This reduces the search space there by improving algorithm efficiency. Though the n-grams of the password that are sent to the server are encrypted, the corresponding structures are sent in plain to enable the server to search in the corresponding structure tables.
[056] Considering the case of n = 3, the Markov model will have three tables namely 1-grams, 2-grams and 3-grams, where in each table will have the n-grams along with scores associated with them. The query for 1-grams and 2-grams are manageable in encrypted setting, since table size is 68 and 682 = 4624 for 1-grams and 2-grams respectively, they are not modified. The 3-grams table however is partitioned based on the structure of 3-grams. This gives 27 tables, one each for a permutation of structures L, D, S, from L3 to S3. Table 1 gives distribution of passwords in RockYou dataset as per Markov model using threshold based on scores.

Password type Threshold % in dataset
Very-weak <= 20 0.90
Weak 20 – 30 27.66
Medium 30 – 40 44.42
Strong 40 – 50 17.97
Very strong >= 50 9.03
TABLE 1: Passwords distribution for RockYou dataset using Markov model [057] Passwords were divided into 5 classes {Very weak, Weak, Medium strong, Strong, Very strong}. This remains same for the proposed model since computation remains same, only search space is reduced by dividing 3-grams tables into smaller tables using structure information. The behaviour of client and server in the optimized Markov model is shown in the flow diagram of FIG. 6 along with an example:
• Client extracts n-grams {σv....σk} from input password x where k is the number of n-grams for a given string.
• Using his public key, pk, client forms a batched ciphertext for each of the n-grams using the privacy preserving indexing search and send them to server

along with corresponding plain structures.
• The server retrieves resultant packed ciphertext corresponding to each n-gram from the respective structure table, rotate and add slots of these packed ciphertexts to obtain score to the first slot of the ciphertexts.
• These packed ciphertexts with scores in the first slot are homomorphically added to obtain final encrypted information score of the password.
[058] The timings for querying the Markov models is given in Table 2. As the structures of n-grams are revealed to the server, there is some leakage to the server. To mitigate this, n-grams of the actual password were obfuscated by combining them with dummy passwords (honey passwords). The honey structures obfuscate the actual structures present in the original password. In the present disclosure, honey passwords have been selected randomly from RockYou dataset. Table 3 show performance of query with honey passwords.

Client side Server side
Time (sec) Memory (MB) Time (sec) Memory (MB)
0.37 49 6.4 52
TABLE 2: Query performance for Markov model (Average over 100 random
password queries)

Query Client side Server side

Time (sec) Memory (MB) Time (sec) Memory (MB)
1-password + 4- 3.7 579.8 55.3 819.7
Honey
1-password + 9- 5.6 855.6 85.5 1095.7
Honey
1-password + 14- 7.5 1104.3 113.6 1344.3
Honey
1-password + 19- 9.1 1283.7 135.7 1523.7
Honey
TABLE 3: Query performance for Markov model with Honey password

[059] According to an embodiment of the disclosure, the PCFG model comprises of several structure tables that each contain variables and their information scores. When a password is queried, it is split into variables based on its structure. These variables are queried in corresponding tables to retrieve their information scores. In case of encrypted domain, since the search is exhaustive, it becomes expensive to search over huge variable tables. For example, an L8 table could potentially have at-most 26^8 entries and an exhaustive search can be tedious. Efficiency of search operation can be improved by reducing the size of these variable tables. In order to decrease the size of variable tables, intermediate 3-gram tables were generated (as in n-gram model) for each variable table along with the information scores. For usual PCFG case, the size of variable table is at-most 68^k, where k is the size variable length of that table (For example, L8 table will have at-most 68^8 entries). By generating n-gram tables with n=3, the size of table is reduced at-most 26^3. To get the probability of a string corresponding to a variable, 3-grams were generated for the string, look up the scores in intermediate 3-gram tables and scores of each 3-gram were added to obtain the final information score of the whole variable. It is important to note that in this approach, the information scores of the 3-grams generated from variable table are higher, which results in higher overall guessing probability of the password. This will result in conservative scoring for a given password which is an advantage to the user.
[060] The operational flow of the client and server in the optimized PCFG model is shown in FIG. 7 is as follows:
• Client extracts structure of the input password and splits the password into variables and corresponding strings based on the structure.
• For each of the strings, if the length is greater than 3, then 3-grams are extracted from the string.
• Using the public key, pk, client forms a batched ciphertext for each of the n-grams using the privacy preserving indexing search and send them to server along with their plain structures.
• The server computes privacy preserving index search of these packed ciphertexts to retrieve scores of all the n-grams.

• The server retrieves resultant packed ciphertext corresponding each to n-gram in the particular structure table, rotate and add slots of these packed ciphertexts to obtain score to the first slot of the ciphertexts.
• These packed ciphertexts with scores in the first slot are homomorphically added to obtain final encrypted score of the password.
[061] The distribution of passwords were provided from Rockyou dataset using the original PCFG model and proposed method in Table 4 using thresholds based on the information scores.

Password Type Original PCFG Proposed method
Threshold Percentage Threshold Percentage
Very weak <= 20 1.21 <= 25 6.93
Weak 20 – 30 65.34 25 – 40 59.24
Medium 30 – 40 23.05 40 – 55 24.86
Strong 40 – 50 6.99 55 – 70 6.586
Very strong >= 50 3.4018 >= 70 2.35
TABLE 4: Passwords distribution for RockYou dataset using PCFG and proposed
model
[062] Original PCFG model is first trained on RockYou dataset to get two types of tables (i) structure table (ii) variable tables. Since we provide structure information along with variables query ciphertexts, no separate query ciphertext is needed for structure table. Variable tables can be very large, hence in the present embodiment each variable table is divided into smaller tables of 1-grams, 2-grams and 3-grams using the Markov model on top of the variable table (here we are using n=3 for Markov model). In table 4, threshold values are different for original PCFG and proposed method because of the following reasons:
• Minimum score for password from Rockyou dataset using PCFG method is 6.9 and using the method of present embodiment is 8.3.
• Median of information scores for passwords from Rockyou dataset using PCFG method is 25.68 and using the method of present embodiment is 35.7
[063] It was inferred that this is because of additional 1-grams and 2-grams

generated for each variable table. Hence, the rise in threshold values. It can also be highlighted that the information score method is more conservative than original PCFG method.
[064] According to an embodiment of the disclosure, the system 100 further comprising enhancing privacy using one or more honey passwords. Empirical analysis have also been provided of how this optimization introduce trade-offs in terms of security and provide an alternative mechanism of including honey passwords to mitigate this.
[065] To further enhance privacy of input password's structure, honey password structures are used. For each input password, k honey structures are generated (where k is decided based on security parameter) and k dummy passwords are included corresponding to those honey structures and encrypt them. To enable server to retrieve the correct structure from the set of structures, a set of k flags (metadata) is also generated: E(1) at the index of correct input structure E(0) at the index of honey structures.
This metadata is encrypted and sent to the server. At the server side, information scores corresponding to all the structures and variables are retrieved and homomorphically aggregated to get the information score of the input password.
[066] As the structures of variables are revealed to the server, there is some leakage to the server. To mitigate this, variables of the actual password were obfuscated by combining them with dummy passwords (honey passwords). The honey structures conceal the actual structures present in the original password. Table 5 show performance of query with honey passwords.

Query Client side (Time-secs/ Memory-MB) Client side (Time-secs/ Memory-MB)
1-password + 4-Honey 1.87 / 287.7 25.2 / 390
1-password + 9-Honey 2.46 / 383.1 36.13 / 499.9
1-password + 14-Honey 3.6 / 522 54.9 / 656.7
1-password + 19-Honey 4.78 / 658.6 72.2 / 810.7
Table 5: Query performance for proposed PCFG method with honey passwords

[067] According to an embodiment of the disclosure, packing technique can also be used to reduce the number of ciphertexts exchanged between the client and the server. Using packing, multiple plaintext values can be encoded into a single ciphertext. To do this, client first retrieves the n-grams table for given n and also corresponding n-grams obtained from the input password. The vector to be encoded is of same length as the number of entries otherwise this is done in batch mode. Each index in the vector corresponds to n-gram from the n-grams table. Client sets an index as 1 if the corresponding n-gram was generated from the input password. Remaining entries will be 0. Client now encrypts this vector as a single ciphertext. Number of ciphertexts generated will be number of entries in an n-gram table divided by batch size which is a power of 2 and decided by user.
[068] According to an embodiment of the present disclosure in the PCFG model, intermediate 3-gram tables are generated for each variable table along with the information scores. For usual PCFG case, the size of variable table is at most 26^n where n is the size parameter (For example, L5 table will have at most 26^5 entries). In the case of intermediate 3-gram tables, the size of table is at most 26^3. To get the information score of a string corresponding to a variable, 3-grams were generated for the string, look up the information scores in intermediate 3-gram tables and add information scores of each 3-gram. It is important to note that in this approach, the information scores of the 3-grams generated from variable table are higher, which results in higher overall guessing information score of the password. This will result in conservative scoring for a given password which is an advantage to the user.
[069] The written description describes the subject matter herein to enable any person skilled in the art to make and use the embodiments. The scope of the subject matter embodiments is defined by the claims and may include other modifications that occur to those skilled in the art. Such other modifications are intended to be within the scope of the claims if they have similar elements that do not differ from the literal language of the claims or if they include equivalent elements with insubstantial differences from the literal language of the claims.

[070] The embodiments of the present disclosure herein solve the problems related to inefficiency of using FHE to search over large datasets. The disclosure provides a method and system for preserving privacy of a password while checking password strength using a password strength meter
[071] It is to be understood that the scope of the protection is extended to such a program and in addition to a computer-readable means having a message therein; such computer-readable storage means contain program-code means for implementation of one or more steps of the method, when the program runs on a server or mobile device or any suitable programmable device. The hardware device can be any kind of device which can be programmed including e.g. any kind of computers like a server or a personal computer, or the like, or any combination thereof. The device may also include means which could be e.g. hardware means like e.g. an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or a combination of hardware and software means, e.g. an ASIC and an FPGA, or at least one microprocessor and at least one memory with software modules located therein. Thus, the means can include both hardware means and software means. The method embodiments described herein could be implemented in hardware and software. The device may also include software means. Alternatively, the embodiments may be implemented on different hardware devices, e.g. using a plurality of CPUs.
[072] The embodiments herein can comprise hardware and software elements. The embodiments that are implemented in software include but are not limited to, firmware, resident software, microcode, etc. The functions performed by various modules described herein may be implemented in other modules or combinations of other modules. For the purposes of this description, a computer-usable or computer-readable medium can be any apparatus that can comprise, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.
[073] The illustrated steps are set out to explain the exemplary embodiments shown, and it should be anticipated that ongoing technological development will change the manner in which particular functions are performed.

These examples are presented herein for purposes of illustration, and not limitation. Further, the boundaries of the functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternative boundaries can be defined so long as the specified functions and relationships thereof are appropriately performed. Alternatives (including equivalents, extensions, variations, deviations, etc., of those described herein) will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein. Such alternatives fall within the scope and spirit of the disclosed embodiments. Also, the words “comprising,” “having,” “containing,” and “including,” and other similar forms are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items. It must also be noted that as used herein and in the appended claims, the singular forms “a,” “an,” and “the” include plural references unless the context clearly dictates otherwise.
[074] Furthermore, one or more computer-readable storage media may be utilized in implementing embodiments consistent with the present disclosure. A computer-readable storage medium refers to any type of physical memory on which information or data readable by a processor may be stored. Thus, a computer-readable storage medium may store instructions for execution by one or more processors, including instructions for causing the processor(s) to perform steps or stages consistent with the embodiments described herein. The term “computer-readable medium” should be understood to include tangible items and exclude carrier waves and transient signals, i.e., be non-transitory. Examples include random access memory (RAM), read-only memory (ROM), volatile memory, non-volatile memory, hard drives, CD ROMs, DVDs, flash drives, disks, and any other known physical storage media.
[075] It is intended that the disclosure and examples be considered as exemplary only, with a true scope of disclosed embodiments being indicated by the following claims.

WE CLAIM:
1. A processor implemented method (200) for preserving privacy of a pass¬word while checking password strength using a password strength meter, the method comprising:
providing, via one or more hardware processors, the password to a client for checking the strength, wherein the password having a password string (202);
extracting, via the one or more hardware processors, one or more n-grams from the password string, wherein n is a number of characters in one or more substrings present in the password string (204);
encrypting, via the one or more hardware processors, the extracted one or more n-grams using a fully homomorphic encryption (FHE) tech¬nique (206);
sending, via the one or more hardware processors, the encrypted one or more n-grams to the password strength meter present on a server, wherein the password strength meter is using a Markov model based technique (208);
searching, via the one or more hardware processors, each n-grams from amongst the one or more n-grams in their respective information score tables to get an information score if n is less than or equal to 2, wherein the information score tables are made for the each n-gram, the information score tables comprise of the n-grams and their guessing information scores (210);
splitting, via the one or more hardware processors, n-grams into 3-grams if n is more than 2, wherein the splitting is done based on a structure of the n-gram, and the division results in generation of derived tables having n-grams and their guessing information scores (212);
searching, via the one or more hardware processors, n-grams in the derived tables to get the information scores if n is more than two (214);

adding, via the one or more hardware processors, information scores of n-grams searched from the information score tables and the derived tables to get a final score (216);
sending, via the one or more hardware processors, the final score to the client (218); and
decrypting, via the one or more hardware processors, the final score using a FHE private key to get a final information score, wherein the final information score is indicative of the strength of the password (220).
2. The method of claim 1 further comprising using a probabilistic context free grammar (PCFG) technique (300) for measuring strength of password, wherein the PCFG technique comprises:
providing, via the one or more hardware processors, the password to the client for checking the strength (302);
extracting, via the one or more hardware processors, the structure of the password string (304);
encrypting, via the one or more hardware processors, variables pre-sent in the password string (306);
sending, via the one or more hardware processors, the encrypted var-iables and the structure of the password string to the password strength me¬ter (308);
creating, via the one or more hardware processors, a set of variable tables corresponding to the variables present in the password string (310);
creating, via the one or more hardware processors, a set of interme-diate 1-gram, 2-gram and 3-grams tables for each variable table of the set of the variable tables (312);
searching, via the one or more hardware processors, one or more variable information scores in corresponding intermediate 1-gram, 2-gram and 3-grams tables derived from variable tables (314);
retrieving, via the one or more hardware processors, a plurality of structure information scores in a structure lookup table (316); and

adding, via the one or more hardware processors, the structure infor¬mation scores and the one or more variable information scores to get the final information score of the password strings, wherein the final infor-mation score is indicative of the strength of the password (318).
3. The method of claim 2, wherein the one or more of Markov model based technique and the PCFG technique reduces search space of the n-gram ta-bles, thereby improving efficiency of the password strength meter.
4. The method of claim 1 wherein the client is one or more of a website, an application, where the password is provided for authentication.
5. The method of claim 1, wherein the structure is made of one or more of the number of lowercase, uppercase, digits and special characters present in the password string.
6. The method of claim 1 further comprising enhancing privacy using one or more honey passwords.
7. The method of claim 1 further comprising privacy preserving indexing con-figured to improve the efficiency of search operation, wherein the privacy preserving indexing is used to get an exact index and utilizing it to compute a resultant information score.
8. A system (100) for preserving privacy of a password while checking pass-word strength using a password strength meter, the system comprises:
an input/ output interface (104) configured to provide the password to a client for checking the strength, wherein the password having a pass-word string;
one or more hardware processors (108);

a memory (110) in communication with the one or more hardware processors, wherein the one or more first hardware processors are configured to execute programmed instructions stored in the memory, to:
extract one or more n-grams from the password string, wherein n is a number of characters in one or more substrings present in the password string;
encrypt the extracted one or more n-grams using a fully ho-momorphic encryption (FHE) technique;
send the encrypted one or more n-grams to the password strength meter present on a server, wherein the password strength meter is using a Markov model based technique;
search each n-gram from amongst the one or more n-gram respective information score tables to get an information score if n is less than or equal to 2, wherein the information score tables are made for each of the n-grams, the information score tables comprise of the n-grams and their guessing information scores;
split n-grams into 3-grams if n is more than 2, wherein the splitting is done based on a structure of the n-gram, and the division results in generation of derived tables having n-grams and their guessing infor-mation scores;
search n-grams in the derived tables to get the information scores if n is more than 2;
add information scores of n-grams searched from the infor-mation score tables and the derived tables to get a final score;
send the final score to the client; and
decrypt the final score using a FHE private key to get a final information score, wherein the final information score is indicative of the strength of the password.

9. The system of claim 7 further comprising using a probabilistic context free
grammar (PCFG) technique for measuring strength of password, wherein
the PCFG technique comprises:
providing, via the one or more hardware processors, the password to the client for checking the strength;
extracting, via the one or more hardware processors, the structure of the password string;
encrypting, via the one or more hardware processors, variables pre-sent in the password string;
sending, via the one or more hardware processors, the encrypted var-iables and the structure of the password string to the password strength me¬ter;
creating, via the one or more hardware processors, a set of variable tables corresponding to the variables present in the password string;
creating, via the one or more hardware processors, a set of interme-diate 1-gram, 2-gram and 3-grams tables for each variable table of the set of the variable tables;
searching, via the one or more hardware processors, one or more variable information scores in corresponding intermediate 1-gram, 2-gram and 3-grams tables derived from variable tables;
retrieving, via the one or more hardware processors, a plurality of structure information scores in a structure lookup table; and
adding, via the one or more hardware processors, the structure infor¬mation scores and the one or more variable information scores to get the final information score of the password strings, wherein the final infor-mation score is indicative of the strength of the password.
10. The system of claim 7, wherein the client is one or more of a website, and
an application, where the password is provided for authentication.