International Association
for Cryptologic Research

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.

Vector commitments with subvector openings (SVC) [Lai-Malavolta and Boneh-Bunz-Fisch, CRYPTO'19] allow one to open a committed vector at a set of positions with an opening of size independent of both the vector's length and the number of opened positions.

We propose a new SVC construction in groups of unknown order that, similarly to that of Boneh et al. has constant-size public parameters, commitments and openings, but in addition enjoys new features. First, our SVC has incremental aggregation: one can merge openings in a succinct way an unbounded number of times. Thanks to incremental aggregation we obtain: faster generation of openings via preprocessing, and a method to generate openings in a distributed way. Second, we propose efficient arguments of knowledge of subvector openings for our SVC, which immediately yields a keyless proof of storage with compact proofs.

Finally, we introduce and contruct Verifiable Decentralized Storage (VDS), a cryptographic primitive that allows to check the integrity of a file stored by a network of nodes in a distributed and decentralized way.

After ratcheting attracted attention mostly due to practical real-world protocols, recently a line of work studied ratcheting as a primitive from a theoretic point of view. Literature in this line, pursuing the strongest security of ratcheting one can hope for, utilized for constructions strong, yet inefficient key-updatable primitives – based on hierarchical identity based encryption (HIBE). As none of these works formally justified utilizing these building blocks, we answer the yet open question whether their use is actually necessary.

We revisit these strong notions of ratcheted key exchange (RKE), and propose a more realistic (and slightly stronger) security definition. In this security definition, both the exposure of the communicating parties' local states and the adversary's ability to attack the executions' randomness are considered. While these two attacks were partially considered in previous work, we are the first to unify them cleanly in a natural game based notion.

Our definitions are based on the systematic RKE notion by Poettering and Rösler (CRYPTO 2018). Due to slight (but meaningful) changes to regard attacks against randomness, we are ultimately able to show that, in order to fulfill strong security for RKE, public key cryptography with (independently) updatable key pairs is a necessary building block. Surprisingly, this implication already holds for the simplest RKE variant (which was previously instantiated with only standard public key cryptography).

Our contributions are thus threefold: (1) We model optimally secure RKE under randomness manipulation to cover realistic attacks, (2) we (provably) extract the core primitive that is necessary to realize strongly secure RKE, and (3) our results indicate under which conditions this primitive is necessary for strongly secure ratcheting and which relaxations in security allow for constructions that only rely on standard public key cryptography.

We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials.

Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable code that is secure against tampering by bounded-size arithmetic circuits.

We show applications of our non-malleable code in constructing non-malleable secret sharing schemes that are robust against bounded-degree polynomial tampering. In fact our result is stronger: we can handle adversaries that can adaptively choose the polynomial tampering function based on initial leakage of a bounded number of shares.

Our results are derived from explicit constructions of seedless non-malleable extractors that can handle bounded-degree polynomial tampering functions. Prior to our work, no such result was known even for degree-2 (quadratic) polynomials.

We construct the first hierarchical identity-based encryption (HIBE) scheme with tight adaptive security in the multi-challenge setting, where adversaries are allowed to ask for ciphertexts for multiple adaptively chosen identities. Technically, we develop a novel technique that can tightly introduce randomness into user secret keys for hierarchical identities in the multi-challenge setting, which cannot be easily achieved by the existing techniques for tightly multi-challenge secure IBE.

In contrast to the previous constructions, the security of our scheme is independent of the number of user secret key queries and that of challenge ciphertext queries. We prove the tight security of our scheme based on the Matrix Decisional Diffie-Hellman Assumption, which is an abstraction of standard and simple decisional Diffie-Hellman assumptions, such as the k-Linear and SXDH assumptions.

Finally, we also extend our ideas to achieve tight chosen-ciphertext security and anonymity, respectively. These security notions for HIBE have not been tightly achieved in the multi-challenge setting before.

Physical Unclonable Functions (PUFs) provide means to generate chip individual keys, especially for low-cost applications such as the Internet of Things (IoT). They are intrinsically robust against reverse engineering, and more cost-effective than non-volatile memory (NVM). For several PUF primitives, countermeasures have been proposed to mitigate side-channel weaknesses. However, most mitigation techniques require substantial design effort and/or complexity overhead, which cannot be tolerated in low-cost IoT scenarios. In this paper, we first analyze side-channel vulnerabilities of the Loop PUF, an area efficient PUF implementation with a configurable delay path based on a single ring oscillator (RO). We provide side-channel analysis (SCA) results from power and electromagnetic measurements. We confirm that oscillation frequencies are easily observable and distinguishable, breaking the security of unprotected Loop PUF implementations. Second, we present a low-cost countermeasure based on temporal masking to thwart SCA that requires only one bit of randomness per PUF response bit. The randomness is extracted from the PUF itself creating a self-secured PUF. The concept is highly effective regarding security, low complexity, and low design constraints making it ideal for applications like IoT. Finally, we discuss trade-offs of side-channel resistance, reliability, and latency as well as the transfer of the countermeasure to other RO-based PUFs.

Double-base chains (DBCs) are widely used to speed up scalar multiplications on elliptic curves. We present three results of DBCs. First, we display a structure of the set containing all DBCs and propose an iterative algorithm to compute the number of DBCs for a positive integer. This is the first polynomial time algorithm to compute the number of DBCs for positive integers. Secondly, we present an asymptotic lower bound on average Hamming weights of DBCs $\frac{\log n}{8.25}$ for a positive integer $n$. This result answers an open question about the Hamming weights of DBCs. Thirdly, we propose a new algorithm to generate an optimal DBC for any positive integer. The time complexity of this algorithm is $\mathcal{O}\left(\left(\log n\right)^2 \log\log n\right)$ bit operations and the space complexity is $\mathcal{O}\left(\left(\log n\right)^{2}\right)$ bits of memory. This algorithm accelerates the recoding procedure by more than $6$ times compared to the state-of-the-art Bernstein, Chuengsatiansup, and Lange's work. The Hamming weights of optimal DBCs are over $60$\% smaller than those of NAFs. Scalar multiplication using our optimal DBC is about $13$\% faster than that using non-adjacent form on elliptic curves over large prime fields.

Recently, in IEEE Internet of Things Journal (DOI: 10.1109/JIOT.2019.2923373 ), Banerjee et al. proposed a lightweight anonymous authenticated key exchange scheme for IoT based on symmetric cryptography. In this paper, we show that the proposal can not resist impersonation attacks due to vulnerable mutual authentication, and give improvements.

We study the problem of $\textit{state machine replication}$ (SMR) -- the underlying problem addressed by blockchain protocols -- in the presence of a malicious adversary who can corrupt some fraction of the parties running the protocol. Existing protocols for this task assume either a $\textit{synchronous network}$ (where all messages are delivered within some known time $\Delta$) or an $\textit{asynchronous network}$ (where messages can be delayed arbitrarily). Although protocols for the latter case give seemingly stronger guarantees, in fact they are incomparable since they (inherently) tolerate a lower fraction of corrupted parties.

We design an SMR protocol that is network-agnostic in the following sense: if it is run in a synchronous network, it tolerates $t_s$ corrupted parties; if the network happens to be asynchronous it is resilient to $t_a\leq t_s$ faults. Our protocol achieves optimal tradeoffs between $t_s$ and $t_a$.

Zero-knowledge proof systems enable a prover to convince a verifier of the validity of a statement without revealing anything beyond that fact. The role of randomness in interactive proofs in general, and in zero-knowledge in particular, is well known. In particular, zero-knowledge with a deterministic verifier is impossible for non-trivial languages (outside of $\mathcal{BPP}$). Likewise, it was shown by Goldreich and Oren (Journal of Cryptology, 1994) that zero-knowledge with a deterministic prover is also impossible for non-trivial languages. However, their proof holds only for auxiliary-input zero knowledge and a malicious verifier.

In this paper, we initiate the study of the feasibility of zero-knowledge proof systems with a deterministic prover in settings not covered by the result of Goldreich and Oren. We prove the existence of deterministic-prover auxiliary-input honest-verifier zero-knowledge for any $\cal NP$ language, under standard assumptions. In addition, we show that any language with a hash proof system has a deterministic-prover honest-verifier statistical zero-knowledge proof, with an efficient prover. Finally, we show that in some cases, it is even possible to achieve deterministic-prover uniform zero-knowledge for a malicious verifier. Our contribution is primarily conceptual, and sheds light on the necessity of randomness in zero knowledge in settings where either the verifier is honest or there is no auxiliary input.