http://www.ntt.co.jp/sc/event_e/event20190308.html
Program
- Collusion Resistant Traitor Tracing from Learning with Errors (Rishab Goyal)
- Fine-grained quantum computational supremacy (Tomoyuki Morimae)
- Non-Malleable Codes for Decision Trees (and more) (Marshall Ball)
- Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness (Akinori Hosoyamada)
Abstracts
Collusion Resistant Traitor Tracing from Learning with Errors
Rishab Goyal (UT Austin)
In this work we provide a traitor tracing scheme with ciphertexts that grow polynomially in log(N) where N is the number of users and prove it secure under the Learning with Errors (LWE) assumption. This is the first traitor tracing scheme with such parameters provably secure from a standard assumption. In addition to achieving new traitor tracing results, we believe our techniques push forward the broader area of computing on encrypted data under standard assumptions. Notably, traitor tracing is substantially different problem from other cryptography primitives that have seen recent progress in LWE solutions.
We achieve our results by first conceiving a novel approach to building traitor tracing that starts with a new form of Functional Encryption that we call Mixed FE. In a Mixed FE system the encryption algorithm is bimodal and works with either a public key or master secret key. Ciphertexts encrypted using the public key can only encrypt one type of functionality. On the other hand the secret key encryption can be used to encode many different types of programs, but is only secure as long as the attacker sees a bounded number of such ciphertexts.
We first show how to combine Mixed FE with Attribute-Based Encryption to achieve traitor tracing. Second we build Mixed FE systems for polynomial sized branching programs (which corresponds to the complexity class LOGSPACE) by relying on the polynomial hardness of the LWE assumption with super-polynomial modulus-to-noise ratio.
This is joint work with Venkata Koppula and Brent Waters. Full paper: https://eprint.iacr.org/2018/346
Fine-grained quantum computational supremacy
Tomoyuki Morimae (Kyoto University)
It is known that several sub-universal quantum computing models cannot be classically simulated in polynomial-time unless the polynomial-time hierarchy collapses. These results, however, do not rule out possibilities of exponential- or sub-exponential-time classical simulations. In this paper, we study fine-grained quantum computational supremacy that excludes superpolynomial-time classical simulations. We first consider the DQC1 model. We show that for any a>0 output probability distributions of the N-qubit DQC1 model cannot be classically sampled within a constant multiplicative error and in 2^{(1−a)N+o(N)} time (under certain conjectures in fine-grained complexity theory). We next show similar fine-grained quantum supremacy results for the HC1Q model, which is another sub-universal model with a classical circuit sandwiched by two Hadamard layers. Finally, we also consider universal quantum computing with Clifford and T gates. We first show that under the exponential-time hypothesis (ETH), output probability distributions of Clifford-T quantum computing cannot be calculated in 2^{o(t)} time within an additive error smaller than 2^{(−3t+14)/7}, where t is the number of T gates. We next show that under another fine-grained complexity conjecture, output probability distributions of Clifford-T quantum computing cannot be classically sampled in 2^{o(t)} time within a constant multiplicative error. There is a classical algorithm that calculates output probability distributions of Clifford-T quantum computing within a constant multiplicative error in ∼2^{βt} time with a non-trivial factor β≃0.47 [S. Bravyi and D. Gosset, Physical Review Letters 116, 250501 (2016)]. Our second result on Clifford-T quantum computing therefore suggests that improving 2^{βt} to sub-exponential time, say 2^{√t}, is impossible.
Non-Malleable Codes for Decision Trees (and more)
Marshall Ball (Columbia University)
We construct efficient, unconditional non-malleable codes that are secure against tamper- ing functions computed by decision trees of depth n^{1/4−o(1)} . Prior to this work, no efficient unconditional non-malleable codes were known for decision trees beyond depth logn. Our result also yields efficient, unconditional non-malleable codes that are exp(−n^{\Omega(1)})- secure against constant-depth circuits of exp(n^{\Omega(1))-size. Prior work of Chattopadhyay and Li (STOC 2017) and Ball et al. (FOCS 2018) only provide protection against exp(O(log^2(n)))-size circuits with exp(−O(log^2(n)))-security. We achieve our result through simple reductions of decision tree tampering to split-state tampering. As an intermediary, we give a simple and generic reduction of leakage-resilient split-state tampering to split-state tampering. Prior work of Aggawarl et al. (TCC 2015) only provides a reduction to split-state non-malleable codes with decoders that exhibit particular properties.
Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness
Akinori Hosoyamada (NTT Secure Platform Laboratories)
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.