International Association
for Cryptologic Research

Keyed and unkeyed cryptographic permutations often iterate simple round functions. Substitution-Permutation Networks (SPNs) are an approach that is popular since the mid 1990s. One of the new directions in the design of these round functions is to reduce the substitution (S-Box) layer from a full one to a partial one, uniformly distributed over all the rounds. LowMC and Zorro are examples of this approach.

A relevant freedom in the design space is to allow for a highly non-uniform distribution of S-Boxes. However, choosing rounds that are so different from each other is very rarely done, as it makes security analysis and implementation much harder. We develop the design strategy Hades and an analysis framework for it, which despite this increased complexity allows for security arguments against many classes of attacks, similar to earlier simpler SPNs. The framework builds up on the wide trail design strategy for SPNs, and it additionally allows for security arguments against algebraic attacks, that are much more of a concern when algebraically simple S-Boxes are used.

Subsequently, this is put into practice by concrete instances and benchmarks for a use case that generally benefits from a smaller number of S-Boxes and showcases the diversity of design options we support: A candidate cipher natively working with objects in GF(p), for securing data transfers with distributed databases using secure multiparty computation (MPC). Compared to the currently fastest design MiMC, we observe significant improvements in online bandwidth requirements and throughput with a simultaneous reduction of preprocessing effort, while having a comparable online latency.

High-order masking countermeasures against side-channel attacks usually require plenty of randomness during their execution. For security against t probes, the classical ISW countermeasure requires O(t^2 s) random bits, where s is the circuit size. However running a True Random Number Generator (TRNG) can be costly in practice and become a bottleneck on embedded devices. In [IKL+13] the authors introduced the notion of robust pseudo-random number generator (PRG), which must remain secure even against an adversary who can probe at most t wires. They showed that when embedding a robust PRG within a private circuit, the number of random bits can be reduced to O(t^4), that is independent of the circuit size s (up to a logarithmic factor). Using bipartite expander graphs, this can be further reduced to O(t^(3+eps)); however the resulting construction is unpractical.

In this paper we describe a practical construction where the number of random bits is only O(t^2) for security against t probes, without expander graphs; moreover the running time of each pseudo-random generation goes down from O(t^4) to O(t). Our technique consists in using multiple independent PRGs instead of a single one. We show that for ISW circuits, the robustness property of the PRG is not required anymore, which leads to simple and efficient constructions. For example, for AES we only need 48 bytes of randomness to get second-order security (t=2), instead of 2880 in the original Rivain-Prouff countermeasure; when implemented on an ARM-based embedded device with a relatively slow TRNG, we obtain a 50% speed-up compared to Rivain-Prouff.

The Schnorr signature scheme is an efficient digital signature scheme with short signature lengths, i.e., $4k$-bit signatures for $k$-bits of security. A Schnorr signature $\sigma$ over a group of size $q\approx 2^{2k}$ consists of a tuple $(s,e) $ where $e\in \mathbb{Z}_q$ is a hash output and $s$ must be computed using the secret key. Schnorr proposed the possibility of shorter Schnorr signatures with the same security level by truncating the hash output to $k$-bits, i.e., $e < 2^k$. A previous result showed that short Schnorr signatures provide $k$-bits of single-user security in the programmable random oracle model plus (a non-standard version of) the generic group model. Another prior result demonstrated that standard Schnorr signatures provide $k$-bits of multi-user security in the programmable random oracle model plus (another non-standard version of) the generic group model. As we discuss in the paper these non-standard versions of the generic group model do not capture all generic attacks, e.g., the generic preprocessing attacks of Corrigan-Gibbs and Kogan. In this paper, we prove that short Schnorr signatures provide $k$-bits of (multi-user) security under the (standard) generic group model and the programmable random oracle model.

Recent works on distributed garbling have provided highly efficient solutions for constant-round MPC protocols tolerating an arbitrary number of malicious corruptions. In this work, we improve upon state-of-the-art protocols in this paradigm for further performance gain.

We improve the protocol for generating authenticated AND triples, which plays a crucial role in many recent works. -- We propose a multi-party authenticated bit protocol from bare IKNP OT extension, allowing us to 1) reduce the communication by $\approx 24\%$ with a small harmless leakage, and 2) eliminate many computation-heavy procedures like bit-matrix multiplications and consistency checks. This improvement also applies to the two-party setting. -- We reduce the cost of consistency check for multi-party authenticated shares by $\rho$ times where $\rho$ is the statistical security parameter, and also cut the number of hash function calls per party by a factor of $2\times$ when computing leaky authenticated AND triples.

We further improve the state-of-the-art multi-party authenticated garbling protocol. -- We take the first step towards applying half-gates in the multi-party setting, which enables us to reduce the size of garbled tables by $2\kappa$ bits per AND gate per garbler, where $\kappa$ is the computational security parameter. This optimization is also applicable in the semi-honest multi-party setting. -- We further reduce the size of garbled tables by about $4\rho$ bits per AND gate, by using an almost universal hash function to perform the circuit authentication in a batch. Prior solution with similar efficiency is only applicable in the two-party setting.

Along with other optimization, we reduce the communication complexity of the whole protocol (including both function-independent and function-dependent preprocessing phases that require the most resources) by $\approx 24\%$ and significantly improve the overall computational efficiency.

Biometric authentication is increasingly being used for large scale human authentication and identification, creating the risk of leaking the biometric secrets of millions of users in the case of database compromise. Powerful ``fuzzy'' cryptographic techniques for biometric template protection, such as secure sketches, could help in principle, but go unused in practice. This is because they would require new biometric matching algorithms with potentially much-diminished accuracy.

We introduce a new primitive called a multisketch that generalizes secure sketches. Multisketches can work with existing biometric matching algorithms to generate strong cryptographic keys from biometric data reliably. A multisketch works on a biometric database containing multiple biometrics --- e.g., multiple fingerprints --- of a moderately large population of users (say, thousands). It conceals the correspondence between users and their biometric templates, preventing an attacker from learning the biometric data of a user in the advent of a breach, but enabling derivation of user-specific secret keys upon successful user authentication.

We design a multisketch over tenprints --- fingerprints of ten fingers --- called TenSketch. We report on a prototype implementation of TenSketch, showing its feasibility in practice. We explore several possible attacks against TenSketch database and show, via simulations with real tenprint datasets, that an attacker must perform a large amount of computation to learn any meaningful information from a stolen TenSketch database.

Traceable range proofs enable regulators to trace the amounts of transactions in privacy-preserving blockchains, but it lacks adequate functionality in the application scenarios such as currency (assets) transfer, international trades and taxation, etc. In this paper, we give multiple modifications and applications on traceable Borromean range proof (TBoRP) and traceable Bulletproofs range proof (TBuRP), which realize functionalities including multi-currency regulation, regulatable private assets transfer, auxiliary privacy calculation and secure joint regulation by usage of zero-knowledge proofs, homomorphic commitments and MPC protocols. Our work can help regulators to choose the regulatory policy as they wish and help users to transfer assets, compute private amounts under the regulation efficiently and independently. Our solutions are well suited for the future applications of regulatable privacy-preserving cryptocurrencies.

Motivated by the fact that in the quantum random oracle model (QROM) introduced by Boneh et al. (Asiacrypt 2011), honest parties (i.e., the cryptosystems) typically use the random oracle (RO) in a classical way while the adversary can send quantum queries to the RO, we first reformalize the classical RO (CRO) and the quantum RO (QRO) by adapting the indifferentiability framework of Maurer et al. (TCC 2004), and equipping a RO with a private and a (quantum) public interface for the honest parties and the adversary, respectively. Then, we give a new separation between the QROM and the ROM by showing that QRO is differentiable from CRO, which is technically different from Boneh et al.'s separation and is based on a new information versus disturbance lemma (that may be of independent interest).

We further abstract a class of BB-reductions in the ROM under the notion of committed-programming reduction (CPRed) for which the simulation of the RO can be easily quantized to handle quantum queries (from the adversary in the QROM). We show that 1) some well-known schemes such as the FDH signature and the Boneh-Franklin identity-based encryption are provably secure under CPReds; and 2) a CPRed associated with an instance-extraction algorithm implies a reduction in the QROM, which subsumes several recent results such as the security of the FDH signature by Zhandry (Crypto 2012) and the KEM variants from the Fujisaki-Okamoto transform by Jiang et al. (Crypto 2018).

We finally show that CPReds are incomparable to non-programming reductions (NPReds) and randomly-programming reductions (RPReds) formalized by Fischlin et al. (Asiacrypt 2010), which gives new insights into the abilities (e.g., observability and programmability) provided by the (Q)ROM, and the hardness of proving security in the QROM.

Multipartite secret sharing schemes are those having a multipartite access structure, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. Secret sharing schemes for multipartite access structures have received considerable attention due to the fact that multipartite secret sharing can be seen as a natural and useful generalization of threshold secret sharing.

This work deals with efficient and explicit constructions of ideal multipartite secret sharing schemes, while most of the known constructions are either inefficient or randomized. Most ideal multipartite secret sharing schemes in the literature can be classified as either hierarchical or compartmented. The main results are the constructions for ideal hierarchical access structures, a family that contains every ideal hierarchical access structure as a particular case such as the disjunctive hierarchical threshold access structure and the conjunctive hierarchical threshold access structure, the constructions for three families of compartmented access structures, and the constructions for two families compartmented access structures with compartments.

On the basis of the relationship between multipartite secret sharing schemes, polymatroids, and matroids, the problem of how to construct a scheme realizing a multipartite access structure can be transformed to the problem of how to find a representation of a matroid from a presentation of its associated polymatroid. In this paper, we give efficient algorithms to find representations of the matroids associated to several families of multipartite access structures. More precisely, based on know results about integer polymatroids, for each of those families of access structures above, we give an efficient method to find a representation of the integer polymatroid over some finite field, and then over some finite extension of that field, we give an efficient method to find a presentation of the matroid associated to the integer polymatroid. Finally, we construct ideal linear schemes realizing those families of multipartite access structures by efficient methods.

Most modern web browsers today sacrifice optimal TLS security for backward compatibility. They apply coarse-grained TLS configurations that support (by default) legacy versions of the protocol that have known design weaknesses, and weak ciphersuites that provide fewer security guarantees (e.g. non Forward Secrecy), and silently fall back to them if the server selects to. This introduces various risks including downgrade attacks such as the POODLE attack that exploits the browsers silent fallback mechanism to downgrade the protocol version in order to exploit the legacy version flaws. To achieve a better balance between security and backward compatibility, we propose a mechanism for fine-grained TLS configurations in web browsers based on the sensitivity of the domain name in the HTTPS request using a white listing technique. That is, the browser enforces optimal TLS configurations for connections going to sensitive domains while enforcing default configurations for the rest of the connections. We demonstrate the feasibility of our proposal by implementing a proof-of-concept as a Firefox browser extension. We envision this mechanism as a built-in security feature in web browsers, e.g. a button similar to the “Bookmark” button in Firefox browsers and as a standardised HTTP header, to augment browsers security.

We continue the study of Ben-Efraim (Asiacrypt 2018) on multiparty garbled circuits that contain both Boolean and arithmetic gates. Concretely, we extend the work of Ben-Efraim from the semi-honest, honest majority security model to the full-threshold actively secure equivalent. We further improve Ben-Efraim's selector gate. A selector gate is a gate that given two arithmetic inputs and one binary input, outputs one of the arithmetic inputs, based on the value of the selection bit input. Our new construction for the selector gate reduces the communication cost to almost half of that of Ben-Efraim's gate. This result applies both to the semi-honest and to the active security model.

In permissioned blockchain systems, participants are admitted to the network by receiving a credential from a certification authority. Each transaction processed by the network is required to be authorized by a valid participant who authenticates via their credential. Use case settings where privacy is a concern thus require proper privacy-preserving authentication and authorization mechanisms. Anonymous credential schemes are cryptographic mechanisms that allow a user to authenticate while showing only those attributes necessary in a given setting, which makes these schemes a great tool for authorizing transactions in permissioned blockchain systems based on the user's attributes. As in most setups of such systems there is one distinct certification authority for each organization in the network, the use of plain anonymous credential schemes still leaks the association of a user to their issuing organization. Camenisch, Drijvers, and Dubovitskaya (CCS 2017) therefore suggest the use of delegatable anonymous credential schemes, which allows to hide even that remaining piece of information. We implement private transaction authorization in Hyperledger Fabric based on delegatable anonymous credentials. To this end, we provide a production-grade open-source implementation of the Camenisch et al. scheme with several optimizations. We then extend Fabric to support the scheme as an additional mechanism for authorizing transactions. Our solution supports revocation and auditing, making it ready for real-world deployment. Our performance measurements show that the scheme, while incurring an overhead in comparison to the less privacy-preserving ones, is practical for settings with enhanced privacy requirements.

Proof-of-burn has been used as a mechanism to destroy cryptocurrency in a verifiable manner. Despite its well known use, the mechanism has not been previously formally studied as a primitive. In this paper, we put forth the first cryptographic definition of what a proof-of-burn protocol is. It consists of two functions: First, a function which generates a cryptocurrency address. When a user sends money to this address, the money is irrevocably destroyed. Second, a verification function which checks that an address is really unspendable. We propose the following properties for burn protocols. Unspendability, which mandates that an address which verifies correctly as a burn address cannot be used for spending; binding, which allows associating metadata with a particular burn; and uncensorability, which mandates that a burn address is indistinguishable from a regular cryptocurrency address. Our definition captures all previously known proof-of-burn protocols. Next, we design a novel construction for burning which is simple and flexible, making it compatible with all existing popular cryptocurrencies. We prove our scheme is secure in the Random Oracle model. We explore the application of destroying value in a legacy cryptocurrency to bootstrap a new one. The user burns coins in the source blockchain and subsequently creates a proof-of-burn, a short string proving that the burn took place, which she then submits to the destination blockchain to be rewarded with a corresponding amount. The user can use a standard wallet to conduct the burn without requiring specialized software, making our scheme user friendly. We propose burn verification mechanisms with different security guarantees, noting that the target blockchain miners do not necessarily need to monitor the source blockchain. Finally, we implement the verification of Bitcoin burns as an Ethereum smart contract and experimentally measure that the gas costs needed for verification are as low as standard Bitcoin transaction fees, illustrating that our scheme is practical.

We propose a simple and powerful new approach for secure computation with input-independent preprocessing, building on the general tool of function secret sharing (FSS) and its efficient instantiations. Using this approach, we can make efficient use of correlated randomness to compute any type of gate, as long as a function class naturally corresponding to this gate admits an efficient FSS scheme. Our approach can be viewed as a generalization of the "TinyTable" protocol of Damgard et al. (Crypto 2017), where our generalized variant uses FSS to achieve exponential efficiency improvement for useful types of gates.

By instantiating this general approach with efficient PRG-based FSS schemes of Boyle et al. (Eurocrypt 2015, CCS 2016), we can implement useful nonlinear gates for equality tests, integer comparison, bit-decomposition and more with optimal online communication and with a relatively small amount of correlated randomness. We also provide a unified and simplified view of several existing protocols in the preprocessing model via the FSS framework.

Our positive results provide a useful tool for secure computation tasks that involve secure integer comparisons or conversions between arithmetic and binary representations. These arise in the contexts of approximating real-valued functions, machine-learning classification, and more.

Finally, we study the necessity of the FSS machinery that we employ, in the simple context of secure string equality testing. First, we show that any "online-optimal" secure equality protocol implies an FSS scheme for point functions, which in turn implies one-way functions. Then, we show that information-theoretic secure equality protocols with relaxed optimality requirements would follow from the existence of big families of "matching vectors." This suggests that proving strong lower bounds on the efficiency of such protocols would be difficult.

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.