Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. Elliptic curve cryptography (ECC) was first proposed in 1985 independently by Victor Miller and Neal Koblitz.

Public key cryptography is based on the creation of mathematical puzzles that are difficult to solve without certain knowledge about how they were created. The creator keeps that knowledge secret (the private key) and publishes the puzzle (the public key). The puzzle can then be used to scramble a message in a way that only the creator can unscramble.

Early public key systems, such as the RSA algorithm, used products of two large prime numbers as the puzzle: a user picks two large random primes as her private key, and publishes their product as her public key. The difficulty of factoring ensures that no one else can derive the private key (i.e., the two prime factors) from the public one. However, due to recent progress in factoring, RSA public keys must now be thousands of bits long to provide adequate security.

Another class of puzzle involves solving the equation ab = c for b when a and c are known. Such equations involving real or complex numbers are easily solved using logarithms. However, in a large finite group, finding solutions to such equations is quite difficult and is known as the discrete logarithm problem.

An elliptic curve is a plane curve defined by an equation of the form

y² = x³ + ax + b

The set of points on such a curve can be shown to form an abelian group (with the point at infinity as identity element). If the coordinates x and y are chosen from a large finite field, the solutions of the equation form a finite abelian group.

Elliptic curve multiplication - Diagram from Certicom ECC Tutorial.

The discrete logarithm problem on such elliptic curve groups is believed to be more difficult than the corresponding problem in (the multiplicative group of nonzero elements of) the underlying finite field. Thus keys in elliptic curve cryptography can be chosen to be much shorter for a comparable level of security.

The U.S. National Security Agency has endorsed ECC technology by including it in its Suite B set of recommended algorithms. You can read more here.