Limits...
Logsum using Garbled Circuits.

Portêlo J, Raj B, Trancoso I - PLoS ONE (2015)

Bottom Line: We propose a technique for computing the logsum operation using Garbled Circuits.This technique relies on replacing the logsum operation with an equivalent piecewise linear approximation, taking advantage of recent advances in efficient methods for both designing and implementing Garbled Circuits.We elaborate on how all the required blocks should be assembled in order to obtain small errors regarding the original logsum operation and very fast execution times.

View Article: PubMed Central - PubMed

Affiliation: INESC-ID, Lisbon, Portugal; Instituto Superior Técnico, Universidade de Lisboa, Lisbon, Portugal.

ABSTRACT
Secure multiparty computation allows for a set of users to evaluate a particular function over their inputs without revealing the information they possess to each other. Theoretically, this can be achieved using fully homomorphic encryption systems, but so far they remain in the realm of computational impracticability. An alternative is to consider secure function evaluation using homomorphic public-key cryptosystems or Garbled Circuits, the latter being a popular trend in recent times due to important breakthroughs. We propose a technique for computing the logsum operation using Garbled Circuits. This technique relies on replacing the logsum operation with an equivalent piecewise linear approximation, taking advantage of recent advances in efficient methods for both designing and implementing Garbled Circuits. We elaborate on how all the required blocks should be assembled in order to obtain small errors regarding the original logsum operation and very fast execution times.

No MeSH data available.


Execution time for selected values of N, ℓ and k, step quantization (SQ) approach, when an Intel Core i7-3630QM CPU @ 2.40GHz with a 6MB L3 cache memory and an 8GB DDR3 RAM memory is considered.N corresponds to the number of inputs for the logsum, ℓ corresponds to the number of bits representing the inputs and k is the number of entries of the look-up table for the piecewise linear approximation. The dashed lines correspond to the experiments performed with the VIPP toolkit; the solid lines correspond to the experiments performed with the JustGarble toolkit.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4374976&req=5

pone.0122236.g004: Execution time for selected values of N, ℓ and k, step quantization (SQ) approach, when an Intel Core i7-3630QM CPU @ 2.40GHz with a 6MB L3 cache memory and an 8GB DDR3 RAM memory is considered.N corresponds to the number of inputs for the logsum, ℓ corresponds to the number of bits representing the inputs and k is the number of entries of the look-up table for the piecewise linear approximation. The dashed lines correspond to the experiments performed with the VIPP toolkit; the solid lines correspond to the experiments performed with the JustGarble toolkit.

Mentions: We considered two different processor and memory settings for our experiments: 1) an Intel Core i7-3630QM CPU @ 2.40GHz with a 6MB L3 cache memory and an 8GB DDR3 RAM memory and 2) an Intel Xeon E5530 CPU @ 2.40GHz with a 8MB L3 cache memory and a 48GB DDR3 RAM memory. The results obtained for the SQ and RQ approaches for the first setting are presented in Figs. 4 and 5, respectively. The execution times obtained for both GC toolkits when the second setting was considered are around 10% to 15% slower than the ones from the first setting, but have otherwise a very similar behavior to them. Therefore, and in order to avoid overloading this section, we decided not to reproduce them. Each of the results was obtained by averaging the execution time of one thousand consecutive runs of the logsum algorithm. As expected, for both GC toolkits and using the same values of ℓ and k, the RQ approach takes longer than the SQ approach to compute a logsum. We observe that for the VIPP toolkit there is a near quadratic increase of the execution time with increasing values of N, probably a consequence of the successively larger circuits that need to be loaded into memory. We also notice that for the JustGarble toolkit there is a constant linear relationship between how long it takes to compute the logsum and the number of inputs for all values of ℓ and k, meaning that our approach also scales nicely with N regarding the execution time. Finally and more importantly, the JustGarble toolkit is consistently two or three orders of magnitude faster than the VIPP toolkit, definitely showing that when larger garbled circuits are considered, it is extremely important to use a toolkit specially designed for optimal memory management.


Logsum using Garbled Circuits.

Portêlo J, Raj B, Trancoso I - PLoS ONE (2015)

Execution time for selected values of N, ℓ and k, step quantization (SQ) approach, when an Intel Core i7-3630QM CPU @ 2.40GHz with a 6MB L3 cache memory and an 8GB DDR3 RAM memory is considered.N corresponds to the number of inputs for the logsum, ℓ corresponds to the number of bits representing the inputs and k is the number of entries of the look-up table for the piecewise linear approximation. The dashed lines correspond to the experiments performed with the VIPP toolkit; the solid lines correspond to the experiments performed with the JustGarble toolkit.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4374976&req=5

pone.0122236.g004: Execution time for selected values of N, ℓ and k, step quantization (SQ) approach, when an Intel Core i7-3630QM CPU @ 2.40GHz with a 6MB L3 cache memory and an 8GB DDR3 RAM memory is considered.N corresponds to the number of inputs for the logsum, ℓ corresponds to the number of bits representing the inputs and k is the number of entries of the look-up table for the piecewise linear approximation. The dashed lines correspond to the experiments performed with the VIPP toolkit; the solid lines correspond to the experiments performed with the JustGarble toolkit.
Mentions: We considered two different processor and memory settings for our experiments: 1) an Intel Core i7-3630QM CPU @ 2.40GHz with a 6MB L3 cache memory and an 8GB DDR3 RAM memory and 2) an Intel Xeon E5530 CPU @ 2.40GHz with a 8MB L3 cache memory and a 48GB DDR3 RAM memory. The results obtained for the SQ and RQ approaches for the first setting are presented in Figs. 4 and 5, respectively. The execution times obtained for both GC toolkits when the second setting was considered are around 10% to 15% slower than the ones from the first setting, but have otherwise a very similar behavior to them. Therefore, and in order to avoid overloading this section, we decided not to reproduce them. Each of the results was obtained by averaging the execution time of one thousand consecutive runs of the logsum algorithm. As expected, for both GC toolkits and using the same values of ℓ and k, the RQ approach takes longer than the SQ approach to compute a logsum. We observe that for the VIPP toolkit there is a near quadratic increase of the execution time with increasing values of N, probably a consequence of the successively larger circuits that need to be loaded into memory. We also notice that for the JustGarble toolkit there is a constant linear relationship between how long it takes to compute the logsum and the number of inputs for all values of ℓ and k, meaning that our approach also scales nicely with N regarding the execution time. Finally and more importantly, the JustGarble toolkit is consistently two or three orders of magnitude faster than the VIPP toolkit, definitely showing that when larger garbled circuits are considered, it is extremely important to use a toolkit specially designed for optimal memory management.

Bottom Line: We propose a technique for computing the logsum operation using Garbled Circuits.This technique relies on replacing the logsum operation with an equivalent piecewise linear approximation, taking advantage of recent advances in efficient methods for both designing and implementing Garbled Circuits.We elaborate on how all the required blocks should be assembled in order to obtain small errors regarding the original logsum operation and very fast execution times.

View Article: PubMed Central - PubMed

Affiliation: INESC-ID, Lisbon, Portugal; Instituto Superior Técnico, Universidade de Lisboa, Lisbon, Portugal.

ABSTRACT
Secure multiparty computation allows for a set of users to evaluate a particular function over their inputs without revealing the information they possess to each other. Theoretically, this can be achieved using fully homomorphic encryption systems, but so far they remain in the realm of computational impracticability. An alternative is to consider secure function evaluation using homomorphic public-key cryptosystems or Garbled Circuits, the latter being a popular trend in recent times due to important breakthroughs. We propose a technique for computing the logsum operation using Garbled Circuits. This technique relies on replacing the logsum operation with an equivalent piecewise linear approximation, taking advantage of recent advances in efficient methods for both designing and implementing Garbled Circuits. We elaborate on how all the required blocks should be assembled in order to obtain small errors regarding the original logsum operation and very fast execution times.

No MeSH data available.