...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Two results on the bit extraction problem
【24h】

Two results on the bit extraction problem

机译：关于位提取问题的两个结果

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

An (n,s, t)-resilient function is a function f:{1, -1)(n) --> {1, -1}(s), such that every element in {1, -1}(s) has the same probability to occur when t arbitrary input variables are fixed by an adversary and the remaining n - t variables are assigned -1 or 1 uniformly and independently. A basic problem is to find the largest possible t given n and s such that an (n,s, t)-resilient function exists. As mentioned in [5,2,3] resilient functions have been involving in some interesting cryptographic applications, such as amplifying privacy and generating shared random strings in the presence of faulty processors. The following coloring problem is closely related to resilient functions. A good coloring of the n-dimensional Boolean cube with c = 2(s) colors is such that in every k-dimensional subcube each color appears 2(k)/c times. Here we are interested in the smallest k for which such a coloring exists. A coloring is locally symmetric if each vertex in the n-cube has the same number of neighbors from each color other than its own. An XOR-type coloring is one obtained by a linear map GF(2)(n) --> GF(2)(s). We answer the following problems proposed by Friedman [5]: (1) If c - 1, are all optimal colorings necessarily locally symmetric? (2) Ale there optimal colorings not obtainable as XOR type colorings? We provide positive answers to both questions. For (2), we show that there are infinitely many non-XOR-type optimal solutions, which is also proved by Stinson et al. with a different method [8]. Our main tool is an expression of the eigenvalues of the distance-i adjacency matrix of the it-cube via the Krawtchouk polynomials. With the technique, we are able to make the background of some claims in [5,p. 318] clearer. Along the way we prove some identities involving the distance distribution of color classes, in order to gain a better understanding of the structure of color classes. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 8]
机译：（n，s，t）弹性函数是函数f：{1，-1）（n）-> {1，-1}（s），这样{1，-1}（当敌手确定t个任意输入变量并且将其余n-t个变量均匀且独立地分配为-1或1时，s）发生的可能性相同。一个基本的问题是在给定n和s的情况下找到最大可能的t，使得存在（n，s，t）弹性函数。如[5,2,3]所述，弹性功能已涉及一些有趣的密码应用程序，例如在存在故障处理器的情况下放大隐私并生成共享的随机字符串。以下着色问题与弹性功能密切相关。 c = 2（s）种颜色的n维布尔立方体的良好着色是，在每个k维子立方体中，每种颜色出现2（k）/ c次。在这里，我们对存在这种颜色的最小k感兴趣。如果n立方体中的每个顶点除每种颜色外具有相同数量的邻居，则该着色是局部对称的。 XOR型着色是通过线性映射GF（2）（n）-> GF（2）（s）获得的一种。我们回答弗里德曼[5]提出的以下问题：（1）如果c-1 n，是否所有最优着色都必须局部对称？ （2）是否有不能作为XOR型着色剂获得最佳的着色剂？对于这两个问题，我们都提供肯定的答案。对于（2），我们表明有无限多的非XOR型最优解，这也得到了Stinson等人的证明。用不同的方法[8]。我们的主要工具是通过Krawtchouk多项式表达it立方体的距离i邻接矩阵的特征值。借助该技术，我们可以作为[5，p。]中某些主张的背景。 318]更清晰。在此过程中，我们证明了一些涉及颜色类别的距离分布的身份，以便更好地了解颜色类别的结构。 （C）2000 Elsevier Science B.V.保留所有权利。 [参考：8]

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号