Efficiency optimizations on Yao`s garbled circuits and their practical applications

Abstract

Bulut bilişim ve büyük veri teknolojilerinin ilerlemesi insanların bilişim sistemlerini kullanmayollarında büyük değişimler getirmiştir. Bu teknolojiler hayatımızı büyük ölçüdekolaylaştırırken, aynı zamanda hesaplamaların uzak bir sunucuda yapılması nedeniyle bilgilerinmahremiyetini ve güvenliğini tehlikeye atmaktadırlar. Birbirine yeterince güvenemeyeniki veya daha fazla tarafın bir fonksiyonu güvenli olarak hesaplamasını gerektirengerçek hayatta karşılaşılabilecek birçok durum vardır. Bu sebeple, kullanıcılarınveri mahremiyetini koruyan çeşitli güvenli hesaplama yöntemleri önerilmiştir. Yao'nunkarıştırılmış devresi protokolü bu güvenli hesaplama problemine karşı önerilmiş en güçlüçözümlerden biridir. Bu tezde, öncelikle Yao protokolünü ve bu protokolün optimizasyonuiçin önerilmiş gelişmelerin tam listesini anlatmaktayız. Aynı zamanda, bu gelişmeleriiletişim ve hesaplama zorluğu olarak kıyaslıyoruz ve birbirleriyle uyumluluklarını analizediyoruz. Bu güçlü protokolün pratikteki kullanımını göstermek amacıyla çeşitli genelYao uygulamalarını (karıştırılmış RAM dahil) inceliyoruz. Bu uygulamaları kullandıklarıkarışık devre optimizasyonlarına göre kıyaslıyoruz. Özel olarak bazı gerçek-hayat uygulamalarıylaYao protokolünü daha da örneklendiriyoruz. Hesaplanacak fonksiyonun dagizli bir bilgi olması durumunda, onun da gizlenmesinin tam bi mahremiyet için gerekliolduğu unutulmamalıdır. Bu doğrultuda geliştirilmiş olan gizli fonksiyon hesaplama yöntemlerini,özellikle karışık devrelerin önemli bir rolünün olduğu iki taraflı durum içintezimizde anlatıyoruz. Son olarak Mohassel ve Sadeghian'ın geliştirmiş olduğu mekanizmayıele alıyoruz ve olası devre haritalarının sayısını hesaplamak için kullanılacak yenibir teknik önererek buna katkıda bulunuyoruz.

The advance of cloud computing and big data technologies brings out major changesin the ways that people make use of information systems. While those technologies extremelyease our lives, they impose the danger of compromising privacy and security ofdata due to performing the computation on an untrusted remote server. Moreover, thereare also many other real-world scenarios requiring two or more (possibly distrustful) partiesto securely compute a function without leaking their respective inputs to each other.In this respect, various secure computation mechanisms have been proposed in order toprotect users' data privacy. Yao's garbled circuit protocol is one of the most powerful solutionsfor this problem. In this thesis, we first describe the Yao's protocol in detail, andinclude the complete list of optimizations over the Yao's protocol. We also compare theiradvantages in terms of communication and computation complexities, and analyse theircompatibility with each other. We also look into generic Yao implementations (includinggarbled RAM) to demonstrate the use of this powerful tool in practice. We comparethose generic implementations in terms of their use of garbled circuit optimizations. Wealso cover the specific real-world applications for further illustration. Moreover, in somescenarios, the functionality itself may also need to be kept private which leads to an idealsolution of secure computation problem. In this direction, we finally cover the problemof Private Function Evaluation, in particular for the 2-party case where garbled circuitshave an important role. We finally analyse the generic mechanism of Mohassel et al.and contribute to it by proposing a new technique for the computation of the number ofpossible circuit mappings.