Harder Problems Make Better Solutions
Like builders of medieval castles, cryptographers try to build impenetrable "walls" to keep out intruders. Those walls consist of mathematical problems that would require years of computation on the world's fastest computers to solve. The tougher those problems, the harder it will be to break through the wall and steal data.
Most methods of creating hard problems - such as techniques that rely on factoring huge numbers - do so only most of the time; occasionally, they produce easy problems. Miklos Ajtai of IBM's Almaden Research Center has overcome that barrier, by devising a reliable way of generating an infinite number of extremely difficult problems. The advance could lead to more secure cryptographic systems and thereby improve the security of electronic transactions.
The work stems from the so-called lattice problem. Ajtai's method of generating problems uses an arbitrarily long string of random numbers to define a set of points, called a lattice, in a mathematical space that has as many dimensions as the total of random numbers in the string. The problem to be solved is finding some of the shortest line segments that could connect any two lattice points. As the number of dimensions increases, the problem's complexity grows so fast that it becomes essentially impossible to solve. In fact, nobody has found a general solution that applies to every possible lattice problem since the German mathematician P.G. Lejeune Dirichlet conceived the problem in 1842.
Ajtai's contribution has been to prove that essentially every problem generated by this method is very likely to be as hard to solve as the worst-case problem - the one that takes the longest time to solve. "This is counterintuitive," says Ajtai. "The reasons are given in a long, technically difficult mathematical proof. The proof shows that with a random lattice you can simulate any lattice, even the one for which the problem is hardest."
Since Ajtai's algorithm also creates its own solution to each problem, it could form the basis of authentication methods, such as identification schemes and digital signatures, for communication over electronic networks. "The work is now in the concept stage," says Ajtai. "It offers further security that can be imposed over the existing security system. At this point, it is impossible to say whether the work will supplement existing cryptography or replace it."
"This not only resolves a problem in pure mathematics that has occupied mathematicians for 20 years," adds Ashok Chandra, manager of computer science at Almaden. "It also provides a foundation for improved security, something that is increasingly important for commercial use of the Internet."
Speeding Up Gene Sequencing
Determining the chemical makeup of genes is a key factor in fields that range from medical research and pharmaceutical science to forensics and agriculture. The process, known as gene sequencing, involves identifying the order of bases - the chemical "letters" that make up the genetic code - in the strands of DNA that make up genes.
Sequencers start by using biotechnological techniques to replicate short lengths of DNA from a particular gene. Next, they apply enzymes to cut those pieces into shorter fragments of varying lengths, which they label with biochemical markers. To identify the specific bases in the fragments, scientists next place them in a gel to which they apply an electric field. Because each individual base carries a tiny electric charge, fragments of different lengths travel at different rates through the gel under the influence of the field. They disperse to form separate bands in the gel. Finally, the bands are read, using optical means, to identify the individual bases.
This method, known as gel electrophoresis, has one major drawback: It's very slow. Sequencing a strand containing just 700 bases can take up to six hours. Biotechnologists have devised several ways to speed up the process. Developments include new gels through which the fragments can move faster and the substitution of liquids for gels.
Those improvements face one problem. Because of the higher speeds that they permit, the bands in the gel become narrower. Reading them strains the limits of optics, because it can require resolution of less than half a wavelength of light. A new patent from IBM Research promises to overcome that difficulty and make possible sequencing speeds significantly faster than is feasible today.
The patent, by Kumar Wickramasinghe and Frederic Zenhausern of the Thomas J. Watson Research Center, relies on the scanning interferometric apertureless microscope (SIAM). This optical device appears to circumvent the laws of physics (although in reality it doesn't), because it permits scientists to view images far smaller than the wavelength of light.
U.S. patent number 5,538,898, granted in late July, specifies application of that technology to read the ultranarrow bands of bases in gels or liquids. "The patent covers any use of a near-field microscope to identify the code sequence of any biomolecule using super-resolution limits for any radiation," says Wickramasinghe.
So far, nobody has applied to license the technology. However, Wickramasinghe expects to receive inquiries. "Universities are pushing gene sequencing technology," he explains. "Berkeley, for example, is already at the optical limit." Meanwhile, the Watson team is carrying out its own studies. "We're doing some experiments with the technology to demonstrate that we can improve sequencing speed by a factor of a hundred," Wickramasinghe declares.
BM Researchers
Receive External Awards
Retired IBM Fellows John Cocke of the Thomas J. Watson Research Center and Reynold B. Johnson of the Almaden Research Center have received certificates of merit from The Franklin Institute, as part of its celebration of the 50th anniversary of the ENIAC computer. The Institute recognized Cocke for his work on Reduced Instruction Set Computer (RISC) architecture and Johnson for developing the first commercial magnetic disk mass data storage system.
Chandrasekaran Mohan, a computer scientist at Almaden, has received the 1996 Innovations Award from the Association for Computing Machinery Special Interest Group on Management of Data. The awards committee cited him for "truly outstanding" innovations that have "made a major impact in the database field."
Almaden scientist Frances Houle has been named a Fellow of the American Vacuum Society. She receives the honor for her contributions to means of modifying solid surfaces and thin films, particularly in electronic materials.
Watson researcher John T. Richards has received the Distinguished Service Award of the Association for Computing Machinery's Special Interest Group on Programming Language. The award recognizes his five years as chairman of the Object-Oriented Programming Systems Languages and Applications Steering Committee.
Academica Sinica, Taiwan's equivalent of the U.S.
National Academy of Sciences, has elected Chang C. Tsuei of Watson to membership, for his lifelong accomplishments in solid-state physics. His major contributions have occurred in high-temperature superconductivity. Two years ago, his team made a significant advance in that area, by designing and implementing a novel tri-crystal tunneling experiment. By revealing half-integer magnetic flux quanta, the experiment demonstrated an unconventional symmetry of superconducting electrons.
Anthony C. Lowe of Watson has been elected president-elect of the Society for Information Displays. He has been the society's treasurer for the past two years.
Nobel laureates J. Georg Bednorz and K. Alex MŸller of the Zurich Research Laboratory have received honorary degrees from the University of Regensburg in Germany. The degrees recognize their discovery of high-temperature superconductivity.
Optical Buses: New Vehicles
for Clustered Computing
Companies that can't afford their own parallel computers are opting for the next best thing: linking up several computers to work on the same problem simultaneously. Such "clusters" can consist of mainframes, midrange computers, workstations or even personal computers. "Virtually every IBM system is going to clusters," says John Crow, manager of optical communications at IBM's Thomas J. Watson Research Center.
For companies seeking really cheap supercomputing, the missing link has been an inexpensive means of connecting the elements in a cluster. Researchers from IBM's Thomas J. Watson Research Center, 3M and Lexmark International have now unveiled a prototype high-performance optical bus, officially named the Jitney Parallel Optical Interconnect, designed to fill that need.
The technology includes a transmitter module, a receiver module and a cable, consisting of 20 strands of optical fiber, that can transmit data at a rate of 1 gigabit per second over distances up to 50 meters. The cable comes from 3M, Lexmark worked on the plastic involved in the optical coupling and Crow's team integrated the components to create a compact, low-cost optoelectronic module.
Jitney has two advantages over conventional copper cable technology. It transfers data faster and
farther, in each case by a factor of about 10. Just as important, it costs 10 to 100 times less to transfer each gigabit. Research kept the price low by combining highly integrated optoelectronic chips with inexpensive plastic optics and
plastic chip packages.
The key advance was adapting the packages for optical use. According to Crow, this demanded extremely tight tolerances, which his team achieved with help from technologists in Bromont, Quebec. In practical terms, Crow summarizes, "With Jitney, you're giving customers the opportunity to make a supercomputer out of their office machines."
Deep Blue, Part Two
Now for the second round. Next May, 15 months after their epic first encounter, world chess champion Garry Kasparov and Deep Blue, the chess-playing parallel computer designed at IBM's Thomas J. Watson Research Center, will once more face off in a man-to-computer struggle for chess
supremacy. Last February, Kasparov recovered from a shock defeat in the first of six games to win the match
4-2 (
