title: NHash: Randomized N-Gram Hashing for Distributed Generation of Validatable Unique Study Identifiers in Multicenter Research.
abstract: BACKGROUND
  A unique study identifier serves as a key for linking research data about a study subject without revealing protected health information in the identifier. While sufficient for single-site and limited-scale studies, the use of common unique study identifiers has several drawbacks for large multicenter studies, where thousands of research participants may be recruited from multiple sites. An important property of study identifiers is error tolerance (or validatable), in that inadvertent editing mistakes during their transmission and use will most likely result in invalid study identifiers.
  
  
  OBJECTIVE
  This paper introduces a novel method called "Randomized N-gram Hashing (NHash)," for generating unique study identifiers in a distributed and validatable fashion, in multicenter research. NHash has a unique set of properties: (1) it is a pseudonym serving the purpose of linking research data about a study participant for research purposes; (2) it can be generated automatically in a completely distributed fashion with virtually no risk for identifier collision; (3) it incorporates a set of cryptographic hash functions based on N-grams, with a combination of additional encryption techniques such as a shift cipher; (d) it is validatable (error tolerant) in the sense that inadvertent edit errors will mostly result in invalid identifiers.
  
  
  METHODS
  NHash consists of 2 phases. First, an intermediate string using randomized N-gram hashing is generated. This string consists of a collection of N-gram hashes f1, f2, ..., fk. The input for each function fi has 3 components: a random number r, an integer n, and input data m. The result, fi(r, n, m), is an n-gram of m with a starting position s, which is computed as (r mod |m|), where |m| represents the length of m. The output for Step 1 is the concatenation of the sequence f1(r1, n1, m1), f2(r2, n2, m2), ..., fk(rk, nk, mk). In the second phase, the intermediate string generated in Phase 1 is encrypted using techniques such as shift cipher. The result of the encryption, concatenated with the random number r, is the final NHash study identifier.
  
  
  RESULTS
  We performed experiments using a large synthesized dataset comparing NHash with random strings, and demonstrated neglegible probability for collision. We implemented NHash for the Center for SUDEP Research (CSR), a National Institute for Neurological Disorders and Stroke-funded Center Without Walls for Collaborative Research in the Epilepsies. This multicenter collaboration involves 14 institutions across the United States and Europe, bringing together extensive and diverse expertise to understand sudden unexpected death in epilepsy patients (SUDEP).
  
  
  CONCLUSIONS
  The CSR Data Repository has successfully used NHash to link deidentified multimodal clinical data collected in participating CSR institutions, meeting all desired objectives of NHash.
authors.affiliation: Institute of Biomedical Informatics, University of Kentucky, Lexington, KY, United States.
authors.forename: Guo-Qiang
authors.identifier: http://orcid.org/0000-0002-3663-1109
authors.initials: GQ
authors.lastname: Zhang
authors.forename: Shiqiang
authors.identifier: http://orcid.org/0000-0003-1515-3184
authors.initials: S
authors.lastname: Tao
authors.forename: Guangming
authors.identifier: http://orcid.org/0000-0002-1234-5247
authors.initials: G
authors.lastname: Xing
authors.forename: Jeno
authors.identifier: http://orcid.org/0000-0003-4412-4251
authors.initials: J
authors.lastname: Mozes
authors.forename: Bilal
authors.identifier: http://orcid.org/0000-0002-6303-7279
authors.initials: B
authors.lastname: Zonjy
authors.forename: Samden D
authors.identifier: http://orcid.org/0000-0001-8626-1137
authors.initials: SD
authors.lastname: Lhatoo
authors.forename: Licong
authors.identifier: http://orcid.org/0000-0001-5549-8780
authors.initials: L
authors.lastname: Cui
keywords: cryptographic hash function; data integration; health information management; multi-center study; patient cohort identification; search interface; study identifiers