Quantum Cryptography

(Towards ultra secure encryption)

Quantum Cryptography harnesses the Heisenberg Uncertainty Principle to define Quantum Key distribution (QKD), for guaranteeing secure communication between 2 parties. It allows the 2 parties to generate a shared random key for encryption & decryption.
It is important to notice here that the state of photon is used to produce the random bit string. As the photon can be measured only once, an eavesdropper can’t measure that and is unable to get the key. Huge no. of keys are produced per second, so the chance of getting required key information is insignificant or very limited.

By harnessing this uncertainty, we create a data-encryption scheme that's essentially unbreakable, called quantum cryptography. Quantum cryptography, uses quantum mechanics to guarantee secure communication. Any two parties can produce a shared random key known only to them to encrypt and decrypt messages between them.

Heisenberg Uncertainty Principle

This principle states that locating a particle in a small region of space makes the momentum of the particle uncertain; and conversely, that measuring momentum of a particle precisely makes the position uncertain.

Qubit Concept

As classical computer uses binary values of 0 and 1, a qubit can exist in 0 or 1 or a superposed value of 0 or 1 also. “Superposed value” means it can be in both the state of either 0 or 1 until the time its value can be measured or when the “qubit” comes to the actual value.

Example:- Schrödinger’s Cat Example
This example supposes that there is a box with a nozzle having a random probability of releasing poisonous gas. A cat is put inside the box. If the gas is released, then cat dies representing state 0. If gas is not released then cat is alive representing state 1. But when the cat is inside the box and we don’t know whether the gas is released or not, according to qubit concept, the cat is both dead AND alive in the box UNTIL we look inside the box to be sure or when qubit narrows down to the actual value.

Why Quantum Encryption is said to be unbreakable or ultra – secure?

Two particles of qubits in a quantum computer system can be entangled. States of the two particles rely on each other irrespective of the distance between them. Such entanglement is a key factor in the computations that is achieved with a quantum system. This property makes a quantum computer to guarantee integrity and an easy system to corrupt through malicious attack.


Attacks that can be made

Laser diodes used to transmit keys , sometimes transmit more than one photon at a time. A hacker could monitor the second photon, leaving the first photon without alerting anyone that the key transmission has been compromised.

Remedy

Scientists have added decoy photons to the key data so that when eavesdropper tries to monitor extra photons, he will also monitor decoy photons. Decoy photons are weaker on average and hence very rarely contain two or more photons. If an eavesdropper attempts a pulse-splitting attack, he will transmit a lower fraction of these decoy pulses than signal pulses. Monitoring separately the transmission of the decoy and signal pulses, compromise can be detected. Hence transmission becomes very much secure.

Recent Developments

• A encrypted quantum key transmitted over a distance of 184.6 km by researchers in the US, based at the Los Alamos National Laboratory (LANL) in New Mexico and the National Institute of Standards and Technology (NIST) in Boulder, Colorado.
• They used Transition-Edge Sensor (TES) technique which detected 65% of received photons, than the conventional photo diodes which detected 20% of photons.
  

Challenges

• Very nascent technology
• Very less commercial interest presently, although interest is increasing day by day by corporate & government agencies.
• Only be beneficial where protection of critical information is required.
  

Unravelling the mystery of PageRanking!

Well, to start with, there is a lot that goes into building a state-of-the-art ranking system. Mr. Larry Page, the co-founder of Google search engine says, "it [the ranking system] takes exactly what you mean and gives back exactly what you want!" (with faster response times, greater scalability, lower costs).
To understand how search engines work, let's get a brief idea of the technologies employed for the purpose:

1. Information Retrieval

It relates to querying of unstructured textual data. Information is organised into documents, documents into unstructured data. To make it clear, each HTML page is considered to be a document.
Documents have associated with them a set of keywords, and then a search is made to locate relevant documents based on user input, for example: the basis of keywords which is also called Keyword-based Information Retrieval. This type of information retrieval can be used for retrieving textual, audio and video data.

2. PageRank Technology

Even though the pages have fewer links to them, but if the links they have are much higher valued, then those pages receive a higher PageRank and are more likely to appear at the top of the search results, having greater importance and relevance. This technology is also referred to as Popularity or Prestige Ranking.

High PageRank does NOT guarantee a high search ranking for any particular term. If it did, then PR10 sites like Adobe would always show up for any search you do. They don't.

However, there are many sites such as home page servers in Universities and Web portals, that host a large number of mostly unrelated pages. For such sites, the popularity of one part of the site does not imply popularity of another part of the site. So, an alternative requires transfer of prestige(importance value) from popular pages to pages that they link to!

Google interprets a link from page A to page B as a vote. Votes cast by pages that are themselves "important" weigh more heavily and help to make other pages important. A hyperlink to a page counts as a vote of support. No links to a web page means no support for that page.

PageRank theory holds that even an imaginary surfer who is randomly clicking on links will eventually stop clicking. The probability, on any step, that he will continue is a damping factor 'd' which is generally assumed to be set around 0.85 .

An algorithm has been defined to calculate the relative relevance of a web page that is going to fulfill a user's query:

PR(A)= ((1-d)/N) + d((PR(B)/L(B)) + (PR(C)/L(C)) + ......)

where d is the damping factor, N is the number of documents in collection and L(X) is the number of links from page X.

Uses of PageRanking

1. In PageRank terms, academic departments link to each other by hiring their faculty from each other.
   
2. A Web Crawler may use PageRank to determine which URL to visit next during a crawl of the Web.
   
3. PageRank may also be used as a methodology to measure the apparent impact of a community like the Blogosphere on the overall Web itself.

3. Hypertext-matching analysis

The technology analyzes the full content of the specific page along with the neighbouring web pages to ensure that the results returned are the most relevant to the user's query.

So, the inference drawn from the aforementioned revolves around 3 major aspects:

Best locally relevant results are served globally: It is ensured that no user query is left behind.

Keeping it simple: For a wide variety of user queries, there has to be a response in multiple languages. Even then, the system has to be made simple and understandable.

No manual intervention: No editing being done manually.The final ordering of the results must be decided by the algorithms alone.

Quantum Computing

This article highlights about the revolutionary concept in computing field called the Quantum Computing. It examines the possibility of computing at the quantum level, that is at the level of atom and molecules size.

Key Objectives:

· To harness the power of atoms and molecules.

· To perform calculations billion of times faster than today’s silicon based computers.

· Quantum properties of particles can be used to represent data structure.

· Quantum mechanics can be used to perform operations with these data.

Current Technology :
· We use silicon based computers
· Information is stored in form of 0’s and 1’s
· Bit System is represented as Yes or No, True or False, High or Low.
· By the use of Optical lithography techniques, we are able to pack more transistors on a Silicon based semiconductor chip making the processors more faster every year.
· Based on Moore’s Laws (Proposed by Intel’s Co-founder Gordan Moore in 1965).

Moore’s Law :

1. Processing power (no. of transistors and speed) of computer chips was doubling every 18 months or so.

2. With the increase in processing power the size of each transistor gets reduced.

Limitations of Moore’s Law :

If Moore’s Law continues unabated, each transistor would be as small as hydrogen atom by the year 2030, where quantum nature of electrons become significant and will generate errors in computation process.

This is due to the Wave-Particle duality principle as stated by Louis De-Broglie in 1920 : “As object approaches to atomic level, it begins to show dual nature given as : λ = h/mv”

However it is possible to exploit this quantum nature to do high computation by applying quantum mechanics on computers

Definition:

A Quantum computer is any device for computation that makes direct use of distinctively quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. In a classical (silicon based) computer, the amount of data is measured by bits, but in a quantum computer, the data is measured by qubits.

The basic principle of quantum computation is that the quantum properties of particles can be used to represent and structure data, and that quantum mechanisms can be devised and built to perform operations with these data.

Bit system

Ø Yes or No
Ø True or False
Ø High or Low
Ø 1 or 0
v Includes only Boolean AND, OR and NOT function

Qubit System

Ø Shade of Yes or No
Ø Intermediate states of True or False
Ø In-between states
Ø Combination as 00, 01,10, 11
v Includes Boolean XOR, XNOR, etc.

“300 qubits can store more than 10⁹⁰ numbers simultaneously which is more than no. atoms visible in universe. This shows the power of quantum computers.”

Representation of Qubit in computers :

· Ion traps
· Nuclear magnetic resonance
· Quantum dots

Quantum Phenomenon :

· Quantum parallelism
· Quantum interference
· Quantum entanglement
· Quantum teleportation

Applications in quantum computer

· Molecular stimulation:

Quantum computer can stimulate chemical interactions allowing chemist to learn more about product interaction. Pharmaceutical research will be able to benefit a lot from this development.

· True randomness:

Quantum computers can generate random numbers with true randomness giving more accuracy in program processing

· Representing data structure:

Qubits can be used to represent data structure such as linked list in a more modified way taking less memory and process with high speed using XOR function.

· Encryption technology:

Encryption schemes currently taking million of years to guess can be checked by quantum computers within a year

· Ultra secure, super dense, communication:

Qubits can allow more information to be communicated per bit than same number of classical bits.

· Improve error correction and detection:

Recovering the information from the noisy transmission path will be faster and accurate.

Recent Developments:

· In 2005, researchers at the University of Michigan built a semiconductor chip which functioned as an ion trap. Such devices, produced by standard lithography techniques, may point the way to scalable quantum computing tools.

· On 13 February, 2007 D-Wave Systems Inc. (dwavesys.com) ran an initial demonstration of their Orion quantum computing system, which is built around a 16-qubit superconducting adiabatic quantum computer processor.

· Very recently, many researchers have begun to investigate the possibility of using quantum mechanics for hypercomputation - that is, solving undecidable problems.

Vehicle Tracking System using GPS

As it has always been a logistic nightmare to track out the vehicles on the way. In order to solve this problem of tracing out the vehicles on the way a vehicle tracking system based on Global Positioning System (GPS) has been devised. The system uses Global Positioning System as its base technology. For the communication purpose the system is set to be configured with the available terrestrial network.

Working of GPS:

The feasibility studies were started in 1960’s. The Pentagon appropriates funding for this system in 1973 and the first satellite related to this topic was launched in 1978, and the system declared fully operational in 1995.

The official name of the system was NAVSTAR GPS (Navigation Satellite Timing And Ranging Global Positioning System) and is developed by US Department of Defence. The Global Positioning System is a worldwide positioning system based on the functioning of the 29 satellites. These satellites keep transmitting the signals at a particular frequency to the earth. The GPS listeners, on earth tune to that particular frequency and listen to the signals sent by the satellite. For positioning any device which is equipped with the GPS listener, signals from three or more satellites is required. The signals from three satellites determine the latitude and longitude of the device on the earth. But the signal from four satellites determines the latitude, longitude and altitude of that device on the earth. More the signals from the satellite more will be the accuracy of the position of the device.

Use of GPS for vehicle tracking system:

For locating or tracking the vehicles, the system uses the GPS as its base technology to locate the vehicle on the earth. For this the vehicle is equipped with the GPS listener. Once the vehicle is located on the earth then the next step is to send this information to the control centre for the mapping of the vehicles. That’s here the terrestrial network comes into scene. The system uses the terrestrial network such as the available CDMA or GSM mobile network for communicating with the control center.

Once the vehicles is located then it is it sends its information such as the latitude, longitude, altitude, speed(derived), etc. to the terrestrial network. The terrestrial network then sends this information to the control center where the vehicle is mapped on the electronic map on the computer. If there is some information that is to be send to the person in the vehicle then it is sent to the terrestrial network. The terrestrial network sends this information to the device in the vehicle. For this the system use the Short Messaging Service (SMS), thus the information that is sent by the control centre to the person in the vehicle appears as SMS to him. Thus, it is fully two way communications between the control center and the device.

The location is represented by the Position Fix. A position fix is based on real – time satellite tracking and is defined by set of co-ordinates. It changes as the GPS receiver moves. Position shows the approximation of the receiver’s true location.

The path which the receiver must follow is denoted by the waypoint. A waypoint is the set of co-ordinates entered into the receiver. The position fix is matched with the waypoint within some allowed error limits. If it is within the error limits, the vehicle is following the correct path unless it is on wrong path and the control centre is sent information about this.

A phenomenon called Ajax

Web applications have evolved a great deal over time. But it wouldn't be wrong to say that the most remarkable transition in web applications is what we've been experiencing in the last few years. This new emerging phenomenon is, what people call, the Web 2.0

For most of the history of the web, client side development has been seen as a lesser technical task. Most (all?) of the power of web based applications was concentrated at the server and the client was pure HTML which basically tells that this particular image or text should be displayed on the screen in this way. This was because most of the users were not on high speed connections or the application tasks required a lot of computing power which clients could not manage or maybe because the data and the logic had to be kept secret. This so called thin-client/fat-server architecture led to an entirely new user interface for web applications which was quite different from the user interfaces provided by desktop operating systems.

Some of the technologies comprising the Web 2.0 intend to change that user interface. One of them is called Ajax, an abbreviation for Asynchronous Javascript and XML. Ajax put the aspect of programming back into client-side rather than the mere markup it used to be. Now what do I mean by those keywords? Let me elaborate.

Ajax is a technology which can be used to give web-based applications a desktop-application like responsiveness and capabilities. Let me take the example of GMail, the poster boy of Ajax. Most of you have used GMail as well as other web based email clients like Yahoo! Mail and Hotmail. One of the difference between them is that GMail (once loaded) appears more responsive and fast, than others. When you click on a message, it loads and shows the message, without the whole page reloading again. This is achieved using some clever javascript programming on the client side by which requests to the server for data are sent in the background (Asynchronously) while normal user interaction can continue in the foreground. When the data fetching completes, the new data is displayed by javascript inside the page without initiating a page reload or refresh.

So how does XML come into the picture? XML (eXtensible Markup Language) is the data format in which the data is usually sent to the client side from the server. A javascript function receives the data, parses it into a DOM (Document Object Model) and renders it on the screen. Too many keywords, eh?

Once again client side programming is fun and new innovative applications of Ajax are coming up fast. Ajax powers various Maps' applications such as Google Maps and Onyomo Maps. Services like Windows Live, Yahoo Mail Beta, Google Suggest and our very own Indian Onyomo.com all utilize the power that Ajax offers. Interesting to note is the fact that the technologies that comprise Ajax viz. Javascript and XML are older than the concept of Ajax. GMail showed the world that they can be combined into a potent combination which can power an entirely new breed of innovative web applications which are more responsive and more desktop like (a capability hitherto difficult to achieve).

The subject is vast and time constraints do not allow me to delve into a lot of detail at the moment. But in case people are interested I may come up with specific tutorials and examples. You can find a lot of resources on these topics simply by googling them.

Since I haven't introduced myself yet; I am Shalin Shekhar Mangar, a final year student of JSS Academy of Technical Education, Noida. I have recently joined a IIT-Delhi based startup called Onyomo.com

What is cryptography and how can it help you?

What is cryptography (or cryptology) ?
cryptography n. art of writing or solving ciphers (a secret or disguised writing)

It protects a message or file from being read by an eavesdropper (one who listen to a private conversation) who has no other means of access to either the original text of what is protected, or the key with which it is encrypted.

How does cryptography work?
You use a program to encrypt it; the program will change the letters into symbols and other weird characters, so when someone opens the file they cannot read it. If you encrypt something and send it to someone the other person will need to have the program to decrypt it.

What can I encrypt?
You can use it to encrypt your e-mail that prevents people from reading it in transit. You can use it to protect the entire contents of your hard disk by encrypting everything. But if you use the Internet, there is at present, no encryption technique available to prevent your ISP (Internet Service Provider) from monitoring your connection, and seeing what web sites you visit. Theoretically, however, you could make a secure connection with your browser to a web site that then serves as a browser, accessing web pages for you that you request, and then sending them to your browser in encrypted form. There are anonymizing services on the Internet for other functions, but these services have been subjected to legal action at times, and required to give up their logs.

Since the Internet is terribly new and complicated, the issue involved can be made clearer by illustrating it in terms of older technology. You can use a code, or a voice scrambler, to keep someone eavesdropping on a telephone conversation of yours from understanding what you are saying.

Email Spamming

Today in every part of the world, millions of internet users are checking their inbox every second. And these people must be aware of most effective internet problem. Can you guess it?

No!
Its Ok.
I tell you.
The problem about which I am highlighting here is of receiving mails from unknown person or organization. In internet language, such mails are termed as SPAM.
Spam is basically message that is related to earn quick money, winning a jackpot and travel trip, advertising different products or some sex-related materials. Such mails are really unwanted and those who send them are called spammers.

Why the name ‘SPAM’?
‘SPAM’ was the first canned meat product that did not require refrigeration introduced in 1937. But why these unwanted mails are termed as spam is unknown. Or, it may come when some Vikings of Monty Python, highly influential team of British and American television comedians who later branched out into films, overshadows other words by shouting the word ‘spam’ excessively. Actually, internet spam do the same task, it overshadows other mails in the inbox and thus occupy unnecessary bytes.

Programming and Girls

So what happens if you-the-geek goes up to your girlfriend (wait! a geek who has a girlfriend? ahem!) ? She says "Ya [your_name_here_o_geek_god], I know it's good for me. But I don't know anything!"

Hmm. Don't worry, it's the same ol' story everywhere and let me tell you; people, all the world over, are debating about how to get more women into computer science. So what steps can we take to bring our favorite girls (comeon, you can't leave me out just because I don't have a girlfriend!) to the fantastic world of programming and computer science in the real sense of the word. Let me forewarn you, the journey is tough and filled with terrors unforseen; of missing (mis-placed?) semi-colons and strange un-decipherable (un-compilable?) code.

So how did we become good programmers? Ofcourse I know the code runs with the blood, and the neurons function in harmony to move our fingers on the keyboard. And the code? what code? it's a direct brain-se (like dil-se) to the computer. Oops, I just got carried away. Flashback...yeah girls and programming. It's something like language and mathematics. You need to learn the nuances of the lingo and become expert enough to be able to express the delicate and precise balance of a mathematical equation. You miss a plus or a minus and it does not compute. You forget to place the equals sign and the stupid compiler can't understand a thing. It's like teaching a child to stand on his/her feet, to walk, to run. We practiced hard enough day and night to reach this kind of dexterity and everybody else must do the same.

It helps an awful lot if you're good at language (an area where girls are better than us, and don't kill me for saying this boys). And it helps an awful lot if you're good at mathematics (no boy, you're looking at the wrong place for a compliment). And remember, 'Practice makes a woman perfect'.

Ok, it's late at night and I need some sleep (yes, geeks do sleep sometimes). I'll wait for the first non-male (ofcourse I mean female by that) comment on this post to continue this geek-talk. And she'll also get a cadbury's eclairs from my side if possible :-)

Coming up next:

• A survival guide to programming for newbies.
• What will I get from a programming contest (I can never win against those #*#$)?
• ... (that's a secret)
• ... (will tell you about this only if you sign a non-disclosure agreement with me)
  

Disclaimer: If you're a girl, please don't mind; and If you do, please try to find a way to forgive me. After all all this is just some crazy geek-talk, right? ;)

Geek Learning Painting!!!

I have decided to learn painting! And the decission has no inspiration from anyone's advice. It was completely on my part. Surprissed!
Everyone was surprissed with my decission, my mom, my sis and even the the arts teacher with whom I met today for learming painting was laughing in surprise. After all a techie learning painting is not something you encounter that easily!

I have been thinking of doing something which I have never done in my life. Something which I have never tasted in my life. Something which I may start from the crap. Something in which Im dummey. Of course there are tons of such things and I want to do many of these. To keep things simple I decided to start with such a thing.

I saw the painting by my sis when sitting in my drawing room and the great idea of me painting such a canvas flashed in my mind. A scenery with signature Saurabh. How is the idea! Brilliant!

I will be going to painting classes from tomorrow. I think learning painting by investing 6 hours a week when you have 168 hours to waste every week is a fair deal. Let's see how is atmosphere there. Meet the people there.

Insight into DP & BFS

Hmmm, thanks to two nice problems, I got some valuable reading of Dynamic Programming and Breadth First Search [Trees].

562. Dividing Coins
I did this program, I didnt even use recursion, yet I think the technique is called Dynamic Programming. From Cormen, I found out that the problem is similar to 0-1 Knapsack problem, and Shalin Bhaiya confirmed the same. However, I think the method I followed made the problem even simpler than 0-1 Knapsack.

439. Knight Moves
This was the TKP problem I was talking about. Used a BFS algo, but however, I didnt exactly use a tree. I used a queue instead. I wonder what is the method I used.. I mean whether what I did comes under DP or not, whether it is indeed BFS or not... Anyway, having done this program gives me tremendous confidence!