Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

High Entropy Random Selection Protocols

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10438323" target="_blank" >RIV/00216208:11320/21:10438323 - isvavai.cz</a>

  • Výsledek na webu

    <a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=aw730U.Cvv" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=aw730U.Cvv</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1007/s00453-020-00770-y" target="_blank" >10.1007/s00453-020-00770-y</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    High Entropy Random Selection Protocols

  • Popis výsledku v původním jazyce

    We study the two party problem of randomly selecting a common string among all the strings of length n. We want the protocol to have the property that the output distribution has high Shannon entropy or high min entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, Shannon entropy and simultaneously min entropy close to n/2. In the literature the randomness guarantee is usually expressed in terms of &quot;resilience&quot;. The notion of Shannon entropy is not directly comparable to that of resilience, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields Shannon entropy ????-????(1) and has ????(logASTERISK OPERATOR????) rounds, improving over the protocol of Goldreich et al. (SIAM J Comput 27: 506-544, 1998) that also achieves this entropy but needs O(n) rounds. Both these protocols need ????(????2) bits of communication. Next we reduce the number of rounds and the length of communication in our protocols. We show the existence, non-explicitly, of a protocol that has 6 rounds, O(n) bits of communication and yields Shannon entropy ????-????(log????) and min entropy ????/2-????(log????). Our protocol achieves the same Shannon entropy bound as, also non-explicit, protocol of Gradwohl et al. (in: Dwork (ed) Advances in Cryptology-CRYPTO &apos;06, 409-426, Technical Report , 2006), however achieves much higher min entropy: ????/2-????(log????) versus ????(log????). Finally we exhibit a very simple 3-round explicit &quot;geometric&quot; protocol with communication length O(n). We connect the security parameter of this protocol with the well studied Kakeya problem motivated by Harmonic Analysis and Analytic Number Theory. We prove that this protocol has Shannon entropy ????-????(????). Its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols.

  • Název v anglickém jazyce

    High Entropy Random Selection Protocols

  • Popis výsledku anglicky

    We study the two party problem of randomly selecting a common string among all the strings of length n. We want the protocol to have the property that the output distribution has high Shannon entropy or high min entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, Shannon entropy and simultaneously min entropy close to n/2. In the literature the randomness guarantee is usually expressed in terms of &quot;resilience&quot;. The notion of Shannon entropy is not directly comparable to that of resilience, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields Shannon entropy ????-????(1) and has ????(logASTERISK OPERATOR????) rounds, improving over the protocol of Goldreich et al. (SIAM J Comput 27: 506-544, 1998) that also achieves this entropy but needs O(n) rounds. Both these protocols need ????(????2) bits of communication. Next we reduce the number of rounds and the length of communication in our protocols. We show the existence, non-explicitly, of a protocol that has 6 rounds, O(n) bits of communication and yields Shannon entropy ????-????(log????) and min entropy ????/2-????(log????). Our protocol achieves the same Shannon entropy bound as, also non-explicit, protocol of Gradwohl et al. (in: Dwork (ed) Advances in Cryptology-CRYPTO &apos;06, 409-426, Technical Report , 2006), however achieves much higher min entropy: ????/2-????(log????) versus ????(log????). Finally we exhibit a very simple 3-round explicit &quot;geometric&quot; protocol with communication length O(n). We connect the security parameter of this protocol with the well studied Kakeya problem motivated by Harmonic Analysis and Analytic Number Theory. We prove that this protocol has Shannon entropy ????-????(????). Its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols.

Klasifikace

  • Druh

    J<sub>imp</sub> - Článek v periodiku v databázi Web of Science

  • CEP obor

  • OECD FORD obor

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Návaznosti výsledku

  • Projekt

  • Návaznosti

    I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Ostatní

  • Rok uplatnění

    2021

  • Kód důvěrnosti údajů

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Údaje specifické pro druh výsledku

  • Název periodika

    Algorithmica

  • ISSN

    0178-4617

  • e-ISSN

  • Svazek periodika

    83

  • Číslo periodika v rámci svazku

    2

  • Stát vydavatele periodika

    US - Spojené státy americké

  • Počet stran výsledku

    28

  • Strana od-do

    667-694

  • Kód UT WoS článku

    000574811400001

  • EID výsledku v databázi Scopus

    2-s2.0-85091845105