Regular Expression Engine with TFHE-rs

The blog post outlines a tutorial for building a homomorphic regular expression engine using TFHE-rs, a Rust library for fully homomorphic encryption (FHE), based on a contribution from a participant in the Zama Bounty Program. It explains the construction of a regex Pattern Matching Engine (PME) that operates on encrypted ASCII bytes, highlighting the power and flexibility of regex for searching text structures. The tutorial covers the creation of an Abstract Syntax Tree (AST) from regex patterns, the translation of these patterns into a RegExpr data structure using Rust's enum type, and the parsing and matching processes against encrypted content. The post discusses the challenges of encoding content into encrypted states and contrasts two strategies for this, ultimately recommending the encryption of entire ASCII values for efficiency in FHE operations. It also contrasts direct AST recursion with the construction of a Deterministic Finite Automata (DFA), although the latter is impractical due to the encrypted nature of the content. Additionally, the post describes optimizations to reduce the number of FHE operations, such as delaying execution paths and caching known expression results, and concludes with instructions on compiling and running the example implementation for testing and performance analysis.