Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Lower Bounds on the Bottleneck Complexity of Secure Multiparty Computation
Get PDFSecure multiparty computation (MPC) is a cryptographic primitive which enables multiple parties to jointly compute a function without revealing any extra information on their private inputs. Bottleneck complexity is an efficiency measure that captures the load-balancing aspect of MPC protocols, defined as the maximum amount of communication required by any party. In this work, we study the problem of establishing lower bounds on the bottleneck complexity of MPC protocols. While the previously known techniques for lower bounding total communication complexity can also be applied to bottleneck complexity, they do not provide nontrivial bounds in the correlated randomness model, which is commonly assumed by existing protocols achieving low bottleneck complexity, or they are applied only to functions of limited practical interest. We propose several novel techniques for lower bounding the bottleneck complexity of MPC protocols. Our methods derive nontrivial lower bounds even in the correlated randomness model and apply to practically relevant functions including the sum function and threshold functions. Furthermore, our lower bounds demonstrate the optimality of some existing MPC protocols in terms of bottleneck complexity or the amount of correlated randomness
LP2+: a robust symmetric-key AKE protocol with perfect forward secrecy, and an advocacy for thorough security proofs
Get PDFSymmetric-key authenticated key establishment (AKE) protocols are particularly well suited in resource constraint environments such as internet of things (IoT) devices. Moreover, they often rely on better understood assumptions than asymmetric ones. In this paper, we review the security model for symmetric-key AKE protocols. We show why several existing models allow trivial attacks while they do not protect against some non-trivial ones. We fix these issues with our new security definitions.
We show that the protocols and of Boyd et al. do not satisfy the claimed security properties. We propose a new 2-message protocol based on them, called . This protocol is proved to satisfy correctness, weak synchronization robustness, entity authentication, key indistinguishability and, as a consequence, it admits perfect forward secrecy. An instantiation of is presented, whose security only relies on that of a pseudo-random function (PRF). Its total execution time in normal cases is dominated by only 14 evaluations of the PRF, making it a lightweight protocol that is particularly well suited for resource-constrained environments such as IoT devices.
The flaws found in the security models as well as in the security arguments could have been avoided with precise and detailed proofs. We thus take this paper as an opportunity to advocate for thorough security proofs. Therefore, we have made the choice of rigor over concision
Decentralized Data Archival: New Definitions and Constructions
Get PDFWe initiate the study of a new abstraction
called incremental decentralized data archival ().
Specifically, imagine that there is an ever-growing, massive database such as a blockchain, a comprehensive human knowledge base like Wikipedia, or the Internet archive. We want to build a decentralized archival of such datasets
to ensure long-term robustness and sustainability.
We identify several important properties
that an scheme should satisfy. First,
to promote heterogeneity and decentralization,
we want to encourage even weak nodes with limited space (e.g., users\u27 home computers) to contribute. The minimum space requirement to contribute should be approximately independent of the data size. Second, if a collection of nodes together receive rewards commensurate with contributing a total of blocks of space, then we want the following reassurances: 1) if is at least the database size, we should be able to reconstruct the entire dataset; and 2) these nodes should actually be commiting roughly space in aggregate --- even when is much larger than the data size, the nodes should be storing redundant copies of the database rather than storing just one copy, and yet impersonating arbitrarily many pseudonyms to get unbounded rewards.
We propose new definitions that mathematically formalize the aforementioned requirements of an scheme.
We also devise an efficient construction in the random oracle model which satisfies the desired security requirements. Our scheme incurs only audit cost, as well as update cost for both the publisher and each node, where hides polylogarithmic factors. Further, the minimum space provisioning required to contribute is as small as polylogarithmic.
Our construction exposes several interesting technical challenges. Specifically, we show that a straightforward application of the standard hierarchical data structure fails, since both our security definition and the underlying cryptographic primitives we employ lack the desired compositional guarantees. We devise novel techniques to overcome these compositional issues, resulting in a construction with provable security while still retaining efficiency. Finally, our new definitions also make a conceptual contribution, and lay the theoretical groundwork for the study of . We raise several interesting open problems along this direction
Quantum Rewinding for IOP-Based Succinct Arguments
Get PDFWe analyze the post-quantum security of succinct interactive arguments constructed from interactive oracle proofs (IOPs) and vector commitment schemes. Specifically, we prove that an interactive variant of the *BCS transformation* is secure in the standard model against quantum adversaries when the vector commitment scheme is collapse binding.
Prior work established the post-quantum security of Kilian\u27s succinct interactive argument, a special case of the BCS transformation for one-message IOPs (i.e., PCPs). That analysis is inherently limited to one message because the reduction, like all prior quantum rewinding reductions, aims to extract classical information (a PCP string) from the quantum argument adversary. Our reduction overcomes this limitation by instead extracting a *quantum algorithm* that implements an IOP adversary; representing such an adversary classically may in general require exponential complexity.
Along the way we define *collapse position binding*, which we propose as the ``correct\u27\u27 definition of collapse binding for vector commitment schemes, eliminating shortcomings of prior definitions.
As an application of our results, we obtain post-quantum secure succinct arguments, in the standard model (no oracles), with the *best asymptotic complexity known*
Quantum Security Analysis of the Key-Alternating Ciphers
Get PDFIn this work, we study the quantum security of key-alternating ciphers (KAC), a natural multi-round generalization of the Even–Mansour (EM) cipher underlying many block cipher constructions, including AES. While the classical security of KAC and the quantum security of the -round KAC (i.e. Even-Mansour) cipher are well understood, the quantum resistance of multi-round KAC remains largely unexplored. We focus on the -round KAC construction, defined using public -bit permutations , and keys , , and as Our main contributions are as follows:
1. Quantum Lower Bounds. We provide the first formal analysis showing that a -round KAC is quantum-secure in both the and models. Specifically, in the model, a (non-adaptive) adversary must make at least quantum queries to the public permutations and at least classical queries to the cipher in order to distinguish it from a random permutation (in contrast to the classical lower bound of queries). As a corollary, we show that in the model, a (non-adaptive) adversary requires quantum queries. To achieve such a result, we employ the quantum hybrid method along with recently proposed lifting theorems in the ideal cipher and random permutation oracle model.
2. Quantum Key-Recovery Attack. We give the first nontrivial quantum key-recovery attack on multi-round KAC in the model where the adversary has quantum access to all of the public permutations. Our quantum attack applies to any -round KAC and achieves quantum query complexity , where , improving over the best known classical bound of , where , from Bogdanov et al. (EUROCRYPT 2012). The attack leverages a novel application of quantum walk algorithms specifically adapted to the KAC structure.
3. The Model. To bridge the classical and settings, we introduce the , in which the adversary has quantum superposition access to at most one permutation. This model is crucial for our lower bound and supports similar key-recovery attacks to Q1, using fewer quantum resources. We believe is of independent interest
Zero-knowledge Authenticator for Blockchain: Policy-private and Obliviously Updateable
Get PDFTransaction details and participant identities on the blockchain are often publicly exposed. In this work, we posit that blockchain\u27s transparency should not come at the cost of privacy. To that end, we introduce zero-knowledge authenticators (zkAt), a new cryptographic primitive for privacy-preserving authentication on public blockchains. zkAt utilizes zero-knowledge proofs to enable users to authenticate transactions, while keeping the underlying authentiction policies private.
Prior solutions for such {policy-private authentication} required the use of threshold signatures, which can only hide the threshold access structure itself. In comparison, zkAt provides privacy for arbitrarily complex authentication policies, and offers a richer interface even within the threshold access structure by, for instance, allowing for the combination of signatures under distinct signature schemes.
In order to construct zkAt, we design a compiler that transforms the popular Groth16 non-interactive zero knowledge (NIZK) proof system into a NIZK with equivocable verification keys, a property that we define in this work. Then, for any zkAt constructed using proof systems with this new property, we show that all public information must be independent of the policy, thereby achieving policy-privacy.
Next, we give an extension of zkAt, called zkAt+ wherein, assuming a trusted authority, policies can be updated obliviously in the sense that a third-party learns no new information when a policy is updated by the policy issuer. We also give a theoretical construction for zkAt+ using recursive NIZKs, and explore the integration of zkAt into modern blockchains. Finally, to evaluate their feasibility, we implement both our schemes for a specific threshold access structure. Our findings show that zkAt achieves comparable performance to traditional threshold signatures, while also attaining privacy for significantly more complex policies with very little overhead
The Accidental Computer: Polynomial Commitments from Data Availability
Get PDFIn this paper, we show two simple variations of a data availability scheme which enable it to act as a multilinear polynomial commitment scheme over the data in a block. The first variation enables commitments over all of the block\u27s data with zero prover overhead: the data availability construction simply serves both purposes. The second variation allows commitments over subsets of data with nonzero but still concretely small proving costs, since most work is already done during data encoding. This works especially well for blockchains with a high degree of data parallelism, as data-parallel computation is particularly amenable to efficient GKR proofs. Since, in GKR, opening the polynomial commitment contributes significantly to prover costs, our construction enables the prover to reuse work already done by the data availability scheme, reducing—or wholly removing—work associated with the polynomial commitment scheme
Enforcing arbitrary constraints on Bitcoin transactions
Get PDFThe challenge of enforcing constraints on Bitcoin transac-
tions has recently gained a lot of attention. The current approach to
solve this problem falls short in certain aspects, such as privacy and
programmability. We design a new solution that leverages zkSNARKs
and allows enforcing arbitrary constraints on Bitcoin transactions while
maintaining some information private. Our approach also bypasses the
non-Turing completeness of Bitcoin Script, allowing the enforcement of
unbounded constraints, namely constraints that repeat a certain opera-
tion an unbounded number of times
Adaptively Secure Blockchain-Aided Decentralized Storage Networks: Formalization and Generic Construction
Get PDFA decentralized storage network (DSN) enables clients to delegate data to servers, where the data must be retained custody for a jointly agreed contract period. Most existing constructions employ proof-of-replication (PoRep) iteratively to provide verifiable guarantees during this period. However, the original PoRep security model does not account for iterative invocation, particularly when aided by a blockchain that serves as an external repository of auxiliary information. Similar concerns arise for another key DSN functionality, i.e., data retrieval, where malicious parties may exploit previous and parallel sessions to undermine fairness.
This work addresses these gaps by formalizing the syntax and adaptive security of blockchain-aided DSN protocols, presenting, to the best of our knowledge, the first formal treatment. Building on this foundation, we propose a generic construction that leverages an Extended UTxO (EUTxO) ledger, automating protocol execution by embedding the required verification into EUTxO\u27s validation logic.
We further prove that the succinctness and non-malleability of the underlying proof system suffice for adaptive security. Our experiments corroborate this: systems lacking these properties are vulnerable to adaptive attacks, e.g., servers offloading storage while still producing valid PoRep proofs
Decentralized Multi-Authority Attribute-Based Inner-Product Functional Encryption: Noisy and Evasive Constructions from Lattices
Get PDFWe initiate the study of multi-authority attribute-based functional encryption for noisy inner-product functionality, and propose two new primitives: (1) multi-authority attribute-based (noisy) inner-product functional encryption (MA-AB(N)IPFE), and (2) multi-authority attribute-based evasive inner-product functional encryption (MA-ABevIPFE). The MA-AB(N)IPFE primitive generalizes the existing multi-authority attribute-based inner-product functional encryption schemes by Agrawal et al. [AGT21], by enabling approximate inner-product computation under decentralized attribute-based control. This newly proposed notion combines the approximate function evaluation of noisy inner-product functional encryption (IPFE) with the decentralized key-distribution structure of multi-authority attribute-based encryption. To better capture noisy functionalities within a flexible security framework, we formulate the MA-ABevIPFE primitive under a generic-model view, inspired by the evasive IPFE framework by Hsieh et al. [HLL24]. It shifts the focus from pairwise ciphertext indistinguishability to a more relaxed pseudorandomness-based game.
To support the above notions, we introduce two variants of lattice-based computational assumptions:
- The evasive IPFE assumption (evIPFE): it generalizes the assumption introduced in [HLL24] to the multi-authority setting and admits a reduction from the evasive LWE assumption proposed by Waters et al. [WWW22];
- The indistinguishability-based evasive IPFE assumption (IND-evIPFE): it is an indistinguishability-based variant of the evasive IPFE assumption designed to capture the stronger security guarantees required by our MA-AB(N)IPFE scheme.
We present concrete lattice-based constructions for both primitives supporting subset policies, building upon the framework of [WWW22]. Our schemes are proven to be statically secure in the random oracle model under the standard LWE assumption and the newly introduced assumptions. Additionally, we demonstrate that our MA-AB(N)IPFE scheme can be transformed, via standard modulus switching, into a noiseless MA-ABIPFE scheme that supports exact inner-product functionality consistent with the MA-IPFE syntax in [AGT21,DP23]. This yields the first lattice-based construction of such a primitive. All our schemes support arbitrary polynomial-size attribute policies and are secure in the random oracle model under lattice assumptions with a sub-exponential modulus-to-noise ratio, making them practical candidates for noise-tolerant, fine-grained access control in multi-authority settings