Due to phenomena like the ubiquity of the Internet and cloud computing it is increasingly common to store and process data on third-party machines. In spite of its attractive aspects, this trend raises a number of security concerns, including: How to ensure that the results computed by third parties are correct (integrity) and no unauthorized information is leaked (privacy)? The current way to deal with these problems is to trust third parties under legislation guarantees. This approach assumes that third-party machines stay honest all time, even if they get hacked! This is unrealistic and contradicted by the numerous security incidents that are regularly reported. In contrast, our vision is that any computing device must be able to store and process data on untrusted machines without risking for privacy and integrity and without the need of trusting these machines. Recent trends in cryptography promise solutions to realize our vision but the existing generation of protocols is limited due to its high costs and its poor support of emerging applications such as data streams processing. The grand challenge of this project is to invent a new generation of cryptographic protocols for computing securely on untrusted machines in a way that is cost-effective and suitable for future application scenarios. Towards this goal we will design new methods to scale up the applicability of cryptographic protocols. One of our key approaches will be trading generality for efficiency. While existing solutions are either general but impractical or efficient but of limited applicability, in PICOCRYPT we will look for protocols that support a wide range of applications while staying efficient. The PICOCRYPT solutions will enable a paradigm shift in the way privacy and integrity will be enforced and will have impact in the IT world by making remote computing safer not only for citizens but also for public and private organizations that due to the current risks renounce to these services.