Theory Day in Taiwan (2019)

Paul Horn (University of Denver, USA)

Title: Gradient and Harnack type Inequalities for PageRank

---

Abstract:
PageRank, as introduced by Brin and Page, and more generally 'personalized PageRank,' has been of fundamental importance in network search. A key parameter in PageRank is the 'jumping constant' which allows (among other things) one to tailor the sensitivity of PageRank to local cuts. In this talk, we describe new gradient estimates (akin to the Li-Yau inequality for solutions to the heat equation) and Harnack type inequalities for graphs satisfying certain curvature conditions. These allow us to compare the 'importance' of different nodes, and how PageRank regularizes as the jumping constant goes to zero.

Bar Alon (Ariel University, Israel)

Title: On Perfectly Secure 2PC in the OT-Hybrid Model

---

Abstract:
A well-known result by Kilian (ACM 1988) asserts that general secure two computation (2PC) with statistical security, can be based on OT. Specifically, in the client-server model, where only one party -- the client -- receives an output, Kilian’s result shows that given the ability to call an ideal oracle that computes OT, two parties can securely compute an arbitrary function of their inputs with unconditional security. Ishai et al. (EUROCRYPT 2011) further showed that this can be done efficiently for every two-party functionality in NC^1 in a single round. However, their results only achieve statistical security, namely, it is allowed to have some error in security. This leaves open the natural question as to which client-server functionalities can be computed with perfect security in the OT-hybrid model, and what is the round complexity of such computation. So far, only a handful of functionalities were known to have such protocols. In addition to the obvious theoretical appeal of the question towards better understanding secure computation, perfect, as opposed to statistical reductions, may be useful for designing secure multiparty protocols with high concrete efficiency, achieved by eliminating the dependence on a security parameter. In this work, we identify a large class of client-server functionalities f: X × Y -> {0,1}, where the server's domain X is larger than the client's domain Y, that have a perfect reduction to OT. Furthermore, our reduction is 1-round using an oracle to secure evaluation of many parallel invocations of 1-out-of-2 bit-OT, as done by Ishai et al. (EUROCRYPT 2011). Interestingly, the set of functions that we are able to compute was previously identified by Asharov (TCC 2014) in the context of fairness in two-party computation, naming these functions full-dimensional. Our result also extends to randomized non-Boolean functions f: X × Y -> {0,...,k-1} satisfying |X|>(k-1)*|Y|.

Takashi Yamakawa (NTT, Japan)

Title: Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness

---

Abstract:
Since the celebrated work of Impagliazzo and Rudich (STOC 1989), a number of black-box impossibility results have been established. However, these works only ruled out classical black-box reductions among cryptographic primitives. Therefore it may be possible to overcome these impossibility results by using quantum reductions. To exclude such a possibility, we have to extend these impossibility results to the quantum setting. In this paper, we initiate the study of black-box impossibility in the quantum setting. We first formalize a quantum counterpart of fully-black-box reduction following the formalization by Reingold, Trevisan and Vadhan (TCC 2004). Then we prove that there is no quantum fully-black-box reduction from collision-resistant hash function to one-way permutation (or even trapdoor permutation). This is an extension to the quantum setting of the work of Simon (Eurocrypt 1998) who showed a similar result in the classical setting.