2014-luchaup-libfte
findings extracted from this paper
-
DFA state-space explosion makes DFA-based FTE impractical for many realistic network-monitor regexes: the minimum DFA for `(a|b)*a(a|b){16}` has 131,073 states requiring 266 MB of precomputed tables, while the equivalent NFA has only 36 states requiring 73 KB — a reduction of roughly four orders of magnitude. Some formats in the Snort corpus required up to 383 MB under DFA-based ranking, rendering them prohibitive for deployment.
-
In PostgreSQL benchmarks, FPE-encrypted account-balance fields (libfte P-DD scheme, regex `\-[0-9]{9}`) reduce throughput by only 0.8% for complex mixed-transaction workloads (USUUI) and only 1.1% for SELECT-only workloads, relative to conventional authenticated encryption. Per-query latency for FPE versus authenticated encryption is identical across all five tested query types.
-
A deterministic FTE scheme (T-DD) that maps 16-digit credit card numbers to 7-byte ciphertext strings achieves simultaneous encryption and compression, reducing on-disk table size from 112 MB (authenticated encryption) to 42 MB — a 62.5% reduction — while maintaining provable privacy. The compression arises because the ciphertext format's message space is smaller than the plaintext's.
-
LibFTE exposes a regex-based API (Python, C++, JavaScript) that instantiates DPI-defeating FTE schemes from a regular-expression format specification alone, without expert cryptographic knowledge. The DCRS FTE scheme implemented in the library makes ciphertexts indistinguishable from real HTTP, SMTP, SMB, or other network-protocol messages under state-of-the-art DPI, and was already integrated into the Tor Browser Bundle at time of publication.
-
LibFTE's NFA-based 'relaxed ranking' sidesteps the PSPACE-hardness obstacle that previously made direct NFA ranking unworkable. Across 3,458 Snort IDS regular expressions in the network-monitor-circumvention setting, NFA-based ranking reduces client/server memory requirements by as much as 30% compared to DFA-based approaches.