This virtual event will be carried out on Wednesday, April 22 2020 at:
https://zoom.us/j/96208032205?pwd=dXdTN2VkMSs5MHhaWkhTRXErb2YyQT09
Schedule:
16:00 – 16:45: Hussien Othman (Ben-Gurion University) (Video)
16:45 – 17:15: break
17:15 – 18:00: Omri Shmueli (Tel Aviv University) (Video)
18:00 – 18:30: break
18:30 – 19:15: Yuval Ishai (Technion) (Video)
_______________________________________________________________________
Title: Evolving Ramp Secret Sharing with a small Gap.
Speaker: Hussien Othman, Ben-Gurion University
Evolving secret-sharing schemes, introduced by Komargodski, Naor, and Yogev (TCC 2016b), are secret-sharing schemes in which there is no a-priory upper bound on the number of parties that will participate. The parties arrive one by one and when a party arrives the dealer gives it a share; the dealer cannot update this share when other parties arrive. Motivated by the fact that when the number of parties is known, ramp secret-sharing schemes are more efficient than threshold secret-sharing schemes, we study evolving ramp secret-sharing schemes. Specifically, we study evolving $(b(j),g(j))$-ramp secret-sharing schemes, where $g,b$ are non-decreasing functions. In such schemes, any set of parties that for some $j$ contains $g(j)$ parties from the first parties that arrive can reconstruct the secret, and any set such that for every $j$ contains less than $b(j)$ parties from the first $j$ parties that arrive cannot learn any information about the secret.
We focus on the case that the gap is small, namely $g(j)-b(j)=j^{\beta}$ for $0<\beta<1$. We show that there is an evolving ramp secret-sharing scheme with gap $t^{\beta}$, in which the share size of the $j$-th party is $\tilde{O}(j^{4-\frac{1}{\log^2 {1/\beta}}})$. Furthermore, we show that our construction results in much better share size for fixed values of $\beta$, i.e., there is an evolving ramp secret-sharing scheme with gap $\sqrt{j}$, in which the share size of the $j$-th party is $\tilde{O}(j)$. Our construction should be compared to the best known evolving $g(j)$-threshold secret-sharing schemes (i.e., when $b(j)=g(j)-1$) in which the share size of the $j$-th party is $\tilde{O}(j^4)$. Thus, our construction offers a significant improvement for every constant $\beta$, showing that allowing a gap between the sizes of the authorized and unauthorized sets can reduce the share size.
In addition, we present an evolving $(k/2,k)$-ramp secret-sharing scheme for a constant $k$ (which can be very big), where any set of parties of size at least $k$ can reconstruct the secret and any set of parties of size at most $k/2$ cannot learn any information about the secret. The share size of the $j$-th party in our construction is $O(\log k\log j)$. This is an improvement over the best known evolving $k$-threshold secret-sharing schemes in which the share size of the $j$-th party is $O(k\log j)$.
Joint work with Amos Beimel.
_______________________________________________________________________
Title: Post-Quantum Zero Knowledge in Constant Rounds
Speaker: Omri Shmueli, Tel Aviv University
Zero-knowledge is a central notion in cryptography. Over the last three decades, different flavors of zero knowledge have been considered, and matching protocols have been constructed.
This talk will focus on zero knowledge against quantum verifiers (aka post-quantum zero knowledge).
Constructing post-quantum zero-knowledge protocols has proven to be a challenging task. This difficulty stems from fundamental barriers in quantum information such as the no-cloning theorem, which prevents traditional proof techniques like rewinding from working.
We will discuss the challenges of existing solutions, and present a new protocol that achieves post-quantum zero-knowledge for NP and QMA in a constant number of rounds, assuming Quantum Fully-Homomorphic Encryption and the Learning with Errors Assumption.
We will not assume prior knowledge in quantum computation in this talk.
Joint work with Nir Bitansky.
_______________________________________________________________________
Title: Cryptographic Sensing
Speaker: Yuval Ishai, Technion
Is it possible to measure a physical object in a way that makes the measurement signals unintelligible to an external observer? Alternatively, can one learn a natural concept by using a contrived training set that makes the labeled examples useless without the line of thought that has led to their choice? We initiate a study of “cryptographic sensing” problems of this type, presenting definitions, positive and negative results, and directions for further research.
Joint work with Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai
Posted by