Minority aspirations and the failed democracy..

I usually don't write about politics. But I couldn't help writing about this one.

The following figure shows the vote distribution of the recently concluded presidential election.

(Source: http://www.srilankanelections.com/)

For me, the green districts (in north and east) do not mean that MR lost or SF won (barring some green spots in the hill country, Colombo and some more urban areas); but rather they mean that minority aspirations are not met by the government ruled by the majority. Look who are living in these areas; either minority Tamils or Tamil-speaking Muslims. If we look at the world history, it is a usual thing that the majority is not sensitive to minority issues. The real challenge is whether MR can reverse this and be sensitive to minority issues. I think it'll take lot more to heal the ethnic division than winning the war. That's when I will say Sri Lanka has real peace. I hope that day is not far away.

Update [2/2/2010]: First of all, I am neither supporting nor in favor of any political party or any political leader in Sri Lanka. From the point of view of democracy, MR should not be allowed to extend his next term more than what is stipulated; it is he who called for an early election (which should not have been done in the first place; if he's truthful, not power hungry and had no hidden agenda, why an early election??) and there should be consequences for it. But to my disappointment, he's allowed to extend his tenure by almost one year. I don't know much about politics, but I know that when a country does not have a strong opposition (like the current situation), it is unfortunate that, at the end of the day, it's the civilians who have bear the consequences.

Update [2/8/2010]: It is disturbing to hear that SF has been arrested. As I mentioned before I am not a supporter of SF, but where is democracy?? Would he be arrested under war crimes, had he not stood against MR?? (A few days before, some army officials were also fired under the same ground.)

First they came for the communists, and I did not speak out—because I was not a communist;
Then they came for the trade unionists, and I did not speak out—because I was not a trade unionist;
Then they came for the Jews, and I did not speak out—because I was not a Jew;
Then they came for me—and there was no one left to speak out for me.
~ Martin Niemoller

Substitute the above with brave journalists, impartial news papers and other media, people who questions the current ruling party, etc... is the history repeating??

How unique/trackable is your browser?

I've just got a "fingerprint" of my browser through the Panopticlick tool. The result is as follows:

Your browser fingerprint appears to be unique among the 389,007 tested so far.

Currently, we estimate that your browser has a fingerprint that conveys at least 18.57 bits of identifying information.

This is a worrying fact; browser fingerprint is a very effective way of tracking users in the Internet. Why should you take defensive measures against such tracing down? This clearly invades your privacy. You probably don't want someone to profile your online trace without your consent or knowledge. If your browser sends out too much unnecessary information (increasing the likelihood of uniqueness), multiple visits to not only the same site but also different sites can be linked. So, with these fingerprints, systems providing anonymous access to digital content, digital cash become ineffective since these methods make an implicit assumption that the attacker does not use the background information available through the communication channel itself.

It should be noted the same browser fingerprinting technique is used to provide protective measures as well. For example, my bank won't ask for additional credentials when I log through the browser I use everyday, but when I log in from a new browser/new location/new computer, they will ask for additional credentials. The challenge is to protect user privacy without compromising security.

Another challenge is to protect user privacy without limiting the usability. For example, one technique to minimize the risk of fingerprinting is to disable java scripts, but most sites require java scripts to work.

Update [2/2/2010]: The above work allows to identify browsers, but not exact users. Researchers from the Isec lab have devised a method to identify users using social network group membership as background knowledge. It's a two step process:
1. Generate a group membership fingerprint for each users (their thesis is that the collection of groups a user is member of is more or less unique).
2. User history stealing technique to identify the links the user previously visited. Their TR is available here (A practical attack to de-anonymize social network users).

ZERO: How was it discovered?

The history behind the concept of zero is an interesting one. We are so used to the number zero that we cannot live without it (what if a zero is dropped from your salary and appended to your electricity bill ;).

On a serious note, in the early history of counting, the number zero neither required nor well understood; and the same with the negative numbers. why? early mathematics was based on counting real things as opposed to abstract ideas. It is fascinating to see that things, like the concept of zero, we take for granted took centuries and many great minds to discover. The following time line of historical events is an indication of this fact. I hope this will be a good reminder to all of us that we will never achieve perfection and we progress through our mistakes/needs. No mistakes/needs, no progress!

3000 BC [3] : Sumerian numerical system - Separated numbers from goods, but no concept zero (zero loaves of breads, zero cows, etc. did not make much sense at that time :D). Some details of their progress:
Version 1: Different types of goods were represented by different symbols, and multiple quantities represented by repetition.
Examples: two units of grains was represented by two grain-marks. Four oil cans was as four oil-can-marks.
Version 2: Separated the quantity of the good from the symbol for the good. That way a great amount of redundancy was prevented. They introduced a sexagesimal system (that is, base 60). Not sure why it's base 60 instead of any other base.
Example: two units of grains as the symbol followed by the symbol of grain.

(Sumerian system)

Around 3000 BC - Egyptians introduced the earliest fully developed base 10 numeration system. It's not a positional number system as the decimal number system we have, but it can represent large numbers. (For example, to represent 45, they used 4 number 10 symbols and 5 number 1 symbols) Similar to Roman numerals.

(Egyptian hieroglyphics)

Egyptians also did not have the concept of zero since they also mainly thought numbers as concrete concepts for measurement of length, trading, etc. Still, I am amazed about Egyptian math; even without the concept of zero, they were able to build precisely calculated colossal pyramids and other structures. Also, through their math skill, they were one of the ancient nations who got close to calculating the correct number of days per year.

2700-2300 BC Sumerian/Akkadians invented the Abacus. They use it with their sexagesimal number system.


Babylonian number system [2]: First to introduce the place value system (just like the decimal number system we have) but still no concept of zero.
Sumerian number system still needed many symbols to represent numbers. Influenced by this number system, Babylonians, towards the end of the 3rd millennium, introduced the place value system. They just needed two symbols to count.

(Babylonian system)

700 - 400 BC - Use of zero to denote an empty position in the notational system.
Babylonians put two wedge symbols to where we would put zero in the decimal notation. These empty wedge symbols only occurred within a number (as in 5403 in decimal); never place at the ends (as in 5430 in decimal); zero was never used as a number, but rather as a punctuation sign.

During this time Greek mathematicians did not use a positional number system. They developed their theories/abstract concepts through shapes/geometry. It was during this period great mathematicians like Euclid lived. Even without the concept of zero, people like Euclid worked on number theory (which lead to the fundamental theorem of arithmetic, Euclidean algorithm, etc), but it was based on geometry. However, Greek astronomers used the notation of zero and it is believed to be similar to how we currently use zero. But they did not appear to have devised a number system based on zero.

(Euclid)

5th century - Indians (mainly Aryabhata) were the first develop a base 10 positional numeral system (remember Babylonians invented base 60 positional numeral system a long time before that) which resembles closely to our current decimal system. These dates are still disputed, but I think it's fair to credit Indians for the number system we currently have.

(Aryabhata)

People started to think about numbers as an abstract concept. As a result, the number zero as we use today was born.

7th century (dates are disputed) - The first appearance of zero as number by Indians. (There is some dispute about the origin as well - there appear to have some Chinese connection as well, but not sure about it)

876 AD - The first record of the Indian use of zero which is dated and agreed by all to be genuine.

Indians formulated arithmetic rules involving zero and negative numbers although they did not get it right in the first few attempts. Brahmagupta, in his book "Brahmasphutasiddhanta", got most of the arithmetic operations right except the division by zero: "0/0 is 0 and a number divided by zero is that number". For many centuries after this, division by zero remained a mistry to peope; they simply did not know how to explain it. During the same time, Islamic/Arabic mathematicians, especially, Al-Khawarizmi, studied Indian number system and contributed to the arithmetics with numbers. The combined work led to the Hindu-Arabic numberal system we are using today. In 12th centure, this system was spreaded to Europe mainly through the Italian mathematician, Fibonacci. There is no doubt that the development of zero is a very important milestone in human civilization and it paved way to many new concepts.

(There is evidence that in the 6th century, Mayans used a base 20 number system with a number zero. Also, they appear to have used the number zero a long before that. However, their knowledge has not influenced others.)

There have been many developments and rules about division by zero in the history, but let's not go into that. Currently we consider division by zero is undefined in any system that obeys the axioms of a field (e.g. real numbers, complex numbers, etc.).

In the 16th century, Newton and Leibniz, fathers of calculus, played a key role in understanding "division by zero" and its applicability to real life. Instead of considering absolute values, working with numbers approaching zero, they were able to develop a new branch of Mathematics, calculus. I think this is another very important milestone on the number zero.

At present, we cannot imagine Math, Physics, Chemistry or any other branch of scinece without having the value zero, yet it took many centuries to develop the idea of having a zero in the number system and people had been working with numbers well before zero came into picture. Empty sets (cardinality zero sets), zero gravity, freezing point, zero probability, accounting, modular arithmetics, calculus, Cartesian coordinate system, indexing are just name a few references.

We would not have progressed this far, had the concept of zero not understood.



References:
[1] http://yaleglobal.yale.edu/about/zero.jsp
[2] http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Zero.html
[3] http://it.stlawu.edu/~dmelvill/mesomath/sumerian.html

The 3rd data privacy day (Jan 28th)

Today is the data privacy day.

Interesting broadcast group key management schemes

In this post, I focus on some really neat broadcast group key management schemes/protocols (BGKM). The idea behind the schemes are based on quite simple algebraic constructs, but they are very elegant.

In addition to other properties, a good GKM scheme should provide the following two properties.
1. Forward secrecy - a user who left the group should not be able to access new keys
2. Backward secrecy - a user who joined the group should not able to access old keys

In my opinion, these are two most difficult properties to satisfy in a group communication setting. In order to satisfy these two properties, it is required to initiate a rekeying operation (i.e. change the existing keys). There have been many GKM schemes proposing various way of doing rekey operation. What set them apart is the communication cost of the rekeying operation. Earlier GKM schemes had O(n) communication overhead, where n is the number of users in the group. Later, it was improved to incorporate a hierarchy and the communication overhead was reduced to O(log n). Further, these rekeying operations are not transparent to users; every time a user joins/leaves, other users need to update their keys. Can we make the communication overhead to be O(1) (i.e. independent of the number of users in the group? This is where the BGKM schemes fit.

BGKM schemes make the rekeying operation transparent to existing users at the expense of additional computational cost at the server which manages the BGKM scheme. There are three noteworthy BGKM schemes which I will go over in some details giving the key ideas in the rest of this post.

1. The secure lock (SL) approach based on the Chinese Remainder Theorem (CRT) [SE 1989]
2. The access control polynomial (ACP) approach based on special polynomials [INFOCOM 2008]
3. The access control vector (ACV) approach based on matrix null spaces [ICDE 2010]

1. The Secure Lock (SL) approach
(Slightly modified the original version)
Each user u_i is given a random secret value s_i and a unique secret number n_i at the time of joining. These n_i's are relatively prime in pairs. The server construct the following congruences and compute the common solution using the CRT and broadcast to the group whenever there is a leave or join.

x ~ r_1 (mod n_1)
x ~ r_2 (mod n_2)
...
x ~ r_n (mod n_n)

where ~ is the congruence symbol, r_i = K XOR s_i, K is the actual key. (r_i < n_i)

Then construct the common solution, using the CRT:
x ~ \sigma{i=1}{n} N/n_i * r_i * f_i (mod N)

where N = n_1 * n_2 * ... * n_n,
f_i ~ N/n_i (mod n_i).

Let the standard representative of the common solution is C.

A user u_r with the secret s_r and the public value n_r derives the key by (C mod n_r) XOR s_r. (Note that C mod n_r gives the value r_r)

Can a newly joined user u_r get its hand on old keys? No, because the old common solution did not consider the congruence x ~ r_r (mod n_r).

Can a user u_r who left the group access new keys? No, because the server removes the congruence x ~ r_r (mod n_r) from the CRT calculation.

2. The Access Control Polynomial (ACP) approach
Each user u_i is given a random secret value s_i at the time of joining. The server construct the following polynomial of order m+n and broadcast to the group whenever there is a leave or join.

f(x) = K + (x - H(s_1 || z))(x - H(s_2 || z))..(x - H(s_n || z))(x - H(a_1 || z))...(x - H(a_m || z))
where K - is the actual key, s_1,.., s_n are the random secret values given to n users, a_1,.., a_m are random fake values used to increase the entropy of f(x), z is a public random value, H is a hash function.

A user u_r with the secret s_r derives the key as f(H(s_r || z)).

Can a newly joined user u_r get its hand on old keys? No, because the old polynomials f`(x)'s do not have (x - H(s_r || z)).

Can a user u_r who left the group access new keys? No, because the server removes (x - H(s_r || z)) from the new polynomials f`(x)'s.

The scheme is quite simple. However the security of this scheme is neither formally analyzed nor proved.

3. The Access Control Vector (ACV) approach
Each user u_i is given a random secret value s_i at the time of joining. The server construct the following the matrix X of n by n + 1 and broadcast a vector created based on a random vector from the null space of X to the group whenever there is a leave or join.

X =
| 1 a_{1,1} .... a_{1,n}|
| 1 a_{2,1} .... a_{2,n}|
| ..................................|
| 1 a_{n,1} .... a_{n,n}|

where a{i,j} = H(s_i || z_i), H is a hash function, z_i's public random random values, s_i is the random secret value given to the user u_i.

The null space of such a matrix is always guranteed to be nontrivial (each row is linearly independent). Hence, there exists a non-trivial colomn vector Y such that XY = 0. The server picks a random vector Y from the null space and compute the ACV (Access Control Vector) and broadcasts.

ACV = (K, 0, ..., 0)^T + Y

A user u_r with the secret s_r derives the K by performing a dot product of ACV and KEV_r (Key Extraction Vector). A user can construct her KEV using her secret and public random z_i's as follows.

KEV_r = (1, H(s_r || z_1, ...., H(s_r || z_n))^T

Can a newly joined user u_r get its hand on old keys? No, because the vector Y in the old ACV's are not orthogonal to her KEV, dot product does not yield the key K.

Can a user u_r who left the group access new keys? No, because the server removes the corresponding row from X, now the vector Y in the new ACV's are not orthogoal to her old KEV.

The scheme is quite elegant. The security of this scheme is analyzed and proved. A downside of this approach is the computational cost at the server when the group size is large.

'Sights unseen' photography

When I first saw the subject of an ongoing photography exhibition 'sights unseen' in the news, I was so exited and was like 'this must be a collection of really cool photos I have hardly seen before'. But my first impression about the exhibition was wrong. However, I found it not only EVEN MORE exciting, but it's inspiring! It's a collection of really cool photos taken by people who are not fortunate enough to see. This bbc audio slideshow tells it all.

(A photo taken by a blind person)

All this time it was wired into my brain that, if you are blind you cannot take photographs. I was proved wrong! And it goes well with good old proverbs.

As I was Googling about the subject, I found the link that photography can be a tool for social change quite interesting.

"Never, never, never quit"

I truly admire the spirit of this story. Life is full of challenges; stories like this (and also this) remind us that we can overcome those challenges if we believe and act. Some people may not end up being the winners always, but we have to admire their spirit.

Effects of the failed christmas bomber..

(Source: http://www.cartoonistgroup.com)