Innovative computer scientist Ruby Lee talks about secure information processing, efficient permutations, fair use in the digital age, and more.
An ACM Fellow, Ruby Lee was cited in the award "for pioneering multimedia instructions in general-purpose processor architecture and innovations in the design and implementation of the instruction set architecture of RISC processors." Dr. Lee is now Forrest G. Hamrick Professor in Engineering and Professor of Electrical Engineering at Princeton University. She received her PhD (E.E.) in 1980 from Stanford University.
UBIQUITY: What are you focused on these days?
RUBY LEE: I've been focusing on the design of processor and platform architectures for new computing and communications paradigms. What will the 21st century programmable processor look like? In the last few years, I've focused on secure information processing. In an era of open Internet and wireless access, I feel that it's important that security be pervasive. This was, of course, way before 9-11. One should turn off secure information processing rather than turn it on. What this means is, design core architecture from the beginning with security in mind rather than as an afterthought, as is done today.
UBIQUITY: What would you call the new paradigm?
LEE: Secure information processing. But it's not just processing. It's also communications and storage. One of the areas I'm working on is, what would instruction set architecture look like for pervasive security? If we were to design processors and platform architectures from scratch, with all the knowledge that we've already gathered from previous architecture studies, how would processors be designed?
UBIQUITY: How would you assess the current state of computer and network security right now?
LEE: Pretty poor.
UBIQUITY: The Atlantic Monthly just published an article by Stephen Budiansky in which he seems to suggest that encryption is so good now that it's almost hopeless for the CIA and organizations like that to break codes. Is there anything in that?
LEE: Security is much more than what's commonly called encryption and decryption. I want to state that up front. For example, protecting intellectual property is also part of what I would call security. Code-breaking in modern symmetric-key cryptography algorithms depends a lot on the length of the key. When we're using pretty long keys, breaking it can be quite hard, but certainly not impossible.
UBIQUITY: If it's quite hard, then why is security so bad?
LEE: Just because code-breaking with long keys can be quite hard does not imply that security is good. Security may be the wrong word to use. It's more like what some people might call "trusted computing". Security is not only military security or national security. It's also in the sense of privacy, anonymity, data integrity, user authentication, service availability, and things like this. Security encompasses what is needed in everyday commercial and social transactions on public Internets and wireless infrastructures. Everyone would agree that you need to protect one's privacy and anonymity in certain cases. And that comes with secure information processing.
UBIQUITY: Well, what needs to be done?
LEE: The problem is that there are a lot of missing links. It's not that the basic technology is not present, but you have to implement the end-to-end security across many service providers and users and operators and machines and nodes and heterogeneous networks, and so forth. And if any one of these links lacks security, then the whole thing fails. It's as weak as the weakest link. Another point is that security today is pretty much perimeter type security like firewalls, so certain perimeter machines will have responsibility for blocking out unwanted traffic or preventing certain traffic from going out. This is not the way to do it. The enterprises today are a lot more fluid, so that you may have a small, tightly-knit group that's dispersed around the world, but they need a certain level of group security that cannot be provided by some single or a few perimeter computers. The same is true for large organizations and nations. So ultimately, every machine ideally has some responsibility for its own level of security.
UBIQUITY: Does the security problem change in nature with the size and capability of the machine? Is security on a handheld confronting the same security problem as much larger machines?
LEE: Yes and no. Yes, in the sense that a handheld computer could be infiltrated in the same way that a desktop or larger machine on the Net might be infiltrated with some rogue code that may later be woken up to launch a distributed denial of service attack. All programmable machines are vulnerable in that sense, in more or less similar ways, if they have the same software vulnerabilities. But obviously, a large server computer making airline reservations would have much better security features on it than a handheld, and therefore it's more secure, you would say, than a handheld computer. What security really comes down to for the everyday person is that today you own PCs connected on the Net, and you really don't want your PC to be used unknowingly to launch a distributed denial of service attack on some Web site. You probably don't have any protection against that. If you multiply this a thousand-fold to billions of information appliances running out there, you can imagine how terrible the denial of service attacks could be, if all these programmable devices can be infiltrated.
UBIQUITY: Is your machine more protected than my machine, do you suppose?
LEE: Probably not.
UBIQUITY: Is this like the cobblers' children who don't wear shoes?
LEE: I think that must be true. What I am working on is the fact that, if you build security into the core software and hardware -- the core OS and the core processor and platform architecture -- then you provide another level of defense that you don't have to depend on users to comply with. Today, whenever there's a security problem, a patch gets put out, and users are supposed to download this patch to fix the problem. But users get busy, or they can't be bothered, or whatever, and the patch isn't installed. But imagine if every device that you buy has this hardware protection inside the processor itself, as a non-optional part of the system. The whole Internet and wireless system would become more secure because at every node security would be provided.
UBIQUITY: Would that help to solve the controversies of things like music swapping?
LEE: I think that was an issue of the cat having gotten out of the bag a little too soon. People are now reluctant to have to pay for the music that they used to get free. You have to provide greater incentives for them to want to pay for the music, which is possible but it's just a little harder. Whereas, if we had started out with a system where music was reasonably protected so that one had to contribute some very small amounts, rather painlessly, towards downloading music, then the problem would never have occurred. So that's a security problem that wasn't thought through in advance.
UBIQUITY: Is there tension between providing protected digital information and allowing the free use of information for non-profit purposes.
LEE: Speaking from the academic community's perspective, while we provide protection for online distribution of music and video and so forth, we also must protect the "fair use" policies that are in place to allow educators, students and researchers access to material free of charge, for educational and non-profit purposes. This just makes it a bit harder for us technologists to allow both because you don't want the Internet to be a closed system where people have less access to information than they had before. But at the same time, because most of today's products are tied up in information, you can't exactly have everything be free, or you won't have any economic incentive for people to produce such information products. Now all of this is at a very high level. When it comes down to actual stuff, I'm working on a lot of details that are pretty theoretical, but they all fit into this general idea that the world is moving towards a need for more secure information processing or more trusted computers. If you don't want your computer to be used by someone else for hostile purposes, you should have that protection.
UBIQUITY: In your research on issues like security and its use in pervasive devices used for e-commerce or whatever, do you have much interaction as a technologist with other disciplines, people in other disciplines?
LEE: Certainly. For example, we are interested in determining what is fair use in the digital age? What's socially acceptable in terms of security and privacy? These are two edges of the same sword. What people really want or what they are willing to put up with. We try to talk to people in other disciplines on this. There's actually not that much concrete work to draw upon in some of these areas.
UBIQUITY: Why is that?
LEE: Because it's extremely complicated. If you just take the copyright issues in the Internet and in the digital medium, you're talking about worldwide, international coverage. And yet, every nation has its own copyright policies and IP assumptions. It's not a very easy issue to deal with across all nations.
UBIQUITY: Just within the US, is there something that you see as a policy that should be put in place about any of these issues?
LEE: Well, certainly, many people are trying to drive to these policies. On the one hand, you have the people who own the content, who want to distribute it through the Internet, and who are driving towards policies that would ensure reasonable economic viability. And then there are the watchdog organizations that make sure that fair use and so forth are upheld.
UBIQUITY: Do you have a strong feeling about the boundaries of fair use?
LEE: I'm seeing a lot more of it, now that I'm in academia. I have an advantage in that I have both the industrial background and the academic background. Unlike many professors, I can certainly understand the industry's need for some level of protection of IP. From an academic point of view, certainly one wants to promote information easily accessible by everyone. So, where to strike the Gordian knot? I think Americans are used to the fact that rights are not removed because of a new technology. If there was a certain level of fair use, at least that level should be maintained in the new information paradigms. That's what one would minimally strive for.
UBIQUITY: Would you push it beyond what has been fair use in the past?
LEE: The whole beauty of the Internet is that everybody anywhere should be able to access certain types of information. You certainly don't want to restrict this freedom unnecessarily. We also have to be careful of the digital divide. It would be nice to push to a little bit more of an open access to other nations, not just the US. But how do you do this in a way that also protects its citizens? The other side of the coin is the control that comes when you institute some of these policies. Suppose you had to distinguish between who gets fair use and who doesn't? That's not good because in a totalitarian regime it allows monitoring of a person's Internet accesses. We can also put information into an "Internet commons" for free access, but there will be disagreement on what goes into this and when. Technology issues are generally much simpler. We need to figure out the policy issues. Those are the harder things to work on. What I've been suggesting to people is that not working on them doesn't mean that a fair policy will result, because all the technologists in their garages are inventing the future fabric of society. Some ad hoc policies will be put in place. It's better to think through it and come up with some strawman proposals that are fair and equitable, before some biased systems become defaults.
UBIQUITY: You mentioned the digital divide in which we normally think of the divide between people, rich and poor, and so forth. What about the digital divide between countries?
LEE: I think there is less of a divide between countries as between categories of people; those who have the access and those who don't.
UBIQUITY: What kind of policy would make sense at the highest level for fixing the digital divide?
LEE: There would have to be a very powerful international body to enforce such policies. Otherwise, even though the Internet is an open space where we could truly have a global society, it would be somehow carved out into artificial boundaries that somewhat mapped into the national boundaries due to the regulations within each country.
UBIQUITY: Everyone who is in technology expresses concern about the digital divide. Is there anyone who is trying to actually do something about it?
LEE: There are many groups studying issues. What might actually happen are specific solutions for specific problems. These are more likely to get nailed down and implemented. Broader government policies that allow fair allocation of the wireless spectrum, for example, are good. Free access to information, supplying poorer communities with computers with Internet access, these are good. But at the same time, you also have to educate communities as to how to use all this technology. I think it's good that there's a lot of awareness of the potential digital divide. But I'm not sure that it has become so bad yet. There's still a lot of promise that everyone will be able to access all the types of information they should be allowed to access, everywhere and any time.
UBIQUITY: Let me ask you about a divide that used to exist, but doesn't exist so much any more. I'm wondering whether you see a divide nowadays between women and men in academia. Or in business, for that matter.
LEE: This is a very interesting question. When I was at Hewlett-Packard out in Silicon Valley, I rarely thought of this problem, and never felt any impact about being a woman in a male-dominated field. But since coming to academia, these issues have been brought to my attention very frequently. For example, women faculty in science and engineering are a very under-represented group, especially in engineering. I'm the only endowed chair senior woman professor in the engineering school here at Princeton, and only one of three full (women) professors in the whole school of engineering. These are certainly issues that the academia is aware of. Last January there was a meeting at MIT that I attended where Charles Vest, MIT President, had nine university presidents come with their senior administrator and two or three senior woman faculty to discuss this very issue.
UBIQUITY: Is this problem going to work itself away as more young women get trained as scientists and engineers?
LEE: What they found was that just filling the pipe wouldn't do it. The thought was, if you filled the pipe with engineering undergrads, then soon they would go on to become graduate students, then assistant professors, associate professors and finally full professors. But apparently this pipe is very leaky.
UBIQUITY: How leaky is it?
LEE: There's data to show that it's extremely leaky. About 30 percent or so of undergraduate engineers may be women, but by the time you get to full professors, it's perhaps two percent. The first thing that had to be done was to produce the data to show this leaky pipe effect. The second thing that was discovered by the MIT women faculty was that, in fact, many women feel good in their assistant professors' years, but feel increasingly marginalized the longer they have been full professors. I myself haven't been in academia long enough to know whether this is true or not but many senior women faculty apparently have said this.
UBIQUITY: That is surprising. What do you think explains it?
LEE: I don't really know. I think young women are very much encouraged today and they all come with high aspirations. The thought is that there's a lot of bias along the way, and so, increasingly, the senior women faculty feel more marginalized. At least that was what the MIT report said. I think it will change, but it probably won't change that fast if people don't bring up these issues specifically and insist that something gets done about it. I think you're seeing a movement of women faculty across the nation in science and engineering who want to make sure that any kind of prejudice that exists in the system with regard to gender inequity should be brought to the public's attention and rectified within the academia. I came from Silicon Valley, and I don't think there's much of a gender problem there, but then again, I was in a very special position as a chief architect at Hewlett-Packard, so I might see a different view.
UBIQUITY: What made you leap from the commercial world to academia?
LEE: When I first did my PhD, I thought about being a professor and researcher. After I graduated, I taught for exactly 15 months as an assistant professor at Stanford, before I got this tremendous offer from Hewlett-Packard to design a new instruction-set architecture to unify this major computer vendor's three computer product lines. I couldn't refuse the offer and I was very happy at Hewlett-Packard for all of the 17 years. So, why did I do this? Actually, I was initially invited to Princeton to give a seminar, and I agreed because our son was an undergraduate here -- I thought it would be a good opportunity to visit him. I gave the seminar and then Princeton made me certain propositions that began to sound very interesting. There are probably at least two reasons for making the switch to academia. One is that I've had the top technical job in industry in at least three different areas already. I was the architect of PA-RISC, and then later of the multimedia instructions that set the direction for modern microprocessors adding multimedia instructions to their instruction set architectures. And then the Intel HP IA-64 architecture, which is the first of the EPIC (Explicitly Parallel Instruction Computer) architectures. I was in processor architecture, then I was chief architect of the multimedia architecture team, and then chief architect for security architecture for e-commerce and extended enterprises. These are top technical jobs in industry. And I've done them. I enjoyed them very much, and I know I can do them very well. This was a new challenge, something I hadn't done.
UBIQUITY: What was the other reason?
LEE: The second reason is that I had for a while been thinking how I could give something back to society, and while it sounds a little bit corny maybe, I was wondering how I could do that in a way that utilized my experience and my interests. The prospect of going to academia to teach future generations of computer architects sounded like a perfect match -- some way that I could use my industry experience to influence the education of new generations, and also perhaps influence the research that was coming out of academia. When I was in industry, sometimes we wished that the academia would do the advanced research in those topics that we never had time to do adequately. And that kind of research wasn't coming out from the universities. I thought perhaps with my industry background I could influence some of this research.
UBIQUITY: And now you've had three years to assess the results. Are the results in? Are you happy?
LEE: I'm really having fun at Princeton. It's a very interesting and exciting community. I'm an elected executive committee member of the Council of the Princeton University Community, the policy group involving administrators, faculty, undergraduate and graduate students, staff and alumni. I'm also on the President's task force on gender equity, faculty hiring committees, inter-disciplinary groups, advisory boards, and so forth. Influencing research is a rather difficult thing to do. I think that there are certain ingrained patterns of thinking, and while one could influence a certain population, I'm not exactly sure how well one could influence the entire population. So that's something that remains to be seen.
UBIQUITY: Are you enjoying teaching?
LEE: I'm enjoying teaching very much. And the students seem to really love having a professor who has a lot of experience as a practitioner of the art. I think teaching forces you to focus on what's really important to transmit to a clean slate mind. Essentially these students are literally clean slates. They don't have any background. They don't know what's important. They have no experience. So, what can you teach them out of this entire field of computer architecture? That's a very challenging job. Unfortunately, I think most of the current textbooks are not exactly appropriate. So, one might have to write new textbooks. The field is changing so fast that it's difficult to capture everything at a particular point in time. You have to be sure the students are capturing concepts that have lasting value. There was a time when industry was perhaps a little ahead of academia in its innovations and so forth, and may, in some parts of Silicon Valley, still be ahead. But I think that the academia has a good chance to take the lead again.
UBIQUITY: Tell us about some of the exciting technological advancements that you've been involved in.
LEE: One area is instruction-set architecture, which is the native language of a computer. This has been considered a mature topic, as if the whole issue has been solved, and no new instruction set architectures could be designed. But what I found is that when one looks at newer computing and communications paradigms, like multimedia, cryptography and secure processing, that in fact, many new operations become very common that were not common before. People tend to give up and say, processors can't do this well, so we'll avoid these operations.
UBIQUITY: Like what?
LEE: One of these operations is bit-level permutations. When you're doing encryption, bit-level permutations take this block of 64 bits that you're encrypting, and rearrange the bits, and every bit can go to any of the 64 bits. This is very useful for spreading the redundancy in the original message over the encrypted message. But microprocessors are word-oriented, which means they are optimized to process a whole chunk of 64 bits simultaneously as a word. Therefore, by definition they're not designed to do bit permutations within a word well. This is something that never was important before in general-purpose computing. In the old days when people thought that hardware-implemented cryptography was more secure than software, they purposely chose to use bit permutations in the cryptography algorithms like DES, the 20-year old Data Encryption Standard. Fixed permutations are easy to do in hardware -- you just re-route wires between the source bits and the destination bits. Today, we want encryption to be efficiently implementable by software as well as hardware, which was specifically requested when NIST asked for proposals for the Advanced Encryption Standard, the AES, to replace DES. So algorithm designers tended to avoid permutations because they are very slow in software running on current processors. Because permutations represent a beautiful way to do what's called diffusion in symmetric key cryptography, I took it as a challenge to see if I could design new instructions for programmable processors that could do any and all permutations very quickly.
UBIQUITY: Is there any way you could summarize it for us?
LEE: Well, to cut a very long story short, today to do a permutation in a programmable processor, it could take anywhere on the order of n instructions, where n is the number of bits to be permuted. For example, if n was 64 bits, it might take 4n (four times 64), that's 256 instructions, or 2n, that's 128 instructions, to do a single permutation. That's very slow. There are ways to speed this up for a few fixed permutations, but not for all possible permutations of n bits. We invented several new methodologies to do bit permutations in O(log n), rather than O(n). O(log n) means to permute 64 bits, it only takes six instructions. And that's the worst case to get any arbitrary permutation of 64 bits. Permutations can be done in better than six instructions, but in the very worst case, it would take log n instructions to do any one of the n! (n factorial) permutations. So that was a tremendous discovery. It had never been possible before, and we do it with a very simple functional unit that can be introduced into any programmable processor, including those tiny processors that go into smart cards. It can be done with very simple instructions, like what's called RISC (reduced instruction set computers) instruction formats. So we've got it down from O(n) to O(log n). And if that was not good enough, I've recently discovered a way that I can do any of these n factorial permutations -- a humongous number of permutations -- in O(1) time, which means, in just one or two execution cycles. I can do this, and the hardware is no more than what's typically available today in microprocessors, with a very small increment. So, we've brought a challenging problem down from O(n) to O(log n) to O(1), and we have also validated the word-orientation of processors by showing that they can also do the most complicated kind of bit processing very quickly with a little new architecture. I find that theoretically very exciting. This would be something that I would never have time to do in industry because I couldn't prove to the executives how it would affect the company's bottom line. It definitely pushes the state of the art in knowledge because permutations have never been thought of this way. Mathematicians only considered the existence of a way to do certain permutations. They never thought about the efficiency in the way that us computer people think about it. So I think to bring an operation from order n down to order log n, and then to order one in the space of less than two years, is pretty thrilling. (For more information on this topic, see "Efficient Permutation Instructions for Fast Software Cryptography," in the December issue of IEEE Micro.).
UBIQUITY: So how would more efficient permutations affect a company's bottom line?
LEE: What it could do is it could speed up tremendously all kinds of new algorithms that might be designed for symmetric key cryptography, as well as speed up old standards like DES and triple DES. This is particularly exciting, especially as the way that permutations were done more quickly in software in the past was to use table look-up methods. Now this is fine when you're running on large computers with big caches and memories. And so, if one permutation took 16 K bytes of table storage, it was not a big deal. Even if you're doing six different types of fixed permutations as in DES, requiring almost 100 Kilobytes of memory just for permutation tables, there may be no problem because a big computer has lots of cache memory. But if you're talking about these constrained environments like cellular phones, or smart cards, where memory is at premium cost, then to be able to use my permutation instructions within the processor itself would be such a cost-savings, not to mention that it's also a performance booster. So, what excites me is that it's a theoretical topic that has very significant industry impact, if the industry knew about it. You not only reduce the cost and power, but you improve the performance. These two goals are usually at odds with each other. To be able to combine both at the same time is truly a good achievement, I think. This is just one of those sort of nerdy areas that I get excited about.
UBIQUITY: No harm in that.
LEE: I probably should also mention multimedia, since the ACM Fellow probably was based on my past work in multimedia. I think I helped to make software multimedia information processing more ubiquitous by introducing multimedia instructions in the processor architecture. These instructions provide very low-cost parallel execution within the processor for very significant acceleration of multimedia and other similar types of computations. And now, every single microprocessor vendor has multimedia instructions in its processor architecture. Such things are not impossible. Very rarely has new architecture been so quickly and so widely adopted by the industry. What I'm trying to do now in secure information architecture is more or less the same thing. I feel confident that it's perfectly doable.