# Program

 Day 2 — December 22nd Session: Hardware Chair: Robbert van Renesse RM 1-315 09:00-10:00 Ed Suh, Cornell Title: Secure Multi-Core Processors with Comprehensive and Verifiable Information Flow Control Abstract: As computing devices are increasingly shared by multiple software entities, hardware-level protection for critical software is essential for a strong security guarantee. This talk will show how static information flow analysis and micro-architecture timing-channel protection can be used to build a multi-core system with comprehensive and verifiable information flow assurance, and briefly discuss how such a system can be leveraged in the context of a self-driving car to protect safety-critical functions. The first part of the talk will introduce a secure hardware design language, named SecVerilog, which enables designers to statically analyze information flow at the hardware level and thus to build systems where information channels are verifiably controlled. SecVerilog is Verilog, extended with security type annotations, and provides rigorous formal assurance that a hardware design enforces timing-sensitive noninterference. Our experiences suggest that SecVerilog can be used to verify security properties of realistic hardware designs with low overhead. For example, we used SecVerilog to build a processor with a verifiable guarantee on timing channel protection as well as to detect implementation bugs in hardware security architecture similar to ARM TrustZone. 10:00-10:15 Tea Break Session: Cryptography, Theory Chair: Andrew Chi-Chih Yao 10:15-10:45 John Steinberger, Tsinghua Title: Provable Security of Substitution-Permutation Networks Abstract: A number of popular block ciphers (such as AES-128, among others) are built on a so-scalled “substitution-permutation network” (SPN)  paradigm. In this talk we discuss recent work investigating SPNs in an idealised paradigm, in which the S-boxes are modeled as random permutations. We show that a small number of rounds (1 or 3, depending on whether nonlinear key schedules are allowed) suffice to attain birthday-type security on the S-box input length. We will introduce a number of (rather cute!) nonlinear key schedules, that offer different structural tradeoffs for the network and that achieve provable security. 10:45-11:15 Yu Yu, Shanghai Jiao Tong University Title: Some Recent Progress on Cryptography from Learning Parity with Noise Abstract: Learning Parity with Noise (LPN) is a notoriously hard problem in learning theory and coding theory. It represents the well-known NPC problem “decoding random linear codes” and its average-case hardness is also well studied. Recently, there has been renewed interest in building provably secure crypto-systems from LPN. This talk will introduce the LPN problem and some recent progress on LPN-based cryptographic schemes such as pseudorandom generators in AC0(mod 2), pseudorandom functions in almost constant depth, and public-key encryption schemes. The is a combination of two works (jointly with John Steinberger at EUROCRYPT 2016 and Jiang Zhang at CRYPTO 2016 respectively). 11:15-11:45 Xiongfeng Ma, Tsinghua Title: From quantumness to security in quantum cryptography Abstract: Coherence and entanglement are two peculiar features of quantum theory. Coherence captures the phenomenon of coherent superposition of quantum states, while entanglement, “the spooky action at a distance”, plays a crucial role in the nonlocality of quantum mechanics. In this talk, I shall present two links: between coherence and randomness in quantum random number generation, and between entanglement and security in quantum key distribution. Random numbers play an indispensable role in modern society in various arenas of finance, cryptography, and computation. Considering individual and coherent measurement of the correlated party, we show that the coherence of formation and the relative entropy of coherence measure the quantum randomness for these two situations, respectively. Furthermore, we calculate the gap between the two quantum randomness, which turns out to related another quantum correlation — discord. In quantum information processing, entanglement becomes an important resource for various tasks, such as teleportation, quantum computation, and cryptography. Intuitively, entanglement means a strong nonlocal correlation between distant parties, which essentially offers a secure key generation tool. Various Bell’s inequality test experiments have proved that eavesdropping (as a local hidden variable) can be fundamentally ruled out. In this talk, I shall link the basic concept of entanglement with the security of key distribution. 11:45-12:15 Kai-Min Chung, Academia Sinica Title: Computational Notions of Quantum Min-Entropy Abstract: Computational notions of entropy have many applications in cryptography and complexity theory. These notions measure how much (min-)entropy a source $X$ has from the eyes of a computationally bounded party who may hold certain “leakage information” $B$ that is correlated with $X$.  In this work, we initiate the study of computational entropy in the *quantum* setting, where $X$ and/or $B$ may become quantum states and the computationally bounded observer is modelled as a small quantum circuit.  Specifically, we investigate to what extent the  classical notions of computational entropy  generalize to the quantum setting, and whether quantum analogues of classical theorems still hold. For example, we show: – There exist quantum states that are *pseudorandom* (i.e. they cannot be distinguished from the totally mixed state by polynomial-sized quantum circuits) but have actual entropy 0 (i.e. are pure states).  In contrast, a classical distribution needs super-logarithmic entropy to be pseudorandom. – We extend the classical Leakage Chain Rule for pseudoentropy to the case where the leakage information $B$ is quantum (while $X$ remains classical).  Specifically, if $X$ has pseudoentropy at least $k$ against quantum distinguishers (i.e. it is indistinguishable from some distribution of min-entropy at least $k$ by polynomial-sized quantum distinguishers) and $B$ consists of at most a logarithmic number $\ell$ of qubits, then $X$ conditioned on $B$ has pseudoentropy at least $k-\ell$ against quantum distinguishers. – We show that a general form of the classical Dense Model Theorem (interpreted as showing the equivalence between two definitions of pseudo-relative-min-entropy) does *not* extend to quantum states. Along the way, we develop quantum analogues of a number of classical techniques (e.g. the Leakage Simulation Lemma, proven using a Non-uniform Min-Max Theorem or Boosting), and also identify classical techniques (namely, Gap Amplification) that do not hold in the quantum setting.   Moreover, we introduce a variety of notions that combine quantum information and quantum complexity, which raise a number of directions for future work. Joint work with Yi-Hsiu Chen, Ching-Yi Lai, Salil Vadhan, and Xiaodi Wu 12:15-13:30 working lunch, lunch talks, mingle  Session Chair: Phil Daian RM 1-222 12:30-13:00 Lunch talk:  Qiang Tang, NJIT Title: Cliptography: Post-Snowden Cryptography Abstract: Despite the laudatory history of development of modern cryptography, an implicit assumption that the implementations are trusted has been made in (essentially) all security definitions. While the dangers of entertaining adversarial implementation of cryptographic primitives seem obvious, the ramifications of such attacks are surprisingly dire: it turns out that—in wide generality—adversarial implementations of cryptographic (randomized) algorithms may leak private information while producing output that is statistically indistinguishable from that of a faithful implementation. I will first briefly describe the intuition about the above subliminal channel attacks. Inspired by some folklore practical wisdom, I will also introduce some simple but rigorous immunizing strategies on subverted randomized algorithms. 13:00-13:30 Feng-Hao Liu, Florida Atlantic University Title: Compact Identity Based Encryption from LWE Abstract: We construct an  identity-based encryption (IBE) scheme from the standard Learning with Errors (LWE) assumption that has \emph{compact} public-key and achieves adaptive security in the standard model. In particular, our scheme only needs 2 public matrices to support $O(\log^2 \secparam)$-bit length identity, and $O(\secparam / \log^2 \secparam)$ public matrices to support $\secparam$-bit length identity. This improves over previous IBE schemes from lattices substantially. Additionally, our techniques from IBE can be adapted to construct a compact digital signature scheme, which achieves existential unforgeability under the standard Short Integer Solution (SIS) assumption with small polynomial parameters. Joint work with Daniel Apon and Xiong Fan 13:30-14:00 Rump session II: 3 talks “Tolerating Password Typos: A security-usability tradeoff.” – Rahul Chatterjee ‘’Hash Garbled Circuits for Free’’ – Xiong Fan “Practical Secure Aggregation for Privacy-Preserving Machine Learning” – Antonio Marcedone “Immutability: This is the database property you are looking for” – Kai Mast 14:00-14:20 Ending notes 14:20- Activities