If I were Larry Page, I would put homomorphic encryption research at a much higher priority than quantum computers, or even researching robots (unless they intend to make most of their money from robots within a few short years, and not rely as much on search money, but that seems pretty unlikely in the short term).
If they plan on continuing to make money from tracking users, then they'd better figure out a way to do it very securely and without invading user privacy, otherwise they're going to feel an increasingly bigger pain in terms of public perception of Google over this, which could lead to them losing money in the long term, too.
I would also forget about tracking "everything possible" until then, and encrypt end-to-end stuff like chatting and video-calls (maybe they can do this one less costly through P2P or a hybrid system). I very much doubt they see a ton of money as a return from tracking and data mining people's chats online. And the downside is quite huge, because those online chats can be abused by the governments. So why not secure them properly? A little cost to them, huge privacy benefit to their users.
The goal should be to only track public, and not private information (at least in the short term, and then they should use homomorphic encryption for public information, too, as that will become increasingly more revealing, too, in the future).
I would also pay a lot of attention to what the Dark Mail Alliance is doing with e-mail encryption, and I would at the very least implement their protocol as an option for people who want to talk securely with others, from inside Gmail. They don't necessarily have to make all of Gmail encrypted by default, although that would obviously be very nice, but probably not very practical until they figure out homomorphic encryption.
There are also other things they could do to make e-mails a little more secure against abusive governments. In the US, ECPA allows the government to take the e-mail after 180 days without a warrant. So how about you ask people to give a password to G-mail, that's locally stored, and can automatically encrypt emails older than 179 days. If you need to access your own 6+ months old e-mails, then you're just asked to insert your password to access them. I don't see this as a huge issue for convenience, since the vast majority of 6+ months old e-mail is never accessed again by most people anyway.
The memories of a privacy-focused Google are certainly getting blurry, but I seem to remember there was a time when Google really cared about user privacy, and didn't have the same mentality as NSA for "collecting it all", storing it forever, and using it forever with data-mining.
Google has a lot of very smart people working for them. I'm sure they can come up with many more and much better solutions than even I proposed here. The problem is they have to want it. If it doesn't come as an objective from the top, then it's not going to happen.
From Wired, last year:
> Lloyd made his pitch, proposing a quantum version of Google’s search engine whereby users could make queries and receive results without Google knowing which questions were asked. The men were intrigued. But after conferring with their business manager the next day, Brin and Page informed Lloyd that his scheme went against their business plan. “They want to know everything about everybody who uses their products and services,” he joked.
http://www.wired.com/wiredscience/2013/10/computers-big-data...
Google needs to lose that attitude. Adapt or die, Google. And by adapt, I mean having their business incentives once again aligned with those of their users, or it's not going to end well for them.