TY - BOOK

T1 - Practical Secure Computation with Pre-Processing

AU - Zakarias, Rasmus Winther

PY - 2016/3/30

Y1 - 2016/3/30

N2 - Secure Multiparty Computation has been divided between protocols best suited for binary circuits and protocols best suited for arithmetic circuits. With their MiniMac protocol in [DZ13], Damgård and Zakarias take an important step towards bridging these worlds with an arithmetic protocol tuned for binary (or small field) circuits. The first main result in this dissertation closes this gap entirely. We present improvements to the MiniMac protocol that obtain full efficiency of the arithmetic protocol while evaluating multiple versions of the same binary circuit on different inputs. The improvements are implemented in practice and show state of the art performance for the Oblivious AES bench- mark application. We do 680 AES circuits in parallel within 3 seconds, resulting in an amortized execution time of 4ms per AES block. The latency of 3 seconds is hard to cope with in practical scenarios such as verification of one time pass- words. Thus motivated to bring down latency for AES we present the second main result which is a dedicated version of the MiniMac protocol to the special structure of AES. We bring down the latency 500-fold to about 6ms in latency for 15 AES blocks in parallel. This yields an astonishing fast evaluation per AES block of 400μs = 400 ∗ 10−6 seconds. Our techniques focus on AES but work in general. In particular we reduce round complexity of the protocol using oblivious table lookup to take care of the non-linear parts. At first glance one might expect table lookup to take much more space for pre-processing material than computing the non-linear parts online (depends on the quality of circuit of course). Surprisingly, even for our optimized AES-circuit this is not the case. We further improve the design of the pre-processing material and end up with only 10 megabyes of pre-processing needed to do 15 AES blocks. Interestingcontinuation of this work would be to apply our technique on other symmetric primitives such as SHA-256.Another interesting application of the MiniMac protocol is that of large integer multiplication. We present in our third main result a technique that allows a protocol for small field arithmetic to do fast large integer multipli- cations. This is achieved by devising pre-processing material that allows the Toom-Cook multiplication algorithm to run between the parties with linear communication complexity. With this result computation on the CPU by the parties is (at least) squared in the input size (number of digits in the operands). To bring this further down we show that our construction also works for the Shönhage-Strassen multiplication technique, allowing us to do large integer multiplications given a small field protocol, communicating O(n log∗ n) ele- ments in the small field and performing O(n log n log log n) operations on small field elements.The fourth main result of the dissertation is a generic and efficient protocol for proving knowledge of a witness for circuit satisfiability in Zero-Knowledge. We prove our construction secure in the UC-framework. Then, we give an im- plementation and benchmark the protocol on an optimized binary circuit for the Oblivious AES demonstration example. In a bit more details, we demon- strate how a prover can prove knowledge of a particular key encrypting a public plain-text to a particular public cipher-text. This is useful, e.g. in a sign-in scenario where we want to protect user secrets (the keys) from leaking if the server in compromised.

AB - Secure Multiparty Computation has been divided between protocols best suited for binary circuits and protocols best suited for arithmetic circuits. With their MiniMac protocol in [DZ13], Damgård and Zakarias take an important step towards bridging these worlds with an arithmetic protocol tuned for binary (or small field) circuits. The first main result in this dissertation closes this gap entirely. We present improvements to the MiniMac protocol that obtain full efficiency of the arithmetic protocol while evaluating multiple versions of the same binary circuit on different inputs. The improvements are implemented in practice and show state of the art performance for the Oblivious AES bench- mark application. We do 680 AES circuits in parallel within 3 seconds, resulting in an amortized execution time of 4ms per AES block. The latency of 3 seconds is hard to cope with in practical scenarios such as verification of one time pass- words. Thus motivated to bring down latency for AES we present the second main result which is a dedicated version of the MiniMac protocol to the special structure of AES. We bring down the latency 500-fold to about 6ms in latency for 15 AES blocks in parallel. This yields an astonishing fast evaluation per AES block of 400μs = 400 ∗ 10−6 seconds. Our techniques focus on AES but work in general. In particular we reduce round complexity of the protocol using oblivious table lookup to take care of the non-linear parts. At first glance one might expect table lookup to take much more space for pre-processing material than computing the non-linear parts online (depends on the quality of circuit of course). Surprisingly, even for our optimized AES-circuit this is not the case. We further improve the design of the pre-processing material and end up with only 10 megabyes of pre-processing needed to do 15 AES blocks. Interestingcontinuation of this work would be to apply our technique on other symmetric primitives such as SHA-256.Another interesting application of the MiniMac protocol is that of large integer multiplication. We present in our third main result a technique that allows a protocol for small field arithmetic to do fast large integer multipli- cations. This is achieved by devising pre-processing material that allows the Toom-Cook multiplication algorithm to run between the parties with linear communication complexity. With this result computation on the CPU by the parties is (at least) squared in the input size (number of digits in the operands). To bring this further down we show that our construction also works for the Shönhage-Strassen multiplication technique, allowing us to do large integer multiplications given a small field protocol, communicating O(n log∗ n) ele- ments in the small field and performing O(n log n log log n) operations on small field elements.The fourth main result of the dissertation is a generic and efficient protocol for proving knowledge of a witness for circuit satisfiability in Zero-Knowledge. We prove our construction secure in the UC-framework. Then, we give an im- plementation and benchmark the protocol on an optimized binary circuit for the Oblivious AES demonstration example. In a bit more details, we demon- strate how a prover can prove knowledge of a particular key encrypting a public plain-text to a particular public cipher-text. This is useful, e.g. in a sign-in scenario where we want to protect user secrets (the keys) from leaking if the server in compromised.

M3 - Ph.D. thesis

BT - Practical Secure Computation with Pre-Processing

PB - Department of Computer Science, Aarhus University

ER -