The secure management of private keys is a fundamental challenge, particularly for the general public, as losing these keys can result in irreversible asset loss. Traditional custodial approaches pose security risks, while decentralized secret sharing schemes offer a more resilient alternative by distributing trust among multiple parties. In this work, we extend an existing decentralized, verifiable, and extensible cryptographic key recovery scheme based on Shamir's secret sharing. We...

In this paper, we study practical constructions of asynchronous distributed key reconfiguration ($\mathsf{ADKR}$), which enables an asynchronous fault-tolerant system with an existing threshold cryptosystem to efficiently generate a new threshold cryptosystem for a reconfigured set of participants. While existing asynchronous distributed threshold key generation ($\mathsf{ADKG}$) protocols theoretically solve $\mathsf{ADKR}$, they fail to deliver satisfactory scalability due to cubic...

We present a new construction of two-party, threshold ECDSA, building on a 2017 scheme of Lindell and improving his scheme in several ways. ECDSA signing is notoriously hard to distribute securely, due to non-linearities in the signing function. Lindell's scheme uses Paillier encryption to encrypt one party's key share and handle these non-linearities homomorphically, while elegantly avoiding any expensive zero knowledge proofs over the Paillier group during the signing process. However,...

The seminal work of Rabin and Ben-Or (STOC'89) showed that the problem of secure $n$-party computation can be solved for $t<n/2$ corruptions with guaranteed output delivery and statistical security. This holds in the traditional static model where the set of parties is fixed throughout the entire protocol execution. The need to better capture the dynamics of large scale and long-lived computations, where compromised parties may recover and the set of parties can change over time, has...

FAPI 2.0 is a suite of Web protocols developed by the OpenID Foundation's FAPI Working Group (FAPI WG) for third-party data sharing and digital identity in high-risk environments. Even though the specifications are not completely finished, several important entities have started to adopt the FAPI 2.0 protocols, including Norway's national HelseID, Australia's Consumer Data Standards, as well as private companies like Authlete and Australia-based connectID; the predecessor FAPI 1.0 is in...

The strength of Elliptic curve cryptography (ECC) relies on curve choice. This work analyzes weak keys in standardized curves, i.e., private keys within small subgroups of the auxiliary group $\mathbb{Z}^*_p$. We quantify weak key prevalence across standardized curves, revealing a potential vulnerability due to numerous small divisors in auxiliary group orders. To address this, we leverage the implicit "baby-steps giant-steps algorithm", which transforms the complex elliptic curve discrete...

A threshold signature scheme distributes the ability to generate signatures through distributed key generation and signing protocols. A threshold signature scheme should be functionally interchangeable, meaning that a signature produced by a threshold scheme should be verifiable by the same algorithm used for non-threshold signatures. To resist future attacks from quantum adversaries, lattice-based threshold signatures are desirable. However, the performance of existing lattice-based...

Threshold signatures enable any subgroup of predefined cardinality $t$ out of a committee of $n$ participants to generate a valid, aggregated signature. Although several $(t,n)$-threshold signature schemes exist, most of them assume that the threshold $t$ and the set of participants do not change over time. Practical applications of threshold signatures might benefit from the possibility of updating the threshold or the committee of participants. Examples of such applications are...

In a federated learning (FL) system, decentralized data owners (clients) could upload their locally trained models to a central server, to jointly train a global model. Malicious clients may plant backdoors into the global model through uploading poisoned local models, causing misclassification to a target class when encountering attacker-defined triggers. Existing backdoor defenses show inconsistent performance under different system and adversarial settings, especially when the malicious...

This paper examines the vulnerabilities inherent in prevailing Public Key Infrastructure (PKI) systems reliant on centralized Certificate Authorities (CAs), wherein a compromise of the CA introduces risks to the integrity of public key management. We present PKChain, a decentralized and compromise-tolerant public key management system built on blockchain technology, offering transparent, tamper-resistant, and verifiable services for key operations such as registration, update, query,...

Amid the landscape of confidential computing, where security and privacy reign supreme, PRIVATON emerges as a pioneering and practical solution to safeguard sensitive data and computations. A verifiable proof of computation model, with one of its variant built upon the dual sandbox strategy, PRIVATON combines Trusted Execution Environment (TEE) technologies with WebAssembly (WASM) runtime environments to establish an ecosystem for privacy-preserving computations. This approach involves fine...

The advent of quantum computers poses a serious challenge to the security of cloud infrastructures and services, as they can potentially break the existing public-key cryptosystems, such as Rivest–Shamir–Adleman (RSA) and Elliptic Curve Cryptography (ECC). Even though the gap between today’s quantum computers and the threats they pose to current public-key cryptography is large, the cloud landscape should act proactively and initiate the transition to the post-quantum era as early as...

This paper presents the first protocols for Proactive Secret Sharing (PSS) that only require constant (in the number of parties, $n$) communication per party per epoch. By harnessing the power of expander graphs, we are able to obtain strong guarantees about the security of the system. We present the following PSS protocols: – A PSS protocol that provides privacy (but no robustness) against an adversary controlling $O(n)$ parties per epoch. – A PSS protocol that provides robustness (but no...

A Single Sign-On (SSO) system allows users to access different remote services while authenticating only once. SSO can greatly improve the usability and security of online activities by dispensing with the need to securely remember or store tens or hundreds of authentication secrets. On the downside, today's SSO providers can track users' online behavior, and collect personal data that service providers want to see asserted before letting a user access their resources. In this work, we...

We propose hinTS --- a new threshold signature scheme built on top of the widely used BLS signatures. Our scheme enjoys the following attractive features: \begin{itemize} \item A {\em silent setup} process where the joint public key of the parties is computed as a deterministic function of their locally computed public keys. \item Support for {\em dynamic} choice of thresholds and signers, after the silent setup, without further interaction. \item Support for {\em general}...

We describe high-throughput threshold protocols with guaranteed output delivery for generating Schnorr-type signatures. The protocols run a single message-independent interactive ephemeral randomness generation procedure (e.g., DKG) followed by a \emph{non-interactive} multi-message signature generation procedure. The protocols offer significant increase in throughput already for as few as ten parties while remaining highly-efficient for many hundreds of parties with thousands of signatures...

The classical "BGW protocol" (Ben-Or, Goldwasser and Wigderson, STOC 1988) shows that secure multiparty computation (MPC) among $n$ parties can be realized with perfect full security if $t < n/3$ parties are corrupted. This holds against malicious adversaries in the "standard" model for MPC, where a fixed set of $n$ parties is involved in the full execution of the protocol. However, the picture is less clear in the mobile adversary setting of Ostrovsky and Yung (PODC 1991), where the...

The production of modern integrated circuit (IC) requires a complex, outsourced supply chain involving computer-aided design (CAD) tools, expert knowledge, and advanced foundries. This complexity has led to various security threats, such as Trojans inserted by adversaries during outsourcing, and physical probing or manipulation of devices at run-time. Our proposed solution, DEFense is an extensible CAD framework for evaluating and proactively mitigating threats to IC at the design-time...

An accountable threshold signature (ATS) is a threshold signature scheme where every signature identifies the quorum of signers who generated that signature. They are widely used in financial settings where signers need to be held accountable for threshold signatures they generate. In this paper we initiate the study of proactive refresh for accountable threshold signatures. Proactive refresh is a protocol that lets the group of signers refresh their shares of the secret key, without...

With the emergence of decentralized systems, spearheaded by blockchains, threshold cryptography has seen unprecedented adoption. Just recently, the trustless distribution of threshold keys over an unreliable network has started to become practical. The next logical step is ensuring the security of these keys against persistent adversaries attacking the system over long periods of time. In this work, we tackle this problem and give two practical constructions for Asynchronous Proactive...

Passwords are difficult to remember, easy to guess and prone to hacking. While there have been several attempts to solve the aforementioned problems commonly associated with passwords, one of the most successful ones to date has been by the Fast Identity Online (FIDO) alliance. FIDO introduced a series of protocols that combine local authentication on a user device with remote validation on relying party servers using public-key cryptography. One of the fundamental problems of FIDO...

Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted party. DKG is an essential building block to many decentralized protocols such as randomness beacons, threshold signatures, Byzantine consensus, and multiparty computation. While significant progress has been made recently, existing asynchronous DKG constructions are inefficient when the reconstruction threshold is larger than one-third of the total nodes. In this paper, we present a simple...

Dynamic-committee proactive secret sharing (DPSS) enables the refresh of secret shares and the alternation of shareholders without changing the secret. Such a proactivization functionality makes DPSS a promising technology for long-term key management and committee governance. In non-asynchronous networks, CHURP (CCS ’19) and COBRA (S&P ’22) have achieved best-case square and cubic communication cost, respectively, w.r.t. the number of shareholders. However, the overhead of asynchronous DPSS...

Public blockchains are state machines replicated via distributed consensus protocols. Information on blockchains is public by default---marking privacy as one of the key challenges. We identify two shortcomings of existing approaches to building blockchains for general privacy-preserving applications, namely (1) the reliance on external trust assumptions and (2) the dependency on execution environments (on-chain, off-chain, zero-knowledge, etc.) with heterogeneous programming...

Secret sharing is an essential tool for many distributed applications, including distributed key generation and multiparty computation. For many practical applications, we would like to tolerate network churn, meaning participants can dynamically enter and leave the pool of protocol participants as they please. Such protocols, called Dynamic-committee Proactive Secret Sharing (DPSS), have recently been studied; however, existing DPSS protocols do not gracefully handle faults: the presence...

As the most dominant authentication mechanism, password-based authentication suffers catastrophic offline password guessing attacks once the authentication server is compromised and the password database is leaked. Password hardening (PH) service, an external/third-party crypto service, has been recently proposed to strengthen password storage and reduce the damage of authentication server compromise. However, all existing schemes are unreliable because they overlook the important restorable...

Protocols for state machine replication (SMR) are typically designed for synchronous or asynchronous networks, with a lower corruption threshold in the latter case. Recent network-agnostic protocols are secure when run in either a synchronous or an asynchronous network. We propose two new constructions of network-agnostic SMR protocols that improve on existing protocols in terms of either the adversarial model or communication complexity: 1. an adaptively secure protocol with optimal...

A proactive secret sharing scheme (PSS), expressed in the dynamic-membership setting, enables a committee of n holders of secret-shares, dubbed as players, to securely hand-over new shares of the same secret to a new committee. We dub such a sub-protocol as a Refresh. All existing PSS under an honest majority, require the use of a broadcast (BC) in each refresh. BC is costly to implement, and its security relies on timing assumptions on the network. So the privacy of the secret and/or its...

Achieving adaptive (or proactive) security in cryptographic protocols is notoriously difficult due to the adversary's power to dynamically corrupt parties as the execution progresses. Inspired by the work of Benhamouda et al. in TCC 2020, Gentry et al. in CRYPTO 2021 introduced the YOSO (You Only Speak Once) model for constructing adaptively (or proactively) secure protocols in massively distributed settings (e.g. blockchains). In this model, instead of having all parties execute an entire...

We present Shanrang, the first fully asynchronous proactive secret sharing scheme with dynamic committee support. Even in the worst possible network environment, where messages could have arbitrary latencies, Shanrang allows a dynamic committee to store a secret and periodically refresh the secret shares in a distributed fashion. When the committee changes, both the old committee and the new committee jointly refresh and transfer the shares to the new committee, without revealing the secret...

This work considers two prominent key management problems in the blockchain space: (i) allowing a (distributed) blockchain system to securely airdrop/send some tokens to a potential client Bob, who is yet to set up the required cryptographic key for the system, and (ii) creating a (distributed) cross-chain bridge that allows interoperability at scale by allowing a (changing) set of nodes in a blockchain to perform transactions on the other blockchain. The existing solutions for the first...

We look at two basic coding theoretic and cryptographic mechanisms developed separately and investigate relationships between them and their implications. The first mechanism is Proactive Secret Sharing (PSS), which allows randomization and repair of shares using information from other shares. PSS enables constructing secure multi-party computation protocols that can withstand mobile dynamic attacks. This self-recovery and the redundancy of uncorrupted shares allows a system to overcome...

This paper presents an Identifiable Cheating Entity (ICE) FROST signature protocol that is an improvement over the FROST signature scheme (Komlo and Goldberg, SAC 2020) since it can identify cheating participants in its Key Generation protocol. The proposed threshold signature protocol achieves robustness in the Key Generation phase of the threshold signature protocol by introducing a cheating identification mechanism and then excluding cheating participants from the protocol. By enabling...

We study zero-knowledge arguments where proofs are: of knowledge, short, publicly-verifiable and produced without interaction. While zkSNARKs satisfy these requirements, we build such proofs in a constrained theoretical setting: in the standard-model---i.e., without a random oracle---and without assuming public-verifiable SNARKs (or even NIZKs, for some of our constructions) or primitives currently known to imply them. We model and construct a new primitive, SPuC (Succinct...

Secure multiparty computation (MPC) has recently been increasingly adopted to secure cryptographic keys in enterprises, cloud infrastructure, and cryptocurrency and blockchain-related settings such as wallets and exchanges. Using MPC in blockchains and other distributed systems highlights the need to consider dynamic settings. In such dynamic settings, parties, and potentially even parameters of underlying secret sharing and corruption tolerance thresholds of sub-protocols, may change over...

Multiparty computation does not tolerate $n/3$ corruptions under a plain asynchronous communication network, whatever the computational assumptions. However, Beerliová-Hirt-Nielsen [BHN, Podc'10] showed that, assuming access to a synchronous broadcast at the beginning of the protocol, enables to tolerate up to $t<n/2$ corruptions. This model is denoted as ``Almost asynchronous'' MPC. Yet, their work [BHN] has limitations: (i) \emph{Setup assumptions:} their protocol is based on an encryption...

We present a non-interactive publicly verifiable secret sharing scheme where a dealer can construct a Shamir secret sharing of a field element and confidentially yet verifiably distribute shares to multiple receivers. We also develop a non-interactive publicly verifiable resharing scheme where existing share holders of a Shamir secret sharing can create a new Shamir secret sharing of the same secret and distribute it to a set of receivers in a confidential, yet verifiable manner. A public...

Edge computing and caching have emerged as key technologies in the future communication network to enhance the user experience, reduce backhaul traffic, and enable various Internet of Things applications. Different from conventional resources like CPU and memory that can be utilized by only one party at a time, a cached data item, which can be considered as a public good, can serve multiple parties simultaneously. Therefore, instead of independent caching, it is beneficial for the parties...

Due to their use in crypto-currencies, threshold ECDSA signatures have received much attention in recent years. Though efficient solutions now exist both for the two party, and the full threshold scenario, there is still much room for improvement, be it in terms of protocol functionality, strengthening security or further optimising efficiency. In the past few months, a range of protocols have been published, allowing for a non interactive -- and hence extremely efficient -- signing...

We present a novel approach for blockchain asset owners to reclaim their funds in case of accidental private-key loss or transfer to a mistyped address. Our solution can be deployed upon failure or absence of proactively implemented backup mechanisms, such as secret sharing and cold storage. The main advantages against previous proposals is it does not require any prior action from users and works with both single-key and multi-sig accounts. We achieve this by a 3-phase Commit() -> Reveal()...

We present a distributed ECDSA protocol, for any number of signatories. The protocol improves on that of the authors (CCS'20), which in turn builds on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS '18). Specifically: ** Only the last round of the protocol requires knowledge of the message, and the other rounds can take place in a preprocessing stage, lending to a non-interactive threshold ECDSA protocol. ** The protocol withstands adaptive corruption of signatories....

Power-based side-channel leakage is a known problem in the design of security-centric electronic systems. As the complexity of modern systems rapidly increases through the use of System-on-Chip (SoC) integration, it becomes difficult to determine the precise source of the side-channel leakage. Designers of secure SoC must therefore proactively apply expensive countermeasures to protect entire subsystems such as encryption modules, and this increases the design cost of the chip. We propose a...

Internet of Things is developing at a very fast rate. In order to ensure security and privacy, end-devices (e.g. smartphones, smart sensors, or any connected smartcards) shall be protected both against cyber attacks (coming down from the network) and against physical attacks (arising from attacker low-level interaction with the device). In this context, proactive protections shall be put in place to mitigate information theft from either side-channel monitoring or active computation/data...

In modern distributed systems, an adversary’s limitations when corrupting subsets of servers may not necessarily be based on threshold constraints, but rather based on other technical or organizational characteristics in the systems. This means that the corruption patterns (and thus protection guarantees) are not based on the adversary being limited by a threshold, but on the adversary being limited by other constraints, in particular by what is known as a General Adversary Structure (GAS)....

This paper exposes a new vulnerability and introducesa corresponding attack, the NoneXistent Name ServerAttack (NXNSAttack), that disrupts and may paralyzethe DNS system making it difficult or impossible for In-ternet users to access websites, web e-mail, online videochats, or any other online resource. The NXNSAttackgenerates a storm of packets between DNS resolvers andDNS authoritative name servers. The storm is producedby the response of resolvers to unrestricted referral re-sponse...

In this paper we present a series of applications steming from a formal treatment of linear secret-sharing isomorphisms, which are linear transformations between different secret-sharing schemes defined over vector spaces over a field $\mathbb{F}$ and allow for efficient multiparty conversion from one secret-sharing scheme to the other. This concept generalizes the folklore idea that moving from a secret-sharing scheme over $\mathbb{F}_{p}$ to a secret sharing ``in the exponent'' can be done...

Multiple protocols implementing exciting cryptographic functionalities using blockchains such as time-lock encryption, one-time programs and fair multi-party computation assume the existence of a cryptographic primitive called extractable witness encryption. Unfortunately, there are no known efficient constructions (or even constructions based on any well studied assumptions) of extractable witness encryption. In this work, we propose a protocol that uses a blockchain itself to provide a...

Building on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS ’18), we present a threshold ECDSA protocol, for any number of signatories and any threshold, that improves as follows over the state of the art: * Signature generation takes only 4 rounds (down from the current 8 rounds), with a comparable computational cost. Furthermore, 3 of these rounds can take place in a preprocessing stage before the signed message is known, lending to a non-interactive threshold ECDSA protocol. *...

Blockchains are gaining traction and acceptance, not just for cryptocurrencies, but increasingly as an architecture for distributed computing. In this work we seek solutions that allow a \emph{public} blockchain to act as a trusted long-term repository of secret information: Our goal is to deposit a secret with the blockchain, specify how it is to be used (e.g., the conditions under which it is released), and have the blockchain keep the secret and use it only in the specified manner (e.g.,...

Single Sign-On (SSO) is becoming an increasingly popular authentication method for users that leverages a trusted Identity Provider (IdP) to bootstrap secure authentication tokens from a single user password. It alleviates some of the worst security issues of passwords, as users no longer need to memorize individual passwords for all service providers, and it removes the burden of these service to properly protect huge password databases. However, SSO also introduces a single point of...

In standard Secret Sharing (SS), a dealer shares a secret $s$ among $n$ parties such that an adversary corrupting no more than $t$ parties does not learn $s$, while any $t+1$ parties can efficiently recover $s$. Proactive Secret Sharing (PSS) retains confidentiality of $s$ even when a mobile adversary corrupts all parties over the lifetime of the secret, but no more than a threshold $t$ in each epoch (called a refresh period). Withstanding such adversaries has become of increasing...

Proactive security is the notion of defending a distributed system against an attacker who compromises different devices through its lifetime, but no more than a threshold number of them at any given time. The emergence of threshold wallets for more secure cryptocurrency custody warrants an efficient proactivization protocol tailored to this setting. While many proactivization protocols have been devised and studied in the literature, none of them have communication patterns ideal for...

Secure Multiparty Computation (MPC) enables a group of $n$ distrusting parties to jointly compute a function using private inputs. MPC guarantees correctness of computation and confidentiality of inputs if no more than a threshold $t$ of the parties are corrupted. Proactive MPC (PMPC) addresses the stronger threat model of a mobile adversary that controls a changing set of parties (but only up to $t$ at any instant), and may eventually corrupt all $n$ parties over a long time. This paper...

We introduce CHURP (CHUrn-Robust Proactive secret sharing). CHURP enables secure secret-sharing in dynamic settings, where the committee of nodes storing a secret changes over time. Designed for blockchains, CHURP has lower communication complexity than previous schemes: $O(n)$ on-chain and $O(n^2)$ off-chain in the optimistic case of no node failures. CHURP includes several technical innovations: An efficient new proactivization scheme of independent interest, a technique (using asymmetric...

In a network of $n$ nodes (modelled as a digraph), the goal of a perfectly secret message transmission (PSMT) protocol is to replicate sender's message $m$ at the receiver's end without revealing any information about $m$ to a computationally unbounded adversary that eavesdrops on any $t$ nodes. The adversary may be mobile too -- that is, it may eavesdrop on a different set of $t$ nodes in different rounds. We prove a necessary and sufficient condition on the synchronous network for the...

SSH is a security network protocol that uses public key cryptography for client authentication. SSH connections are designed to be run between a client and a server and therefore in enterprise networks there is no centralized monitoring of all SSH connections. An attractive method for enforcing such centralized control, audit or even revocation is to require all clients to access a centralized service in order to obtain their SSH keys. Doing this will introduce security and availability...

We put forward the notion of self-guarding cryptographic protocols as a countermeasure to algorithm substitution attacks. Such self-guarding protocols can prevent undesirable leakage by subverted algorithms if one has the guarantee that the system has been properly working in an initialization phase. Unlike detection-based solutions they thus proactively thwart attacks, and unlike reverse firewalls they do not assume an online external party. We present constructions of basic primitives for...

In this work we provide a framework for dynamic secret sharing and present the first dynamic and verifiable hierarchical secret sharing scheme based on Birkhoff interpolation. Since the scheme is dynamic it allows, without reconstructing the message distributed, to add and remove shareholders, to renew shares, and to modify the conditions for accessing the message. Furthermore, each shareholder can verify its share received during these algorithms protecting itself against malicious dealers...

The secure storage of long-lived sensitive data is constantly growing in its relevance due to the ever increasing digitization of documents. One very important challenge of this research field is to provide confidentiality for the stored data even in the long term. The only known approach to achieve this, as required, for instance, for medical records, is to use proactive secret sharing. However, all currently known schemes suffer from being inefficient. They require information-theoretic...

Software-update mechanisms are critical to the security of modern systems, but their typically centralized design presents a lucrative and frequently attacked target. In this work, we propose CHAINIAC, a decentralized software-update framework that eliminates single points of failure, enforces transparency, and provides efficient verifiability of integrity and authenticity for software-release processes. Independent $\textit{witness servers}$ collectively verify conformance of software...

A service may be implemented over several servers, and those servers may become compromised by an attacker, e.g. through software vulnerabilities. When this happens, the service manager will remove the vulnerabilities and re-instate the server. Typically, this will involve regenerating the public key by which clients authenticate the service, and revoking the old one. This paper presents a scheme which allows a storage service composed of several servers to create a group public key in a...

The amount of digital data that requires long-term protection of integrity, authenticity, and confidentiality grows rapidly. Examples include electronic health records, genome data, and tax data. In this paper we present the secure storage system LINCOS, whichprovides protection of integrity, authenticity, and confidentiality in the long-term, i.e., for an indefinite time period. It is the first such system. It uses the long-term integrity scheme COPRIS, which is also presented here and is...

Besides security against classical cryptanalysis, its important for cryptographic implementations to have sufficient robustness against side-channel attacks. Many countermeasures have been proposed to thwart side channel attacks, especially power trace measurement based side channel attacks. Additionally, researchers have proposed several evaluation metrics to evaluate side channel security of crypto-system. However, evaluation of any crypto-system is done during the testing phase and is not...

Proactive secret sharing (PSS) schemes are designed for settings where long-term confidentiality of secrets has to be guaranteed, specifically, when all participating parties may eventually be corrupted. PSS schemes periodically refresh secrets and reset corrupted parties to an uncorrupted state; in PSS the corruption threshold $t$ is replaced with a corruption rate which cannot be violated. In dynamic proactive secret sharing (DPSS) the number of parties can vary during the course of...

Secure Multiparty Computation (MPC) protocols allow a set of distrusting participants to securely compute a joint function of their private inputs without revealing anything but the output of the function to each other. In 1991 Ostrovsky and Yung introduced the \emph{proactive security model}, where faults spread throughout the network, analogous to the spread of a virus or a worm. More specifically, in the proactive security model, the adversary is not limited in the number of parties it...

A $(t+1,n)$ proactive secret sharing is to protect a secret in long-lived system by distributing it to a group of $n$ participants and refreshing their shares periodically in this fixed group, while any $t+1$ and more than $t+1$ shares can reconstruct the secret. In some environment, it needs to change not only the number of participants $n$ but also the threshold value $t$. An adaptive proactive secret sharing is to refresh the shares as $t$ and $n$ change. In this paper, we propose a...

Pseudo-basis is a powerful and fundamental concept in coding theory, introduced by Kurosawa and Suzuki (EUROCRYPT '08), which allows to efficiently localize t errors in a codeword in an interactive fashion, even by using a linear error correcting code with distance only t+1. It is used to construct the first efficient, communication and round optimal, 2-round perfectly secure message transmission (PSMT) scheme for n=2t+1, where an infinitely powerful adversary can actively corrupt t out of n...

In this paper, we investigate how to achieve verifiable secret sharing (VSS) schemes by using the Chinese Remainder Theorem (CRT). We first show that two schemes proposed earlier are not secure from an attack where the dealer is able to distribute inconsistent shares to the users. Then we propose a new VSS scheme based on the CRT and prove its security. Using the proposed VSS scheme, we develop joint random secret sharing~(JRSS) and proactive SSS protocols, which, to the best of our...

We introduce the notion of a Social Secret Sharing Scheme, in which shares are allocated based on a player's reliability and the way he interacts with other participants. During the share refresh phase, weights of participants are adjusted in a way that participants who cooperate will end up with more shares than those who defect. On the other hand, corrupted players will be disenrolled immediately for the computation safety. Our motivation is that, in real world applications, components of...

In~\cite{DT07} Damgard and Thorbek proposed the linear integer secret sharing (LISS) scheme. In this note we show that the LISS scheme can be made proactive.

(Full version of a PKC 2009 paper) We take a step towards a more realistic modeling of personal digital signatures, where a human user, his mobile equipment, his PC and a server are all considered as independent players in the protocol, and where only the human user is assumed incorruptible. We then propose a protocol for issuing digital signatures on behalf of the user. This protocol is proactively UC-secure assuming at most one player is corrupted in every operational phase. In more...

In dynamic networks with flexible memberships, group signatures and distributed signatures are an important problem. Dynamic threshold cryptosystems are best suited to realize distributed signatures in dynamic (e.g. meshed) networks. Without a group manager or a trusted third party even more flexible scenarios can be realized. Gennaro et al. showed, it is possible to dynamically increase the size of the signer group, without altering the public key. We extend this idea by removing members...

Erasing old data and keys is an important tool in cryptographic protocol design. It is useful in many settings, including proactive security, adaptive security, forward security, and intrusion resilience. Protocols for all these settings typically assume the ability to perfectly erase information. Unfortunately, as amply demonstrated in the systems literature, perfect erasures are hard to implement in practice. We propose a model of partial erasures where erasure instructions leave almost...

The notion of Signer-Base Intrusion-Resilient (SiBIR) signatures was introduced in [IR02] as a scheme that can withstand an arbitrary number of key-exposures, as long as both of its modules are not compromised simultaneously. This was achieved by dividing time into predefined time periods, each corresponding to a different time-evolving secret key, while maintaining a constant public key. The two modules of this scheme consist of a signer that can generate signatures on its own, and a base...

We construct a reasonably efficient threshold and proactive pseudo-random permutation (PRP). Our protocol needs only O(1) communication rounds. It tolerates up to (n-1)/2 of n dishonest servers in the semi-honest environment. Many protocols that use PRPs (e.g., a CBC block cipher mode) can now be translated into the distributed setting. Our main technique for constructing invertible threshold PRPs is a distributed Luby-Rackoff construction where both the secret keys *and* the input are...

We give a simple and efficient construction of a verifiable random function (VRF) on bilinear groups. Our construction is direct. In contrast to prior VRF constructions [MRV99, Lys02], it avoids using an inefficient Goldreich-Levin transformation, thereby saving several factors in security. Our proofs of security are based on a decisional bilinear Diffie-Hellman inversion assumption, which seems reasonable given current state of knowledge. For small message spaces, our VRF's proofs and keys...

Nowadays, to model practical systems better, such as the Internet network and ad hoc networks, researchers usually regard these systems as asynchronous networks. Meanwhile, proactive secret sharing schemes are often employed to tolerate a mobile adversary. Considering both aspects, an asynchronous proactive threshold signature scheme is needed to keep computer systems secure. So far, two asynchronous proactive secret sharing schemes have been proposed. One is proposed by Zhou in 2001, which...

Verifiable secret sharing schemes (VSS) are secret sharing schemes (SSS) dealing with possible cheating by participants. In this paper we use the VSS proposed by Cramer, Damgard and Maurer \cite{CDM99,CDM00,Cra00}. They introduced a purely linear algebraic method to transform monotone span program (MSP) based secret sharing schemes into VSS. In fact, the monotone span program model of Karchmer and Wigderson \cite{KW93} deals with arbitrary monotone access structures and not just threshold...

Verifiable secret sharing is an important primitive in distributed cryptography. With the growing interest in the deployment of threshold cryptosystems in practice, the traditional assumption of a synchronous network has to be reconsidered and generalized to an asynchronous model. This paper proposes the first \emph{practical} verifiable secret sharing protocol for asynchronous networks. The protocol creates a discrete logarithm-based sharing and uses only a quadratic number of messages in...

We propose a robust proactive threshold signature scheme, a multisignature scheme and a blind signature scheme which work in any Gap Diffie-Hellman (GDH) group (where the Computational Diffie-Hellman problem is hard but the Decisional Diffie-Hellman problem is easy). Our constructions are based on the recently proposed GDH signature scheme of Boneh et al. \cite{bls}. Due to the instrumental structure of GDH groups and of the base scheme, it turns out that most of our constructions are...

We consider threshold cryptosystems over a composite modulus $N$ where the \emph{factors} of $N$ are shared among the participants as the secret key. This is a new paradigm for threshold cryptosystems based on a composite modulus, differing from the typical treatment of RSA-based systems where a ``decryption exponent'' is shared among the participants. Our approach yields solutions to some open problems in threshold cryptography; in particular, we obtain the following: 1. \emph{Threshold...

In his well-known Information Dispersal Algorithm paper, Rabin showed a way to distribute information in n pieces among n servers in such a way that recovery of the information is possible in the presence of up to t inactive servers. An enhanced mechanism to enable construction in the presence of malicious faults, which can intentionally modify their pieces of the information, was later presented by Krawczyk. Yet, these methods assume that the malicious faults occur only at reconstruction...

We study the problem of maintaining authenticated communication over untrusted communication channels, in a scenario where the communicating parties may be occasionally and repeatedly broken into for transient periods of time. Once a party is broken into, its cryptographic keys are exposed and perhaps modified. Yet, we want parties whose security is thus compromised to regain their ability to communicate in an authenticated way aided by other parties. In this work we present a mathematical...

We consider a "mobile adversary" which may corrupt all participants throughout the lifetime of the system in a non-monotonic fashion (i.e. recoveries are possible) but the adversary is unable to corrupt too many participants during any short time period. Schemes resiliant to such adverasry are called proactive. We present a proactive RSA system in which a threshold of servers applies the RSA signature (or decryption) function in a distributed manner. Employing new combinatorial and...