Institute of Information Science, Academia Sinica

Linear-sized circuits for compaction and selection
Elaine Shi (Cornell University)

Abstract:
In this talk, I will describe how to construct an O(n w (polylog* n - polylog* w))-sized circuit for solving
1) selection, i.e., finding the median of n elements each of bit-length w;
2) compaction, i.e., sorting an array of n elements each with a 1-bit key and a w-bit payload.
For w >= log^{(c)} n where log^{(c)} denotes taking iterative logarithm any constant number of times, the circuit size is strictly linear and optimal, i.e., O(nw).
We also show a non-trivial, non-comparison-based generalization of the AKS sorting network: sorting n elements each of w bits requires a circuit of O(n w log K) size (ignoring polylog* factors) assuming each element's key comes from [K]. For keys much shorter than log n-bits, our circuit size is asymptotically better than AKS.
Results of such nature are long known to be impossible (see [Knuth'73]) in the comparator-based model which is adopted by known sorting networks; and we are the first to show non-trivial, non-comparison-based results in the circuit model of computation.
Finally, I will briefly comment on the relations of this result to constructing optimal ORAM.

break

Title: Obfuscation from LWE? Candidates, Proofs and Attacks
Hoeteck Wee (École normale supérieure)

Abstract:
Multi-linear encodings provide a way to "encrypt" many pairs of matrices, such that we can check whether any subset product is zero, while potentially hiding all other information about the matrices. Instantiated with the GGH15 candidate encodings, this immediately yields a remarkably simple candidate obfuscator for NC1, whose security seems related to the LWE assumption. So, how far are we from obfuscation for circuits or NC1 from LWE? In this talk, we provide a survey of the existing candidates, proofs and attacks.