International Association
for Cryptologic Research

Topology-hiding computation (THC) is a form of multi-party computation over an incomplete communication graph that maintains the privacy of the underlying graph topology. Existing THC protocols consider an adversary that may corrupt an arbitrary number of parties, and rely on cryptographic assumptions such as DDH.

In this paper we address the question of whether information-theoretic THC can be achieved by taking advantage of an honest majority. In contrast to the standard MPC setting, this problem has remained open in the topology-hiding realm, even for simple "privacy-free" functions like broadcast, and even when considering only semi-honest corruptions.

We uncover a rich landscape of both positive and negative answers to the above question, showing that what types of graphs are used and how they are selected is an important factor in determining the feasibility of hiding topology information-theoretically. In particular, our results include the following.

* We show that topology-hiding broadcast (THB) on a line with four nodes, secure against a single semi-honest corruption, implies key agreement. This result extends to broader classes of graphs, e.g., THB on a cycle with two semi-honest corruptions. * On the other hand, we provide the first feasibility result for information-theoretic THC: for the class of cycle graphs, with a single semi-honest corruption.

Given the strong impossibilities, we put forth a weaker definition of distributional-THC, where the graph is selected from some distribution (as opposed to worst-case). * We present a formal separation between the definitions, by showing a distribution for which information theoretic distributional-THC is possible, but even topology-hiding broadcast is not possible information-theoretically with the standard definition. * We demonstrate the power of our new definition via a new connection to adaptively secure low-locality MPC, where distributional-THC enables parties to "reuse" a secret low-degree communication graph even in the face of adaptive corruptions.

The random oracle model (ROM) is an idealized model where hash functions are modeled as random functions that are only accessible as oracles. Although the ROM has been used for proving many cryptographic schemes, it has (at least) two problems. First, the ROM does not capture quantum adversaries. Second, it does not capture non-uniform adversaries that perform preprocessings. To deal with these problems, Boneh et al. (Asiacrypt'11) proposed using the quantum ROM (QROM) to argue post-quantum security, and Unruh (CRYPTO'07) proposed the ROM with auxiliary input (ROM-AI) to argue security against preprocessing attacks. However, to the best of our knowledge, no work has dealt with the above two problems simultaneously.

In this paper, we consider a model that we call the QROM with (classical) auxiliary input (QROM-AI) that deals with the above two problems simultaneously and study security of cryptographic primitives in the model. That is, we give security bounds for one-way functions, pseudorandom generators, (post-quantum) pseudorandom functions, and (post-quantum) message authentication codes in the QROM-AI.

We also study security bounds in the presence of quantum auxiliary inputs. In other words, we show a security bound for one-wayness of random permutations (instead of random functions) in the presence of quantum auxiliary inputs. This resolves an open problem posed by Nayebi et al. (QIC'15). In a context of complexity theory, this implies $ \mathsf{NP}\cap \mathsf{coNP} \not\subseteq \mathsf{BQP/qpoly}$ relative to a random permutation oracle, which also answers an open problem posed by Aaronson (ToC'05).

Bitcoin and similar blockchain systems have a limited transaction throughput because each transaction must be processed by all parties, on-chain. Payment channels relieve the blockchain by allowing parties to execute transactions off-chain while maintaining the on-chain security guarantees, i.e., no party can be cheated out of their funds. However, to maintain these guarantees all parties must follow blockchain updates ardently. To alleviate this issue, a channel party can hire a "watchtower" to periodically check the blockchain for fraud on its behalf.

However, watchtowers will only do their job properly if there are financial incentives, fees, and punishments. There are known solutions, but these need complex smart contracts, and as such are not applicable to Bitcoin's simple script language. This raises the natural question of whether incentivized watchtowers are at all possible in a system like Bitcoin.

In this work, we answer this question affirmatively, by introducing Cerberus channels, an extension of Lightning channels. Cerberus channels reward watchtowers while remaining secure against bribing and collusion; thus participants can safely go offline for an extended period of time. We show that Cerberus channels are correct, and provide a proof-of-concept implementation in the Bitcoin script language.

We demonstrate that XOR Arbiter PUFs with an even number of arbiter chains have inherently biased responses, even if all arbiter chains are perfectly unbiased. This rebukes the believe that XOR Arbiter PUFs are, like Arbiter PUFs, unbiased when ideally implemented and proves that independently manufactured Arbiter PUFs are not statistically independent.

As an immediate result of this work, we suggest to use XOR Arbiter PUFs with odd numbers of arbiter chains whenever possible. Furthermore, our analysis technique can be applied to future types of PUF designs and can hence be used to identify design weaknesses, in particular when using Arbiter PUFs as building blocks and when developing designs with challenge pre-processing. Finally, we discuss consequences for the parameter recommendations of the Interpose PUF.

Investigating the reason of the systematic bias of XOR Arbiter PUF, we exhibit that Arbiter PUFs suffer from a systematic uniqueness weakness.

While $GF(2^n)$ polynomial bases are widely used in symmetric-key components, e.g. MDS matrices, we show that even low time/space complexities can be achieved by using $GF(2^n)$ shifted polynomial bases (SPB) or generalized polynomial bases (GPB).

Some of the papers on lattice basis owe respect to randomization reduction or deterministic reduction. These biases, especially non-deterministic reduction is used to show that lattices are interesting hard problems within the set of NP Complete problems. Though the shortest vector problem (SVP) seems promising. It is nearly enough to facilitate and establish the lattice basis an exception from the priori art [1]. The many configurations of their vertices seem to dismiss the wonderful properties of the dynamic faces that abounds in various lattice constructs. The elements of these faces found in between regions bounded by the vertices and edges are of great interest to cryptography. When represented as numerical values serve as mathematical images of the basis distribution. In this paper, it is shown that each vector representation has the potential to generate cryptographically secure number of keys. This follows a somewhat rigid rule; deterministic and yet a chaotic arrangement of the lattice vectors represented within a matrix of column (c) and rows (r), where (c=>16 and r=>16). A fitting rule is already available with the necessary mechanism to produce 1: n relationship for a plaintext against many ciphertext. It is that found in Open Knight Tour (OKT or KT) movements. This can easily be modified to absorb larger lattice basis. They are ready made with properties that are closely related to the regular vectors of Euclidean space.

This paper applies biomimetic engineering to the problem of permissionless Byzantine consensus and achieves results that surpass the prior state of the art by four orders of magnitude. It introduces a biologically inspired asymmetric Sybil-resistance mechanism, Proof-of-Balance, which can replace symmetric Proof-of-Work and Proof-of-Stake weighting schemes.

The biomimetic mechanism is incorporated into a permissionless blockchain protocol, Key Retroactivity Network Consensus (“KRNC”), which delivers ~40,000 times the security and speed of today’s decentralized ledgers. KRNC allows the fiat money that the public already owns to be upgraded with cryptographic inflation protection, eliminating the problems inherent in bootstrapping new currencies like Bitcoin and Ethereum.

The paper includes two independently significant contributions to the literature. First, it replaces the non-structural axioms invoked in prior work with a new formal method for reasoning about trust, liveness, and safety from first principles. Second, it demonstrates how two previously overlooked exploits — book-prize attacks and pseudo-transfer attacks — collectively undermine the security guarantees of all prior permissionless ledgers.

Sorting on encrypted data using Somewhat Homomorphic Encryption (SHE) schemes is currently inefficient in practice when the number of elements to be sorted is very large. Hence alternate protocols that can efficiently perform computation and sorting on encrypted data is of interest. Recently, Kesarwani et al. (EDBT 2018) proposed a protocol for efficient sorting on data encrypted using an SHE scheme in a model where one of the two non-colluding servers is holding the decryption key. The encrypted data to be sorted is transformed homomorphically by the first server using a randomly chosen monotonic polynomial with possibly large coefficients, and then the non-colluding server holding the decryption key decrypts, sorts, and conveys back the sorted order to the first server without learning the actual values except possibly for the order.

In this work we demonstrate an attack on the above protocol that allows the non-colluding server holding the decryption key to recover the original plaintext inputs (up to a constant difference). Though our attack runs in time exponential in the size of plaintext inputs and degree of the polynomial but polynomial in the size of coefficients, we show that our attack is feasible for 32-bit inputs, hence accounting for several real world scenarios. Of independent interest is our algorithm for recovering the integer inputs (up to a constant difference) by observing only the integer polynomial outputs.

We introduce SPHINCS+, a stateless hash-based signature framework. SPHINCS+ has significant advantages over the state of the art in terms of speed, signature size, and security, and is among the nine remaining signature schemes in the second round of the NIST PQC standardization project. One of our main contributions in this context is a new few-time signature scheme that we call FORS. Our second main contribution is the introduction of tweakable hash functions and a demonstration how they allow for a unified security analysis of hash-based signature schemes. We give a security reduction for SPHINCS+ using this abstraction and derive secure parameters in accordance with the resulting bound. Finally, we present speed results for our optimized implementation of SPHINCS+ and compare to SPHINCS-256, Gravity-SPHINCS, and Picnic.

We initiate a systematic study of pseudorandom functions (PRFs) that are computable by simple matrix branching programs; we refer to these objects as “matrix PRFs”. Matrix PRFs are attractive due to their simplicity, strong connections to complexity theory and group theory, and recent applications in program obfuscation.

Our main results are:

* We present constructions of matrix PRFs based on the conjectured hardness of some simple computational problems pertaining to matrix products.

* We show that any matrix PRF that is computable by a read-c, width w branching program can be broken in time poly(w^c); this means that any matrix PRF based on constant-width matrices must read each input bit omega(log lambda) times. Along the way, we simplify the “tensor switching lemmas” introduced in previous IO attacks.

* We show that a subclass of the candidate local-PRG proposed by Barak et al. [Eurocrypt 2018] can be broken using simple matrix algebra.

* We show that augmenting the CVW18 IO candidate with a matrix PRF provably immunizes the candidate against all known algebraic and statistical zeroizing attacks, as captured by a new and simple adversarial model.

We investigate concretely efficient protocols for distributed oblivious linear evaluation over vectors (Vector-OLE). Boyle et al. (CCS 2018) proposed a protocol for secure distributed pseudorandom Vector-OLE generation using sublinear communication, but they did not provide an implementation. Their construction is based on a variant of the LPN assumption and assumes a distributed key generation protocol for single-point Function Secret Sharing (FSS), as well as an efficient batching scheme to obtain multi-point FSS. We show that this requirement can be relaxed, resulting in a weaker variant of FSS, for which we give an efficient protocol. This allows us to use efficient probabilistic batch codes that were also recently used for batched PIR by Angel et al. (S&P 2018). We construct a full Vector-OLE generator from our protocols, and compare it experimentally with alternative approaches. Our implementation parallelizes very well, and has low communication overhead in practice. For generating a VOLE of size $2^{20}$, our implementation only takes $0.52$s on 32 cores.

A number of important real-world protocols including the Transport Layer Security (TLS) protocol have the ability to negotiate various security-related choices such as the protocol version and the cryptographic algorithms to be used in a particular session. Furthermore, some insecure application-layer protocols such as the Simple Mail Transfer Protocol (SMTP) negotiate the use of TLS itself on top of the application protocol to secure the communication channel. These protocols are often vulnerable to a class of attacks known as downgrade attacks which targets this negotiation mechanism. In this paper we create the first taxonomy of TLS downgrade attacks. Our taxonomy classifies possible attacks with respect to four different vectors: the protocol element that is targeted, the type of vulnerability that enables the attack, the attack method, and the level of damage that the attack causes. We base our taxonomy on a thorough analysis of fifteen notable published attacks. Our taxonomy highlights clear and concrete aspects that many downgrade attacks have in common, and allows for a common language, classification, and comparison of downgrade attacks. We demonstrate the application of our taxonomy by classifying the surveyed attacks.

Multikey fully homomorphic encryption (MFHE) scheme enables homomorphic computation on data encrypted under different keys. To decrypt a result ciphertext, all the involved secret keys are required. For multi decryptor setting, decryption is a protocol with minimal interaction among parties. However, all prior schemes supporting the protocol are not secure in public channel against a passive external adversary who can see any public information not joining the protocol. Furthermore, the possible adversaries have not been defined clearly.

In this paper, we revisit the security of MFHE and present a secure one-round decryption protocol. We apply it to one of existing schemes and prove the scheme is secure against possible static adversaries. As an application, we construct a two round multiparty computation without common random string.

We propose OCEAN, an alternative miner reward system for blockchains that seeks to discourage pooling by providing a pool's variance mitigation functionality as a blockchain built-in. Our proposal relies on Succinct, Non-interactive Arguments of Knowledge (SNARKs), an advanced modern cryptographic tool that enables anyone to prove complex statements with the proof not growing in size with the complexity of the statement. We expect that blockchains that implement our proposal would see less pooling centralization than what is currently observable in deployed cryptocurrencies.

The Gimli permutation was proposed in CHES 2017 and the hash mode Gimli-Hash is now included in the Round 2 candidate Gimli in NIST's Lightweight Cryptography Standardization process. In the Gimli document, the security of the Gimli permutation has been intensively investigated. However, little is known about the security of Gimli-Hash. The designers of Gimli have claimed $2^{128}$ security against all attacks on Gimli-Hash, whose hash is a 256-bit value. Firstly, we present the trivial generic preimage attack on the structure of Gimli-Hash matching the $2^{128}$ security bound, both, in time and memory complexity. Following such a generic preimage attack framework, we then describe specific preimage attacks on 2/3/4/5 (out of 24) rounds of Gimli-Hash using divide-and-conquer methods. As will be shown, the application of the divide-and-conquer methods much benefits from the properties of the SP-box and the linear layer of Gimli. Therefore, this work can also be viewed to make the first step to exploit specific properties of the SP-box. Finally, the divide-and-conquer method was also applied to a collision attack on up to 5-round Gimli-Hash. As a support of our method, we provide a practical colliding four-block message pair for the full-state collision of 3-round Gimli-Hash. We hope our analysis can advance the understanding of Gimli-Hash.

The Number Theoretic Transform (NTT) technique is widely used in the implementation of the cryptographic schemes based on the Ring Learning With Errors problem(RLWE), since it provides efficient algorithm for multiplication of polynomials over the finite field. However, to employ NTT, the finite field is required to have some special root of unity, such as $n$-th root, which makes the module $q$ in RLWE big since we need $q\equiv 1\mod 2n$ to ensure such root exits. At Inscrypt 2018, Zhou et al. proposed a technique called preprocess-then-NTT to reduce the value of modulus $q$ while the NTT still works, and the time complexity is just a constant ($>1$) multiple of the original NTT algorithm asymptotically. In this paper, we revisit the preprocess-then-NTT technique and point out it can be improved such that its time complexity is as the same as the original NTT algorithm asymptotically. What's more, through experiments we find that even compared with the original NTT our improved algorithm may have some advantages in efficiency.

This work envisions a new encryption primitive for many-to-many paradigms such as group messaging systems. Previously, puncturable encryption (PE) was introduced to provide forward security for asynchronous messaging services. However, existing PE schemes were proposed only for one-to-one communication, and causes a significant overhead for a group messaging system. In fact, the group communication over PE can only be achieved by encrypting a message multiple times for each receiver by the sender's device, which is usually suitable to restricted resources such as mobile phones or sensor devices. Our new suggested scheme enables to re-encrypt ciphertexts of puncturable encryption by a message server (i.e., a proxy) so that computationally heavy operations are delegated to the server who has more powerful processors and a constant power source. We then proposed a new Puncturable Proxy Re-Encryption (PPRE) scheme. The scheme is inspired by unidirectional proxy re-encryption (UPRE), which achieves forward secrecy through fine-grained revocation of decryption capability by integrating the PE scheme. This paper first presents a forward secure PPRE in the group messaging service. Our scheme is IND-CCA secure under 3-weak Decision Bilinear Diffie-Hellman Inversion assumption

We construct the first adaptively secure garbling scheme based on standard public-key assumptions for garbling a circuit $C: \{0, 1\}^n \mapsto \{0, 1\}^m$ that simultaneously achieves a near-optimal online complexity $n + m + \textrm{poly}(\lambda, \log |C|)$ (where $\lambda$ is the security parameter) and \emph{preserves the parallel efficiency} for evaluating the garbled circuit; namely, if the depth of $C$ is $d$, then the garbled circuit can be evaluated in parallel time $d \cdot \textrm{poly}(\log|C|, \lambda)$. In particular, our construction improves over the recent seminal work of Garg et al. (Eurocrypt 2018), which constructs the first adaptively secure garbling scheme with a near-optimal online complexity under the same assumptions, but the garbled circuit can only be evaluated gate by gate in a sequential manner. Our construction combines their novel idea of linearization with several new ideas to achieve parallel efficiency without compromising online complexity.

We take one step further to construct the first adaptively secure garbling scheme for parallel RAM (PRAM) programs under standard assumptions that preserves the parallel efficiency. Previous such constructions we are aware of is from strong assumptions like indistinguishability obfuscation Ananth et al. (TCC 2016). Our construction is based on the work of Garg et al. (Crypto 2018) for adaptively secure garbled RAM, but again introduces several new ideas to handle parallel RAM computation, which may be of independent interests. As an application, this yields the first constant round secure computation protocol for persistent PRAM programs in the malicious settings from standard assumptions.

We present a new methodology to efficiently realize recursive composition of succinct non-interactive arguments of knowledge (SNARKs). Prior to this work, the only known methodology relied on pairing-based SNARKs instantiated on cycles of pairing-friendly elliptic curves, an expensive algebraic object. Our methodology does not rely on any special algebraic objects and, moreover, achieves new desirable properties: it is *post-quantum* and it is *transparent* (the setup is public coin).

We exploit the fact that recursive composition is simpler for SNARKs with *preprocessing*, and the core of our work is obtaining a preprocessing zkSNARK for rank-1 constraint satisfiability (R1CS) that is post-quantum and transparent. We obtain this latter by establishing a connection between holography and preprocessing in the random oracle model, and then constructing a holographic proof for R1CS.

We experimentally validate our methodology, demonstrating feasibility in practice.

We present the first protocols for private information retrieval that allow fast (sublinear-time) database lookups without increasing the server-side storage requirements. To achieve these efficiency goals, our protocols work in an offline/online model. In an offline phase, which takes place before the client has decided which database bit it wants to read, the client fetches a short string from the servers. In a subsequent online phase, the client can privately retrieve its desired bit of the database by making a second query to the servers. By pushing the bulk of the server-side computation into the offline phase (which is independent of the client's query), our protocols allow the online phase to complete very quickly—in time sublinear in the size of the database. Our protocols can provide statistical security in the two-server setting and computational security in the single-server setting. Finally, we prove that our protocols are optimal in terms of the trade-off they achieve between communication and running time.