Internet real-name registration requires a user to provide personal identification credentials including his/her real name to an online service provider when registering for an account. In China, real-name registration has been implemented since 2010 for purchasing train tickets and mobile phone SIM cards. In 2013, the Chinese government announced that real-name registration would be implemented for Internet users to protect against cyber crimes, including cyber bullying, rumor spreading and identity theft. When real-name registration is in place, law enforcement agencies can obtain the real identity of a user who attempts to leverage the anonymity provided by the Internet to conduct criminal activities. However, real-name registration also potentially infringes on online privacy.This chapter presents a privacy-preserving Internet real-name registration approach based on Shamir’s secret sharing scheme. The approach helps protect the identities of online users while enabling law enforcement to obtain the identities of users involved in criminal activities on the Internet.