International Association
for Cryptologic Research

In this paper, we propose coded Merkle tree (CMT), a novel hash accumulator that offers a constant-cost protection against data availability attacks in blockchains, even if the majority of the network nodes are malicious. A CMT is constructed using a family of sparse erasure codes on each layer, and is recovered by iteratively applying a peeling-decoding technique that enables a compact proof for data availability attack on any layer. Our algorithm enables any node to verify the full availability of any data block generated by the system by just downloading a $\Theta(1)$ byte block hash commitment and randomly sampling $\Theta(\log b)$ bytes, where $b$ is the size of the data block. With the help of only one honest node in the system, our method also allows any node to verify any tampering of the coded Merkle tree by just downloading $\Theta(\log b)$ bytes. We provide a modular library for CMT in {\sf Rust} and {\sf Python} and demonstrate its efficacy inside the {\sf Parity Bitcoin} client.

The fast developing Industrial Internet of Things (IIoT) technologies provide a promising opportunity to build large-scale systems to connect numerous heterogeneous devices into the Internet. Most existing IIoT infrastructures are based on a centralized architecture, which is easier for management but cannot effectively support immutable and verifiable services among multiple parties. Blockchain technology provides many desired features for large-scale IIoT infrastructures, such as decentralization, trustworthiness, trackability, and immutability. This paper presents a blockchain-based IIoT architecture to support immutable and verifiable services. However, when applying blockchain technology to the IIoT infrastructure, the required storage space posts a grant challenge to resource-constrained IIoT infrastructures. To address the storage issue, this paper proposes a hierarchical blockchain storage structure, \textit{ChainSplitter}. Specially, the proposed architecture features a hierarchical storage structure where the majority of the blockchain is stored in the clouds, while the most recent blocks are stored in the overlay network of the individual IIoT networks. The proposed architecture seamlessly binds local IIoT networks, the blockchain overlay network, and the cloud infrastructure together through two connectors, the \textit{blockchain connector} and the \textit{cloud connector}, to construct the hierarchical blockchain storage. The blockchain connector in the overlay network builds blocks in blockchain from data generated in IIoT networks, and the cloud connector resolves the blockchain synchronization issues between the overlay network and the clouds. We also provide a case study to show the efficiency of the proposed hierarchical blockchain storage in a practical Industrial IoT case.

Since the mid 2000s, asymptotically-good strongly-multiplicative linear secret sharing schemes over a fixed finite field have turned out as a central theoretical primitive in numerous constant-communication-rate results in multi-party cryptographic scenarios, and, surprisingly, in two-party cryptography as well.

Known constructions of this most powerful class of arithmetic secret sharing schemes all rely heavily on algebraic geometry (AG), i.e., on dedicated AG codes based on asymptotically good towers of algebraic function fields defined over finite fields. It is a well-known open question since the first (explicit) constructions of such schemes appeared in CRYPTO 2006 whether the use of ``heavy machinery'' can be avoided here. I.e., the question is whether the mere existence of such schemes can also be proved by ``elementary'' techniques only (say, from classical algebraic coding theory), even disregarding effective construction. So far, there is no progress.

In this paper we show the theoretical result that, (1) {\em no matter whether this open question has an affirmative answer or not}, these schemes {\em can} be constructed explicitly by {\em elementary algorithms} defined in terms of basic algebraic coding theory. This pertains to all relevant operations associated to such schemes, including, notably, the generation of an instance for a given number of players $n$, as well as error correction in the presence of corrupt shares. Moreover, we show that (2) the algorithms are {\em quasi-linear time} (in $n$); this is several asymptotically significantly more efficient than known constructions. That said, the {\em analysis} of the mere termination of these algorithms {\em does} still rely on algebraic geometry, in that it requires ``blackbox application'' of suitable {\em existence} results for these schemes.

Our method employs a nontrivial, novel adaptation of a classical (and ubiquitous) paradigm from coding theory that enables transformation of {\em existence} results on asymptotically good codes into {\em explicit construction} of such codes via {\em concatenation}, at some constant loss in parameters achieved. In a nutshell, our generating idea is to combine a cascade of explicit but ``asymptotically-bad-yet-good-enough schemes'' with an asymptotically good one in such a judicious way that the latter can be selected with exponentially small number of players in that of the compound scheme. This opens the door to efficient, elementary exhaustive search.

In order to make this work, we overcome a number of nontrivial technical hurdles. Our main handles include a novel application of the recently introduced notion of Reverse Multiplication-Friendly Embeddings (RMFE) from CRYPTO 2018, as well as a novel application of a natural variant in arithmetic secret sharing from EUROCRYPT 2008.

We consider the problem of securely generating the keys of the Paillier crypto system [11] with (t, n) threshold decryption, without a trusted dealer. Nishide and Sakurai [10] describe a solution, secure in the malicious model. We use their ideas to make a simpler solution for the semi-honest model, and further introduce a few optimisations. We implement the secure key generation protocol on a single computer, and consider its performance.

Blaze, Bleumer and Strauss introduced the notion of proxy re-encryption (PRE), which enables a semi-trusted proxy to transform ciphertexts under Alice's public key into ciphertexts under Bob's public key. The important property to note here is, the proxy should not learn anything about the plaintext encrypted. In 2009, Weng et al. introduced the concept of conditional proxy re-encryption (CPRE), which permits the proxy to re-encrypt only ciphertexts satisfying a condition specified by Alice into a ciphertext for Bob. CPRE enables fine-grained delegation of decryption rights useful in many practical scenarios, such as blockchain-enabled distributed cloud storage and encrypted email forwarding. Several CPRE schemes exist in the literature based on costly bilinear pairing operation in the random oracle model. We propose the first construction of an efficient CPRE scheme without pairing, satisfying chosen ciphertext security under the computational Diffie Hellman (CDH) assumption and its variant in the random oracle model.

A {\em blackbox} secret sharing (BBSS) scheme works in exactly the same way for all finite Abelian groups $G$; it can be instantiated for any such group $G$ and {\em only} black-box access to its group operations and to random group elements is required. A secret is a single group element and each of the $n$ players' shares is a vector of such elements. Share-computation and secret-reconstruction is by integer linear combinations. These do not depend on $G$, and neither do the privacy and reconstruction parameters $t,r$. This classical, fundamental primitive was introduced by Desmedt and Frankel (CRYPTO 1989) in their context of ``threshold cryptography.'' The expansion factor is the total number of group elements in a full sharing divided by $n$. For threshold BBSS with $t$-privacy ($1\leq t \leq n-1$), $t+1$-reconstruction and arbitrary $n$, constructions with minimal expansion $O(\log n)$ exist (CRYPTO 2002, 2005).

These results are firmly rooted in number theory; each makes (different) judicious choices of orders in number fields admitting a vector of elements of very large length (in the number field degree) whose corresponding Vandermonde-determinant is sufficiently controlled so as to enable BBSS by a suitable adaptation of Shamir's scheme. Alternative approaches generally lead to very large expansion. The state of the art of BBSS has not changed for the last 15 years.

Our contributions are two-fold. (1) We introduce a novel, nontrivial, effective construction of BBSS based on {\em coding theory} instead of number theory. For threshold-BBSS we also achieve minimal expansion factor $O(\log n)$. (2) Our method is more versatile. Namely, we show, for the first time, BBSS that is {\em near-threshold}, i.e., $r-t$ is an arbitrarily small constant fraction of $n$, {\em and} that has expansion factor~$O(1)$, i.e., individual share-vectors of {\em constant} length (``asymptotically expansionless''). Threshold can be concentrated essentially freely across full range. We also show expansion is minimal for near-threshold and that such BBSS cannot be attained by previous methods.

Our general construction is based on a well-known mathematical principle, the local-global principle. More precisely, we first construct BBSS over local rings through either Reed-Solomon or algebraic geometry codes. We then ``glue'' these schemes together in a dedicated manner to obtain a global secret sharing scheme, i.e., defined over the integers, which, as we finally prove using novel insights, has the desired BBSS properties. Though our main purpose here is advancing BBSS for its own sake, we also briefly address possible protocol applications.

Emerging non-volatile memories (NVMs) have been considered promising alternatives to DRAM for future main memory design. Among the NVMs, Phase-Change Memory (PCM) can serve as a good substitute due to its low standby power, high density, and good scalability. However, PCM material also induces security design challenges mainly due to its interior non-volatility. Designing the memory system necessitates considering the challenges which may open the backdoor for attackers. A threat model can help to identify security vulnerabilities in design processes. It is all about finding the security problems, and therefore it should be done early in the design and adoption of manufacture. To our knowledge, this paper is the first attempt to thoroughly discuss the potential threat models for the PCM memory, which can provide a good reference for designing the new generation of PCM. Meanwhile, this paper gives security advice and potential security solutions to design a secure PCM to protect against these potential threats.

Encrypted multi-maps (EMMs) enable clients to outsource the storage of a multi-map to a potentially untrusted server while maintaining the ability to perform operations in a privacy-preserving manner. EMMs are an important primitive as they are an integral building block for many practical applications such as searchable encryption and encrypted databases. In this work, we formally examine the tradeoffs between privacy and efficiency for EMMs.

Currently, all known dynamic EMMs with constant overhead reveal if two operations are performed on the same key or not; that is, they leak the $\mathit{global\ key\text{-}equality\ pattern}$. In our main result, we present strong evidence that the leakage of the global key-equality pattern is inherent for any dynamic EMM construction with $O(1)$ efficiency. In particular, we consider the slightly smaller leakage of $\mathit{decoupled\ key\text{-}equality\ pattern}$ where leakage of key-equality between update and query operations is decoupled and the adversary only learns whether two operations of the $\mathit{same\ type}$ are performed on the same key or not. We show that any EMM with at most decoupled key-equality pattern leakage incurs $\Omega(\log n)$ overhead in the $\mathit{leakage\ cell\ probe\ model}$. This is tight as there exist ORAM-based constructions of EMMs with logarithmic slowdown that leak no more than the decoupled key-equality pattern (and actually, much less). Furthermore, we present stronger lower bounds that encrypted multi-maps leaking at most the decoupled key-equality pattern but are able to perform one of either the update or query operations in the plaintext still require $\Omega(\log n)$ overhead. Finally, we extend our lower bounds to show that dynamic, $\mathit{response\text{-}hiding}$ searchable encryption schemes must also incur $\Omega(\log n)$ overhead even when one of either the document updates or searches may be performed in the plaintext.

Robust secret sharing is a strengthening of standard secret sharing that allows the shared secret to be recovered even if some of the shares being used in the reconstruction have been adversarially modified. In this work, we study the setting where out of all the $n$ shares, the adversary is allowed to adaptively corrupt and modify $t$ shares, where $n = 2t+1$. Further, we deal with \textit{rushing} adversaries, meaning that the adversary is allowed to see the honest parties' shares before modifying its own shares.

It is known that when $n = 2t+1$, to share a secret of length $m$ bits and recover it with error less than $2^{-\sec}$, shares of size at least $m+\sec$ bits are needed. Recently, Bishop, Pastro, Rajaraman, and Wichs (EUROCRYPT 2016) constructed a robust secret sharing scheme with shares of size $m + O(\sec\cdot\textrm{polylog}(n,m,\sec))$ bits that is secure in this setting against non-rushing adversaries. Later, Fehr and Yuan (EUROCRYPT 2019) constructed a scheme that is secure against rushing adversaries, but has shares of size $m + O(\sec\cdot n^{\epsilon}\cdot \textrm{polylog}(n,m,\sec))$ bits for an arbitrary constant $\epsilon > 0$. They also showed a variant of their construction with share size $m + O(\sec\cdot\textrm{polylog}(n,m,\sec))$ bits, but with super-polynomial reconstruction time. We present a robust secret sharing scheme that is secure against rushing adversaries, has shares of size $m+O(\sec \log{n} (\log{n}+\log{m}))$ bits, and has polynomial-time sharing and reconstruction. Central to our construction is a polynomial-time algorithm for a problem on semi-random graphs that arises naturally in the paradigm of local authentication of shares used by us and in the aforementioned work.

We suggest new applications of protocols of Non-commutative cryptography defined in terms of subsemigroups of Affine Cremona Semigroups over finite commutative rings and their homomorphic images to the constructions of possible instruments of Post Quantum Cryptography. This approach allows to define cryptosystems which are not public keys. When extended protocol is finished correspondents have the collision multivariate transformation on affine space K ^n or variety (K*)^n where K is a finite commutative ring and K* is nontrivial multiplicative subgroup of K . The security of such protocol rests on the complexity of word problem to decompose element of Affine Cremona Semigroup given in its standard form into composition of given generators. The collision map can serve for the safe delivery of several bijective multivariate maps F_i (generators) on K^n (or (K*)^n) from one correspondent to another. So asymmetric cryptosystem with nonpublic multivariate generators where one side (Alice) knows inverses of F_i but other does not have such a knowledge is possible. We consider the usage of single protocol or combinations of two protocols with platforms of different nature. The usage of two protocols with the collision spaces K^n and (K*)^n allows safe delivery of two sets of generators of different nature. In terms of such sets we define an asymmetric encryption scheme with the plainspace (K*)^n, cipherspace K^n and multivariate non-bijective encryption map of unbounded degree O(n) and polynomial density on K^n with injective restriction on (K*)^n. Algebraic cryptanalysis faces the problem to interpolate a natural decryption transformation which is not a map of polynomial density.

Functional encryption is a generalization of public-key encryption in which possessing a secret functional key allows one to learn a function of what the ciphertext is encrypting. This paper introduces the first fully-fledged open source cryptographic libraries for functional encryption. It also presents how functional encryption can be used to build efficient privacy-enhanced machine learning models and it provides an implementation of three prediction services that can be applied on the encrypted data. Finally, the paper discusses the advantages and disadvantages of the alternative approach for building privacy-enhanced machine learning models by using homomorphic encryption.

Communication across distributed systems, where each system runs its own consensus, is a problem previously studied only within a single trust domain (e.g., a datacenter). With the appearance of distributed ledgers or blockchains, numerous protocols requiring robustness against adversarial behavior have emerged. Cross-chain communication thereby plays a fundamental role in cryptocurrency exchanges, sharding, as well as the bootstrapping and migration of distributed ledgers. Unfortunately, existing proposals are designed ad-hoc for specific use-cases, making it hard to gain confidence on their correctness and to use them as building blocks for new systems.

In this paper, we provide the first systematic exposition of protocols for cross-chain communication. Through formalization of the underlying research question, which reduces to the fair exchange problem, we identify threat and network model assumptions, necessary for designing correct cross-chain communication protocols. We overview main applications, derive a classification and provide a comparative analysis of existing approaches. Further, we survey and classify techniques for verifying state cross-chain and mechanisms for constructing locks.

We study a class of MACs, which we call corruption detectable MAC, that is able to not only check the integrity of the whole message, but also detect a part of the message that is corrupted. It can be seen as an application of the classical Combinatorial Group Testing (CGT) to message authentication. However, previous work on this application has inherent limitation in communication. We present a novel approach to combine CGT and a class of linear MACs (XOR-MAC) that enables to break this limit. Our proposal, XOR-GTM, has a significantly smaller communication cost than any of the previous ones, keeping the same corruption detection capability. Our numerical examples for storage application show a reduction of communication by a factor of around 15 to 70 compared with previous schemes. XOR-GTM is parallelizable and is as efficient as standard MACs. We prove that XOR-GTM is provably secure under the standard pseudorandomness assumptions.

Distributed hash tables (DHT) are a fundamental building block in the design of distributed systems with applications ranging from content distribution networks to off-chain storage networks for blockchains and smart contracts. When DHTs are used to store sensitive information, system designers use end-to-end encryption in order to guarantee the confidentiality of their data. A prominent example is Ethereum's off-chain network Swarm.

In this work, we initiate the study of end-to-end encryption in DHTs and the many systems they support. We introduce the notion of an encrypted DHT and provide simulation-based security definitions that capture the security properties one would desire from such a system. Using our definitions, we then analyze the security of a standard approach to storing encrypted data in DHTs. Interestingly, we show that this "standard scheme" leaks information probabilistically, where the probability is a function of how well the underlying DHT load balances its data. We also show that, in order to be securely used with the standard scheme, a DHT needs to satisfy a form of equivocation with respect to its overlay. To show that these properties are indeed achievable in practice, we study the balancing properties of the Chord DHT---arguably the most influential DHT---and show that it is equivocable with respect to its overlay in the random oracle model. Finally, we consider the problem of encrypted DHTs in the context of transient networks, where nodes are allowed to leave and join.

Due to their impressive advantages, Radio Frequency IDentification (RFID) systems are ubiquitously found in various novel applications. These applications are usually in need of quick and accurate authentication or identification. In many cases, it has been shown that if such systems are not properly designed, an adversary can cause security and privacy concerns for end-users. In order to deal with these concerns, impressive endeavors have been made which have resulted in various RFID authentications being proposed. In this study, we analyze three lightweight RFID authentication protocols proposed in Wireless Personal Communications (2014), Computers & Security (2015) and Wireless Networks (2016). We show that none of the studied protocols provides the desired security and privacy required by the end-users. We present various security and privacy attacks such as secret parameter reveal, impersonation, DoS, traceability, and forward traceability against the studied protocols. Our attacks are mounted in the Ouafi–Phan RFID formal privacy model which is a modified version of the well-known Juels–Weis privacy model.

Evolving secret-sharing schemes, introduced by Komargodski, Naor, and Yogev (TCC 2016b), are secret-sharing schemes in which there is no a-priory upper bound on the number of parties that will participate. The parties arrive one by one and when a party arrives the dealer gives it a share; the dealer cannot update this share when other parties arrive. Motivated by the fact that when the number of parties is known, ramp secret-sharing schemes are more efficient than threshold secret-sharing schemes, we study evolving ramp secret-sharing schemes. Specifically, we study evolving $(b(j),g(j))$-ramp secret-sharing schemes, where $g,b: N \to N$ are non-decreasing functions. In such schemes, any set of parties that for some $j$ contains $g(j)$ parties from the first parties that arrive can reconstruct the secret, and any set such that for every $j$ contains less than $b(j)$ parties from the first parties that arrive cannot learn any information about the secret.

We focus on the case that the gap is small, namely $g(i)-g(i)=t^{\beta}$ for $0<\beta<1$. We show that there is an evolving ramp secret-sharing scheme with gap $t^{\beta}$, in which the share size of the $j$-th party is $\tilde{O}(j^{4-\frac{1}{\log^2 {1/\beta}}})$. Furthermore, we show that our construction results in much better share size for fixed values of $\beta$, i.e., there is an evolving ramp secret-sharing scheme with gap $\sqrt{t}$, in which the share size of the $j$-th party is $\tilde{O}(j)$. Our construction should be compared to the best known evolving $g(j)$-threshold secret-sharing schemes (i.e., when $b(j)=g(j)-1$) in which the share size of the $j$-th party is $\tilde{O}(j^4)$. Thus, our construction offers a significant improvement for every constant $\beta$, showing that allowing a gap between the sizes of the authorized and unauthorized sets can reduce the share size.

In addition, we present an evolving $(k/2,k)$-ramp secret-sharing scheme for a constant $k$ (which can be very big), where any set of parties of size at least $k$ can reconstruct the secret and any set of parties of size at most $k/2$ cannot learn any information about the secret. The share size of the $j$-th party in our construction is $O(\log k\log j)$. This is an improvement over the best known evolving $k$-threshold secret-sharing schemes in which the share size of the $j$-th party is $O(k\log j)$.

A symmetric searchable encryption (SSE) scheme allows a client (data owner) to search on encrypted data outsourced to an untrusted cloud server. The search may either be a single keyword search or a complex query search like conjunctive or Boolean keyword search. Information leakage is quite high for dynamic SSE, where data might be updated. It has been proven that to avoid this information leakage an SSE scheme with dynamic data must be forward private. A dynamic SSE scheme is said to be forward private, if adding a keyword-document pair does not reveal any information about the previous search result with that keyword.

In SSE setting, the data owner has very low computation and storage power. In this setting, though some schemes achieve forward privacy with honest-but-curious cloud, it becomes difficult to achieve forward privacy when the server is malicious, meaning that it can alter the data. Verifiable dynamic SSE requires the server to give a proof of the result of the search query. The data owner can verify this proof efficiently. In this paper, we have proposed a generic publicly verifiable dynamic SSE (DSSE) scheme that makes any forward private DSSE scheme verifiable without losing forward privacy. The proposed scheme does not require any extra storage at owner-side and requires minimal computational cost as well for the owner. Moreover, we have compared our scheme with the existing results and show that our scheme is practical.

Algorithms for solving the Bounded Distance Decoding problem (BDD) are used for estimating the security of lattice-based cryptographic primitives, since these algorithms can be employed to solve variants of the Learning with Errors problem (LWE). In certain parameter regimes where the target vector is small and/or sparse, batches of BDD instances emerge from a combinatorial approach where several components of the target vector are guessed before decoding. In this work we explore trade-offs in solving ``Batch-BDD'', and apply our techniques to the small-secret Learning with Errors problem. We compare our techniques to previous works which solve batches of BDD instances, such as the hybrid lattice-reduction and meet-in-the-middle attack. Our results are a mixed bag. We show that, in the ``enumeration setting'' and with BKZ reduction, our techniques outperform a variant of the hybrid attack which does not consider time-memory trade-offs in the guessing phase for certain Round5 (17-bits out of 466), Round5-IoT (19-bits out of 240), and NTRU LPrime (23-bits out of 385) parameter sets. On the other hand, our techniques do not outperform the Hybrid Attack under standard, albeit unrealistic, assumptions. Finally, as expected, our techniques do not improve on previous works in the ``sieving setting'' (under standard assumptions) where combinatorial attacks in general do not perform well.

CSIDH, presented at Asiacrypt 2018, is a post-quantum key establishment protocol based on constructing isogenies between supersingular elliptic curves. Several recent works give constant-time implementations of CSIDH along with some optimizations of the ideal-class group action evaluation algorithm, including the SIMBA technique of Meyer, Campos, and Reith and the two-point method of Onuki, Aikawa, Yamazaki, and Takagi. A recent work of Cervantes-Vázquez, Chenu, Chi-Domínguez, De Feo, Rodríguez-Henríquez, and Smith details a number of improvements to the works of Meyer et al. and Onuki et al. Several of these optimizations---in particular, the choice of ordering of the primes, the choice of SIMBA partition and strategies, and the choice of bound vector which defines the secret keyspace---have been made in an ad hoc fashion, and so while they yield performance improvements it has not been clear whether these choices could be improved upon, or how to do so. In this work we present a framework for improving these optimizations using (respectively) linear programming, dynamic programming, and convex programming techniques. Our framework is applicable to any CSIDH security level, to all currently-proposed paradigms for computing the class group action, and to any choice of model for the underlying curves. Using our framework---along with another new optimization technique---we find improved parameter sets for the two major methods of computing the group action: in the case of the implementation of Meyer et al. we obtain a 16.85% speedup without applying the further optimizations proposed by Cervantes-Vázquez et al., while for that of Cervantes-Vázquez et al. under the two-point method we obtain a speedup of 5.08%, giving the fastest constant-time implementation of CSIDH to date.

Structure-preserving signatures on equivalence classes (SPS-EQ) introduced at ASIACRYPT 2014 are a variant of SPS where a message is considered as a projective equivalence class, and a new representative of the same class can be obtained by multiplying a vector by a scalar. Given a message and corresponding signature, anyone can produce an updated and randomized signature on an arbitrary representative from the same equivalence class. SPS-EQ have proven to be a very versatile building block for many cryptographic applications.

In this paper, we present the first EUF-CMA secure SPS-EQ scheme under standard assumptions. So far only constructions in the generic group model are known. One recent candidate under standard assumptions are the weakly secure equivalence class signatures by Fuchsbauer and Gay (PKC'18), a variant of SPS-EQ satisfying only a weaker unforgeability and adaption notion. Fuchsbauer and Gay show that this weaker unforgeability notion is sufficient for many known applications of SPS-EQ. Unfortunately, the weaker adaption notion is only proper for a semi-honest (passive) model and as we show in this paper, makes their scheme unusable in the current models for almost all of their advertised applications of SPS-EQ from the literature.

We then present a new EUF-CMA secure SPS-EQ scheme with a tight security reduction under the SXDH assumption providing the notion of perfect adaption (under malicious keys). To achieve the strongest notion of perfect adaption under malicious keys, we require a common reference string (CRS), which seems inherent for constructions under standard assumptions. However, for most known applications of SPS-EQ we do not require a trusted CRS (as the CRS can be generated by the signer during key generation). Technically, our construction is inspired by a recent work of Gay et al. (EUROCRYPT'18), who construct a tightly secure message authentication code and translate it to an SPS scheme adapting techniques due to Bellare and Goldwasser (CRYPTO'89).