## CryptoDB

### Tianren Liu

#### Publications

**Year**

**Venue**

**Title**

2021

CRYPTO

The $t$-wise Independence of Substitution-Permutation Networks
📺
Abstract

Block ciphers such as the Advanced Encryption Standard (Rijndael) are used extensively in practice, yet our understanding of their security continues to be highly incomplete. This paper promotes and continues a research program aimed at {\em proving} the security of block ciphers against important and well-studied classes of attacks. In particular, we initiate the study of (almost) $t$-wise independence of concrete block-cipher construction paradigms such as substitution-permutation networks and key-alternating ciphers. Sufficiently strong (almost) pairwise independence already suffices to resist (truncated) differential attacks and linear cryptanalysis, and hence this is a relevant and meaningful target. Our results are two-fold.
Our first result concerns substitution-permutation networks (SPNs) that model ciphers such as AES. We prove the almost pairwise-independence of an SPN instantiated with concrete S-boxes together with an appropriate linear mixing layer, given sufficiently many rounds and independent sub-keys. Our proof relies on a {\em characterization} of S-box computation on input differences in terms of sampling output differences from certain subspaces, and a new randomness extraction lemma (which we prove with Fourier-analytic techniques) that establishes when such sampling yields uniformity. We use our techniques in particular to prove almost pairwise-independence for sufficiently many rounds of both the AES block cipher (which uses a variant of the patched inverse function $x \mapsto x^{-1}$ as the $S$-box) and the MiMC block cipher (which uses the cubing function $x \mapsto x^3$ as the $S$-box), assuming independent sub-keys.
Secondly, we show that instantiating a key-alternating cipher (which can be thought of as a degenerate case of SPNs) with most permutations gives us (almost) $t$-wise independence in $t + o(t)$ rounds. In order to do this, we use the probabilistic method to develop two new lemmas, an {\em independence-amplification lemma} and a {\em distance amplification lemma}, that allow us to reason about the evolution of key-alternating ciphers.

2021

TCC

Multi-party PSM, Revisited: Improved Communication and Unbalanced Communication
📺
Abstract

We improve the communication complexity in the Private Simultaneous Messages (PSM) model, which is a minimal model of non-interactive information-theoretic multi-party computation. The state-of-the-art PSM protocols were recently constructed by Beimel, Kushilevitz and Nissim (EUROCRYPT 2018).
We present new constructions of $k$-party PSM protocols. The new protocols match the previous upper bounds when $k=2$ or $3$ and improve the upper bounds for larger $k$. We also construct $2$-party PSM protocols with unbalanced communication complexity.
More concretely,
- For infinitely many $k$ (including all $k \leq 20$), we construct $k$-party PSM protocols for arbitrary functionality $f:[N]^k\to\{0,1\}$, whose communication complexity is $O_k(N^{\frac{k-1}{2}})$. This improves the former best known upper bounds of $O_k(N^{\frac{k}{2}})$ for $k\geq 6$, $O(N^{7/3})$ for $k=5$, and $O(N^{5/3})$ for $k=4$.
- For all rational $0<\eta<1$ whose denominator is $\leq 20$, we construct 2-party PSM protocols for arbitrary functionality $f:[N]\times[N]\to\{0,1\}$, whose communication complexity is $O(N^\eta)$ for one party, $O(N^{1-\eta})$ for the other. Previously the only known unbalanced 2-party PSM has communication complexity $O(\log(N)), O(N)$.

2020

TCC

Information-Theoretic 2-Round MPC without Round Collapsing: Adaptive Security, and More
📺
Abstract

We present simpler and improved constructions of 2-round protocols for secure multi-party computation (MPC) in the semi-honest setting. Our main results are new information-theoretically secure protocols for arithmetic NC1 in two settings:
(i) the plain model tolerating up to $t < n/2$ corruptions; and
(ii) in the OLE-correlation model tolerating any number of corruptions.
Our protocols achieve adaptive security and require only black-box access to the underlying field, whereas previous results only achieve static security and require non-black-box field access. Moreover, both results extend to polynomial-size circuits with computational and adaptive security, while relying on black-box access to a pseudorandom generator. In the OLE correlation model, the extended protocols for circuits tolerate up to $n-1$ corruptions.
Along the way, we introduce a conceptually novel framework for 2-round MPC that does not rely on the round collapsing framework underlying all of the recent advances in 2-round MPC.

2019

CRYPTO

Reusable Non-Interactive Secure Computation
📺
Abstract

We consider the problem of Non-Interactive Two-Party Secure Computation (NISC), where Rachel wishes to publish an encryption of her input x, in such a way that any other party, who holds an input y, can send her a single message which conveys to her the value f(x, y), and nothing more. We demand security against malicious parties. While such protocols are easy to construct using garbled circuits and general non-interactive zero-knowledge proofs, this approach inherently makes a non-black-box use of the underlying cryptographic primitives and is infeasible in practice.Ishai et al. (Eurocrypt 2011) showed how to construct NISC protocols that only use parallel calls to an ideal oblivious transfer (OT) oracle, and additionally make only a black-box use of any pseudorandom generator. Combined with the efficient 2-message OT protocol of Peikert et al. (Crypto 2008), this leads to a practical approach to NISC that has been implemented in subsequent works. However, a major limitation of all known OT-based NISC protocols is that they are subject to selective failure attacks that allows a malicious sender to entirely compromise the security of the protocol when the receiver’s first message is reused.Motivated by the failure of the OT-based approach, we consider the problem of basing reusable NISC on parallel invocations of a standard arithmetic generalization of OT known as oblivious linear-function evaluation (OLE). We obtain the following results:We construct an information-theoretically secure reusable NISC protocol for arithmetic branching programs and general zero-knowledge functionalities in the OLE-hybrid model. Our zero-knowledge protocol only makes an absolute constant number of OLE calls per gate in an arithmetic circuit whose satisfiability is being proved. We also get reusable NISC in the OLE-hybrid model for general Boolean circuits using any one-way function.We complement this by a negative result, showing that reusable NISC is impossible to achieve in the OT-hybrid model. This provides a formal justification for the need to replace OT by OLE.We build a universally composable 2-message reusable OLE protocol in the CRS model that can be based on the security of Paillier encryption and requires only a constant number of modular exponentiations. This provides the first arithmetic analogue of the 2-message OT protocols of Peikert et al. (Crypto 2008).By combining our NISC protocol in the OLE-hybrid model and the 2-message OLE protocol, we get protocols with new attractive asymptotic and concrete efficiency features. In particular, we get the first (designated-verifier) NIZK protocols for NP where following a statement-independent preprocessing, both proving and verifying are entirely “non-cryptographic” and involve only a constant computational overhead. Furthermore, we get the first statistical designated-verifier NIZK argument for NP under an assumption related to factoring.

2018

TCC

On Basing Search SIVP on NP-Hardness
★
Abstract

The possibility of basing cryptography on the minimal assumption
$$\mathbf{NP }\nsubseteq \mathbf{BPP }$$
NP⊈BPP is at the very heart of complexity-theoretic cryptography. The closest we have gotten so far is lattice-based cryptography whose average-case security is based on the worst-case hardness of approximate shortest vector problems on integer lattices. The state-of-the-art is the construction of a one-way function (and collision-resistant hash function) based on the hardness of the
$$\tilde{O}(n)$$
O~(n)-approximate shortest independent vector problem
$${\textsf {SIVP}}_{\tilde{O}(n)}$$
SIVPO~(n).Although
$${\textsf {SIVP}}$$
SIVP is NP-hard in its exact version, Guruswami et al. (CCC 2004) showed that
$${\textsf {gapSIVP}}_{\sqrt{n/\log n}}$$
gapSIVPn/logn is in
$$\mathbf{NP } \cap \mathbf{coAM }$$
NP∩coAM and thus unlikely to be
$$\mathbf{NP }$$
NP-hard. Indeed, any language that can be reduced to
$${\textsf {gapSIVP}}_{\tilde{O}(\sqrt{n})}$$
gapSIVPO~(n) (under general probabilistic polynomial-time adaptive reductions) is in
$$\mathbf{AM } \cap \mathbf{coAM }$$
AM∩coAM by the results of Peikert and Vaikuntanathan (CRYPTO 2008) and Mahmoody and Xiao (CCC 2010). However, none of these results apply to reductions to search problems, still leaving open a ray of hope: can
$$\mathbf{NP }$$
NPbe reduced to solving search SIVP with approximation factor
$$\tilde{O}(n)$$
O~(n)?We eliminate such possibility, by showing that any language that can be reduced to solving search
$${\textsf {SIVP}}$$
SIVP with any approximation factor
$$\lambda (n) = \omega (n\log n)$$
λ(n)=ω(nlogn) lies in AM intersect coAM.

#### Coauthors

- Léonard Assouline (1)
- Melissa Chase (1)
- Yevgeniy Dodis (2)
- Yuval Ishai (1)
- Daniel Kraschewski (1)
- Huijia Lin (1)
- Rafail Ostrovsky (1)
- Martijn Stam (1)
- John P. Steinberger (1)
- Stefano Tessaro (1)
- Vinod Vaikuntanathan (5)
- Hoeteck Wee (3)