Posted in July 2015
What is Privacy?
Over the past couple of years, “privacy” has received widespread media coverage. Some people say that if one does not have anything to hide, then there is no need of privacy. A lot has been written about the amount and kind of data collected by corporations. It is said that there is no need to worry as only metadata is collected and not the data itself. What it really means is that, users have lower level of protection by law as compared to a situation where data is being collected. In an earlier article here I have written how metadata can sometimes provide more information than the data itself. But what is “privacy”?
The first legal article on privacy titled “The Right to Privacy” was published in 1890 by Samuel Warren and Louis Brandeis. In this article they discuss privacy as the “right to be let alone”. They also mention “Numerous mechanical devices threaten to make good the prediction that ‘what is whispered in the closer shall be proclaimed from the house tops.’” In the same year William James addressed the idea of being able to present ourselves to different people by withholding private information.
Another way of looking at privacy is by using the metaphor used by Erving Goffman in his book “The Presentation of self in Everyday Life”. He writes that society is a stage in which we are actors. But as with most stages, there is a backstage, an area which is invisible to the public, where we do things not to be presented to the public. Privacy plays the role of allowing us to prepare for the presentation before going on to the stage.
Stephen B. Wicker mentions that privacy could be thought in terms of observability and controllability in control theory. Controllability denotes acquiring enough information so that the system can be driven to the desired state. An example would be personalized advertisement. If the advertiser has enough information about the person, then the advertisements viewed by the person would be suited to the needs and the advertiser would reap benefits.
In 2009, Helen Nissenbaum wrote a book “Privacy in Context” in which she introduces the idea of contextual integrity. She maintains that we control the personal information we want to hold by having a boundary. In addition she uses the metaphor of a zone of seclusion, in which the control is handled differently depending on the context and the person’s perception of solitude. This includes that the person is able to exercise various thoughts without worrying of censure.
Post-Quantum public key cryptosystems
Public-key cryptosystems, such as RSA, Diffie-Hellman and Elliptic Curves, which are in use today are based on Integer Factorization Problem (IFP) or Discrete Log problem (DLP). Their strength lies in the difficulty of determining the private key when the public key is known. These algorithms are part of internet standards, for example TLS and GPG, and are used for key exchange. But these algorithms can potentially be broken in polynomial time by Shor’s algorithm if quantum computers become operational. This means we need to look for cryptosystems which will not be susceptible when attacked using quantum computers.
In 1978, two years after the publication of the seminal paper by Diffie and Hellman on the use of private and public keys for cryptography, McEliece proposed a public key cryptosystem based on algebraic coding theory. In this system, a generator matrix is used as the private key and a transformed version of it as the public key. The security of the system lies in the hardness of decoding a large linear code with no visible structure. An attacker would is forced to use syndrome decoding while the person in possession of the private key could use fast decoding algorithms. The original McEliece cryptosystem, based on binary Goppa codes, has not yet been broken in polynomial time. The main advantage of this system is the fast encryption and decryption mechanism, which is two or three magnitude faster than RSA. One might wonder why this algorithm has not found widespread implementation yet. There are two disadvantages which are the main reasons for the lack of popularity of this system. First, the key size is very large and second, information rate is very low (k/n = 0.5, which means there are as many redundancy bits as information bits). This increases the bandwidth required which makes the system prone to transmission errors. The original system required public keys of size in the order of hundreds of kilobits while RSA uses a key size of 1024, 2048 and 4096 bits.
Researchers have been working to reduce the key size of the McEliece cryptosystem so that it can be used in practical applications. To reduce the key size many alternatives to Goppa codes have been proposed. One such alternative is based on Low Density Parity Check (LDPC) codes. Though it seemed to be an attractive alternative, it was possible to search for low weight codewords in the dual of the public key. In order to counter this weakness the use of Quasi-Cyclic LDPC codes has been proposed. QC-LDPC is an effective alternative to reduce the size of public keys of McEliece cryptosystem. This system requires a public key of size about 50 kilobits to achieve a security equivalent of 2048 bit RSA. This is a reduction of key size by a magnitude of ten from the original McEliece cryptosystem while maintaining the advantage of fast encoding and decoding.