Limits...
Logsum using Garbled Circuits.

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

Bottom Line: 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.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.


Related in: MedlinePlus

Circuit diagram for the logsum operation for any N inputs.The logsum of N elements is computed using a hierarchical structure, computing the logsum of two elements at a time. After each level the number of bits required to represent the output increases by 1. If the inputs are represented by ℓ bits, the output will be represented by ℓ+p bits, with p = ⌈log2N⌉.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0122236.g003: Circuit diagram for the logsum operation for any N inputs.The logsum of N elements is computed using a hierarchical structure, computing the logsum of two elements at a time. After each level the number of bits required to represent the output increases by 1. If the inputs are represented by ℓ bits, the output will be represented by ℓ+p bits, with p = ⌈log2N⌉.

Mentions: The Garbled Circuit described previously implements the logsum operation for the simplest case of N = 2 input values. Here we present the generalization of this methods to any given N. Let us start by recalling the original formulation of the logsum in Equation 3, which for N = 4 can be written asz(m)=logexp(m1)+exp(m2)+exp(m3)+exp(m4)=logelogexp(m1)+exp(m2)+elogexp(m3)+exp(m4)=logez(m′)+ez(m″),(6)with m′ = (m1,m2) and m′′ = (m3,m4). This means that the logsum for N = 4 input values can be obtained by computing two logsum operations, each of two input values. This process can be repeated as many times as needed, leading to a hierarchical tree structure for computing the logsum operation, as illustrated in Fig. 3. With this structure, the difference in the number of bits between the output and the inputs is p = ⌈log2N⌉.


Logsum using Garbled Circuits.

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

Circuit diagram for the logsum operation for any N inputs.The logsum of N elements is computed using a hierarchical structure, computing the logsum of two elements at a time. After each level the number of bits required to represent the output increases by 1. If the inputs are represented by ℓ bits, the output will be represented by ℓ+p bits, with p = ⌈log2N⌉.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0122236.g003: Circuit diagram for the logsum operation for any N inputs.The logsum of N elements is computed using a hierarchical structure, computing the logsum of two elements at a time. After each level the number of bits required to represent the output increases by 1. If the inputs are represented by ℓ bits, the output will be represented by ℓ+p bits, with p = ⌈log2N⌉.
Mentions: The Garbled Circuit described previously implements the logsum operation for the simplest case of N = 2 input values. Here we present the generalization of this methods to any given N. Let us start by recalling the original formulation of the logsum in Equation 3, which for N = 4 can be written asz(m)=logexp(m1)+exp(m2)+exp(m3)+exp(m4)=logelogexp(m1)+exp(m2)+elogexp(m3)+exp(m4)=logez(m′)+ez(m″),(6)with m′ = (m1,m2) and m′′ = (m3,m4). This means that the logsum for N = 4 input values can be obtained by computing two logsum operations, each of two input values. This process can be repeated as many times as needed, leading to a hierarchical tree structure for computing the logsum operation, as illustrated in Fig. 3. With this structure, the difference in the number of bits between the output and the inputs is p = ⌈log2N⌉.

Bottom Line: 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.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.


Related in: MedlinePlus