Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.06125 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911783540752384 |
|---|---|
| author | Dæhli, Karen M. Obead, Sarah A Lin, Hsuan-Yin Rosnes, Eirik |
| author_facet | Dæhli, Karen M. Obead, Sarah A Lin, Hsuan-Yin Rosnes, Eirik |
| contents | In private computation, a user wishes to retrieve a function evaluation of messages stored on a set of databases without revealing the function's identity to the databases. Obead \emph{et al.} introduced a capacity outer bound for private nonlinear computation, dependent on the order of the candidate functions. Focusing on private \emph{quadratic monomial} computation, we propose three methods for ordering candidate functions: a graph edge-coloring method, a graph-distance method, and an entropy-based greedy method. We confirm, via an exhaustive search, that all three methods yield an optimal ordering for $f < 6$ messages. For $6 \leq f \leq 12$ messages, we numerically evaluate the performance of the proposed methods compared with a directed random search. For almost all scenarios considered, the entropy-based greedy method gives the smallest gap to the best-found ordering. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_06125 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Capacity Outer Bound for Private Quadratic Monomial Computation Dæhli, Karen M. Obead, Sarah A Lin, Hsuan-Yin Rosnes, Eirik Information Theory In private computation, a user wishes to retrieve a function evaluation of messages stored on a set of databases without revealing the function's identity to the databases. Obead \emph{et al.} introduced a capacity outer bound for private nonlinear computation, dependent on the order of the candidate functions. Focusing on private \emph{quadratic monomial} computation, we propose three methods for ordering candidate functions: a graph edge-coloring method, a graph-distance method, and an entropy-based greedy method. We confirm, via an exhaustive search, that all three methods yield an optimal ordering for $f < 6$ messages. For $6 \leq f \leq 12$ messages, we numerically evaluate the performance of the proposed methods compared with a directed random search. For almost all scenarios considered, the entropy-based greedy method gives the smallest gap to the best-found ordering. |
| title | Improved Capacity Outer Bound for Private Quadratic Monomial Computation |
| topic | Information Theory |
| url | https://arxiv.org/abs/2401.06125 |