检索结果-内蒙古大学图书馆

Fundamental Limits of Multi-Message private computation

IEEE Transactions on Communications 2025年

作者： Gholami, Ali Wan, Kai Jahani-Nezhad, Tayyebeh Sun, Hua Ji, Mingyue Caire, Giuseppe The Electrical Engineering and Computer Science Department Technische Universität Berlin Berlin10587 Germany The School of Electronic Information and Communications Huazhong University of Science and Technology Wuhan430074 China The Department of Electrical Engineering University of North Texas DentonTX76203 United States The Department of Electrical and Computer Engineering the University of Florida GainesvilleFL32611 United States

In a typical formulation of the private information retrieval (PIR) problem, a single user wishes to retrieve one out of K files from N servers without revealing the demanded file index to any server. This paper formulates an extended model of PIR, referred to as multi-message private computation (MMPC), where instead of retrieving a single file, the user wishes to retrieve P > 1 linear combinations of files while preserving the privacy of the demand information. The MM-PC problem is a generalization of the private computation (PC) problem (where the user requests one linear combination of the files), and the multi-message private information retrieval (MM-PIR) problem (where the user requests P > 1 files). A baseline achievable scheme repeats the optimal PC scheme by Sun and Jafar P times, or treats each possible demanded linear combination as an independent file and then uses the near optimal MM-PIR scheme by Banawan and Ulukus. In this paper, we propose a new MMPC scheme that significantly improves upon the baseline schemes. In doing so, we design the queries inspired by the structure in the cache-aided scalar linear function retrieval scheme by Wan et al., which leverages the dependency between linear functions to reduce the amount of communications. To ensure the decodability of our scheme, we propose a new method to benefit from the existing dependency, referred to as the sign assignment step. In the end, we use Maximum Distance Separable matrices to code the queries, which allows the reduction of download from the servers, while preserving privacy. By the proposed schemes, we characterize the capacity within a multiplicative factor of 2. © 1972-2012 IEEE.

关键词： multi-message private information retrieval multiple linear combinations private computation

来源：评论

学校读者我要写书评

暂无评论

private computation:: k-connected versus 1-connected networks

引用

JOURNAL OF CRYPTOLOGY 2006年第3期19卷 341-357页

作者： Blaeser, Markus Jakoby, Andreas Liskiewicz, Maciej Manthey, Bodo ETH Inst Theoret Informat CH-8092 Zurich Switzerland Med Univ Lubeck Inst Theoret Informat D-23538 Lubeck Germany

We study the role of connectivity of communication networks in private computations under information theoretical settings in the honest-but-curious model. We show that some functions can be 1-privately computed even if the underlying network is 1-connected but not 2-connected. Then we give a complete characterisation of non-degenerate functions that can be 1-privately computed on non-2-connected networks. Furthermore, we present a technique for simulating 1-private protocols that work on arbitrary (complete) networks on k-connected networks. For this simulation, at most (1-k/(n-1)) . L additional random bits are needed, where L is the number of bits exchanged in the original protocol and n is the number of players. Finally, we give matching lower and upper bounds for the number of random bits needed to compute the parity function on k-connected networks 1-privately, namely [(n=-2)/(k-1)] - 1 random bits for networks consisting of n players.

关键词： private computation secure multi-party computation secure function evaluation connectivity parity randomness

来源：评论

学校读者我要写书评

暂无评论

private computation using a PEZ dispenser

引用

THEORETICAL COMPUTER SCIENCE 2003年第1-3期306卷 69-84页

作者： Balogh, J Csirik, JA Ishai, Y Kushilevitz, E Ohio State Univ Dept Math Columbus OH 43210 USA Technion Dept Comp Sci IL-32000 Haifa Israel

We show how a (big) PEZ dispenser can be used by two or more players to compute a function of their inputs while hiding the values of the inputs from each other. In contrast to traditional approaches for solving this ... 详细信息

关键词： mathematical games private computation cryptographic protocols

来源：评论

学校读者我要写书评

暂无评论

A theorem on sensitivity and applications in private computation

引用

SIAM JOURNAL ON COMPUTING 2002年第5期31卷 1424-1437页

作者： Gál, A Rosén, A Univ Texas Dept Comp Sci Austin TX 78712 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Univ Toronto Dept Comp Sci Toronto ON Canada

In this paper we prove a theorem that gives an ( almost) tight upper bound on the sensitivity of a multiple-output Boolean function in terms of the sensitivity of its coordinates and the size of the range of the function. We apply this theorem to get improved lower bounds on the time ( number of rounds) to compute Boolean functions by private protocols. These bounds are given in terms of the sensitivity of the function being computed and the amount of randomness used by the private protocol. These lower bounds are tight (up to constant factors) for the case of the xor function and together with the results in [ E. Kushilevitz and A. Rosen, SIAM J. Discrete Math., 11 (1998), pp. 61-80.] establish a tight (up to constant factors) tradeoff between randomness and time in private computation.

关键词： sensitivity private computation randomness lower bounds

来源：评论

学校读者我要写书评

暂无评论

On private computation in incomplete networks

引用

DISTRIBUTED COMPUTING 2007年第3期19卷 237-252页

作者： Beimel, Amos Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

Suppose that some parties are connected by an incomplete network of reliable and private channels. The parties cooperate to execute some protocol. However, the parties are curious-after the protocol terminates each party tries to learn information from the communication it heard. We say that a function can be computed privately in a network if there is a protocol in which each processor learns only the information implied by its input and the output of the function (in the information theoretic sense). The question we address in this paper is what functions can be privately computed in a given incomplete network. Every function can be privately computed in two-connected networks with at least three parties. Thus, the question is interesting only for non two-connected networks. Generalizing results of (Blaser et al. in J. Cryptol, 19(3): 341-357, 2006), we characterize the functions that can be computed privately in simple networks-networks with one separating vertex and no leaves. We then deal with private computations in arbitrary non two-connected networks: we reduce this question to private computations of related functions on trees, and give some sufficient conditions and necessary conditions on the functions that can be privately computed on trees.

关键词： private computation incomplete communication networks connectivity

来源：评论

学校读者我要写书评

暂无评论

The Capacity of private computation

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2019年第6期65卷 3880-3897页

作者： Sun, Hua Jafar, Syed Ali Univ North Texas Dept Elect Engn Denton TX 76203 USA Univ Calif Irvine Dept Elect Engn & Comp Sci Ctr Pervas Commun & Comp Irvine CA 92697 USA

We introduce the problem of private computation, comprised of N distributed and non-colluding servers, K independent datasets, and a user who wants to compute a function of the datasets privately, i.e., without revealing which function he wants to compute, to any individual server. This private computation problem is a strict generalization of the private information retrieval (PIR) problem, obtained by expanding the PIR message set (which consists of only independent messages) to also include functions of those messages. The capacity of private computation, C, is defined as the maximum number of bits of the desired function that can be retrieved per bit of total download from all servers. We characterize the capacity of private computation, for N servers and K independent datasets that are replicated at each server, when the functions to be computed are arbitrary linear combinations of the datasets. Surprisingly, the capacity, C = (1 + 1/N + ... + 1/NK-1)(-1), matches the capacity of PIR with N servers and K messages. Thus, allowing arbitrary linear computations does not reduce the communication rate compared to pure dataset retrieval. The same insight is shown to hold even for arbitrary non-linear computations when the number of datasets K -> infinity.

关键词： Capacity private computation private information retrieval

来源：评论

学校读者我要写书评

暂无评论

Comprehension from Chaos: Towards Informed Consent for private computation 23

Comprehension from Chaos: Towards Informed Consent for Priva...

引用

30th ACM SIGSAC Conference on Computer and Communications Security (ACM CCS)

作者： Kacsmar, Bailey Duddu, Vasisht Tilbury, Kyle Ur, Blase Kerschbaum, Florian Univ Alberta Edmonton AB Canada Univ Waterloo Waterloo ON Canada Univ Chicago Chicago IL 60637 USA

ISBN: (纸本)9798400700507

private computation, which includes techniques like multi-party computation and private query execution, holds great promise for enabling organizations to analyze data they and their partners hold while maintaining data subjects' privacy. Despite recent interest in communicating about differential privacy, end users' perspectives on private computation have not previously been studied. To fill this gap, we conducted 22 semi-structured interviews investigating users' understanding of, and expectations for, private computation over data about them. Interviews centered on four concrete data-analysis scenarios (e.g., ad conversion analysis), each with a variant that did not use private computation and another that did. While participants struggled with abstract definitions of private computation, they found the concrete scenarios enlightening and plausible even though we did not explain the complex cryptographic underpinnings. private computation increased participants' acceptance of data sharing, but not unconditionally;the purpose of data sharing and analysis was the primary driver of their attitudes. Through collective activities, participants emphasized the importance of detailing the purpose of a computation and clarifying that inputs to private computation are not shared across organizations when describing private computation to end users.

关键词： private computation Secure Multi-Party computation User Study

来源：评论

学校读者我要写书评

暂无评论

Ω(log n) lower bounds on the amount of randomness in 2-private computation

引用

SIAM JOURNAL ON COMPUTING 2005年第4期34卷 946-959页

作者： Gál, A Rosén, A Univ Texas Dept Comp Sci Austin TX 78712 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

We consider the amount of randomness necessary in information-theoretic private protocols. We prove that at least Omega( log n) random bits are necessary for the t-private computation of the function xor by n players for any t >= 2. In view of the upper bound of O(t(2) log(n/t)) [ E. Kushilevitz and Y. Mansour, SIAM J. Discrete Math., 10 ( 1997), pp. 647 - 661], this bound is tight, up to constant factors, for any fixed t. For a class of protocols obeying certain restrictions, we give a stronger lower bound of Omega( t log( n/ t)). We note that all known randomness efficient private protocols designed specifically for xor belong to this class. In fact we prove slightly stronger statements: we prove that on every input there is a run where the number of random bits used is large, rather than proving only that on some input there is a run where the number of random bits used is large. All our lower bounds hold for the "trusted dealer" model as well, and the Omega( t log( n/ t)) lower bound for restricted protocols is tight, up to constant factors, for any t >= 2 in this model. In comparison, the previous lower bounds on the amount of randomness required by t-private computation of explicit functions did not grow with n for constant values of t, and our results improve the previous lower bounds for xor for any 2 <= t = o( log n). Our results also show that already for t = 2, Omega( log n) random bits are necessary, while it is known that for the case of t = 1 a single random bit is sufficient for privately computing xor for any number of players. Our proofs use novel techniques by which we extract random variables from a t-private protocol, and then use the t-privacy property of the protocol to prove properties of these random variables. These properties in turn imply that the number of random bits used by the players is large.

关键词： private computation randomness lower bounds

来源：评论

学校读者我要写书评

暂无评论

private Polynomial computation From Lagrange Encoding

引用

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2020年 15卷 553-563页

作者： Raviv, Netanel Karpuk, David A. CALTECH Dept Elect Engn Pasadena CA 91125 USA Univ Los Andes Dept Matemat Bogota 111711 Colombia

private computation is a generalization of private information retrieval, in which a user is able to compute a function on a distributed dataset without revealing the identity of that function to the servers. In this paper, it is shown that Lagrange encoding, a powerful technique for encoding Reed-Solomon codes, enables private computation in many cases of interest. In particular, we present a scheme that enables private computation of polynomials of any degree on Lagrange encoded data, while being robust to Byzantine and straggling servers, and to servers colluding to attempt to deduce the identities of the functions to be evaluated. Moreover, incorporating ideas from the well-known Shamir secret sharing scheme allows the data itself to be concealed from the servers as well. Our results extend private computation to high degree polynomials and to data-privacy, and reveal a tight connection between private computation and coded computation.

关键词： private computation private information retrieval (PIR) data privacy Reed-Solomon codes

来源：评论

学校读者我要写书评

暂无评论

private Linear computation for Noncolluding Coded Databases

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2022年第3期40卷 847-861页

作者： Obead, Sarah A. Lin, Hsuan-Yin Rosnes, Eirik Kliewer, Jorg New Jersey Inst Technol Helen & John C Hartmann Dept Elect & Comp Engn Newark NJ 07102 USA Simula UiB N-5006 Bergen Norway

private computation in a distributed storage system (DSS) is a generalization of the private information retrieval (PIR) problem. In such a setting, a user wishes to compute a function of f messages stored in n noncolluding coded databases, i.e., databases storing data encoded with an [n,k] linear storage code, while revealing no information about the desired function to the databases. We consider the problem of private linear computation (PLC) for coded databases. In PLC, a user wishes to compute a linear combination over the f messages while keeping the coefficients of the desired linear combination hidden from the databases. For a DSS setup where data is stored using a code from a particular family of linear storage codes, we derive an outer bound on the PLC rate, which is defined as the ratio of the desired amount of information and the total amount of downloaded information. In particular, the proposed converse is valid for any number of messages and linear combinations, and depends on the rank of the coefficient matrix obtained from all linear combinations. Further, we present a PLC scheme with rate equal to the outer bound and hence settle the PLC capacity for the considered class of linear storage codes. Interestingly, the PLC capacity matches the maximum distance separable coded capacity of PIR for the considered class of linear storage codes.

关键词： Spread spectrum communication Codes Protocols Distributed databases Information retrieval Indexes Linear codes Capacity information-theoretic privacy private computation private information retrieval

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：