FORM 2
THE PATENTS ACT, 1970 (39 of 1970) & THE PATENTS RULES, 2003
COMPLETE SPECIFICATION (See section 10, rule 13)
1. Title of the invention: CONFIGURATION OF A MIX NETWORK BASED ON
DETERMINATION OF ANONYMITY
2. Applicant(s)
NAME NATIONALITY ADDRESS
TATA CONSULTANCY Indian Nirmal Building, 9th Floor, Nariman
SERVICES LIMITED Point, Mumbai, Maharashtra 400021,
India
3. Preamble to the description
COMPLETE SPECIFICATION
The following specification particularly describes the invention and the manner in which it
is to be performed.

TECHNICAL FIELD
[0001] The present subject matter relates, in general, to mix networks, and in
particular, to configuration of a mix network based on determination of anonymity of the mix network.
BACKGROUND
[0002] The Internet enables users to connect to each other or to various websites
from anywhere and at any point in time. The users can access/publish information seamlessly through wireless or wired networks indistinguishably. However, interacting or communicating over the Internet can result in vulnerability with respect to private or confidential information. While information provided during a single communication interaction or session may not appear significant, such information when aggregated can provide a lot of information regarding a user and associated entities.
[0003] Further, on the Internet, users have few controls, if any, over the privacy of
their actions, and hence privacy and security of personal data remains a matter of concern among Internet users who frequently use the Internet for making online purchases, visiting social networking sites, participating in online games, or attending forums. Therefore, Internet privacy protection is paramount to users for protecting sensitive and private data, and communications. To enable true network privacy, anonymity is to be provided to the users. Anonymity may be understood as protecting against revelation of identity of a user. For providing anonymity, various anonymity networks are in use. Anonymity networks are intended to enable Internet privacy and allow users to carry out their activities anonymously on the Internet, typically by frequently changing the data path through a subset of participating routers/ servers in the network. An anonymity network enables users to access the Web while blocking any tracking or tracing of their identity on the Internet. The anonymity network also makes traffic analysis and network surveillance difficult.

SUMMARY
[0004] This summary is provided to introduce concepts related to configuration of
a mix network based on determination of anonymity of the mix network. The concepts are further described below in the detailed description. This summary is neither intended to identify essential features of the claimed subject matter nor is it intended for use in determining or limiting the scope of the claimed subject matter.
[0005] In an embodiment, method(s) and system(s) for determining anonymity of
a network are described. The network includes a plurality of nodes. The method includes transforming the network into a bi-partite graph. The graph may include a set of input and output vertices connected together by a set of edges. Further, the set of vertices represent the plurality of nodes of the network. The method may also include computing connectivity index of the graph based on a matrix representation of the graph of order (m+n). The matrix may be indicative of adjacency between the set of vertices of the graph. The adjacency matrix may be reduced to generate a reduced adjacency matrix including m rows and n columns. Further, the method may include evaluating the anonymity of the mix network based on the connectivity index.
[0006] The anonymity of the mix network may be zero when the number of rows
(m) and columns (n) is equal to one. Furthermore, the anonymity of the mix network may be a function of the connectivity index when m and n of the reduced adjacency matrix is greater than one. In addition, the method may include comparing the anonymity of the network with a pre-defined level of anonymity. The method may further include configuring the network to achieve the pre-defined level of anonymity when the anonymity of the network is less than the pre-defined level of anonymity.
BRIEF DESCRIPTION OF THE DRAWINGS
[0007] The detailed description is described with reference to the accompanying
figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the drawings to reference like features and components.

[0008] Fig. 1 illustrates a network environment implementation of a network
analysis system, in accordance with an embodiment of the present subject matter.
[0009] Fig. 2a illustrates an exemplary mix network and a bi-partite graph of the
same for determining degree of anonymity of the mix network, in accordance with an embodiment of the present subject matter.
[0010] Fig. 2b illustrates an exemplary graph representing variation of degree of
anonymity with variation in number of edges in a mix network and a weighted mix network, in accordance with an embodiment of the present subject matter.
[0011] Fig. 3 shows a flowchart illustrating a method for determining anonymity
of a mix network, in accordance with an embodiment of the present subject matter.
DETAILED DESCRIPTION
[0012] Typically, in communications over the Internet, privacy of the users,
systems, and organizations are of major concern. In typical Internet communication, intruders or attackers may observe the communication/traffic patterns between the users/organizations to detect information, such as who is sending messages to whom, leading to a serious threat to the user's privacy. Even when end users exercise caution and/or employ conventional security programs, they may be revealing information about themselves without their knowledge. Thus, Internet based communications can be utilized as a source of significant information about users. In an example, information about a user can be obtained from IP (Internet Protocol) address of their communications devices (computers, phones, etc). Also, interaction records, such as search engine queries, can provide valuable information regarding that specific user's intent and/or interest. In another example, more often than not, communications are transmitted in an unencrypted format and therefore any intercepted or misdirected message may be easily used by unintended recipients.
[0013] While information provided during a single communication interaction or
session may not appear significant, such information when aggregated can provide a lot of information regarding a user and associated entities. In particular, data mining tools

can be employed to correlate and learn information from a subset thereof. Such tools can be employed by malicious individuals to perpetrate identity fraud, by advertisers for targeted advertising, and by government agencies for monitoring. For example, a single cookie providing information, such as a zip code, may appear harmless but when combined with other information, for example, cookies, address, and search history, can be used to identify and learn about a particular individual.
[0014] To prevent access of data, shared over the Internet by a third party,
network anonymity is provided. Anonymity involves preserving confidentiality of user data and hiding information that may identify a communication pattern over a communication network. Anonymity networks enable users to access the web while blocking any tracking or tracing of identity of the users on the Internet. Examples of the anonymity networks may include mix networks, The Onion Router (TOR), Crowd, and the like. In the mix networks, a proxy server receives a set of inputs from multiple users and transmits re-encrypted outputs in such a manner that the relationship between inputs and outputs can not be learned by anyone but the mix server. The proxy server functions as a relay between a user and a destination web site and hides IP address of the user's system from the destination web site. In peer to peer (P2P) networks, anonymity of participants is usually achieved by special routing overlay networks that hide physical location of each node from other participants. However, the above mentioned networks are mostly complex and do not provide low latency or real-time solutions.
[0015] Other systems for measuring anonymity focus on the level of anonymity
from the perspective of a single user or message. By observing an anonymous communication system, an adversary typically obtains a probability distribution linking a sender of a communication to all possible recipients, and vice versa. For example, by using an entropy based metric one can measure sender anonymity for a given recipient (or a message received) or recipient anonymity for a given sender (or a message sent). In the entropy based metric, a probabilistic theory may be used for a given distribution of probabilities. Accordingly, measure of information contained in a particular distribution may be represented as,

where,
X = discrete random variable with a probability mass function (pmf) Pr (X = i) = pi
Where pi is the probability that an ith user is transmitting a message
i = an element of the anonymity set (user)
H (X) = Entropy of the system after attack H(X)

HM = Maximum entropy of the system to be measured HM = log2 (N) N = Number of honest senders (size of anonymity set)
[0016] Further, in the abovementioned metric, d = 0 when user appears as
originator of message with a probability 1 and d = 1 when all users appear to be an originator of message with a probability of 1/N. However, such a metric may not be able to express a system-wide anonymity level. Further, existing anonymity metrics are based on information theory and are computationally intensive (NP-Class). In an example, identification of anonymity of a network based on permanent of a matrix, as proposed by Matthew Edman is computationally intensive and is applicable to a bi-graph G(V1, V2, E) only with |V1| = m, |V2| = n, where m<=n. Moreover, the existing anonymity metrics are unable to provide real-time solutions. Furthermore, the conventional techniques do not facilitate in providing the design of a mix network to achieve a required level of anonymity.
[0017] In various implementations, the present subject matter discloses a system
and a method for determining anonymity of a mix network, and configuring the mix network to achieve at least a pre-determined level of anonymity. Anonymity may be understood as a measure of how secure a communication would be over a communication network so that an intruder or an attacker may not be able to identify a communication pattern. A typical mix network may be understood as a communication network, including a plurality of nodes, which may utilize a chain of proxy servers. Each message or communication pattern over the mix network may be encrypted and sent to each of the proxy servers using well known encryption techniques. Thereafter, the encrypted message

or communication pattern may be sent to a recipient. The present subject matter utilizes a graph theoretic technique for identifying a degree of anonymity, also referred to as anonymity, of the mix network.
[0018] In an implementation, the present subject matter may include transforming
the mix network into a graph (G), such as a bi-partite graph. The graph (G) may include a set of vertices (V) connected together by a set of edges (E). The set of vertices (V) indicate the plurality of nodes of the mix network. Further, the set of vertices (V) is partitioned into two disjoint sets of vertices of order m and n corresponding to input and output ports of the mix network, respectively. Further, the present subject matter may include generating an adjacency matrix (A) representation of the graph (G) such that the vertices of the set of vertices (V) are adjacent to each other. In an implementation, the adjacency matrix (A) may be reduced to include m rows and n columns and may be referred as reduced adjacency matrix (Amxn).
[0019] The present subject matter may include computing a connectivity index
(CI) of the graph (G), based on the reduced adjacency matrix (Amxn). The connectivity index of the graph (G) is defined as:

where, u, v represent vertices of the graph (G) connected to each other by means of an edge, and dG(u) and dG(v) represent the degree of the vertices u and v, respectively. The degree of a vertex may be understood as number of edges incident on the vertex. The connectivity index may be referred as Randic index, when β is equal to -1/2.
[0020] The present subject matter further describes evaluating the anonymity of
the mix network based on the CI, based on the following equation:


[0021] The present subject matter indicates that the anonymity of the network
may be zero when at least one of m and n of the reduced adjacency matrix (Amxn) is equal to one. In another implementation, the anonymity of the network may be a function of the CI when both m and n of the reduced adjacency matrix (Amxn) are greater than one. The present subject matter further includes comparing the anonymity of the network with a pre-defined level of anonymity. If the anonymity of mix network is equal to or greater than the pre-defined level of anonymity, the present subject matter may indicate the mix network to be secure.
[0022] In case the anonymity of mix network is less than the pre-defined level of
anonymity, the present subject matter may facilitate in configuring the mix network to achieve the pre-defined level of anonymity. For example, the number of edges of the graph (G) may be increased such that the CI of the graph (G) may be modified. Further, a new value of β may be selected for computing the connectivity index of the mix network. Thereafter, the anonymity of the mix network may be re-calculated based on the modified CI and this procedure may be repeated until the mix network achieves the pre-defined level of anonymity.
[0023] In an implementation, the present subject matter may facilitate in
determining the degree of anonymity of a weighted mix network. In the weighted mix network, entries of the adjacency matrix (A) may be associated with a weight. Therefore, in this case, weighted CI may be defined as,

where, dG+(i) and dG-(j) are out and in degree of the nodes i and j, respectively.
[0024] Using the weighted CI as computed above, the anonymity of the weighted
mix network may be calculated as,

[0025] The present subject matter provides mechanisms to anonymize and secure
network interaction such that others are not able to identify a user, information associated

therewith and/or intent, among other things. The present subject matter also facilitates in providing privacy in various fields. Examples of such fields may include but are not limited to, social networks, data collection (blood samples, on-line voting, survey data), security applications, such as convoying and scheduling of secured events, and communication of confidential/ personal information. The secured events may include armed force usage (missile launching), armed force communications, and the like. Accordingly, the present subject matter facilitates in anonymizing a target location as well as a source of launching the missile. This may be beneficial in avoiding tracking of sources of launch of missile and target locations. It will be understood that the target location may correspond to an output port of a mix network and the source of missile launching may correspond to an input port of the mix network.
[0026] Further, the present subject matter discloses a real time system for
determining anonymity of mix networks using a graph theoretic technique based on Connectivity Index. For a given mix network and required anonymity level of a system, the present subject matter may identify whether the system is safe or not. If not, the present subject matter may re-configure the mix network and evaluate the re-configured network until the mix network achieves a desired level of anonymity.
[0027] These and other advantages of the present subject matter would be
described in greater detail in conjunction with the following figures. While aspects of described systems and methods for determining anonymity of a network can be implemented in any number of different computing systems, environments, and/or configurations, the embodiments are described in the context of the following exemplary system(s).
[0028] Fig. 1 illustrates a network environment 100 implementing a network
analysis system 102, in accordance with an embodiment of the present subject matter. In said embodiment, the network environment 100 includes the network analysis system 102 configured to determine anonymity of a mix network and configure the mix network in case the anonymity of the mix network is less than a pre-defined level. The mix network may be understood as a communication network, including a plurality of nodes, which

may utilize a chain of proxy servers. Each message or communication pattern over the mix network may get encrypted to each of the proxy servers using well known encryption techniques. Thereafter, the encrypted message may be sent to a recipient.
[0029] The network analysis system 102 may be implemented in a variety of
computing systems, such as a laptop computer, a desktop computer, a notebook, a workstation, a mainframe computer, a server, a network server, and the like. In one implementation, the network analysis system 102 may be included within an existing information technology infrastructure or a database management structure. Further, it will be understood that the network analysis system 102 may be connected to a plurality of user devices 104-1, 104-2, 104-3,...,104-N, collectively referred to as the user devices 104 or as an individual user device 104. The user device 104 may include, but is not limited to, a desktop computer, a portable computer, a mobile phone, a handheld device, and a workstation. The user devices 104 may be used by users, such as database analysts, programmers, developers, data architects, software architects, module leaders, projects leaders, database administrator (DBA), stakeholders, and the like.
[0030] As shown in the Figure 1, the user devices 104 are communicatively
coupled to the network analysis system 102 over a network 106 through one or more communication links for facilitating one or more end users to access and operate the network analysis system 102. In one implementation, the network 106 may be a wireless network, a wired network, or a combination thereof. The network 106 may also be an individual network or a collection of many such individual networks, interconnected with each other and functioning as a single large network, e.g., the Internet or an intranet. The network 106 may be implemented as one of the different types of networks, such as intranet, Local Area Network (LAN), Wide Area Network (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 Protocol (HTTP), Transmission Control Protocol/Internet Protocol (TCP/IP), etc., to communicate with each other. Further, the network 106 may include a variety of network devices, including routers, bridges, servers, computing devices, storage devices, and the like.

[0031] The network analysis system 102 further includes interface(s) 108.
Further, the interface(s) 108 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, and a printer. Additionally, the interface(s) 108 may enable the network analysis system 102 to communicate with other devices, such as web servers and external repositories. The interface(s) 108 may also facilitate multiple communications within a wide variety of networks and protocol types, including wired networks, for example, LAN, cable, etc., and wireless networks, such as WLAN, cellular, or satellite. For the purpose, the interface(s) 108 may include one or more ports.
[0032] In an implementation, the network analysis system 102 includes
processor(s) 110 coupled to a memory 112. The processor(s) 110 may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor(s) 110 may be configured to fetch and execute computer-readable instructions stored in the memory 112.
[0033] The memory 112 may include any computer-readable medium known in
the art including, for example, volatile memory, such as static random access memory (SRAM), and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes.
[0034] Further, the network analysis system 102 includes module(s) 114 and data
116. The module(s) 114 include, for example, a transformation module 118, a computation module 120, a configuration module 122, and other module(s) 124. The other module(s) 124 may include programs or coded instructions that supplement applications or functions performed by the network analysis system 102.
[0035] The data 116 may include vertices 126, edges data 128, anonymity data
130, and other data 132. The other data 132, amongst other things, may serve as a repository for storing data that is processed, received, or generated as a result of the

execution of one or more modules in the module(s) 114. Although the data 116 is shown internal to the network analysis system 102, it may be understood that the data 116 can reside in an external repository (not shown in the figure), which may be coupled to the network analysis system 102. The network analysis system 102 may communicate with the external repository through the interface(s) 108 to obtain information from the data 116.
[0036] As mentioned herein, the present subject matter discloses a system and a
method for determining anonymity of a mix network. The transformation module 118 may be configured to transform the network into a graph (G), such as a bi-partite graph. It will be evident to a person skilled in the art that the mix network may be represented as an n-partite graph G(V1, V2, ..., E). Further, the graph (G) may include a set of vertices (V) connected together by a set of edges (E). The set of input and output vertices may be partitioned into two disjoint vertex sets of order m and n corresponding to input and output ports of the mix network, respectively. An edge may be understood as an association between two vertices. Further, an edge between two nodes i and j is represented as (i, j) and,

[0037] With respect to the mix network, a vertex is a node and an edge is a link
between two nodes and accordingly the set of vertices (V) represent the plurality of nodes of the mix network. In an implementation, the transformation module 118 may also be configured to store details pertaining to the mix network. For example, the transformation module 118 may store details related to the nodes as vertices data 126. The transformation module 118 may also be configured to store details associated with the connections between the nodes of the mix network as edges data 128. In an implementation, the transformation module 118 may be configured to transform the bipartite graph into a complete bi-partite graph. It will be understood that the complete bipartite graph is a bi-partite graph where every vertex of a first set is connected to every vertex of a second set.

[0038] Further, the transformation module 118 may be configured to generate an
adjacency matrix (A) representing the graph (G). The adjacency matrix (A) is indicative of adjacency between vertices of the graph (G). It will be understood that two vertices are said to be adjacent to each other, if there exists an edge between them. Accordingly, the above mentioned matrix may be referred as an adjacency matrix. Further, the adjacency matrix (A) may be reduced to include m rows and n columns and may be referred as a reduced adjacency matrix (Amxn).
[0039] In an implementation, the computation module 120 of the network
analysis system 102 may be configured to compute connectivity index (CI) of the graph based on the adjacency matrix (A) as mentioned above in equation (2). The connectivity index of the graph (G) may be understood as connectivity between the set of vertices (V) of the graph (G) and is represented as:

where, u, v represent vertices of the graph (G), there is an edge between u and v (they are adjacent), and dG(u) and dG(v) represent the degree of the vertices u and v, respectively. The degree of a vertex may be understood as the number of edges associated with the vertex of a graph.
[0040] Considering the value of β as -1/2, the CI of the graph (G) may be
represented as,

where dG (u) and dG (v) represent the degree of the vertices u and v, respectively. It will be evident to a person skilled in the art that the value of β may be set to any other value as per the requirement. In a scenario, when value of β is set as -1/2, the CI of the complete bipartite graph (G) may be given as √mn . In another scenario, when value of β is set as 1/2, the CI of the complete bipartite graph (G) may be given as mn√mn.
[0041] As the graph (G) indicates the mix network, the computation module 120
may be configured to evaluate the anonymity of the mix network based on the CI of the

graph (G) as computed above. The degree of anonymity as identified above may define how secure the communication network is. In a scenario, the anonymity or degree of anonymity of the mix network may be zero when at least one of m and n of the reduced adjacency matrix (Amxn) is equal to one. In another scenario, the degree of anonymity of the mix network may be a function of the CI when m and n of the reduced adjacency matrix (Amxn) is greater than one. Accordingly, the degree of anonymity of the mix network may be evaluated using equation (3) and is represented as,

where,xβ(G) represents CI of the graph, and
m, n represents the number of rows and columns of the reduced adjacency matrix (Amxn),
respectively.
[0042] In an implementation, the network analysis system 102 may include a
configuration module 122 configured to compare the degree of anonymity of the mix network with a pre-defined level of anonymity. It will be understood that the pre-defined level of anonymity may be provided by a user. The pre-defined level of anonymity is stored as anonymity data 130. For example, if the user intends to have a desired degree of anonymity for a mix network, the configuration module 122 may be configured to compare the degree of anonymity of the mix network with the desired degree of anonymity. Based on the comparison, the configuration module 122 may determine whether the mix network has achieved a degree of anonymity as is desired by the user.
[0043] In the present implementation, when the degree of anonymity is less than
the desired level of anonymity, the configuration module 122 may facilitate the mix network in obtaining the desired level of anonymity. The configuration module 122 may be configured to re-configure the mix network according to the pre-defined level of anonymity and latency bounds for a message to be communicated. The configuration module 122 may facilitate in re-configuring the mix network based on minimum and

maximum latency bounds. For example, the configuration module 122 may facilitate in identifying the latency bounds and input/output ports and may increase number of edges between the vertices. Also, a different value of β may be selected for computing the connectivity index of the mix network.
[0044] Thereafter, an adjacency matrix may be generated based on the new set of
vertices and edges. This adjacency matrix is then used for computing the CI of the graph to determine the degree of anonymity of the mix network.
[0045] Accordingly, the present subject matter provides a lightweight anonymity
metric to measure the degree of anonymity of a mixed network using connectivity index in a graph-theoretic approach. The present subject matter also facilitates in checking whether a current mix network has the desired level of anonymity or not. If not, the current mix network may be configured to achieve the desired level of anonymity for secure communications through the mix network. Further, the network analysis system as described may be employed for various kinds of mix networks. Moreover, the present subject matter utilizes the connectivity index for distributed systems to obtain real-time and computationally less intensive solutions. In a worst case, the computational complexity of the present anonymity metric is O(n2).
[0046] Fig. 2a illustrates an exemplary mix network 200 and a bi-partite graph
202 of the same for determining degree of anonymity of the mix network 200, in accordance with an embodiment of the present subject matter. In an implementation, input vertices of the mix network 200 may be represented as S={s1, s2, ....sm}. An input such as si=j may indicate that an input arrives at input line Si at time j. For example, as is shown in the Figure, s1= 1 may indicate that the input arrives at input line S1 at 1 min. In another implementation, output vertices from the mix network 200 may be represented as T={t1, t2,….., tn}. An output such as tp=k may indicate that the output will be delivered from output line tp at time k to the intended user. For example, as is shown in the Figure, t1=3 may indicate that the output was delivered at output line t1 at 3 mins.
[0047] Further, for every interaction over the mix network 200, the network
analysis system 102 may define a lower bound (∆min) and an upper bound (∆max) for each

message that may be delivered over the mix network 200. The Amin and the Amax may be understood as the minimum and maximum time with which the message may be delivered. As described above, the mix network 200 may be represented as a bi-partite graph 202 by the transformation module 118. As may be indicated by the Figure, the bipartite graph 202 include two vertex sets S and T with order |S| = m, |T| = n. These two vertex sets correspond to input and output vertices of the mix network 200.
[0048] In an implementation of the present subject matter, for any pair of vertices
(si, tj), one taken from each of S and T, an edge exists between the vertices if the following condition is satisfied-
(si=k,tj=l) such that Amin < l - k < Amax
[0049] Using the above mentioned information and considering the value of P as
1/2, the computation module 120 may compute the CI of the graph. It will be understood that the CI may be computed by using equation (2)
[0050] Further, considering m = 3 and n =3 with Amin = 1 and Amax = 4, the degree
of anonymity of the mix network 200 may be computed by the computation module 120 using equation (3) for the below mentioned corresponding reduced adjacency matrix (Amxn) of the mix network 200:
T1 T2 T3
S1 1 1 0
S2 111
S3 0 1 1

[0051] Fig. 2b illustrates exemplary graphs 204 and 206 representing variation of
degree of anonymity with variation in number of edges in a mix network and a weighted mix network respectively, in accordance with an embodiment of the present subject matter. As described above, CI of the mix network may be computed by representing the mix network in a reduced adjacency matrix (Amxn) of with m = 20 and n = 20. The

transformation module 118 may be configured to transform the mix network into a bipartite graph. As described above, the CI may be computed by the computation module 120 by considering β as 1/2. Furthermore, based on the CI, the degree of anonymity d(A) of the mix network may be evaluated by the computation module 120.
[0052] Upon determination of the degree of anonymity of the mix network, the
configuration module 122 may compare the degree of anonymity with a desired level of anonymity that may be pre-defined by a user. Upon comparison, if it is identified that the degree of anonymity of the mix network is less than the pre-defined level of anonymity, the mix network may be configured to achieve the pre-defined level of anonymity. For example, the configuration module 122 may randomly select a pair of non-adjacent vertices and may add an edge between such a pair, based on pre-determined rules. The pre-determined rules may include increasing upper bound of the message latency as described above. The addition of a new edge between the non-adjacent pair of vertices renders the graph non-isomorphic to the adjacency matrix. The variation of degree of anonymity with variation in number of edges may be plotted as a graph as indicated by the graph 204. The graph 204 may indicate that as the number of edges of the mix network increases, the degree of anonymity increases. Accordingly, the network analysis system 102 may enable a user to achieve desired level of anonymity for a mix network for facilitating secure communication.
[0053] In an implementation, the degree of anonymity may be determined for a
[0054] Further, as mentioned above in equation (4), weighted CI may be defined
as,
weighted mix network. In this case, each entry (i, j) in the reduced adjacency matrix (Amxn) that may be generated by the transformation module 118 for the weighted mix network may be associated with a weight. The weight may be understood as a probability that a message may be routed from i to j and may be represented as Pij. Further, the weight may be associated with the degree of the vertices of the graph of the weighted mix network. Accordingly, for each input vertex i of the weighted mix network,



where, dG+(u) and dG-(v) are out and in degree of the nodes i and j, respectively.
[0055] Considering dG-(v) = 1, the degree of anonymity for the weighted mix
network may be represented as shown in equation (5). Referring to the graph 206, the variation of degree of anonymity with variation in number of edges may be plotted for w a weighted mix network.
[0056] Fig. 3 illustrates a method 300 for determining the degree of anonymity of
a network, in accordance with an embodiment of the present subject matter. The method 300 may be described in the general context of computer executable instructions stored on computer readable medium, such as any digital storage medium. Generally, computer executable instructions can include routines, programs, objects, components, data structures, procedures, modules, and functions that perform particular functions or implement particular abstract data types. The method 300 may also be practiced in a distributed computing environment where functions are performed by remote processing devices that are linked through a communication network. In a distributed computing environment, computer executable instructions may be located in both local and remote computer storage media, including memory storage devices.
[0057] The order in which the method 300 is described is not intended to be
construed as a limitation, and any number of the described method blocks can be combined in any order to implement the method 300 or alternative methods. Additionally, individual blocks may be deleted from the method 300 without departing from the spirit and scope of the subject matter described herein. Furthermore, the method 300 can be implemented in any suitable hardware, software, firmware, or combination thereof.
[0058] Referring to Fig. 3, at block 302, the method 300 may include
transforming the mix network into a graph, for example, by the transformation module 118. The graph may include a set of input and output vertices connected together by a set of edges. Further, the set of input and output vertices may represent the plurality of nodes of the mix network. The transformation module 118 may further be configured to

generate a matrix, such as an adjacency matrix (A) based on the graph. The adjacency matrix (A) may be indicative of the adjacency between vertices of the graph. The adjacency matrix (A) may further be reduced to include m rows and n columns and may be referred as a reduced adjacency matrix (Amxn).
[0059] At block 304, the method 300 may include computing connectivity index
of the graph based on the adjacency matrix of the graph. The computation module 120 may be configured to compute the connectivity index of the graph using the equation (2). The connectivity index of the graph (G) may be understood as connectivity between the set of vertices (V) of the graph (G) and is represented as:

[0060] The reduced adjacency matrix (Amxn) may include m rows and n columns
that are indicative of number of inputs and outputs of the mix network, respectively.
[0061] Further, at block 306, the method 300 may include evaluating anonymity
of the mix network based on the connectivity index. The computation module 120 may be configured to evaluate degree of anonymity of the mix network by using the equation (3).

[0062] The degree of anonymity of the network may be indicative of extent of
security that may be provided by the mix network. The degree of anonymity of the mix network may be zero when at least one of m and n of the reduced adjacency matrix (Amxn) is equal to one. In case, m and n of the reduced adjacency matrix (Amxn) is greater than one, the degree of anonymity of the mix network is a function of the connectivity index, as given by the equation (3).

[0063] At block 308, the method 300 may include comparing the anonymity of
the network with a pre-defined level of anonymity and ascertaining whether the anonymity of the network is less than a pre-defined level of anonymity or not.. The configuration module 122 may be configured to compare the anonymity of the mix network with a pre-defined level of anonymity. In an implementation, the pre-defined level of anonymity may be a desired level of anonymity by the user. If the degree of anonymity of the mix network is greater than or equal to the pre-defined level of anonymity, the method 300 moves to block 310. If the degree of anonymity of the mix network is less than the pre-defined level of anonymity, the method 300 moves to block 312.
[0064] At block 310, the method 300 may include indicating the mixed network
to be secure for communication. The configuration module 122 may indicate whether the mix network has the required level of anonymity or not.
[0065] At block 312, the method 300 may include identifying at least one pair of
non-adjacent vertices from amongst the set of input and output vertices of the graph. The configuration module 122 may be configured to identify the at least one pair of non-adjacent vertices. The method 300 may further include adding an edge between the at least one pair of non-adjacent vertices.
[0066] Further, at block 314, the method 300 may include defining a latency time
period associated with transmission of a message over the mix network, such as mix network 200. The latency time period may be understood as delay in transmissions of the message over the mix network 200. Accordingly, the degree of anonymity of the mix network may be re-evaluated based on the connectivity index of the graph with more edges. Therefore, the method 300 moves to block 302. The present subject matter facilitates in performing iterations until the desired level of anonymity is achieved.
[0067] Although embodiments for configuration of a mix network based on
determination of anonymity of the mix network have been described in language specific to structural features and/or methods, it is to be understood that the present subject matter is not necessarily limited to the specific features or methods described. Rather, the

specific features and methods are disclosed as exemplary implementations for the network analysis system.

I/We claim:
1. A method for determining anonymity of a mix network, wherein the mix network
comprises a plurality of nodes, the method comprising:
transforming the mix network into a graph, wherein the graph comprises a set of input and output vertices connected together by a set of edges, and wherein the set of input and output vertices represent the plurality of nodes of the mix network;
computing a connectivity index of the graph based on an adjacency matrix representation of the graph, wherein the adjacency matrix is indicative of adjacent vertices of the graph, and wherein the adjacency matrix is reduced to generate a reduced adjacency matrix including m rows and n columns indicative of number of inputs and outputs of the mix network, respectively;
evaluating the anonymity of the mix network based on the connectivity index, wherein the anonymity of the mix network is zero when at least one of m and n of the reduced adjacency matrix is equal to one, and wherein the anonymity of the mix network is a function of the connectivity index when both m and n of the reduced adjacency matrix are greater than one; and
configuring the mix network to achieve a pre-defined level of anonymity when the anonymity of the mix network is less than the pre-defined level of anonymity.
2. The method as claimed in claim 1, wherein the mix network is a weighted mix network and each entry in the adjacency matrix is associated with a weight.
3. The method as claimed in claim 1, wherein the graph is a bi-partite graph.
4. The method as claimed in claim 1, wherein the evaluating comprises comparing the anonymity of the mix network with a pre-defined level of anonymity.

5. The method as claimed in claim 1, wherein the configuring comprises,
creating one or more edges between at least one pair of non-adjacent input and output vertices;
generating a new graph based on the creation of the one or more edges; and
re-evaluating the anonymity of the mix network based on the connectivity index of the new graph.
6. The method as claimed in claim 1, wherein the configuring further comprises identifying a β value to compute a new connectivity index of the mix network.
7. The method as claimed in claim 1, wherein the configuring further comprises defining a latency time period associated with transmission of a message over the mix network.
8. A network analysis system (102) configured to determine anonymity of a mix network, the mix network comprising a plurality of nodes, the network analysis system (102) comprising:
a processor (110);
a transformation module (118) coupled to the processor (110), the transformation module configured to,
transform the mix network into a graph, wherein the graph comprises a set of input and output vertices connected together by a set of edges wherein the set of input and output vertices represent the plurality of nodes of the mix network; and
generate an adjacency matrix representation of the graph, wherein the adjacency matrix is indicative of adjacency between the set of input and output vertices of the graph, and wherein the adjacency matrix is reduced to generate a reduced adjacency matrix including m rows and n columns indicative of number of inputs and outputs of the mix network respectively; and

a computation module (120) coupled to the processor (110), the computation module (120) configured to,
compute connectivity index of the graph based on the reduced adjacency matrix; and
evaluate the anonymity of the network based on the connectivity index, wherein the anonymity of the mix network is zero when at least one of m and n of the reduced adjacency matrix is equal to one, and wherein the anonymity of the mix network is a function of the connectivity index when m and n of the reduced adjacency matrix is greater than one.
9. The network analysis system (102) as claimed in claim 8, wherein the computation module (120) is further configured to select a value of β for computing the connectivity index of the mix network.
10. The network analysis system (102) as claimed in claim 8 further comprising a configuration module (122) coupled to the processor (110), the configuration module (122) configured to,
define a latency time period associated with transmission of a message over the mix network;
compare the anonymity of the network with a pre-defined level of anonymity; and
configure the network to achieve the pre-defined level of anonymity when the anonymity of the network is less than the pre-defined level of anonymity.
11. The network analysis system (102) as claimed in claim 8, wherein the
configuration module (122) is further configured to,
identify at least one pair of non-adjacent vertices from amongst the set of vertices of the graph;
add an edge between the at least one pair of non-adjacent vertices based on pre-determined rules; and

re-evaluate the anonymity of the network based on the connectivity index of the graph, wherein the graph comprises more edges.
12. The network analysis system (102) as claimed in claim 8, wherein the pre-defined level of anonymity is provided by a user.
13. A non-transitory computer-readable medium having embodied thereon a computer program for executing a method for determining anonymity of a mix network, wherein the mix network comprises a plurality of nodes, the method comprising:
transforming the mix network into a graph, wherein the graph comprises a set of input and output vertices connected together by a set of edges, and wherein the set of input and output vertices represent the plurality of nodes of the mix network;
computing connectivity index of the graph based on an adjacency matrix representation of the graph, wherein the adjacency matrix is indicative of adjacent vertices of the graph, and wherein the adjacency matrix is reduced to generate a reduced adjacency matrix including m rows and n columns indicative of number of inputs and outputs of the mix network respectively;
evaluating the anonymity of the mix network based on the connectivity index, wherein the anonymity of the mix network is zero when at least one of m and n of the reduced adjacency matrix is equal to one, and wherein the anonymity of the mix network is a function of the connectivity index when m and n of the reduced adjacency matrix is greater than one; and
configuring the mix network to achieve a pre-defined level of anonymity when the anonymity of the mix network is less than the pre-defined level of anonymity.