The emergence of cloud computing provides an unlimited computation/storage for users, and yields new opportunities for multimedia analysis and retrieval research. However, privacy of users, e.g., search intention, may be leaked to the server and maliciously utilized by companies or individuals with animus. This paper presents a privacy-preserving multimedia analysis framework based on a widely-adopted structure, i.e., bipartite graph, so that multimedia analysis and retrieval in the encrypted domain is enabled. This work aims to keep the server unaware of what the user wants to retrieve, and at the same time take advantage of the server's computation power. Homomorphic encryption schemes and communication protocols in the encrypted domain are integrated to facilitate bipartite graph construction and implement the Hungarian algorithm to find the best matching. Two applications, video tag suggestion and video copy detection, are developed on top of the privacy-preserving framework, and the evaluation results demonstrate that performance obtained in the encrypted domain is comparable with that obtained in the plain text domain.