International Association
for Cryptologic Research

Non-committing encryption (NCE) was introduced by Canetti et al. (STOC '96). Informally, an encryption scheme is non-committing if it can generate a dummy ciphertext that is indistinguishable from a real one. The dummy ciphertext can be opened to any message later by producing a secret key and an encryption random coin which ``explain'' the ciphertext as an encryption of the message. Canetti et al. showed that NCE is a central tool to achieve multi-party computation protocols secure in the adaptive setting. An important measure of the efficiently of NCE is the ciphertext rate, that is the ciphertext length divided by the message length, and previous works studying NCE have focused on constructing NCE schemes with better ciphertext rates. We propose an NCE scheme satisfying the ciphertext rate $\mathcal{O}(\log \lambda)$ based on the decisional Diffie-Hellman (DDH) problem, where $\lambda$ is the security parameter. The proposed construction achieves the best ciphertext rate among existing constructions proposed in the plain model, that is, the model without using common reference strings. Previously to our work, an NCE scheme with the best ciphertext rate based on the DDH problem was the one proposed by Choi et al.~(ASIACRYPT '09) that has ciphertext rate $\mathcal{O}(\lambda)$. Our construction of NCE is similar in spirit to that of the recent construction of the trapdoor function proposed by Garg and Hajiabadi (CRYPTO '18).

Bitcoin and its underlying blockchain protocol have received recently significant attention in the context of building distributed systems as well as from the perspective of the foundations of the consensus problem. At the same time, the rapid development of quantum technologies brings the possibility of quantum computing devices from a theoretical concept to an emerging technology. Motivated by this, in this work we revisit the formal security of the core of the Bitcoin protocol, called the Bitcoin backbone, under the assumption that the adversary has access to a scalable quantum computer. We prove that the protocol's essential properties stand in the post-quantum setting assuming a suitably bounded Quantum adversary in the Quantum Random Oracle (QRO) model. Specifically, our results imply that security can be shown by bounding the quantum queries so that each quantum query is worth $O(p^{-1/2})$ classical ones and that the wait time for safe settlement is expanded by a multiplicative factor of $O(p^{-1/6})$, where $p$ is the probability of success of a single classical query to the protocol's underlying hash function.

The Lightning Network (LN) is a payment network running as a second layer on top of Bitcoin and other Blockchains. This paper presents the possibility of performing a balance lockdown in the LN due to misbehaving nodes associated to a given channel. We formalize and introduce a practical attack, minimizing the economic cost of the attack. We present results that validate our claims, and provide experimental results and potential countermeasures to handle the problem.

In November 2018, the HomomorphicEncryption.org consortium published the Homomorphic Encryption Security Standard. The Standard recommends several sets of Learning with Errors (LWE) parameters that can be selected by application developers to achieve a target security level \( \lambda \in \{128,192,256\} \). These parameter sets all involve a power-of-two dimension \( n \leq 2^{15} \), an error distribution of standard deviation \( \sigma \approx 3.19 \), and a secret whose coefficients are either chosen uniformly in \( Z_q \), chosen according to the error distribution, or chosen uniformly in \( \{ -1, 0, 1\} \). These parameter sets do not necessarily reflect implementation choices in the most commonly used homomorphic encryption libraries. For example, several libraries support dimensions that are not a power of two. Moreover, all known implementations for bootstrapping for the CKKS, BFV and BGV schemes use a sparse secret and a large ring dimension such as \( n \in \{ 2^{16}, 2^{17} \} \), and advanced applications such as logistic regression have used equally large dimensions. This motivates the community to consider widening the recommended parameter sets, and the purpose of this paper is to investigate such possible extensions. We explore the security of possible sparse-secret LWE parameter sets, taking into account hybrid attacks, which are often the most competitive in the sparse-secret regime. We present a conservative analysis of the hybrid decoding and hybrid dual attacks for parameter sets of varying sparsity, with the goal of balancing security requirements with bootstrapping efficiency. We also show how the methodology in the Standard can be easily adapted to support parameter sets with power-of-two dimension \( n \geq 2^{16} \). We conclude with a number of discussion points to motivate future improvements to the Standard.

In this short paper, we provide protocols to batch and aggregate multiple non-membership proofs into a single proof of constant size with bilinear accumulators. We subsequently use the accumulator to construct a bilinear Vector Commitment with constant sized openings and a linear public parameter. We also provide ways to speed up the verification of membership and non-membership proofs and to shift most of the computational burden from the Verifier to the Prover. Furthermore, we have designed the protocols so that the Verifier needs a constant amount of storage for verification despite the linear public parameter. Since all the protocols are public coin, they can me made non-interactive with a Fiat-Shamir heuristic.

Event date: 16 January to 17 January 2020
Submission deadline: 31 October 2019
Notification: 30 November 2019

Event date: 13 December to 15 December 2019
Submission deadline: 30 October 2019
Notification: 10 November 2019

Videos from the Crypto 2019 conference are online on YouTube. The videos from the Rump Session are in a separate playlist.

Grover's search algorithm gives a quantum attack against block ciphers by searching for a key that matches a small number of plaintext-ciphertext pairs. This attack uses $O(\sqrt{N})$ calls to the cipher to search a key space of size $N$. Previous work in the specific case of AES derived the full gate cost by analyzing quantum circuits for the cipher, but focused on minimizing the number of qubits.

In contrast, we study the cost of quantum key search attacks under a depth restriction and introduce techniques that reduce the oracle depth, even if it requires more qubits. As cases in point, we design quantum circuits for the block ciphers AES and LowMC. Our circuits give a lower overall attack cost in both the gate count and depth-times-width cost models. In NIST's post-quantum cryptography standardization process, security categories are defined based on the concrete cost of quantum key search against AES. We present new, lower cost estimates for each category, so our work has immediate implications for the security assessment of post-quantum cryptography.

As part of this work, we release Q# implementations of the full Grover oracle for AES-128, -192, -256 and for the three LowMC instantiations used in Picnic, including unit tests and code to reproduce our quantum resource estimates. To the best of our knowledge, these are the first two such full implementations and automatic resource estimations.

This paper introduces a new way of instantiating supersingular isogeny-based cryptography in which parties can work in both the ($p+1$)-torsion of a set of supersingular curves and in the ($p-1$)-torsion corresponding to the set of their quadratic twists. Although the isomorphism between a given supersingular curve and its quadratic twist is not defined over GF($p^2$) in general, restricting operations to the x-lines of both sets of twists allows all arithmetic to be carried out over GF($p^2$) as usual. Furthermore, since supersingular twists always have the same GF($p^2$)-rational j-invariant, the SIDH protocol remains unchanged when Alice and Bob are free to work in both sets of twists.

This framework lifts the restrictions on the shapes of the underlying prime fields originally imposed by Jao and De Feo, and allows a range of new options for instantiating isogeny- based public key cryptography. This includes alternatives that exploit Mersenne, Solinas, and Montgomery-friendly primes, the possibility of halving the size of the primes of the Jao-De Feo construction at no known loss of asymptotic security, and more.

The Camenisch-Lysyanskaya rerandomizable signature (CL-RRS) scheme is an important tool in the construction of privacy preserving protocols. One of the limitations of CL-RRS is that the signature size is linear in the number of messages to be signed. In 2016, Pointcheval-Sanders introduced a variant of rerandomizable signature (PS-RRS) scheme which removes the above limitation. However, the security of PS-RRS scheme was proved under an interactive assumption. In 2018, Pointcheval-Sanders improved this to give a reduction under a parameterized assumption.

In 2012, Gerbush et al.\ introduced the dual-form signature technique to remove the dependency on interactive/parameterized assumption. They applied this technique on the CL-RRS scheme (for single message) and proved its unforgeability under static assumptions instead of the interactive assumption used in the original work but in the symmetric composite-order pairing setting.

In this work, we realize a fully rerandomizable signature scheme in the prime order setting without random oracle based on the SXDH assumption. The signature structure is derived from Ghadafi's structure-preserving signature. We first apply the dual-form signature technique to obtain a composite-order variant, called \texttt{RRSc}. A signature in \texttt{RRSc} consists of only two group elements and is thus independent of the message block length. The security of the proposed scheme is based on subgroup hiding assumptions. Then we use the dual pairing vector space framework to obtain a prime-order variant called \texttt{RRS} and prove its security under the SXDH assumption.

Outsourcing data to the cloud for personal use is becoming an everyday trend rather than an extreme scenario. The frequent out- sourcing of data increases the possible attack window because users do not fully control their personal files. Typically, once there are established secure channels between two endpoints, communication is considered se- cure. However, in the cloud model the receiver–the cloud–cannot be fully trusted, either because it has been under adversarial control, or because it acts maliciously to increase its revenue by deleting infrequent accessed file blocks. One approach used by current literature to address the aforemen- tioned security concerns is via Remote Data Integrity Checking (RDIC) protocols, whereby a data owner can challenge an untrusted cloud service provider (CSP) to prove faithful storage of its data. Current RDIC protocols assume that the original data format remains unchanged. However, users may wish to compress their data in order to enjoy less charges. In that case, current RDIC protocols become impracti- cal because, each time compression happens on a file, the user has to run a new RDIC protocol. In this work we initiate the study for Auditable Compressed Storage (ACS). After defining the new model we instanti- ate two protocols for different widely used compression techniques: run length encoding and Huffman encoding. In contrast with conventional RDIC, our protocols allow a user to delegate the compression to the cloud in a provably secure way: The client can verify correctness of com- pression without having to download the entire uncompressed file and check it against the compressed one.

We show how to generalize lattice reduction algorithms to module lattices in order to reduce $\gamma$-approximate ModuleSVP over module lattices with rank $k \geq2$ to $\gamma'$-approximate ModuleSVP over module lattices with rank $2 \leq \beta \leq k$. To do so, we modify the celebrated slide-reduction algorithm of Gama and Nguyen to work with module filtrations, a higher-dimensional analogue of the ($\mathbb{Z}$-)basis of a lattice. The particular value of $\gamma$ that we achieve depends on the underlying number field $K$, the ring $R \subset K$, and the embedding (as well as, of course, $k$ and $\beta$). However, for reasonable choices of these parameters, the approximation factor that we achieve is surprisingly close to the one achieved by ``plain'' lattice reduction algorithms, which require an arbitrary SVP oracle in the same dimension. In other words, we show that ModuleSVP oracles are nearly as useful as SVP oracles for solving approximate ModuleSVP in higher dimensions. Our result generalizes the recent independent result of Lee, Pellet-Mary, Stehl\'e, and Wallet, which works in the important special case when $\beta = 2$ and $R = \mathcal{O}_K$ is the ring of integers of $K$ under the canonical embedding. Indeed, at a high level our reduction can be thought of as a generalization of theirs in roughly the same way that slide reduction generalizes LLL reduction.

During the last decade, several misbehaving Certificate Authorities (CA) have issued fraudulent TLS certificates allowing MITM kinds of attacks which result in serious security incidents. In order to avoid such incidents, Yakubov et al. recently proposed a new PKI architecture where CAs issue, revoke, and validate X.509 certificates on a public blockchain. In their proposal, each CA has a smart contract on the blockchain for publishing the hash values of its issued certificates and managing their revocation status. However, their proposal has several security and privacy issues. First, TLS clients can only validate certificates through either full nodes or web services, but cannot verify the correctness of the incoming responses. Second, certificate transparency is not fully provided because CAs do not store the certificates themselves but only their hash values in the blockchain which makes to detect fake ones impossible. In this paper, we eliminate the issues of the Yakubov et al.’s scheme and propose a new PKI architecture based on permissioned blockchain with a modified PBFT consensus mechanism. In our modified PBFT, the validators (i.e., the consensus nodes) utilize a dynamic threshold signature scheme to generate signed blocks. In this way, the trust to external entities can be completely eliminated during certificate validation. More concretely, TLS clients can easily verify the genuinity of the final state of the TLS certificates using signed block headers and the Merkle proofs. Also, the privacy of the TLS clients is fully preserved during validation process by avoiding additional communication with the external entities. Our scheme enjoys the dynamic property of the threshold signature because TLS clients do not have to change the verification key even if the validator set is dynamic. Furthermore, TLS clients are also not required to be a peer of the blockchain network and avoid communication overhead. We implement our proposal on private Ethereum network to demonstrate the experimental results. The results show that our proposal has negligible overhead during TLS handshake. The certificate validation duration is less than the duration in the conventional PKI and Yakubov et al.’s scheme.

Public key cryptography protocols, such as RSA and elliptic curve cryptography, will be rendered insecure by Shor’s algorithm when large-scale quantum computers are built. Cryptographers are working on quantum-resistant algorithms, and lattice-based cryptography has emerged as a prime candidate. However, high computational complexity of these algorithms makes it challenging to implement lattice-based protocols on low-power embedded devices. To address this challenge, we present Sapphire – a lattice cryptography processor with configurable parameters. Efficient sampling, with a SHA-3-based PRNG, provides two orders of magnitude energy savings; a single-port RAM-based number theoretic transform memory architecture is proposed, which provides 124k-gate area savings; while a low-power modular arithmetic unit accelerates polynomial computations. Our test chip was fabricated in TSMC 40nm low-power CMOS process, with the Sapphire cryptographic core occupying 0.28 mm2 area consisting of 106k logic gates and 40.25 KB SRAM. Sapphire can be programmed with custom instructions for polynomial arithmetic and sampling, and it is coupled with a low-power RISC-V micro-processor to demonstrate NIST Round 2 lattice-based CCA-secure key encapsulation and signature protocols Frodo, NewHope, qTESLA, CRYSTALS-Kyber and CRYSTALS-Dilithium, achieving up to an order of magnitude improvement in performance and energy-efficiency compared to state-of-the-art hardware implementations. All key building blocks of Sapphire are constant-time and secure against timing and simple power analysis side-channel attacks. We also discuss how masking-based DPA countermeasures can be implemented on the Sapphire core without any changes to the hardware.

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.