中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

Secret Sharing Schemes via Bounded Indistinguishability

:::

Secret Sharing Schemes via Bounded Indistinguishability

  • 講者Christopher Williamson 先生 (Computer Science and Engineering, Chinese University of Hong Kong)
    邀請人:鐘楷閔
  • 時間2015-12-07 (Mon.) 10:00 ~ 12:00
  • 地點資訊所新館106演講廳
摘要

We say that a function ƒ:Σn → {0,1} isɛ-fooled by k-wise indistinguishability if ƒ cannot distinguish with advantageɛbetween any two distributionsμ,ν overΣn whose projections to any k symbols are identical. We study the class of functions ƒ that are fooled by bounded indistinguishability, and highlight differences between this notion and that of bounded independence. WhenΣ = {0,1}, we observe that whether ƒ is fooled is closely related to its approximate degree. We also consider larger alphabets, and obtain a secret sharing scheme such that for every 0 <σ<ρ≤ 1 , it is possible to share a secret among n parties so that any set of fewer than σn parties can learn nothing about the secret, and any set of at least pn can reconstruct the secret. An appealing property of this scheme is that both sharing and reconstruction can be done with poly-sized AC0  circuits.