http://www.ntt.co.jp/sc/event_e/event20181026.html
Program
- New Techniques for obtaining Adaptive Security in Garbling Schemes (Akshayaram Srinivasan)
- Secret Sharing and CDS (Tianren Liu)
- New Bleichenbacher Records: Fault Attacks on qDSA Signatures (Akira Takahashi)
Abstracts
New Techniques for obtaining Adaptive Security in Garbling Schemes
Akshayaram Srinivasan (UC Berkeley)
Garbled circuits are fundamental cryptographic primitives. They have diverse applications such as designing secure multiparty computation protocols, in parallel cryptography, in constructing program obfuscation and more recently in constructing IBE schemes without pairings. The security of garbling schemes have been analyzed in two settings: the selective setting and the adaptive setting. In the selective setting, an adversary is forced to declare the input on which he wishes to evaluate the circuit before seeing the garbled circuit and in the adaptive setting, he is allowed to choose the input adaptively depending on the garbled circuit. Constructing adaptive garbled circuits where the size of the garbled input is small has been a major open problem in cryptography. In this talk, I will give a construction of adaptive garbled circuits where the size of the garbled input is (nearly) optimal. I will also discuss extensions to adaptively garbling RAM programs.
Based on joint work(s) with Sanjam Garg and Rafail Ostrovsky.
Secret Sharing and CDS
Tianren Liu (MIT)
We study secret sharing schemes for general (non-threshold) access structures. A general secret sharing scheme for $n$ parties is associated to a monotone function $F:{0,1}^n\to{0,1}$. In such a scheme, a dealer distributes shares of a secret $s$ among $n$ parties. Any subset of parties $T \subseteq [n]$ should be able to put together their shares and reconstruct the secret $s$ if $F(T)=1$, and should have no information about $s$ if $F(T)=0$. One of the major long-standing questions in information-theoretic cryptography is to minimize the (total) size of the shares in a secret-sharing scheme for arbitrary monotone functions $F$.
There is a large gap between lower and upper bounds for secret sharing. The best known scheme for general $F$ has shares of size $2^{n-o(n)}$, but the best lower bound is $\Omega(n^2/\log n)$. Indeed, the exponential share size is a direct result of the fact that in all known secret-sharing schemes, the share size grows with the size of a circuit (or formula, or monotone span program) for $F$. Indeed, several researchers have suggested the existence of a {\em representation size barrier} which implies that the right answer is closer to the upper bound, namely, $2^{n-o(n)}$.
We overcome this barrier by constructing a secret sharing scheme for any access structure with shares of size $2^{0.994n}$ and a linear secret sharing scheme for any access structure with shares of size $2^{0.999n}$. As a contribution of independent interest, we also construct a secret sharing scheme with shares of size $2^{\tilde{O}(\sqrt{n})}$ for double exponential different monotone access structures.
Our secret sharing schemes build on our new protocol for conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate. For genearl predicates where the input size is $n$ for both parties, the best protocols prior to our work required communication complexity $O(2^{n/2})$.
We present the first protocol with $2^{O(\sqrt(n\log n))}$ communication complexity. To obtain these results, we draw upon techniques for non-linear reconstruction developed in the context of information-theoretic private information retrieval (PIR).
Based on joint works with Vinod Vaikuntanathan and Hoeteck Wee.
New Bleichenbacher Records: Fault Attacks on qDSA Signatures
Akira Takahashi (Kyoto University)
Signature generation in (EC)DSA and other Schnorr-like schemes uses ephemeral secret values known as nonces. It is well known that nonces should be sampled uniformly in a certain interval and should never be revealed; if the actual distribution of nonces deviates from the uniform distribution or nonces are partially exposed, there exist attacks on these schemes that can, in the worst case, yield to the recovery of the entire secret signing key, and hence fully compromise the security of the signature scheme.
In this talk, we present our two recent contributions to the study of attacks against nonces in Schnorr-like schemes: 1) highly optimized version of Bleichenbacher’s attack technique against biased nonces, and 2) novel fault attacks on a recent, high-profile Schnorr-like scheme of Renes and Smith (ASIACRYPT 2017), called quotient Digital Signature (qDSA), when instantiated over the Curve25519 Montgomery curve.
Combining our two contributions, we are able to achieve a full secret key recovery on qDSA by applying our version of Bleichenbacher’s attack to these faulty signatures. The targeted parameters (in terms of the number of leaked bits and signature security level) were previously considered out of reach, and we thus have set new records in the implementation of Bleichenbacher’s attack.
Joint work with: Mehdi Tibouchi (NTT) and Masayuki Abe (NTT)