CIF: Small: New Approaches to the Design and Analysis of Graphical Models for Linear Codes and Secret Sharing Schemes

CIF：小：线性码和秘密共享方案图形模型设计和分析的新方法

• 批准号: 0916919
• 负责人: Alexander Barg
• 金额: $ 35.07万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-15 至 2013-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0916919&HistoricalAwards=false
• 关键词: CIF; Small; New; Approaches; Design

NSF Proposal 0916919 New approaches to the design and analysis of graphical models for linear codes and secret sharing schemesAbstractError-correcting coding enables one to design reliable systems of transmission and storage of information and is used universally for sending packets over the web, in writing data on CD's and flash memory devices, and other similar means of modern communication. A very efficient method of encoding information for error protection is the so-called "iterative decoding," which assumes that every binary digit of transmission is recovered based on its realiblity and the realibility of a few other, carefully selected bits of the encoded message. This method of error correction is analyzed based on the representation of the encoding as a graph in the plane in which recovery from errors proceeds by successive exchange of information between the nodes of the graph in an iterative procedure performed in a number of rounds. One of the main goals of this research is to reduce complexity (the number of rounds) needed for reliable recovery of the transmission from errors in the communication medium.Graphical models of linear codes have so far been restricted to trellises, i.e., cycle-free graphs, and graphs with exactly one cycle (tail-biting trellises). This research studies complexity of realization of codes and iterative decoding algorithms on connected graphs with cycles, deriving complexity estimates from the tree-decomposition of graphs. One of the goals of this research is to find methods of constructing low-complexity realizations of codes for such well-known code families as Reed-Muller and Reed-Solomon codes, and explore the optimality gap of these representations. Methods of matroid theory used in the study of graphical models will also be explored in the analysis of access structures of secret sharing schemes and secure multi-party computation protocols.

NSF 提案 0916919 线性码和秘密共享方案的图形模型设计和分析的新方法摘要纠错编码使人们能够设计可靠的信息传输和存储系统，并普遍用于通过网络发送数据包、在网络上写入数据CD 和闪存设备以及其他类似的现代通信方式。 一种非常有效的编码信息以防止错误的方法是所谓的“迭代解码”，它假设传输的每个二进制数字都根据其真实性以及编码消息的其他一些精心选择的位的真实性来恢复。基于将编码表示为平面中的图来分析这种纠错方法，其中通过在多轮执行的迭代过程中图的节点之间的连续信息交换来进行错误恢复。 这项研究的主要目标之一是降低从通信介质中的错误中可靠恢复传输所需的复杂性（轮数）。迄今为止，线性码的图形模型仅限于网格，即无循环图，以及只有一个周期的图（咬尾格子）。这项研究研究了带循环的连通图上代码实现的复杂性和迭代解码算法，从图的树分解中得出复杂性估计。这项研究的目标之一是找到为 Reed-Muller 和 Reed-Solomon 码等著名代码族构建低复杂度代码实现的方法，并探索这些表示的最优性差距。在秘密共享方案和安全多方计算协议的访问结构分析中，还将探索用于图模型研究的拟阵理论方法。