Efficient Garbled RAM

 Garbled Circuits (GC) originally proposed by Yao is the cryptographic technique that is traditionally used to perform secure two party computation (2PC) for functions. However, circuits by their nature are static, and if the two parties want to securely compute a RAM program involving dynamic memory accesses, then converting the RAM program to a circuit would incur a polynomial cost in the size of the memory as every memory locations will need to be scanned on each access. To avoid this polynomial blowup, the abstraction of Garbled RAM (GRAM) was introduced by Lu and Ostrovsky to garble RAM programs directly without converting to a circuit. In this work, we use techniques of tri-state circuits (TSC) proposed in the recent work of Heath et. al. to present a new Garbled RAM scheme which matches the best known asymptomatic overhead of O(log³(N)* loglogN) gates per access while providing significant improvements in constant factors. As part of our scheme we propose new constructions for the garbled stack/co-stack data structures which have both an average-case and worst-case cost of O(log N). Our new construction is an improvement over the existing garbled stack/co-stack construction used in all previous works which have a worst-case cost of O(N).