This book constitutes the carefully refereed and revised selected papers of the 4th Canada-France MITACS Workshop on Foundations and Practice of Security, FPS 2011, held in Paris, France, in May 2011. The book contains a revised version of 10 full papers, accompanied by 3 keynote addresses, 2 short papers, and 5 ongoing research reports. The papers were carefully reviewed and selected from 30 submissions. The topics covered are pervasive security and threshold cryptography; encryption, cryptanalysis and automatic verification; and formal methods in network security.