John R. Douceur, Atul Adya, Josh Benaloh, William J. Bolosky and Gideon Yuval
Microsoft Research
USA

We describe the design of a Windows file-system directory service that ensures the persistence, integrity, privacy, syntactic legality, and case-insensitive uniqueness of the names it indexes. Byzantine state replication provides persistence and integrity, and encryption imparts privacy. To enforce Windows’ baroque name syntax – including restrictions on allowable characters, on the terminal character, and on several specific names – we develop a cryptographic process – called “exclusive encryption” – that inherently excludes syntactically illegal names and that enables the exclusion of case-insensitively duplicate names without access to their plaintext. This process excludes entire names by mapping the set of allowed strings to the set of all strings, excludes certain characters through an amended prefix encoding, excludes terminal characters through varying the prefix coding by character index, and supports support case-insensitive comparison of names by extracting and encrypting case information separately. We also address the issues of hiding name-length information and access-authorization information, and we report a newly discovered problem with enforcing case-insensitive uniqueness for Unicode names.

Keywords: security, directory service, Byzantine fault tolerance, cryptographic protocols

Read Paper (in PDF)