International Association
for Cryptologic Research

We present new classical and quantum algorithms for solving random subset-sum instances. First, we improve over the Becker-Coron-Joux algorithm (EUROCRYPT 2011) from $\widetilde{\mathcal{O}} \left(2^{0.291 n}\right)$ downto $\widetilde{\mathcal{O}} \left(2^{0.283 n}\right)$, using more general representations with values in $\{-1,0,1,2\}$.

Next, we improve the state of the art of quantum algorithms for this problem in several directions. By combining the Howgrave-Graham-Joux algorithm (EUROCRYPT 2010) and quantum search, we devise an algorithm with asymptotic cost $\widetilde{\mathcal{O}} \left(2^{0.236 n}\right)$, lower than the cost of the quantum walk based on the same classical algorithm proposed by Bernstein, Jeffery, Lange and Meurer (PQCRYPTO 2013). This algorithm has the advantage of using classical memory with quantum random access, while the previously known algorithms used the quantum walk framework, and required quantum memory with quantum random access.

We also propose new quantum walks for subset-sum, performing better than the previous best time complexity of $\widetilde{\mathcal{O}} \left(2^{0.226 n}\right)$ given by Helm and May (TQC 2018). We combine our new techniques to reach a time $\widetilde{\mathcal{O}} \left(2^{0.216 n}\right)$. This time is dependent on a heuristic on quantum walk updates, formalized by Helm and May, that is also required by the previous algorithms. We show how to partially overcome this heuristic, and we obtain an algorithm with quantum time $\widetilde{\mathcal{O}} \left(2^{0.218 n}\right)$ requiring only the standard classical subset-sum heuristics.

Event date: 19 June 2020
Submission deadline: 16 March 2020
Notification: 12 April 2020

Federated learning is gaining significant interests as it enables model training over a large volume of data that is distributedly stored over many users, while protecting the privacy of the individual users. However, a major bottleneck in scaling federated learning to a large number of users is the overhead of secure model aggregation across many users. In fact, the overhead of state-of-the-art protocols for secure model aggregation grows quadratically with the number of users. We propose a new scheme, named Turbo-Aggregate, that in a network with $N$ users achieves a secure aggregation overhead of $O(N\log{N})$, as opposed to $O(N^2)$, while tolerating up to a user dropout rate of $50\%$. Turbo-Aggregate employs a multi-group circular strategy for efficient model aggregation, and leverages additive secret sharing and novel coding techniques for injecting aggregation redundancy in order to handle user dropouts while guaranteeing user privacy. We experimentally demonstrate that Turbo-Aggregate achieves a total running time that grows almost linear in the number of users, and provides up to $14\times$ speedup over the state-of-the-art schemes with upto $N=200$ users. We also experimentally evaluate the impact of several key network parameters (e.g., user dropout rate, bandwidth, and model size) on the performance of Turbo-Aggregate.

\emph{Off-chain channel networks} are one of the most promising technologies for dealing with blockchain scalability and delayed finality issues. Parties that are connected within such networks can send coins to each other without interacting with the blockchain. Moreover, these payments can be ``routed'' over the network. Thanks to this, even the parties that do not have a channel in common can perform payments between each other with a help of intermediaries.

In this paper, we present a new technique (that we call \emph{Dynamic Internal Payment Splitting (DIPS)}) that allows the intermediaries in the network to split the payments into several sub-payments. This can be done recursively multiple times by subsequent intermediaries. Moreover, the resulting ``payment receipts'' can be aggregated by each intermediary into one short receipt that can be propagated back in the network. We present a protocol (that we call ``Ethna'') that uses this technique. We provide a formal security definition of our protocol and we prove that Ethna satisfies it. We also implement a simple variant of Ethna in Solidity and provide some benchmarks.

This paper has four main goals. First, we show how we solved the CHES 2018 AES challenge in the contest using essentially a linear classifier combined with a SAT solver and a custom error correction method. This part of the paper has previously appeared in a preprint of our own and later as a contribution to a preprint write-up of the solutions by the three winning teams. This solution serves as a baseline for other solutions explored in the paper.

Second, we develop a novel deep neural network architecture for side-channel analysis that completely breaks the AES challenge, allowing for fairly reliable key recovery with just a single trace on the unknown-device part of the CHES challenge. This solution significantly improves upon all previously published solutions of the AES challenge, including our baseline linear solution.

Third, we consider the question of leakage attribution for both the classifier we used in the challenge and for our deep neural network. Direct inspection of the weight vector of our machine learning model yields a lot of information on the implementation for our linear classifier. For the deep neural network, we test three other strategies (occlusion of traces; inspection of adversarial changes; knowledge distillation) and find that these can yield information on the leakage essentially equivalent to that gained by inspecting the weights of the simpler model.

Fourth, we study the properties of adversarially generated side-channel traces for our model. Partly reproducing recent work on useful features in adversarial examples in our application domain, we find that a linear classifier generalizing to an unseen device much better than our linear baseline can be trained using only adversarial examples (fresh random keys, adversarially perturbed traces) for our deep neural network. This gives a new way of extracting human-usable knowledge from a deep side channel model while also yielding insights on adversarial examples in an application domain where relatively few sources of spurious correlations between data and labels exist.

In the fall of 2018, a professor became obsessed with conspiracy theories of deeper connections between discrete-log based cryptography and lattice based cryptography. That obsession metastisized and spread to some of the students in the professor's cryptography course through a cryptanalysis challenge that was set as a class competition. The students and the professor continued travelling further down the rabbit hole, refusing to stop when the semester was over. Refusing to stop even as some of the students graduated, and really refusing to stop even now, but pausing long enough to write up this chronicle of their exploits.

Functional Encryption denotes a form of encryption where a master secret key-holder can control which functions a user can evaluate on encrypted data. Learning With Errors (LWE) (Regev, STOC'05) is known to be a useful cryptographic hardness assumption which implies strong primitives such as, for example, fully homomorphic encryption (Brakerski-Vaikuntanathan, FOCS'11) and lockable obfuscation (Goyal et al., Wichs et al., FOCS'17). Despite its strength, however, there is just a limited number of functional encryption schemes which can be based on LWE. In fact, there are functional encryption schemes which can be achieved by using pairings but for which no secure instantiations from lattice-based assumptions are known: function-hiding inner product encryption (Lin, Baltico et al., CRYPTO'17) and compact quadratic functional encryption (Abdalla et al., CRYPTO'18). This raises the question whether there are some mathematical barriers which hinder us from realizing function-hiding and compact functional encryption schemes from lattice-based assumptions as LWE.

To study this problem, we prove an impossibility result for function-hiding functional encryption schemes which meet some algebraic restrictions at ciphertext encryption and decryption. Those restrictions are met by a lot of attribute-based, identity-based and functional encryption schemes whose security stems from LWE. Therefore, we see our results as important indications why it is hard to construct new functional encryption schemes from LWE and which mathematical restrictions have to be overcome to construct secure lattice-based functional encryption schemes for new functionalities.

We present a new secure multiparty computation protocol that allows for evaluating a number of instances of a boolean circuit in parallel, with a small online communication complexity per instance of $10$ bits per party and multiplication gate. Our protocol is secure against an active adversary corrupting a dishonest majority. The protocol uses an approach introduced recently in the setting of honest majority and information-theoretically security, based on the algebraic notion known as reverse multiplication friendly embeddings, which essentially transforms a batch of evaluations of an arithmetic circuit over a small field into one evaluation of another arithmetic circuit over a larger field. To obtain security against a dishonest majority, we combine this approach with the well-known SPDZ protocol that provides security against a dishonest majority but operates over a large field. As SPDZ and its variants, our protocol operates in the preprocessing model. Structurally our protocol is most similar to MiniMAC, a protocol which bases its security on the use of error-correcting codes, but our protocol has a communication complexity which is half of that of MiniMAC when the best available binary codes are used. With respect to certain variant of MiniMAC that utilizes codes over larger fields, our communication complexity is slightly worse; however, that variant of MiniMAC needs a much larger preprocessing than ours. We also show that our protocol also has smaller amortized communication complexity than Committed MPC, a protocol for general fields based on homomorphic commitments, if we use the best available constructions for those commitments. Finally, we construct a preprocessing phase from oblivious transfer based on ideas from MASCOT and Committed MPC.

A universal circuit (UC) is a general-purpose circuit that can simulate arbitrary circuits (up to a certain size $n$). Valiant provides a $k$-way recursive construction of universal circuits (STOC 1976), where $k$ tunes the complexity of the recursion. More concretely, Valiant gives theoretical constructions of 2-way and 4-way UCs of asymptotic (multiplicative) sizes $5n\log n$ and $4.75 n\log n$ respectively, which matches the asymptotic lower bound $\Omega(n\log n)$ up to some constant factor.

Motivated by various privacy-preserving cryptographic applications, Kiss et al. (Eurocrypt 2016) validated the practicality of 2-way universal circuits by giving example implementations for private function evaluation. G{\"{u}}nther et al. (Asiacrypt 2017) and Alhassan et al. (ePrint/2019/348) implemented the 2-way/4-way hybrid UCs with various optimizations in place towards making universal circuits more practical. Zhao et al. (Asiacrypt 2019) optimized Valiant's 4-way UC to asymptotic size $4.5 n\log n$ and proved a lower bound $3.64 n\log n$ for UCs under Valiant framework. As the scale of computation goes beyond 10-million-gate ($n=10^7$) or even billion-gate level ($n=10^9$), the constant factor in circuit size plays an increasingly important role in application performance. In this work, we investigate Valiant's universal circuits and present an improved framework for constructing universal circuits with the following advantages.

[*Simplicity*] Parameterization is no longer needed. In contrast to that previous implementations resort to a hybrid construction combining $k=2$ and $k=4$ for a tradeoff between fine granularity and asymptotic size-efficiency, our construction gets the best of both worlds when configured at the lowest complexity (i.e., $k=2$).

[*Compactness*] Our universal circuits have asymptotic size $3n\log n$, improving upon the best previously known $4.5n\log n$ by 33\% and beating the $3.64n\log n$ lower bound for UCs constructed under Valiant's framework (Zhao et al., Asiacrypt 2019).

[*Tightness*] We show that under our new framework the universal circuit size is lower bounded by $2.95 n\log n$, which almost matches the $3n\log n$ circuit size of our 2-way construction.

We implement the 2-way universal circuits and evaluate its performance with other implementations, which confirms our theoretical analysis.

Let $l$ and $k$ be two integers such that $l|k$. Define $T_l^k(X):=X+X^{p^l}+\cdots+X^{p^{l(k/l-2)}}+X^{p^{l(k/l-1)}}$ and $S_l^k(X):=X-X^{p^l}+\cdots+(-1)^{(k/l-1)}X^{p^{l(k/l-1)}}$, where $p$ is any prime.

This paper gives explicit representations of all solutions in $\GF{p^n}$ to the affine equations $T_l^{k}(X)=a$ and $S_l^{k}(X)=a$, $a\in \GF{p^n}$. For the case $p=2$ that was solved very recently in \cite{MKCL2019}, the result of this paper reveals another solution.

Machine learning (ML) methods have been widely used in genomic studies. However, genomic data are often held by different stakeholders (e.g. hospitals, universities, and healthcare companies) who consider the data as sensitive information, even though they desire to collaborate. To address this issue, recent works have proposed solutions using Secure Multi-party Computation (MPC), which train on the decentralized data in a way that the participants could learn nothing from each other beyond the final trained model. We design and implement several MPC-friendly ML primitives, including class weight adjustment and parallelizable approximation of activation function. In addition, we develop the solution as an extension to TF Encrypted (Dahl et al., 2018), enabling us to quickly experiment with enhancements of both machine learning techniques and cryptographic protocols while leveraging the advantages of TensorFlow’s optimizations. Our implementation compares favorably with state-ofthe-art methods, winning first place in Track IV of the iDASH2019 secure genome analysis competition. 1

The stream ciphers are a set of symmetric algorithms that receive a secret message as a sequence of bits and perform an encryption operation using a complex function based on key and IV, and combine xor with bit sequences. One of the goals in designing stream ciphers is to obtain a minimum period, which is one of the primary functions of using T-functions. On the other hand, the use of jump index in the design of LFSRs has made the analysis of LFSR-based stream ciphers more complicated. In this paper, we have tried to introduce a new method for designing the initial functions of stream ciphers with the use of T-functions concepts and the use of jump indexes, that has the maximum period. This method is resist side-channel attacks and can be efficiently implemented in hardware for a wide range of target processes and platforms.

We introduce a natural generalization of two-source non-malleable extractors (Cheragachi and Guruswami, TCC 2014) called as \textit{multi-source non-malleable extractors}. Multi-source non-malleable extractors are special independent source extractors which satisfy an additional non-malleability property. This property requires that the output of the extractor remains close to uniform even conditioned on its output generated by tampering {\it several sources together}. We formally define this primitive, give a construction that is secure against a wide class of tampering functions, and provide several applications. More specifically, we obtain the following results: \begin{itemize} \item For any $s \geq 2$, we give a construction of a $s$-source non-malleable extractor for min-entropy $\Omega(n)$ and error $2^{-n^{\Omega(1)}}$ against {\it cover-free tampering family}. Roughly, cover-free tampering requires that for every source, there exists another source that is not tampered together with this source. Cover-free tampering is a strict superset of many natural tampering function families such as individual tampering and disjoint tampering functions (where $[s]$ is partitioned into several sets and each set is tampered independently). \item We show how to efficiently preimage sample given the output of (a variant of) our extractor and this immediately gives rise to a $s$-state non-malleable code secure against cover-free tampering family (via a generalization of the result by Cheragachi and Guruswami). \item We show that a modification of our construction of multi-source non-malleable extractors gives a $t$-out-of-$n$ non-malleable secret sharing scheme (Goyal and Kumar, STOC 2018) against $t$-cover-free tampering. Informally, $t$-cover-free tampering requires that every share is tampered together with at most $t-2$ other shares and includes disjoint tampering as a special case. This is the first construction of $t$-out-of-$n$ non-malleable secret sharing for every $t,n$ with security against a strict super class of disjoint tampering. \item We show that a stronger notion of $s$-source non-malleable extractor that is multi-tamperable against disjoint tampering functions gives a single round network extractor protocol (Kalai et al., FOCS 2008) with attractive features. Plugging in with a new construction of multi-tamperable, 2-source non-malleable extractors provided in our work, we get a network extractor protocol for min-entropy $\Omega(n)$ that tolerates an {\it optimum} number ($t = p-2$) of faulty processors and extracts random bits for {\it every} honest processor. The prior network extractor protocols could only tolerate $t = \Omega(p)$ faulty processors and failed to extract uniform random bits for a fraction of the honest processors. \end{itemize}

Privacy is a critical issue for blockchains and decentralized applications. Currently, there are several blockchains featured for privacy. For example, Zcash uses zk-SNARKs to hide the transaction data, where addresses and amounts are not visible to the public. The zk-SNARK technology is secure and has been running stably in Zcash for several years. However, it cannot support smart contracts, which means people are not able to build decentralized applications on Zcash.

To solve this problem, two protocols, Quorum ZSL and Nightfall, have tried to implement zk-SNARKs through smart contracts. In this way, decentralized applications with privacy features are enabled by these protocols on the blockchain. However, experiments on the Ethereum Virtual Machine show that these protocols cost a lot of time and gas for running, meaning they are not suitable for everyday use.

In this paper, we propose an efficient privacy protocol using zk-SNARKs based on smart contracts. It helps to make several decentralized applications, like digital assets, stable coins, and payments, confidential. The protocol balances the trade-off between the gas cost of smart contracts and the computational complexity of zk-SNARK proof generation. Moreover, it uses the In-band Secret Distribution to store private information on the blockchain. The gas cost for a confidential transaction is only about 1M, and the transaction generation takes less than 6 seconds on a regular computer.

Efficiently supporting inference tasks of deep neural network (DNN) on the resource-constrained Internet of Things (IoT) devices has been an outstanding challenge for emerging smart systems. To mitigate the burden on IoT devices, one prevalent solution is to outsource DNN inference tasks to the public cloud. However, this type of ``cloud-backed" solutions can cause privacy breach since the outsourced data may contain sensitive information. For privacy protection, the research community has resorted to advanced cryptographic primitives to support DNN inference over encrypted data. Nevertheless, these attempts are limited by the real-time performance due to the heavy IoT computational overhead brought by cryptographic primitives.

In this paper, we proposed an edge-computing-assisted framework to boost the efficiency of DNN inference tasks on IoT devices, which also protects the privacy of IoT data to be outsourced. In our framework, the most time-consuming DNN layers are outsourced to edge computing devices. The IoT device only processes compute-efficient layers and fast encryption/decryption. Thorough security analysis and numerical analysis are carried out to show the security and efficiency of the proposed framework. Our analysis results indicate a 99%+ outsourcing rate of DNN operations for IoT devices. Experiments on AlexNet show that our scheme can speed up DNN inference for 40.6X with a 96.2% energy saving for IoT devices.

Functional encryption (FE) combiners allow one to combine many candidates for a functional encryption scheme, possibly based on different computational assumptions, into another functional encryption candidate with the guarantee that the resulting candidate is secure as long as at least one of the original candidates is secure. The fundamental question in this area is whether FE combiners exist. There have been a series of works (Ananth et. al. (CRYPTO '16), Ananth-Jain-Sahai (EUROCRYPT '17), Ananth et. al (TCC '19)) on constructing FE combiners from various assumptions.

We give the first unconditional construction of combiners for functional encryption, resolving this question completely. Our construction immediately implies an unconditional universal functional encryption scheme, an FE scheme that is secure if such an FE scheme exists. Previously such results either relied on algebraic assumptions or required subexponential security assumptions.

Statistical Multi-Party Computation (MPC) protocols based on two-party Oblivious Transfer (OT) have one severe drawback: the adversary can abort the protocol without repercussions. (Ishai, Ostrovsky, and Zikas, Crypto 14) introduced the notion of Identifiable Abort (IA). We extend the work of (Fitzi, Garay, Maurer, and Ostrovsky, Crypto 01) and investigate, under which conditions n-party MPC can be constructed from smaller functionalities in the setting of IA. Previous work already contains an impossibility result for two-party functionalities (Ishai, Strovski, and Seyalioglu, TCC 12) and a universal n-party setup (Ishai, Ostrovsky, and Zikas, Crypto 14).

We thus investigate setup functionalities of size between 3 and (n-1). In this paper we give novel upper bounds for the sizes of functionalities needed for IA. In particular, we find out, that it is possible to construct n-party MPC with IA from an (n-1)-party setup and a broadcast, if at least 3 parties are honest. We achieve our result by using a new and innovative technique called conflict graph and its complementary association graph, which uses a broadcast channel to model the knowledge of honest parties regarding the identity of malicious parties.

Sigma-Protocols form a well-understood basis for plug-and-play secure algorithmics. Bulletproofs (Bünz et al., SP 2018) have been introduced as a ``drop-in'' for Sigma-Protocols in some important applications; notably, zero-knowledge (ZK) for arithmetic circuits and range proofs, each with logarithmic communication instead of linear.

At the heart of Bulletproofs is an ingenious, logarithmic-size proof of knowledge (PoK), denoted BP, showing that a compact Pedersen commitment to a long vector satisfies a quadratic equation (``an inner product relation''). However, applications, like those mentioned, meet with technical difficulties: (1) BPs are not ZK and (2) protocol theory requires ``reinvention'' with the quadratic constraint proved as its ``pivot.'' This leads to practical, yet complex ZK protocols where applying natural plug-and-play intuition appears hard.

Our approach is radically different. We reconcile Bulletproofs with the theory of Sigma-Protocols such that (a) applications can follow established protocol theory, thereby dispensing with the need for ``reinventing'' it, while (b) enjoying exactly the same communication reduction. We do this by giving a precise perspective on BPs as a significant strengthening of the power of Sigma-protocols. We believe this novel perspective is rather useful for practical design.

Our program combines two essential components. First, we isolate a natural Sigma-Protocol as alternative pivot that directly yields ZK proofs for arbitrary linear statements, while deploying suitable BPs to compress communication. We also develop convenient utility enhancements of the pivot. Second, to enable ZK proofs of nonlinear statements, we integrate the pivot as a blackbox with a novel variation on -- hitherto largely overlooked -- arithmetic secret sharing based techniques for Sigma-Protocols (ICITS 2012); this linearizes ``all nonlinear statements'' using the fact that arbitrary linear ones can be proved. This yields simple circuit ZK with logarithmic communication. Similarly for range proofs, which are now trivial. Our results are based on either of two assumptions, the Discrete Logarithm assumption, or an assumption derived from the Strong-RSA assumption.

In this paper, we use genus theory to analyze the hardness of the decisional Diffie--Hellman problem (DDH) for ideal class groups of imaginary quadratic orders, acting on sets of elliptic curves through isogenies; such actions are used in the Couveignes--Rostovtsev--Stolbunov protocol and in CSIDH. Concretely, genus theory equips every imaginary quadratic order $\mathcal{O}$ with a set of assigned characters $\chi : \mathop{cl}(\mathcal{O}) \to \{ \pm 1\}$, and for each such character and every secret ideal class $[\mathfrak{a}]$ connecting two public elliptic curves $E$ and $E' = [\mathfrak{a}] \star E$, we show how to compute $\chi([\mathfrak{a}])$ given only $E$ and $E'$, i.e.\ without knowledge of $[\mathfrak{a}]$. In practice, this breaks DDH as soon as the class number is even, which is true for a density $1$ subset of all imaginary quadratic orders. For instance, our attack works very efficiently for all supersingular elliptic curves over $\F_p$ with $p \equiv 1 \bmod 4$. Our method relies on computing Tate pairings and walking down isogeny volcanoes.

NTS-KEM is one of the 17 post-quantum public-key encryption (PKE) and key establishment schemes remaining in contention for standardization by NIST. It is a code-based cryptosystem that starts with a combination of the (weakly secure) McEliece and Niederreiter PKE schemes and applies a variant of the Fujisaki-Okamoto (Journal of Cryptology 2013) or Dent (IMACC 2003) transforms to build an IND-CCA secure key encapsulation mechanism (KEM) in the classical random oracle model (ROM). Such generic KEM transformations were also proven to be secure in the quantum ROM (QROM) by Hofheinz et. al. (TCC 2017), Jiang et. al. (Crypto 2018) and Saito et. al. (Eurocrypt 2018). However, the NTS-KEM specification has some peculiarities which means that these security proofs do not directly apply to it.

This paper identifies a subtle issue in the IND-CCA security proof of NTS-KEM in the classical ROM, as detailed in its initial NIST second round submission, and proposes some slight modifications to its specification which not only fixes this issue but also makes it IND-CCA secure in the QROM. We use the techniques of Jiang et. al. (Crypto 2018) and Saito et. al. (Eurocrypt 2018) to establish our IND-CCA security reduction for the modified version of NTS-KEM, achieving a loss in tightness of degree 2; a quadratic loss of this type is believed to be generally unavoidable for reductions in the QROM (Jiang at. al., ePrint 2019/494). Following our results, the NTS-KEM team has accepted our proposed changes by including them in an update to their second round submission to the NIST process.