\chapter{Anonimato}

test


\section{Modelo de protocolo para un sistema anónimo basado en estrategias bio-inspiradas}


\textbf{Resumen}

In this paper we propose to use some of the tools provided by the Distributed Artificial Intelligence (DAI), in particular Artificial Ant Colony Systems, building anonymous systems that have the virtue of having acceptable levels of Anonymity at a low cost. This cost refers to the performance criteria typically used in the process of routing telecommunications systems, such as response times (latency), the consumption of network resources, among others.



\subsection{Introduction}
To preserve privacy on each person's data who participate in interaction network, such as the Internet, we must to use tools that are capable of providing protection against some types of attack. The attacks in this particular study case are intended to get (without authorization) users' ``private information'', including their own identity. For this type of attack have been proposed several ideas to help establish certain levels of Anonymity, which in most cases have tended to undermine the communications' performance. This still is an open problem: the anonymous systems still need to ensure the Anonymity at low cost (low response times, low resources consumption, usability of the system, etc.), this is to have \emph{efficient Anonymity}. This paper presents a first approach to Distributed Artificial Intelligence to this branch of Information Technologies Security, that is, it intends to delegate the responsibility to achieve efficient Anonymity levels to the Distributed Artificial Intelligence, we propose 
to use Artificial Ant Colony systems.

\subsection{Artificial Systems Ant Colony in Anonymity}
\label{rlsm:ia-anonimato}

Considering the ideas proposed for probabilistic Anonymity systems \cite{rlsm:chaum-mix}\cite{rlsm:mixminion}\cite{rlsm:diaz-mixes}\cite{rlsm:tor-design}, and Artificial Ant Colony Systems' features used in telecommunications networks \cite{rlsm:antnet}\cite{rlsm:ants-white}\cite{rlsm:ants-loadbalancing}, this proposal is based on select messages' routes in a probabilistic way, using the probabilities set by mobile adaptive agents (the ants). These routes, having probabilistic components may include, depending the network parameters' configuration, certain controlled levels of Anonymity, in this way, we could have ``intelligent control'' on generated response times and we could have ``intelligent control'' on another indexes that they can be incorporated, such as resource consumption (load balancing).

We propose \emph{mimic} real messages to agents, that is, each message has the same structure as the ants, and the only difference between them lies in the message payload, these mimic messages are encrypted with the destination node's public key. To match their sizes, we propose to use a single size for each agent, including the data structure to stores information to update the tables at each node, plus useless filler and the destination's public key encryption. Each message has the same size as the agents, each one is fractionated or filled, and the the message's  payload is sent encrypted with the the destination node's public key. Each message is re-assembled at the destination node, using a numbering sequence established in the sending node. To have the messages the same structure that ants, they also contribute to the routing tables update, thus the attackers can't distinguish between the ants and the real messages. In this way, we can compare the messages with the ants having the task of loading the 
food into the nest, for this reason there are two types of ants in our system, \emph{the scouts and the load} both without apparent differences.

We use an encryption layers strategy, so each node that an ant visits encrypts information related to the previous node with a symmetric encryption technique involves only each previously node key and to reach each destinations, including the final, we can log only the previous node, and not the entire sequence to the origin. To do the reverse route, the node sends final response to the previous node, and it decrypts the layer that contains the node information before him, and so on until the initial node (the sender).

To optimize the performance criteria typically used in routing systems, while achieving increased levels of Anonymity, we must to set properly the update routing tables' rules. To do this, every time an ant moves from one place to another, update the routing table. To enhance the route's  probability, it's selected based in performance criteria. 

The following steps show the process:

\begin {description}
  \item [A.] We consider a system of $N$ nodes forming a P2P network (such as Gnutella or other with similar characteristics), along with their servers (bootstrap).
  \item [B.] Sets the parameters' values used, like uniformity index. In cases where you consider other performance criteria involved in the calculation, are initialized in this step.
  \item [C.] Each participating node requests the list of other nodes to one or more servers in the P2P network. This list contains their public key.
  \item [D.] The routes tables are initialized with probability $1/M$. $M$ depends on the number of neighbors each node has.
  \item [E.] The system is represented by a graph forming the solution space that will be traveled by the ants.
  \item [F.] The following procedure is repeated on the graph until reach a stable solution:
  \begin {description}
    \item [1.] Is placed $m$ scout ants in each node.
    \item [2.] For each $N-1$ places from every node in particular, are sent $m$ scout ants that choose the next hop (neighbor node) using the transition probabilities of the routing table.
    \item [3.] Routing tables are updated.
  \end {description}
  \item [G.] When a node sends a message anonymously, it encrypts that with the recipient's public key and place a data structure similar to the scout ants, ie, creates a \emph{load ant}. Each one carries a message part, which is split in order to match its size with the scout ant. Each fragment of the message contains a sequence number.
  \item [H.] For each ant's jump, the intermediate node encrypt the previous node's  identity with its private key.
  \item [I.] When a load ant reaches the end node, and all the others load ants have reached, it is possible to complete the original message is decrypted with its private key, and re-assembled it using the corresponding sequence numbers.
  \item [J.] To send the reply message, the end node uses the return path encrypted in layers.
\end {description}

\subsection{Conclusion}
\label{rlsm:conclusion}

It is proposed to implement in a distributed P2P System based probabilistic Anonymous Artificial Ant Colony Systems. To do that we can use a set of participating nodes as potential routers of anonymous messages. The routes for sending messages are constructed based on the strategies proposed for telecommunications systems that optimize performance criteria through the use of \emph{Artificial Ant Colony Systems}. Once routes are created, Anonymity is achieved by selecting a probabilistic message routes and through the use of encryption in layers down the route of return or response.

\subsection*{Acknowledgements}
This work was supported by the Mi­nis­te­rio de Industria, Turismo y Comercio (MITyC, Spain) through the Project Avanza Competitividad I+D+I TSI-020100-2010-482 and the Ministerio de Ciencia e Innovaci?n (MICINN, Spain) through the Project TEC2010-18894/TCM. Rodolfo Leonardo Sumoza Matos is also supported by the Programme Al$\beta$an, the European Union Programme of High Level Scholarships for Latin America, scholarship No. E07D401826VE. We must to thank to José Lisandro Aguilar Castro for his revision, advices and recomendations about the whole content of this paper.


\begin{thebibliography}{1}

\bibitem{rlsm:terminology}
Pfitzmann, A., Hansen, M.: Anonymity, Unobservability, and Pseudonymity: A Consolidated Proposal for Terminology. In: http://dud.inf.tu-dresden.de/Anon\_Terminology.shtml, (2000)

\bibitem{rlsm:diaz01}
D\'{\i}az, C., Seys, S., Claessens, J., Preneel, B.: Towards measuring Anonymity. In: Designing Privacy Enhancing Technologies (PET'02). Springer LNCS 2482, pp. 54-68, (2002)

\bibitem{rlsm:serj01}
Serjantov, A., Danezis, G.: Towards an Information Theoretic Metric for Anonymity. In: Proceedings of Privacy Enhancing Technologies Workshop, (2002)

\bibitem{rlsm:chaum-mix}
Chaum, D.: Untraceable electronic mail, return addresses, and digital pseudonyms. In: Communications of the ACM, Vol. 4, No. 2, (1981)

\bibitem{rlsm:diaz-mixes}
D\'{\i}az, C., Serjantov, A.: Generalising Mixes. In: Proceedings of Privacy Enhancing Technologies workshop (PET 2003), pp. 18-31, (2003)

\bibitem{rlsm:mixminion}
Danezis, G., Dingledine, R., Mathewson, N.: Mixminion: Design of a Type III Anonymous Remailer Protocol. In: Proceedings of the 2003 IEEE Symposium on Security and Privacy, pp. 2-15, (2003)

\bibitem{rlsm:tor-design}
Dingledine, R., Mathewson, N., Syverson, P.: Tor: The Second-Generation Onion Router. In: Proceedings of the 13th USENIX Security Symposium, (2004)

\bibitem{rlsm:antnet}
Caro, G.D., Dorigo, M.: AntNet: Distributed Stigmergetic Control for Communications Networks. In: Journal of Artificial Intelligence
Research, (1998)

\bibitem{rlsm:ants-white}
White, T., Pagurek, B.: Connection Management using Adaptive Mobile Agents. In: Proceedings of the International Conference on
Parallel and Distributed Processing Techniques and Applications, pp. 802-809, (1998)

\bibitem{rlsm:ants-loadbalancing}
Schoonderwoerd, R.: Ant-Based Load Balancing in Telecommunications Networks. In: Adaptive Behavior, Vol. 5, pp. 169-207, (1997)

\end{thebibliography}




\section{Sistema de medición alternativo}


\textbf{Resumen}
This paper proposes the use of a system of measures for Anonymity based on the characteristics that define their main properties: the index of uniformity of the probability distribution and size of all anonymous. In previous proposals, the most widely used is based on the entropy, an index used in information theory, which has several drawbacks with respect to representation of the properties mentioned in the first place does not represent them explicitly and being a logarithmic index does not represent Anonymity levels or degrees that require linear behavior. To measure the uniformity index is proposed to use the Root Mean Square Error criterion or the Jensen-Shannon divergence. For anonymous set size proposes the use of a function of N.
Claves(metrics, Anonymity, Root Squared Mean Error, Jensen-Shannon Divergence).



\subsection{Introduction}

The measures used to quantify levels of Anonymity achieved by the systems, mechanisms and tools in general is still considered an open problem. Several alternatives have been proposed for this purpose, and used more widely accepted so far is based on a type of measurement based on the Information Theory: Entropy, however, does not explicitly consider the fundamental characteristics of Anonymity: anonymous set size and uniformity index of the probability distribution. In this paper, we propose two indices explicitly representing both indicators. On one hand the anonymous set size would be represented by a function of N and uniformity index would be represented using one of these indicators: the Root Mean Square Error (RMSE) or the criteria of Jensen-Shannon divergence (CDJs .)

Pfiztmann et al. \cite{terminology} established terminology to standardize the terms used in the context of Anonymity, in which it was determined that a subject is anonymous when it can not be differentiated from other subjects belonging to the same set. This set is called the Anonymous Set. In describing the Anonymity in these terms, states that its levels increase as you grow the size of that set and when the probability distribution assigned by the attacker to the members of that group tends to be uniform. The proximity of a probability distribution to any uniform probability distribution is what we call uniformity index of the probability distribution.

The latest proposals and the most widely used so far are those based on a measurement used in the context of Information Theory: Entropy, as defined Shannon \cite{shannon}. This proposal was discussed in the work Díaz et al. \cite{diaz01} and Serjantov et al. \cite{serj01}, then there have been several streams that use the same basis, such as those proposed by Deng et al. \cite{yuxin}, Edman et al. \cite{combinatorial} and Gierlichs et al. \cite{revisiting}. However, not explicitly shown in the two aforementioned Anonymity characteristics, in particular the uniformity index.

Section 2 provides a theoretical review of the entropy and specific problems are shown in relation to its use as a measure of Anonymity, in sections 3 and 4 show the basic concepts necessary for the use of the measures proposed in section 5, establishing the uniformity index measurements of the probability distribution.


\subsection{Related work}
There have been several proposals to quantify the degree or level of Anonymity provided by any anonymous system. In \cite{reiter} define the degree of Anonymity as $1 - p$, where $p$ is the probability assigned to a particular user by the attacker. In \cite{berthold} define the degree of Anonymity as $A=\log_2(N)$, where $N$ is the number of users of the system. This degree only depends on the number of users of the system, and does not take into account the information the attacker may obtain by observing the system. In \cite{diaz01} and \cite{serj01} propose to measure the information the attacker gets, taking into account the whole set of users and the probability information the attacker obtains about them, to do that they propose to use Information Theory Entropy to measure the degree of Anonymity (using Shannon's entropy definition \cite{shannon}). None of them takes explicitly in consideration the anonymous set size and its uniformity index of probability distribution function like separated indexes 
to be measures, and these are the most important Anonymity's descriptors. Besides, in \cite{diaz01} proposed to use a normalized degree, but this measures could reach its maximal level with $N=2$ (anonymous set size), contradicting the Anonymity's fundamental characteristics described in \cite{terminology}: Anonymity level increases by increasing the size of the anonymous set and by increasing the uniformity index of probability distribution function. In \cite{yuxin}, \cite{combinatorial}, \cite{revisiting} use Shannon's entropy with different focus but with the same problems. When they use Entropy, are using the logarithmic function, that mean to have no linear degrees to compare systems. For example, if we have four (4) systems, and the attackers don't have any information about them, that mean the attackers assigned the uniformity distribution function for all of them, and, if the first set has $N=100$, the second one has $N=200$, the third one has $N=400$ and the fourth one has $N=800$, the Anonymity 
degrees using Entropy are: $6.6438$, $7.6438$, $8.6438$, $9.6438$, respectively. These scenarios with the same probability distribution and different $N$ (twice between each one) must to have twice the Anonymity degree comparing each one with the next one, but it is not happening because entropy's logarithmic function is not linear.


\subsection{Proposal}

We propose to use two indexes to measure Anonymity, each one to establish the levels of Anonymity's characteristics: One to measure the anonymous set size(we can use $N$ or $1/N$, where $N$ is the number of the elements), and one to measure uniformity index of probability distribution function assigned by the attacker. To measure the uniformity index we propose to use two metrics: the MSE - Mean Square Error and/or the JSD - Jennsen-Shannon Divergence.

\subsubsection{Root Squared Mean Error - RSME}

This term is used to estimate variance's error, this error is the residual sum of squares divided by the number of degrees of freedom. In regression analysis, it's an observed quantity given a particular sample, it's sample-dependent. Besides, this term is often referred to as "out-of-sample mean squared error": the mean value of the squared deviations of the predictions from the true values, over an out-of-sample test space, generated by a model estimated over a particular sample space. This also is an observed quantity, and it varies by sample and by out-of-sample test space.

\begin{equation}
RSME=\frac{\sqrt{(\bar{X}-X)^{2}}}{n(n-1)}
\end{equation}


In our case, we can use $p_{i}=\frac{1}{N}$ (probabilities in a uniform distribution) to represent $\bar{X}$, and $p_{i}$ is the probability assigned to the attacker to represent $X$. This measure permit to establish how far is the attacker's probability distribution from the uniform distribution.

\begin{equation}
RSME_a=\frac{\sqrt{\displaystyle\sum_{i=1}^N (\frac{1}{N}-p_{i})^{2}}}{N(N-1)}
\end{equation}

If one system has a $RSME_a\approxeq1$ that mean it provides bad Anonymity protection. If another system has a $RSME_a\approxeq0$ that mean it provides good Anonymity protection. But we have to look the set size to definitively take a real perspective of the Anonymity degree.

\subsubsection{Jennesen-Shannon divergence}

The Jensen-Shannon divergence is a popular method of measuring the similarity between two or more probability distributions. It is based on the Kullback-Leibler divergence, with the notable (and useful) difference that it is always a finite value. The square root of the Jensen-Shannon divergence is a metric to measure one Anonymity index: uniformity index of probability distribution function.

\begin{equation}
JSD(P_{1},P_{2})=H\left(\displaystyle\sum_{i=1}^2 \pi_i P_i\right)-\displaystyle\sum_{i=1}^2 \pi_i P_i
\end{equation}

\begin{equation}
JSD_a(P_{1},P_{2})=\sqrt{JSD(P_{1},P_{2})}
\end{equation}

where $\pi_i$ are the weights for the probability distributions  $P_1,P_2$, in this case $\pi_i=1, \nabla i=\{1,2\}$, and $H(P)$ is the Shannon entropy for distribution $P$. In this case, $P_1$ is a uniform distribution and $P_2$ is attacker's probability distribution.

With this result we can use both indexes to represent anonymity level o degree.


\subsubsection{Results}
\begin{description}
  \item[Option 1:] Anonymity degree ($AD$)using MSE to measure uniformity index of probability distribution function and $1/N$ to measure anonymity set size.\\
\begin{center}$AD =  1 / N ±MSE_a$\end{center}
  \item[Option 2:] Anonymity degree using JSD to measure uniformity index of probability distribution and $1/N$ to measure anonymity set size.\\
\begin{center}$AD =  1 / N ±JSD_a$\end{center}
\end{description}

In both cases, the uniformity index and the set size are expressed separately and don't have the linearity problem.

\subsubsection*{Acknowledgments.}
This work was supported by the Ministerio de Industria, Turismo y Comercio (MITyC, Spain) through the Project Avanza Competitividad I+D+I TSI-020100-2010-482 and the Ministerio de Ciencia e Innovaci?n (MICINN, Spain) through the Project TEC2010-18894/TCM. Rodolfo Leonardo Sumoza Matos is also supported by the Programme Al$\beta$an, the European Union Programme of High Level Scholarships for Latin America, scholarship No. E07D401826VE.


\begin{thebibliography}{}

\bibitem{terminology}
Pfitzmann, A.,  Hansen, M.: Anonymity, Unobservability, and Pseudonymity: A Consolidated Proposal for Terminology. http://dud.inf.tu-dresden.de/Anon\_Terminology.shtml, (2000)

\bibitem{diaz01}
Diaz, C., Seys, S., Claessens J., Preneel, B.: Towards measuring anonymity. In: Proceedings of Privacy Enhancing Technologies Workshop (PET'02) - Springer LNCS 2482. pp. 54-68, (2002)

\bibitem{serj01}
Serjantov, A., Danezis, G.: Towards an Information Theoretic Metric for Anonymity. In: Proceedings of Privacy Enhancing Technologies Workshop (PET'02) - Springer LNCS 2482. (2002)

\bibitem{shannon}
Shannon, C.: The mathematical theory for communicactions. In: Bell Systems Technical Journal. pp. 30:50-64, (1948)

\bibitem{yuxin}
Deng, Y., Pang, J., Wu, P.: Measuring Anonymity with Relative Entropy. In: Proceedings of the 4th International Workshop on Formal Aspects in Security and Trust (FAST'06), Lecture Notes in Computer Science 4691. pp. 65-79, Springer, (2007)

\bibitem{combinatorial}
Edman, M., Sivrikaya, F., Yener, B.: A Combinatorial Approach to Measuring Anonymity. In: In Intelligence and Security Informatics. pp. 356-363, (2007)

\bibitem{revisiting}
Gierlichs, B., Troncoso, C., Diaz, C., Preneel, B., Verbauwhede, I.: Revisiting A Combinatorial Approach Toward Measuring Anonymity. In: Workshop on Privacy in the Electronic Society (WPES 2008), V. Atluri and M. Winslett (Eds.), pp. 111-116,  ACM Press, (2008)

\bibitem{berthold}
Berthold, O., Pfitzmann, A., Standtke, R.: The Disavantages of Free Mix Routes and How to overcome them. In: Hannes Federath (Ed.), Proceedings of Privacy Enhancing Technologies Workshop (PET'01), Lecture Notes in Computer Science. pp. 30-45, Springer-Verlag, (2001)

\bibitem{reiter}
Reiter, M., Rubin, A.: Crowds: Anonymity for Web Transactions. In: ACM Transactions on Information and System Security. vol. 1, no. 1, (1998)

\bibitem{vernier}
Vernier, D., and Gastineau, J.: What are Mean Squared Error and Root Mean Squared Error? Article \#1014. http://www.vernier.com/  (2011)

\bibitem{jianhua}
Jianhua, L.: Divergences Measures Based in Shannon Entropy. IEEE Transactions on Information Theory. vol. 37, no. 1 (1991)


\end{thebibliography}






