img

specter

Blockchain / Cyperpunk

Specter

BLOG Metaverse

Stay Foolish, Stay Hungry

分布式密钥生成

| 阅读：次

目录

[TOC]

Asynchronous Distributed Key Generation protocol

为基于离散对数的门槛密码系统设计了一个新的简单和具体有效的ADKG 协 议。在一个由n≥3t+1 个节点组成的异步网络中，最多只有t个节点可能是恶意的，我们的ADKG协议实现了O(κn3 ) 的预期通信成本，并且在预期的O(log n)轮。因此，我们的协议改进了 先前已知的通用ADKG协议的Kokoris- Kogias 等人[43] 的通信量增加了n 倍，预期运行时间增 加了n/log n 倍。对于设置假设，Kokoris-Kogias 等人 [43] 假设了随机Oracle (RO )，而我们的协议假设了 RO和PKI(PKI只需要用于我们的ACSS构建)。 在我们的协议结束时，每个节点收到一个随机选择的 秘密z∈Zq 的阈值秘密份额，其中Zq 是一个大小为q 的字 段。因此，我们的协议与现成的基于离散对数的阈值密 码系统[21], [9], [31]兼容。 我们的协议还支持任何重建阈值l∈[t+1 ，n-t] ，即要 求l个节点使用秘钥z(例如，产生一个阈值签名或解密 一个阈值加密)。为了有效地获得这一特性，我们设计了一个新的加法同态的高门槛

GitHub

论文思路架构

DKG 分布式密钥生成

  1. 参与方选择一个共享参数集：所有参与方必须就共享参数集达成一致，这些参数可以包括系统参数、安全参数等。

  2. 随机数生成：每个参与方生成自己的随机数，并将其发送给其他参与方。

  3. 消息交换：参与方之间进行消息交换，以便收集其他参与方的随机数。

  4. 验证：参与方使用收集到的随机数进行验证，以确保其他参与方没有作弊。

  5. 分享密钥部分：每个参与方根据协议的规则将自己的密钥部分分享给其他参与方。

  6. 密钥重构：一旦所有参与方都分享了他们的密钥部分，他们可以通过将这些部分组合在一起来重构完整的密钥。

在分布式密钥生成（DKG）协议中，椭圆曲线可以被用来实现密钥生成和共享过程的安全性。椭圆曲线密码学提供了一种强大的加密和密钥交换方案，其安全性基于椭圆曲线离散对数问题的难解性。

ABE的密钥生成部分主要是椭圆曲线

密钥共享

CSS的同步与异步

广播协议

  • Reliable Broadcast(RBC)
  • reedsolomon的可靠性

    ReedSolomon的融入可能性

拜占庭安全

FLP不可能性定理

分布式系统都需要考虑FLP不可能性定理

拜占庭错误的解决

异步拜占庭二元协议（Asynchronous Binary Agreement，ABA）是一种协议，用于解决在分布式系统中存在拜占庭错误的情况下，如何使一组节点就一个二进制值达成一致。ABA协议需要满足以下三个属性：1）一致性：没有两个诚实的节点输出不同的值；2）有效性：如果所有诚实的节点具有相同的输入值，则没有诚实的节点输出不同的值；3）终止性：每个诚实的节点最终都会输出一个值。由于FLP不可能性定理，所有ABA协议都依赖于随机化来解决异步环境下达成共识的问题。通常使用共同硬币协议提供共享随机数来实现ABA协议。

多项式承诺

https://blog.csdn.net/mutourend/article/details/125922653

Kate

Bulletproofs

FRI

Feldman

Pedersen

权限控制

融入ABE

Tips

ReedSolomon可以同时实现纠错、门限和承诺

- 容错性
- 通信成本
- 计算成本
- 密码学假设

SS综述

秘密共享是指将一个秘密分解成多个份额，并将份额分配给多方，只有各方将各自的份额聚集在一起才能重构秘密的密码学方法。更具体地说，秘密的持有者（有时称为经销商）创建 n 份秘密，并为重构秘密所需的份额数定义阈值 t。然后交易商继续分配股票，使它们由不同的各方控制。

在这项调查中，将描述秘密分享方案的最重要的构造，解释秘密分享 方案与单调公式和单调跨度程序之间的联系。已知的秘密共享方案的主要 问题是共享规模大:它是各方数量的指数级。猜想这是不可能避免的 。将讨论已知的份额大小的下限。这些下限是相当弱的，在下限和上 限之间有很大的差距。对于线性秘密共享方案，这是一类基于线性代数的 方案，包含大多数已知的方案，关于共享大小的超多项式下限是已知的。 将对这些下限的证明进行描述。还将提出两个结果，将汉密尔顿 访问结构的秘密共享方案与NP与coNP问题以及密码学中的一个主要开放 问题–从单向函数构建遗忘传输协议联系起来。

秘密共享方案的一个主要问题是，在实现一般访问结构的最佳已知秘密共享方案中，份额的大小与访问结构中的各方数量成指数关系。因此，已知的一般访问结构的构架是不切实际的。即使是隐式访问结构也是如此( 例如，其特征函数可由小型统一电路计算的访问结构)。另一方面，就接入结构而言，共享秘密的最佳已知下限(例如，在[23，29]中)与上述上限相差甚远。

for every n, there is an access structure with n parties such that sharing l-bit secrets requires shares of length Ω(ln/ log n).

https://www.cs.umd.edu/~gasarch/TOPICS/secretsharing/sizelarge.pdf

猜想

Conjecture 1. There exists an ε > 0 such that for every integer n there is an access structure with n parties, for which every secret-sharing scheme distributes shares of length exponential in the number of parties, that is, 2εn.

线性秘密共享方案的信息比率可以通过以下公式计算：

IR = (n - k) / k

其中，n是秘密的总数，k是需要访问秘密的最小阈值。信息比率表示为一个实数，通常在0到1之间。它越接近1，表示方案越高效，因为共享的信息量越少。当信息比率等于1时，方案被称为完美秘密共享方案。

基于属性的共享

根据一些基于用户凭证的策略，对数据进行加密。在Sahai和Waters[Fuzzy identity-based encryption]提出的基于属性的加密系统中，每个用户都有一组属性(即证书)，如果属性 的某些词成立，提供者将授予解密信息的权限(例如，如果一个用户是 “ 朋友 “和 “重要”，她可以解密电子邮件)。

阈值共享

http://blog.nsfocus.net/secret-gdpr/

  1. 基于超平面几何的秘密共享，包括Blakley方案和Brickell方案；
    • Brickell的秘密共享方案采用向量方法，一个秘密拥有者Dealer把秘密s嵌入到一个向量中，在通过一个矩阵把秘密共享为n个子秘密分发给n个参与者，具体方法如下： 选择秘密s，和随机向量(y2,y3, …… ，yt), 生成一个nt矩阵M，M有n行，每行记为Mi,任意t个行向量都是线性无关的。秘密份额为(s1，s2，……，sn).每个份额是行向量Mi和列向量(s,y2,y3, …… ，yt),的乘积。即si = Mi (s,y2,y3, …… ，yt) 包括Blakley方案和Brickell方案

  2. 基于插值多项式的秘密共享，包括经典的Shamir阈值秘密共享方案； Shamir秘密共享是Blakley & Brickell方案中的特例。正因为范德蒙德矩阵的特殊性，线性无关性（xi不相等的任意t阶方阵都是满秩的）和构造简单（并且分布式节点很容易统一这个矩阵），所以大多数方案应用Shamir秘密共享。如果需要把Shamir秘密秘密共享应用到一般模式可以考虑把范德蒙德矩阵用一般矩阵替代。

  3. Mignotte，Asmuth & Bloom提出的基于中国剩余定理的秘密共享； 基于中国剩余定理（CRT）的秘密共享方案相对于Shamir秘密共享方案在以下场景中更适用：

  • 大规模秘密共享：当需要进行大规模的秘密共享，涉及到大量的参与者和大量的秘密信息时，基于CRT的秘密共享方案可以更高效地处理。它可以通过将秘密信息分解为多个模数，利用CRT的并行计算特性，实现快速的秘密信息重构。

  • 快速秘密恢复：基于CRT的秘密共享方案具有较快的秘密恢复速度。通过利用CRT的运算，可以通过简单的模数和余数计算快速重构秘密信息。这在一些需要迅速恢复秘密信息的场景中很有优势。

  • 分布式计算：基于CRT的秘密共享方案适用于分布式计算环境。它允许将秘密信息分解为多个模数，并在不同的计算节点上进行并行计算。这样可以利用分布式计算的优势，提高计算效率和系统的可扩展性。

  • 低安全性要求：相对于某些复杂的秘密共享方案，基于CRT的秘密共享方案在安全性要求较低的场景中更适用。它可以提供一定程度的安全性，但可能在某些高安全性要求的场景下需要额外的安全增强措施。

sss-vss

http://aandds.com/blog/sss-vss.html

hbacss

观察到MPC理论与实践之间存在这种差距的主要原因是缺乏有效的可验证/完全秘密共享 (VSS/CSS) 结构；现有的CSS协议要么需要 a) 在实践中具有挑战性的广播频道，要么 b) 引入至少是玩家数量的二次方的计算和通信开销。这项工作介绍了 hbACSS，这是一套最佳弹性异步完整秘密共享协议，在计算和通信开销方面都是（准）线性的。为了开发 hbACSS，论文开发了 hbPolyCommit，一种高效的多项式承诺方案，它在计算和通信开销方面是（准）线性（多项式），不需要可信设置。hbACSS 协议随着参与方数量的增加而扩展得很好，特别是，在使用 hbACSS 来生成 MPC 输入掩码：一个有用的原语的时候。

主要流程

  1. 经销商阶段：经销商从多项式中计算每个B项，并广播相应的多项式承诺。然后，她使用公钥加密各方的共享和评估证明，并通过 AVID 方案可验证地发送它们。
  2. 共享验证：每一方检索其加密的有效负载，并尝试根据多项式承诺解密和验证其共享。如果足够多的各方成功接收有效份额，则输出份额。
  3. 牵连有问题的经销商：如果任何一方发现他们收到的股票无效或解密失败，他们会泄露他们的密钥，使另一方能够在从分散计划中检索到该方的有效载荷后确认交易商有问题。
  4. 份额回收：一旦交易商被牵连为有问题，收到有效份额的各方将份额进行分配，使其余各方能够重建份额。

We now explain hbACSS0 in more detail, following along with the protocol pseudocode given in Algorithm 1. Security analysis and the other variants follow in this section. 1) Sharing and Committing: The protocol shares a batch of B inputs at a time, {s1 , …, sB }. The dealer creates a degree-t Shamir sharing φk(·) for each input such that φk(0) = sk, and each party Pi’s share of sk is φk(i). The dealer then uses the PolyCommit procedure to create a commitment Ck to each polynomial φk(·). The commitments are then broadcasted, ensuring all the parties can validate their shares against the same set of commitments. Next, for each party Pi, the dealer creates an encrypted payload zi, consisting of the shares {φk(i)}k∈[1,B] and the polynomial evaluation proof πi, encrypted under Pi’s public key PKi. The dealer then Disperses these encrypted payloads. With the broadcast and dispersal complete, the dealer’s role in the protocol is complete—since information dispersal itself requires only one initial round of messages from the dealer, the dealer’s entire role is sending messages in the first round. 2) Share Verification: Each party Pi waits for ReliableBroadcast and Disperse to complete, and then retrieves their payload {zi}. The party then attempts to decrypt and validate its shares. If decryption is successful and all the shares are valid, then Pi signals this by sending an OK message to the other recipients. The goal of the OK and READY messages (lines 302-307) is to ensure that if any party outputs a share, then enough correct parties have shares for share recovery to succeed if necessary. 3) Implicating a faulty dealer: If any honest party Pi receives a share that either fails to decrypt or fails verification, they reveal their secret key by sending (IMPLICATE,SKi,k) to all, which other parties can use to repeat the decryption and confirm that the dealer dispersed invalid data. 4) Share Recovery: If an honest party discovers their shares are faulty after other honest parties have already output, the protocol must enter Share Recovery. In this phase, parties with valid shares are presented with evidence that the dealer is faulty. If convinced, these parties will divulge the keys needed to decrypt their own shares. To avoid the need for constant re-keying, we present a practical modification for long-term keys in Section V-C.

来自deepl翻译

1）共享和提交： 该协议每次分享一批B的输入，{s1, ..., sB }。庄家为每个输入创建一个degree-t Shamir共享φk(-)，这样φk(0)=sk，每一方Pi的sk份额是φk(i)。
然后庄家使用PolyCommit程序为每个多项式φk(-)创建一个承诺Ck。然后，这些承诺被广播出去，确保所有各方都能根据同一组承诺来验证他们的份额。
接下来，对于每一方Pi，庄家创建一个加密的有效载荷zi，由股份{φk(i)}k∈[1,B]和多项式评估证明πi组成，在Pi的公钥PKi下进行加密。然后，庄家将这些加密的有效载荷散布出去。随着广播和散布的完成，庄家在协议中的作用也就完成了--因为信息散布本身只需要庄家的一轮初始信息，庄家的全部作用就是在第一轮中发送信息。
2) 分享验证： 每一方Pi等待ReliableBroadcast和Disperse完成，然后检索其有效载荷{zi}。然后，该方试图解密并验证其份额。如果解密成功并且所有的份额都是有效的，那么Pi通过向其他接收者发送一个OK消息来表示这一点。OK和READY消息（第302-307行）的目的是确保如果任何一方输出一个份额，那么足够多的正确方拥有份额，以便在必要时成功恢复份额。
3) 暗示一个有问题的经销商： 如果任何诚实的一方Pi收到一个解密失败或验证失败的份额，他们通过向所有人发送(IMPLICATE,Ski,k)来揭示他们的秘密密钥，其他各方可以用它来重复解密并确认经销商散布无效数据。
4）份额恢复： 如果一个诚实的一方在其他诚实的一方已经输出后发现他们的份额有问题，协议必须进入份额恢复阶段。在这个阶段，拥有有效股份的各方会被告知庄家有问题的证据。如果被说服，这些当事方将泄露解密他们自己股份所需的密钥。为了避免不断地重新配钥匙，我们在第五章C节提出了一个针对长期钥匙的实际修改。

AVID

完整性 VSS with Share Recovery （VSS-R）

异步

http://www.soumyabasu.com/assets/pdf/basu-ccs19.pdf

  1. 随机化：在ACSS协议中，参与方使用随机数来生成多项式和份额。这种随机化可以使攻击者无法预测参与方的行为，并增加了协议的安全性。

  2. 纠错码：为了检测和纠正消息传输过程中的错误，ACSS协议使用纠错码。这些码可以检测并纠正一定数量的错误，并确保参与方收到正确的消息。

  3. 超时：如果某个节点长时间未响应，则其他节点可以将其视为故障节点，并继续执行协议。这种超时机制可以确保即使存在故障节点，也不会影响整个系统的运行。

hbPolyCommit

访问控制结构

Tips

加法秘密共享的缺陷

可扩展性低 （没有分析出缺陷在哪）

MPC 局限性

安全的多方计算：在多数不诚实设置中，对于容忍非一个恶意破坏的恒定轮次 MPC 协议，一些研究采用剪切和选择方法或 BMR 和 SPDZ 的组合方法来构建 MPC 协议。但是，它们的具体效率非常低。在这种情况下，最著名的 MPC 协议遵循基于 TinyOT 类协议的分布式乱码框架。这些 MPC 协议与 2PC 协议具有相同的结构，但需要执行一致性检查程序来检查多次执行之间共享或全局密钥的一致性。最近，Poddar 等人应用具有恶意安全性的恒定轮次 MPC 协议构建了一个称为参议院的系统，该系统允许协作方运行分析SQL查询，同时保持个人数据的私密性。Yang等人提出了具有恶意安全性的最先进的常量轮MPC协议，并可用于进一步提高上述应用程序的性能。虽然半门优化完全应用于两方设置中的分布式乱码构建，但这仅在多方设置中部分完成。将半栅技术（甚至最近的切片和切割技术）完全应用于多方混淆电路是一个挑战。

在多数诚实设置中，可以使用较少的通信和计算基于复制的秘密共享来构建恒定轮次 MPC 协议。在最多一个恶意方的三方设置中，Mohassel 等人通过构建单个 Yao 式的混淆电路，提出了目前最有效的三轮 3PC 协议，其中恶意安全的 3PC 协议与半诚实的 Yao 的 2PC 协议具有基本相同的成本。同时，Ishai 等人构建了一个两轮3PC协议，同时需要发送三个混淆电路。在最多有一次恶意破坏的四方设置中，Byali 等人提出了最先进的协议，并且有五轮通信，需要发送一个单Yao式的混淆电路。该协议可以实现更强的安全属性，即GOD。在最多有两个恶意破坏的五方设置中，Chandran 等人提出了最著名的 MPC 协议，进行了 8 轮通信。他们采用 BMR 混淆电路来防止串通，并提出了一种经过验证的 OT 原语，使整个 MPC 协议只依赖于对称密钥原语，而不需要 OT 协议。在通信成本方面，它们的恶意安全协议比不诚实多数的半诚实 MPC 协议减少 60%，而其半诚实变体需要的通信减少 8 倍。他们的构造也可以扩展到阈值的 方。后来，Byali等人构建了具有公平性或 GOD 的安全五方计算 (5PC)，其开销比 5PC 协议的开销小，满足中止的安全性。

References

  1. N. Alon, O. Goldreich, J. H ̊astad, and R. Peralta. Simple constructions of almost k- wise independent random variables. Random Structures & Algorithms, 3:289–304, 1992.
  2. L. Babai, A. G ́al, and A. Wigderson. Superpolynomial lower bounds for monotone span programs. Combinatorica, 19(3):301–319, 1999.
  3. A. Beimel. Secure Schemes for Secret Sharing and Key Distribution. PhD thesis, Technion, 1996. www.cs.bgu.ac.il/ beimel/pub.html.
  4. A. Beimel and B. Chor. Universally ideal secret sharing schemes. IEEE Trans. on Information Theory, 40(3):786–794, 1994.
  5. A. Beimel, A. G ́al, and M. Paterson. Lower bounds for monotone span programs. Computational Complexity, 6(1):29–45, 1997. Conference version: FOCS ’95.
  6. A. Beimel and Y. Ishai. On the power of nonlinear secret-sharing. SIAM J. on Discrete Mathematics, 19(1):258–280, 2005.
  7. A. Beimel, N. Livne, and C. Padro ́. Matroids can be far from ideal secret sharing. In R. Canetti, editor, Proc. of the Fifth Theory of Cryptography Conference – TCC 2008, volume 4948 of Lecture Notes in Computer Science, pages 194–212, 2008.
  8. A. Beimel and I. Orlov. Secret sharing and non-shannon information inequalities. IEEE Trans. on Information Theory, 2011. Accepted for publication. Preliminary version in TCC 2009, LNCS vol, 5444:539–557, 2009.
  9. A. Beimel and A. Paskin. On linear secret sharing for connectivity in directed graphs. In R. Ostrovsky, R. De Prisco, and I. Visconti, editors, Proc. of the Sixth Conference on Security and Cryptography for Networks, volume 5229 of Lecture Notes in Computer Science, pages 172–184. Springer-Verlag, 2008.
  10. A. Beimel and E. Weinreb. Separating the power of monotone span programs over different fields. SIAM J. on Computing, 34(5):1196–1215, 2005.
  11. A. Beimel and E. Weinreb. Monotone circuits for monotone weighted threshold functions. Inform. Process. Lett., 97(1):12–18, 2006. Conference version: Proc. of 20th Annu. IEEE Conf. on Computational Complexity, pages 67-75, 2005.
  12. M. Bellare and P. Rogaway. Robust computational secret sharing and a unified account of classical secret-sharing goals. In Proc. of the 14th ACM conference on Computer and communications security, pages 172–184, 2007.
  13. M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non- cryptographic fault-tolerant distributed computations. In Proc. of the 20th ACM Symp. on the Theory of Computing, pages 1–10, 1988.
  14. J. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. In S. Goldwasser, editor, Advances in Cryptology – CRYPTO ’88, volume 403 of Lecture Notes in Computer Science, pages 27–35. Springer-Verlag, 1990.
  15. J. Benaloh and S. Rudich. Private communication, 1989.
  16. M. Bertilsson and I. Ingemarsson. A construction of practical secret sharing schemes using linear block codes. In J. Seberry and Y. Zheng, editors, Advances in Cryptology – AUSCRYPT ’92, volume 718 of Lecture Notes in Computer Science, pages 67–79. Springer-Verlag, 1993.
  17. G. R. Blakley. Safeguarding cryptographic keys. In R. E. Merwin, J. T. Zanca, and M. Smith, editors, Proc. of the 1979 AFIPS National Computer Conference, volume 48 of AFIPS Conference proceedings, pages 313–317. AFIPS Press, 1979.
  18. C. Blundo, A. De Santis, R. De Simone, and U. Vaccaro. Tight bounds on the information rate of secret sharing schemes. Designs, Codes and Cryptography, 11(2):107–122, 1997.
  19. C. Blundo, A. De Santis, L. Gargano, and U. Vaccaro. On the information rate of secret sharing schemes. Theoretical Computer Science, 154(2):283–306, 1996.
  20. C. Blundo, A. De Santis, and U. Vaccaro. On secret sharing schemes. Inform. Process. Lett., 65(1):25–32, 1998.
  21. E. F. Brickell. Some ideal secret sharing schemes. Journal of Combin. Math. and Combin. Comput., 6:105–113, 1989.
  22. E. F. Brickell and D. M. Davenport. On the classification of ideal secret sharing schemes. J. of Cryptology, 4(73):123–134, 1991.
  23. R. M. Capocelli, A. De Santis, L. Gargano, and U. Vaccaro. On the size of shares for secret sharing schemes. J. of Cryptology, 6(3):157–168, 1993.
  24. D. Chaum, C. Cr ́epeau, and I. Damg ̊ard. Multiparty unconditionally secure proto- cols. In Proc. of the 20th ACM Symp. on the Theory of Computing, pages 11–19, 1988.
  25. B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In Proc. of the 26th IEEE Symp. on Foundations of Computer Science, pages 383–395, 1985.
  26. B. Chor and E. Kushilevitz. Secret sharing over infinite domains. J. of Cryptology, 6(2):87–96, 1993.
  27. T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, 1991.
  28. R. Cramer, I. Damg ̊ard, and U. Maurer. General secure multi-party computation from any linear secret-sharing scheme. In B. Preneel, editor, Advances in Cryp- tology – EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 316–334. Springer-Verlag, 2000.
  29. L. Csirmaz. The size of a share must be large. In A. De Santis, editor, Advances in Cryptology – EUROCRYPT ’94, volume 950 of Lecture Notes in Computer Science, pages 13–22. Springer-Verlag, 1995. Journal version in: J. of Cryptology, 10(4):223–231, 1997.
  30. L. Csirmaz. The dealer’s random bits in perfect secret sharing schemes. Studia Sci. Math. Hungar., 32(3–4):429–437, 1996.
  31. Y. Desmedt and Y. Frankel. Shared generation of authenticators and signatures. In J. Feigenbaum, editor, Advances in Cryptology – CRYPTO ’91, volume 576 of Lecture Notes in Computer Science, pages 457–469. Springer-Verlag, 1992.
  32. M. van Dijk. A linear construction of perfect secret sharing schemes. In A. De Santis, editor, Advances in Cryptology – EUROCRYPT ’94, volume 950 of Lecture Notes in Computer Science, pages 23–34. Springer-Verlag, 1995.
  33. M. van Dijk. On the information rate of perfect secret sharing schemes. Designs, Codes and Cryptography, 6:143–169, 1995.
  34. M. van Dijk, T. Kevenaar, G.-J. Schrijen, and P. Tuyls. Improved constructions of secret sharing schemes by applying (λ, ω)-decompositions. Inform. Process. Lett., 99(4):154 – 157, 2006.
  35. S.Even,O.Goldreich,andA.Lempel.Arandomizedprotocolforsigningcontracts. CACM, 28(6):637–647, 1985.
  36. A. G ́al. A characterization of span program size and improved lower bounds for monotone span programs. Computational Complexity, 10(4):277–296, 2002.
  37. A. G ́al and P. Pudl ́ak. Monotone complexity and the rank of matrices. Inform. Process. Lett., 87:321–326, 2003.
  38. R. Gennaro, M. O. Rabin, and T. Rabin. Simplified vss and fact-track multiparty computations with applications to threshold cryptography. In Proc. of the 17th ACM Symp. on Principles of Distributed Computing, pages 101–111, 1998.
  39. O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In Proc. of the 19th ACM Symp. on the Theory of Computing, pages 218–229, 1987.
  40. V. Goyal, O. Pandey, A. Sahai, and B. Waters. Attribute-based encryption for fine-grained access control of encrypted data. In Proc. of the 13th ACM conference on Computer and communications security, pages 89–98, 2006.
  41. J. H ̊astad, R. Impagliazzo, L. A. Levin, and M. Luby. Construction of a pseudo- random generator from any one-way function. SIAM J. on Computing, 28(4):1364– 1396, 1999.
  42. M. Hirt and U. Maurer. Player simulation and general adversary structures in perfect multiparty computation. J. of Cryptology, 13(1):31–60, 2000.
  43. R. Impagliazzo. A personal view of average-case complexity. In Proc. of the 10th IEEE Structure in Complexity Theory, pages 134–147, 1995.
  44. R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-way permutations. In Proc. of the 21st ACM Symp. on the Theory of Computing, pages 44–61, 1989.
  45. M. Ito, A. Saito, and T. Nishizeki. Secret sharing schemes realizing general access structure. In Proc. of the IEEE Global Telecommunication Conf., Globecom 87, pages 99–102, 1987. Journal version: Multiple assignment scheme for sharing secret. J. of Cryptology, 6(1):15-20, 1993.
  46. M. Karchmer and A. Wigderson. On span programs. In Proc. of the 8th IEEE Structure in Complexity Theory, pages 102–111, 1993.
  47. E. D. Karnin, J. W. Greene, and M. E. Hellman. On secret sharing systems. IEEE Trans. on Information Theory, 29(1):35–41, 1983.
  48. E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997.
  49. J. Mart ́ı-Farr ́e and C. Padro ́. On secret sharing schemes, matroids and polyma- troids. In S. Vadhan, editor, Proc. of the Fourth Theory of Cryptography Conference – TCC 2007, volume 4392 of Lecture Notes in Computer Science, pages 253–272. Springer-Verlag, 2007.
  50. F. Matu ́ˇs. Infinitely many information inequalities. In IEEE International Sym- posium on Information Theory 2007, pages 41–44, 2007.
  51. J. R. Metcalf-Burton. Improved upper bounds for the information rates of the secret sharing schemes induced by the Vamos matroid. Technical Report abs/0809.3010, CoRR, 2008.
  52. M. Naor and A. Wool. Access control and signatures via quorum secret sharing. IEEE Transactions on Parallel and Distributed Systems, 9(1):909–922, 1998.
  53. M. O. Rabin. How to exchange secrets by oblivious transfer. Technical Report TR-81, Harvard Aiken Computation Laboratory, 1981. Available online in the Cryptology ePrint Archive, Report 2005/187, eprint.iacr.org/2005/187.
  54. M. O. Rabin. Randomized Byzantine generals. In Proc. of the 24th IEEE Symp. on Foundations of Computer Science, pages 403–409, 1983.
  55. J. Rompel. One-way functions are necessary and sufficient for secure signatures. In Proc. of the 22nd ACM Symp. on the Theory of Computing, pages 387–394, 1990.
  56. S. Rudich. Private communication (via M. Naor), 1989.
  57. A. Sahai and B. Waters. Fuzzy identity-based encryption. In R. Cramer, editor, Advances in Cryptology – EUROCRYPT 2005, pages 457–473. Springer-Verlag,2005.
  58. A. Shamir. How to share a secret. Communications of the ACM, 22:612–613, 1979.
  59. B. Shankar, K. Srinathan, and C. Pandu Rangan. Alternative protocols for gen- eralized oblivious transfer. In S. Rao, M. Chatterjee, P. Jayanti, C. S. Murthy,and S. K. Saha, editors, Proc. of ICDCN 2008, volume 4904 of Lecture Notes in Computer Science, pages 304–309. Springer-Verlag, 2008.
  60. G. J. Simmons. How to (really) share a secret. In S. Goldwasser, editor, Advances in Cryptology – CRYPTO ’88, volume 403 of Lecture Notes in Computer Science, pages 390–448. Springer-Verlag, 1990.
  61. G. J. Simmons, W. Jackson, and K. M. Martin. The geometry of shared secret schemes. Bulletin of the ICA, 1:71–88, 1991.
  62. J. Simonis and A. Ashikhmin. Almost affine codes. Designs, Codes and Cryptog- raphy, 14(2):179–197, 1998.
  63. D.R.Stinson.Decompositionconstructionforsecretsharingschemes.IEEETrans. on Information Theory, 40(1):118–125, 1994.
  64. T. Tassa. Hierarchical threshold secret sharing. In M. Naor, editor, Proc. of the First Theory of Cryptography Conference – TCC 2004, volume 2951 of Lecture Notes in Computer Science, pages 473–490. Springer-Verlag, 2004.
  65. T. Tassa. Generalized oblivious transfer by secret sharing. Designs, Codes and Cryptography, 58, 2011.
  66. T. Tassa and N. Dyn. Multipartite secret sharing by bivariate interpolation. In M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, editors, Proc. of the 33rd International Colloquium on Automata, Languages and Programming, volume 4052 of Lecture Notes in Computer Science, pages 288–299. Springer-Verlag, 2006.
  67. V. Vinod, A. Narayanan, K. Srinathan, C. Pandu Rangan, and K. Kim. On the power of computational secret sharing. In T. Johansson and S. Maitra, editors, Indocrypt 2003, volume 2904 of Lecture Notes in Computer Science, pages 162–176. Springer-Verlag, 2003.
  68. B. Waters. Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization. Technical Report 2008/290, Cryptology ePrint Archive, 2008. http://eprint.iacr.org/.
  69. A. C. Yao. Unpublished manuscript, 1989. Presented at Oberwolfach and DIMACS workshops.
  70. R. W. Yeung. Information Theory and Network Coding. Springer, 2008.
  71. Z.ZhangandR.W.Yeung.Oncharacterizationofentropyfunctionviainformation inequalities. IEEE Trans. on Information Theory, 44(4):1440–1452, 1998.