We have designed efficient encrypted algorithms for collective operations. The newly developed algorithms are theoretically optimal in that they achieve the performance bounds. Our empirical evaluation shows that our novel encrypted collective algorithms outperform the naive algorithms to a very large degree on production systems. Moreover, using our algorithms, the overhead for supporting security in communicating large messages with MPI_Allgather, MPI_Bcast, MPI_Scatter, and MPI_Gather is almost negligible in modern multi-core clusters with many MPI processes running on each node.