It could be difficult to explain simply why in the last 5 years mathematical cryptography community and community of researchers of CRISPR immunity have been working independently on a very similar ( If not the same ) problem. The problem of collision and pre - image resistance of the hash functions by CRISPR antiviral defence mechanism. Both mathematicians and CRISPR researchers describe intuitively the same attacks on hash functions which have been targeting the collision and preimage resistance properties.
The goal of my review, thus, hence, is to bridge the results obtained by the two communities and to define some future trends in this new and strangly "unconscious" area of genome editing having direct applications in personalized medicine.
Hash functions : preimage and collision resistance.
Hash functions are compressing functions, mapping messages of large size ( say, invading DNA type ) to hash values of small constant size ( for example, crRNA message in CRISP-cas systems ).
Mathematicians had found that hash functions must be collision - resistant ( I.e. it is hard ( but not impossible ) to find collision produced self - targeting when a couple of messages (crRNA and crRNA *) such that
Hash(crRNA) = Hash (crRNA*) ).
Following mathematicians, hash functions must be also preimage - resistant.This means for essentially all pre-specified outputs ( for example crRNA message in CRISP-cas systems ) it is computationally infeasible to find any input or unique conditions of crRNA biogenesis ( preimage )in the given cell at all such that.
Hash(crRNA) = h
When given any h for which a corresponding input is not known. It is very important because CRISPR immunity contains the challenge that the phage attacker is " asked to solve" what should not be known in advance.
In some formal sense, usual definitions of preimage resistance include mathematical randomness. Theorists Rogaway and Shrimpton distinguish 3 cases of preimage resistance: aPre cases when the attacker challenge is random but Key is fixed, ePre case when Key is random but the attacker challenge is fixed and Pre cases when both attacker challenge and the Key of such coding "theory" are random.
In the CRISPR Cryptanalysis context the requirement of being random ( exactly speaking - pseudorandom ) seems much stronger than collision resistance. In both mathematical cryptography community and genome editing community preimage and collision resistance have became the most popular security notions for hash functions.
CRISPR - Cas Cryptanalysis .Type 1.
Clustered regularly interspaced short polindromic repeat (CRISPR) in bacteria and archaea represents natural immune system , small guide crRNA, which are employed for sequence - specific targeting nucleic acids. CRISPR Cas comprises a genomic locus called " repeats " separated by uniquely sequences (or spacers) that can originate from mobile genetic elements ( MGEs) such as bacteriophages, transposons or plasmids. CRISPR arrays are usually preceded by an AT - rich leader sequence and is blanked by a Cas genes encoding Cas - proteins.
The leader appears to promote transcription towards the repeats, generating basis of the crRNA counter-attack. Recent studies have proposed that CRISPR Cas system is obvious an antiviral defence mechanism.( Makarova et al, 2006; Barrangou & Marrafffini, 2014 )
There are two main classes of CRISPR-cas systems. In class 1 CRISPR-cas systems of types 1,3,4 the effector module consists of a multi - protein complex, whereas class 2 ( types 2,5,6 ) uses only 1 effector protein.(Savitskaya,Musharova & Severinov 2016).
When bacteria are under phage attack, bacteria use a very unusual Cryptanalytic Adaptation - bacteria acquire new spacers from invading DNA. CRISPR arrays can acquire new repeat spacers units that are introducing unexpected quasi - randomness for the attacker during Biogenesis and Interference. As the result, crRNAs are used as guides to achieve the attacker's degradation.
CRISPR - Cas Cryptanalysis. Type 2.
CRISPR immunity is faced with the following fundamental question of " natural " cryptanalysis of hash functions : how to recognize self from non-self to thwart attacks without triggering autoimmunity.
Researchers showed recently that CRISPRs provide the means to exclude self - DNA from targeting in S. epidermidis. Attacker is faced with special kind of resistance from self DNA. They are differently recognized by the crRNA outside the protospicer, namely: the -8 nt of repeat sequence at the crRNA 5'terminus pairs only with CRISPR DNA.
Nevertheless, self targeting is a very rare and lethal event ( Paez - Espino et al 2013 ) in CRISP-cas systems. CRISP hash functions are used in Nature to destroy own DNA structure of other schemes.
Conclusion
Despite enormous progress in understanding CRISP-Cas immunity in prokaryotes during the last decade, many interdisciplinary questions still remain unanswered. Awareness of the deepest link between mathematical cryptanalysis of hash functions and genome editing will broader our understanding of biotechnological tools and foundations of personalized medicine.
Michael A. Popov, Director Researcher, Prime States Quantum Lab