With the proliferation of cloud computing, security becomes a key issue. Code obfuscation is a promising approach in that domain. It has been proposed to make an adversary confused about understanding the program, thereby making attacks more difficult. In this paper, we propose a novel method which exploits multi-core processing to substantially increase the complexity of programs, complicating the original ones. At basic block level, this method automatically partitions any serial thread into an arbitrary number of parallel threads. Moreover, the program semantics are preserved through using guards, guaranteeing that one basic-block be active at a time. Our method allows for m^n possible combinations for a given program, for m threads and n basic-blocks, which significantly complicates the execution state, as well as changes the layout of basic blocks in memory. We provide a proof of correctness of the algorithm, as well as an implementation within the LLVM framework. For a naive implementation, a slow down of 10-130 is measured depending on the communication distance among threads, while code similarity (as a measure of complexity) is less than 2% in most cases. We further explore the effect of a thread affined loop assignment on performance; promising results indicate a maximum of three times slowdown, with negligible change in complexity.