Recent advances in technology provided a suitable environment for the people in which they can benefit from online services in their daily lives. Despite several advantages, online services also constitute serious privacy risks for their users as the main input to algorithms are privacy sensitive such as demographic information, shopping patterns, medical records, etc. While traditional security mechanisms can eliminate a number of attacks from outside, these mechanisms can not protect the privacy of the users as the service provider itself constitutes the biggest potential risk. In this thesis, we focus on principled solutions to protect the privacy of users in multimedia applications. For this purpose we propose to keep the privacy-sensitive data safe by means of encryption during processing. This approach eliminates the risk of possible privacy abuse as the sensitive data is only available to the owner but no other party. However, once encrypted, the structure in data is destroyed as a consequence of the encryption procedure and thus we need appropriate tools to process encrypted data. Therefore, we focus on a number of cryptographic tools such as homomorphic encryption schemes and multiparty computation (MPC) techniques to realize privacy-preserving multimedia applications. The proposed principled solutions consider the signal processing aspect of the multimedia applications which is a new idea to the best of our knowledge. In particular, we focus on a number of prototypical applications namely, face detection, user clustering in a social network, recommendation generation and anonymous fingerprinting. Based on these selected applications, we addressed the major challenges for secure signal processing: data representation, data expansion, realizing linear and non-linear operations and efficiency of the proposed protocols in terms of communication and computational costs. We propose to scale and round the signal values prior to encryption as these operations are highly inefficient to be realized in the encrypted domain. Moreover, we reserve sufficient space in terms of bit length for each signal sample to accommodate the possible expansion in bit size in the subsequent processing steps. However, reserving more bits for signals does not contradict with the data expansion problem. As the cipher text space is much larger than the size of the original -- and even scaled -- signal samples, data expansion after encryption increases data transmission and storage costs significantly. In order to minimize the cost we propose to pack a number of signal samples in one encryption and process them when they are in the packed form. This approach requires cryptographic protocols particularly designed for the packed data but in the end saves considerable resources regarding bandwidth and storage capacity, even computational power. Homomorphism plays a crucial role in our proposed solutions. With the help of homomorphic encryption, we are able to implement linear operations such as correlation and projection without interaction. However, linear operations are only a part of the signal processing. For the non-linear operations like distance computation, thresholding and comparison, we exploit MPC techniques. These techniques are often interactive and computationally expensive compared to the original systems in plain. However, by using data packing and designing the protocols with care, the communication and computational costs were reduced significantly. In this thesis, we have shown that preserving privacy for multimedia signal processing is feasible. We determined the major challenges of secure signal processing and combined a set of cryptographic tools successfully with signal processing to realize the applications in the encrypted domain. The proposed solutions demonstrate that the privacy concerns in multimedia signal processing applications can be coped with by using cryptographic tools. Moreover, protocols that are designed to realize certain operations in the encrypted domain can be used in other applications and settings with a number of modifications.