Single Sign-On (SSO) is a core component in a federated identity management (FIM). Dynamic Single Sign-on (DSSO) is a more flexible SSO where users can change their service requirements dynamically. However, the security in the current SSO and DSSO systems remain questionable. As an example, personal credentials could be illegally used to allow illegal users to access the services. It is indeed a challenging task to achieve strong security in SSO and DSSO. In this paper, we propose a generic construction of DSSO with strong security. We propose the formal definitions and security models for SSO and DSSO, which enable one to achieve the security of SSO and DSSO with the underlying (standard) security assumptions. We also provide a formal security proof on our generic DSSO scheme.