New Obfuscation Scheme for Conjunctions

Abstract

Recently, there has been renewed interest in conjunction obfuscations. A conjunction, which is called pattern matching with wildcards sometimes, is associated with a pattern |$\mathsf{pat}\in \{0,1,*\}^n$| where * is a wildcard. It accepts if and only if the input bits are the same as the pattern at all non-wildcard positions. The conjunction obfuscation starts to get noticed because it provides the ability to protect these sensitive patterns while preserving its functionality. It is meaningful when the conjunction obfuscation is applied in the pattern matching, biological recognition, resisting SQL injection attacks and so on. In this work, we propose a new candidate of conjunction obfuscation. It not only retains the simplicity of the intuitive scheme in BKM18, but also adds wildcards to the pattern. Besides, we also propose a conjunction obfuscation with multi-bit output. The second obfuscation has the same size of the obfuscated program as the first obfuscation. Both obfuscations provide the distributional virtual black-box security.