Secure two-party input-size reduction: Challenges, solutions and applications

Autor: Duc Viet Le, Mikhail J. Atallah, Javad Darivandpour
Rok vydání: 2021
Předmět:
Zdroj: Information Sciences. 567:256-277
ISSN: 0020-0255
DOI: 10.1016/j.ins.2021.01.038
Popis: The computation and communication costs of many secure multiparty protocols would benefit from a preprocessing that replaces large inputs with much smaller values without changing the outputs. This preprocessing is especially advantageous when its cost can be amortized over subsequent computations that all benefit from smaller inputs. The above holds for protocols based on garbled circuits, homomorphic encryption, or other techniques. Problems benefiting from such preprocessing include pattern matching, information retrieval, and sequence comparisons that depend on (in)equality of comparands. Motivated by this (in)equality-preservation requirement, we define the problem as follows: Alice’s and Bob’s inputs are their respective private sets S A and S B of large integers, and their private outputs are images of their sets under a function ρ that injectively maps S A ∪ S B into { 0 , 1 , … , N - 1 } for a small N ⩾ | S A | + | S B | . Alice’s (Bob’s) knowledge of this mapping on S A ( S B ) must reveal nothing about S B ( S A ). Thus, neither party should be able to learn ρ ( x ) for any x that is not in its private set; otherwise, s/he could exploit the small codomain of ρ to learn about the other party’s set. We formalize the problem, propose efficient and secure (semi-honest model) solutions to it, and discuss its use cases.
Databáze: OpenAIRE
Externí odkaz: