A Research Topic

When I went back to Unicamp to start the PhD, it was very different from my arrival for the master’s. I was already at home: I knew the place, the people, and how things worked, both inside the Institute of Computing and around campus. At the same time, everything was very different. We were a family now; it wasn’t just me on my own anymore, free to live however I wanted. We had to find a place to live, and not just a back room in some república. We had a son who needed attention, schedules, food, someone to look after him while we were in class, working on the thesis, or, sometimes, just trying to have a little time together as a couple.

We managed to find a little house on the far edge of Campinas, but close enough to Unicamp to keep life reasonably practical. We also found a little school for Pedro, which brought us some peace of mind — at least on a part-time basis, which was what we could afford. Toward the end of the semester, we could sometimes put him in full-time to have more time to study and work. At first, it was only my UFLA salary, but soon Gisele got a scholarship. Life was tight, but manageable.

One thing I had already noticed about Unicamp’s research areas, which was quite different from UFMG, was its very strong focus on theoretical aspects of computing: theory of computation, formal methods, and, in particular, a heavy emphasis on graph theory. In the PhD, there was no way to avoid certain areas of computing, as I had done in my master’s. I had to take courses and also sit the qualifying exams, which covered practically the whole research spectrum of the Institute of Computing. The more systems-oriented areas didn’t worry me as much, but theory and databases were weak points of my UFMG background and also areas I had avoided during the master’s. Now there was no way around it: I was going to have to study these topics.

So I started taking several courses in these areas. One of the courses that stuck with me most was focused on graphs, offered as a “topics” course, which meant the content varied according to the professor and semester. That year, the topic was network flow algorithms (graphs). The goal was to show how graphs and flow algorithms could solve problems that, at first glance, didn’t seem to have anything to do with graph theory, like how to color maps, for example.

As expected, we also studied shortest path algorithms and the famous traveling salesman problem. Along these lines, the professor proposed a rather challenging assignment. The idea was a simplified simulation of traffic: find the lowest-cost path in a graph, but with an additional rule. The professor ran the algorithms, identified the paths each one chose, and then increased the cost of the most-used edges. The idea was to simulate congestion: if everyone picks the same path suggested by a GPS, that path stops being the best one. The assignment required both a correct implementation of the algorithms and the creation of a reasonable heuristic to avoid the most obvious route. There was plenty of room for creativity. I was far from the best result, but I passed the course.

Meanwhile, I was working with my advisor to define a thesis topic. Besides the qualifying exams, I had to present a thesis project to a committee, which required already having a concrete idea and an initial literature review. We were still kind of unsure of exactly where to go. At that point, the most likely option was to work on implementing elliptic curve algorithms, since there were many people in Unicamp’s cryptography group already working in this area with good results.

In parallel, I was reading cryptography papers and ended up intrigued by Boneh and Franklin’s work on shared RSA keys and its possible relationship to David Chaum’s blind signatures scheme, used in e-Cash. I began to wonder whether it might be possible to build something similar to threshold signatures using techniques inspired by Chaum’s blind signatures. From this line of thought, a variant emerged that we called blinded-key signatures. That ended up becoming the central topic of my thesis: defining and analyzing a cryptographic scheme to hide public keys and exploring protocols and possible uses of that idea.

At that time, there was a lot of interest in computing research around the concept of mobile agents. The vision was that the internet would simply become infrastructure, and the code would go to wherever the data was located. People imagined, for instance, agents that would travel through airline systems to find tickets, or agents that would be sent to financial environments to execute operations and then return with the results. People imagined a stock exchange that would be a computing environment into which we could send our agents to trade for us. One big problem was the security of these mobile agents and ways to allow them to securely sign contracts or agreements. Putting a signing key inside the agent was not secure, since it could be easily extracted by the host and used in unauthorized ways. Our idea was to hide that key in such a way that, even if the agent was captured, it would have little or no practical value. It was in that context that the thesis scheme took shape.

Advice nobody asked for but I am giving anyway:

• When choosing a thesis topic, it’s always a good idea to pick one that is part of your advisor’s main research topic or your lab’s focus. That lets you have more exchanges with colleagues and more help from your advisor. Working on a new topic like I chose to do is a lonelier path, and you may run into problems that nobody will be able to help you solve (more on this later).