Sep 15, 2017 (Friday) at Columbia University, the Mudd Building, Computer Science Dept, 500 West 120th Street, New York, NY. CS Conference Room and Lounge.
Program
| 9:30 – 10:00. | Introduction/Coffee |
| 10:00 – 10:50. | Peihan Miao (UC Berkeley) Laconic Oblivious Transfer and its Applications |
| 11:00 – 11:50. | Rio Lavigne (MIT) Topology Hiding Computation on All Graphs |
| 12:00 – 2:00. | Lunch (not provided) |
| 2:00 – 2:50. | Ben Fuller (University of Connecticut) Cryptographically Protected Database Search |
| 3:00 – 3:50. | Tianren Liu (MIT) Towards Breaking the Exponential Barrier for General Secret Sharing |
| 3:50 – 4:20. | Break |
| 4:20 – 5:10. | Postponed to next NY CryptoDay |
Venue
Address: Columbia University, the Mudd Building, Computer Science Dept, 500 West 120th Street, New York, NY.
CS Conference Room and Lounge: Follow directions to department office below, then go through both the double steel-glass doors and double wooden doors, and head down hallway to left. The entrance to the CS lounge and conference room is to the right of the door leading outside to the courtyard.
The department office is at the entrance to the Computer Science Building, itself located in the lobby of the 4th floor of the Mudd Engineering Building. There are doors to Mudd on the 1st floor at 500 West 120th Street (near Amsterdam Avenue). The Mudd doors on the campus level are on the 4th floor. Starting at the main entrance to the campus at Broadway and 116th Street, walk along College Walk and turn left up the steps. At the top of the steps is a large building with a dome: Low Library. Take the walkway to the right of Low Library, and the Mudd building is at the end of this walk. Upon entering Mudd, turn right and then right again. This is the entrance to Computer Science.
Organizers
Fabrice Benhamouda (IBM Research)
Tal Rabin (IBM Research)
with the help and support of Tal Malkin (Columbia).
Support
Some travel support for NYC Crypto Day is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467.
Abstracts
- Laconic Oblivious Transfer and its Applications / Peihan Miao (UC Berkeley)
We introduce a novel technique for secure computation over large inputs. Specifically, we provide a new oblivious transfer (OT) protocol with a laconic receiver. Laconic OT allows a receiver to commit to a large input D (of length M) via a short message. Subsequently, a single short message by a sender allows the receiver to learn m_{D[L]}, where the messages m_0, m_1 and the location L \in [M] are dynamically chosen by the sender. All prior constructions of OT required the receiver’s outgoing message to grow with D. Our key contribution is an instantiation of this primitive based on the Decisional Diffie-Hellman (DDH) assumption. The technical core of this construction is a novel use of somewhere statistically binding (SSB) hashing in conjunction with hash proof systems. Next, we show applications of laconic OT to non-interactive secure computation on large inputs and multi-hop homomorphic encryption for RAM programs.
Based on joint work with Chongwon Cho, Nico Döttling, Sanjam Garg, Divya Gupta, and Antigoni Polychroniadou. - Topology Hiding Computation on All Graphs / Rio LaVigne (MIT)
A distributed computation in which nodes are connected by a partial communication graph is called topology-hiding if it does not reveal information about the graph beyond what is revealed by the output of the function. Previous results have shown that topology-hiding computation protocols exist for graphs of constant degree and logarithmic diameter in the number of nodes [Moran-Orlov-Richelson, TCC’15; Hirt et al., Crypto’16] as well as for other graph families, such as cycles, trees, and low circumference graphs [Akavia-Moran, Eurocrypt’17], but the feasibility question for general graphs was open. In this work we positively resolve the above open problem: we prove that topology-hiding computation is feasible for all graphs under the Decisional Diffie-Hellman assumption. Our techniques employ random-walks to generate paths covering the graph, upon which we apply the Akavia-Moran topology-hiding broadcast for chain-graphs (paths). To prevent topology information revealed by the random-walk, we design multiple random-walks that, together, are locally identical to receiving at each round a message from each neighbors and sending back processed messages in a randomly permuted order. We can also extend this result to use deterministic walks (exploration sequences), opening up the possibility for a perfectly-complete topology hiding broadcast.
Joint work with Adi Akavia and Tal Moran. - Cryptographically Protected Database Search / Ben Fuller (University of Connecticut)
Protected database search systems cryptographically isolate the roles of reading from, writing to, and administering the database. This separation limits unnecessary administrator access and protects data in the case of system breaches. Since protected search was introduced in 2000, the area has grown rapidly; systems are offered by academia, start-ups, and established companies. However, there is no best protected search system or set of techniques. Design of such systems is a balancing act between security, functionality, performance, and usability. This challenge is made more difficult by ongoing database specialization, as some users will want the functionality of SQL, NoSQL, or NewSQL databases. This database evolution will continue, and the protected search community should be able to quickly provide functionality consistent with newly invented databases.
At the same time, the community must accurately and clearly characterize the tradeoffs between different approaches. In this talk, we survey the range of tradeoffs between security and privacy. In particular, we
1) identify the important primitive operations across database paradigms,
2) evaluate the current state of protected search systems in implementing these base operations, and
3) analyze attacks against protected search for different base queries. - Towards Breaking the Exponential Barrier for General Secret Sharing / Tianren Liu (MIT)
A non-monotone secret-sharing scheme for a Boolean (access) function F: {0,1}^n to {0,1} is a randomized algorithm that on input a secret, output n pairs of shares s_{1,0},s_{1,1},…,s_{n,0},s_{n,1} such that for any x_1,…,x_n, the n shares s_{1,x_1},…,s_{n,x_n} determine the secret if F(x_1,…,x_n)=1 and reveal nothing about the secret otherwise. Standard monotone secret-sharing correspond to the special case where F is monotone and s_{1,0} = … = s_{n,0} = \bot.The best secret sharing schemes for general functions (in both the monotone and non-monotone case) have shares of size \Omega(2^n). It has long been conjectured that one cannot do much better, namely, that there are access functions for which any secret sharing scheme necessarily has shares of size 2^{\Omega(n)}.In this work, we show non-monotone secret sharing schemes for every access function F with shares of size 2^{O(\sqrt(n) log n)}, disproving the conjecture for non-monotone secret sharing schemes. Our technique uses a new notion of decomposable matching vector (DMV) families as well as new constructions of DMV families. Matching vector families are combinatorial objects that have previously been used in circuit complexity, in construction of Ramsey graphs and in private information retrieval (PIR) protocols.Along the way, we also construct the first two-party and multi-party conditional disclosure of secrets (CDS) protocols for general functions with communication complexity 2^{O(\sqrt(n) log n)}.Joint works with Vinod Vaikuntanathan and Hoeteck Wee. - Be Adaptive, Avoid Overcommitting / Ilan Komargodski (Cornell Tech)
For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fon. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future.Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to $n$-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to $2^n$. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of $m \ll n$ bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire $n$-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only $2^m \ll 2^n$.In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs.
Joint work with Zahra Jafargholi, Chethan Kamath, Karen Klein, Krzysztof Pietrzak and Daniel Wichs.
Advertisements
