We introduce TinyGarble, a novel automated methodology for generating compressed Boolean circuits for Yao’s Garbled Circuit (GC) protocol. TinyGarble achieves an unprecedented level of compactness and scalability by introducing sequential function description to GC. It also allows adaptation of powerful logic synthesis tools for optimizing the generated circuit using newly created custom libraries. While our approach is in contrast with the state-of-the-art garbling methods that only operate on the combinational logic, we introduce new transformations such that our sequential circuits can be securely evaluated by interfacing with the earlier frontend garbling schemes. TinyGarble’s ultra compact circuit representations can fit merely on the processor cache, which results in fewer cache misses and thereby leads to less number of CPU cycles. Proof-of-concept implementation of TinyGarble on benchmark circuits demonstrates a high degree of compactness and scalability. We improve the results of the best known automatic tool for GC generation reported in [36] by several orders of magnitude: for example, TinyGarble can compact the 1024-bit multiplication by 4172 times, while decreasing the number of non-XOR’s by 67% in comparison. Moreover, TinyGarble is able to implement functions that have never been reported before, such as RSA-8192 and SHA-3, which can be represented as circuits requiring about 7.87MB and 160KB of memory respectively. Finally, our sequential description enables us to design a secure calculator based on a stack machine. This is the first scalable emulation of a universal circuit for semi-private function evaluation where the number of instruction invocations is not limited by the circuit size.