New Technology for High-Speed Software Encryption
Business Problem
As the demand for encryption expands from defense and financial applications to larger professional and consumer markets, a dilemma presents itself. Software implementations of strong encryption algorithms like the Data Encryption Standard (DES) are very slow. Relatively efficient, special-purpose hardware implementations of some of these algorithms do exist, but they are difficult to integrate into low-cost computing and communications products. Developers of low-cost encryption products must choose between strong security and acceptable speed. Software implementations achieve acceptable speed only by using algorithms that do not have provably strong properties and may have been broken by the cryptanalytic community. This is a significant impediment to the introduction of cryptography into new markets.
Bellcore Solution
Bellcore’s Applied Research organization has recently patented [1] and published [2] the VRATM algorithm for generating random bits. Encryption based on this algorithm is the first and only scheme that is both:
For example, VRA encryption can be applied to real-time digital video applications as well as to general-purpose computer and communications security. Due to the efficiency and flexibility of VRA encryption, it is also attractive for devices like digital handsets that are limited in their computational power by cost, battery drain and weight considerations.
Technical Background
The VRA algorithm allows a very efficient software implementation of a classical encryption scheme that is known as a “Vernam cipher.” Briefly, a Vernam cipher uses any secure pseudo-random generator to create a sequence of pseudo-random bits. Successive bits in this sequence are then exclusive-or’ed with successive bits of the original message to encrypt it.
The speed and security of VRA encryption are accomplished through a novel decomposition of the pseudo-random sequence computation. The pseudo-random generator is based on a secure block cipher like triple-DES. The secure and slow block cipher computations are mostly limited to a preliminary preparation of a special table. The on-line encryption process consists mostly of a small number of extremely simple operations like look-ups into the special table, and bitwise exclusive-ors. (The on-line part of the VRA algorithm produces 5 to 10 times as many bits as it requires from the secure cipher.)
Speed, of course, is not the only issue. A fast encryption scheme is relatively easy to propose. However, designing a cipher that is both fast and secure has proven elusive. Even if a viable candidate were to arise, it could not be used in commercial applications until it were subjected to years of cryptanalytic attack by the research community.
In contrast, VRA encryption can be based on any existing trusted secure block cipher, like triple-DES. The security of VRA relies only on the security of the underlying trusted block cipher and not on other unproved assumptions. This result is based on recent theoretical developments in pseudo-random sequence generation and graph theory.
VRA encryption has three parameters that can be tuned for the time, space, and security requirements of each application. For example, the parameters were tuned for a video-teleconferencing application using triple-DES as the secure block cipher. This software requires less than two seconds of preprocessing and 128 kilobytes of storage. It yields on-line encryption rates of tens of megabits per second on a workstation or Pentium PC. As for security, these same parameters guarantee that breaking a VRA-encrypted block entails an unfeasible calculation comparable to what would be required to break DES itself.
Company Background
Bellcore is a leading provider of innovative, state-of-the-art software, training and consulting services for the telecommunications industry, as well as other information-intensive industries and organizations. The company has over 5800 employees and $1B in annual revenue.
Bellcore holds over 600 patents in diverse areas including multimedia-network delivery techniques, information and network integrity, fraud management, lithium-ion batteries, information-retrieval algorithms, and database innovations geared towards large-scale systems and privacy issues.
To Follow Up
Bellcore is interested in licensing this patented solution to interested parties. To follow up, please contact Garrett Dreier at Bellcore, 445 South St., Morristown, NJ 07960 (973) 829-4795 (fax -2645) or send him email at gdreier@bellcore.com.
References
TMVRA is a trademark of Bellcore
(last updated January 18, 1998)
home, biography, home-theater
journal, low-cost,
large-area display, quantum realism,
a potter's book, against Peter Singer
Copyright 2003, Terence J. Nelson