Cryptography has been used both, historically and in modern times, as a tool to protect and authenticate information: encryption of messages and storage, and protecting information in usage as well. For the last 30+ years, the notion of Malicious Cryptography has been developed and evolved. The idea behind the notion is that when a cryptographic system is implemented in a larger system, then it can be repurposed to perform tasks beyond its specified goals.

Online surveys are frequently used to collect feedback on sensitive topics, yet most deployed platforms rely on authenticated accounts, cookies, or operator-enforced policies to protect anonymity and limit participation. These approaches offer limited protection against retrospective deanonymization in the event of database compromise. The anonymous survey primitive addresses this problem by enabling authenticated yet anonymous submissions with at-most-once participation per survey, without requiring a trusted setup. Current solutions may however be computationally demanding when aiming for large scale deployment. We revisit this primitive and present CAnonize, a new anonymous survey protocol that considerably improves the efficiency compared to the state of the art, while also relying on weaker computational assumptions and preserving a strong corruption model: our protocol relies solely on the SXDH assumption in asymmetric bilinear groups (q-type assumptions were used before), and offers unlinkability under adaptive corruption of the registration authority, survey authorities, and users, even under full transcript exposure and post-compromise database leakage. We confirm the efficiency benefits and practicality of CAnonize through a prototype implementation in Rust: using the BLS12-381 curves, the running times for submitting and processing a survey response are below 100ms for the user and for the survey authority.

Git services such as GitHub, have been widely used to manage projects and enable collaborations among multiple entities. Just as in messaging and cloud storage, where end-to-end security has been gaining increased attention, such a level of security is also demanded for Git services. Content in the repositories (and the data/code supply-chain facilitated by Git services) could be highly valuable, whereas the threat of system breaches has become routine nowadays. However, existing studies of Git security to date (mostly open source projects) suffer in two ways: they provide only very weak security, and they have a large overhead.

Every computing paradigm involving communication requires new security protocols employing cryptography. For example, the Internet gave rise to TLS/SSL, and Mobile Computing gave rise to End-to-End Encryption protocols. In this paper, we address an emerging IoT paradigm involving beacons attached to things and security protocols associated with this new configuration. Specifically, we address the “Beacon Notification Problem,” a critical IoT paradigm aimed at providing secure and efficient real-time notifications from beacons to their owners. Since the beacon notification problem has not yet been formally defined, we begin by inspecting natural requirements based on the operational setting and establishing correctness, security, and privacy definitions through the use of cryptographic games. To resolve the beacon notification problem, we propose a novel cryptographic tool we call XDHIES, which is a considerable extension of available Diffie-Hellman encryption schemes. We then show a new notification protocol built upon XDHIES and we prove that this cryptographic protocol is secure and private and successfully meets all the above problem's requirements.

Anonymous tokens are, essentially, digital signature schemes that enable issuers to provide users with signatures without learning the user inputs or the final signatures. These primitives allow applications to propagate trust while simultaneously protecting the user identity. They have become a core component for improving the privacy of several real-world applications including ad measurements, authorization protocols, spam detection, and VPNs. In certain applications, it is natural to associate signatures with specific public metadata, ensuring that trust is only propagated with respect to only a certain set of users and scenarios. To solve this, we study the notion of anonymous tokens with public metadata. We present a variant of RSA blind signatures with public metadata where issuers may only generate signatures that verify for a certain choice of public metadata that is a modification of a scheme by Abe and Fujisaki. Our protocol exclusively uses standard cryptography with widely available implementations. We prove security from the one-more RSA assumptions with multiple exponents that we introduce. Furthermore, we provide evidence that the concrete security bounds should be nearly identical to standard RSA blind signatures. We show that our protocol incurs minimal overhead over standard RSA blind signatures and report anonymous telemetry for a real-world deployment to showcase its scalability. Following our work, our protocol has been proposed as a technical specification in an IRTF internet draft.

In this paper, we investigate whether the privacy mechanism of periodically changing the pseudorandom identities of Bluetooth Low Energy (BLE) beacons is sufficient to ensure privacy. We consider a new natural privacy notion for BLE broadcasting beacons which we call ``Timed-sequence- indistinguishability'' of beacons. This new privacy definition is stronger than the well-known indistinguishability, since it considers not just the advertisements' content, but also the advertisements' broadcasting times which are observable in the physical world. We then prove that beacons with periodically changing pseudorandom identities do not achieve timed-sequence- indistinguishability. We do this by presenting a novel privacy attack against BLE beacons, which we call the ``Battery Insertion Attack.'' This new time-based privacy attack can be executed by merely inserting or reinserting the beacon's battery at the adversary's chosen time. We performed this attack against an actually deployed beacon. To mitigate the ``Battery Insertion Attack'' and other attacks associated with periodic signaling, we propose a new countermeasure involving quasi-periodic randomized scheduling of identity changes. We prove that our countermeasure ensures timed-sequence indistinguishability for beacons, thereby enhancing the beacon's privacy. Additionally, we show how to integrate this countermeasure in the attacked system while essentially preserving its feasibility and utility, which is crucial for practical industrial adoption.

The cloud has become pervasive, and we ask: how can we protect cloud data against the cloud itself? For secure user-to-user communication via a cloud server, End-to-End encryption has been formally studied, building on existing TLS channels without requiring new primitives. However, enabling user-to-same-user secure outsourced data storage–solving the analogous problem of “privacy from the server” while (1) relying on existing infrastructure and (2) supporting user mobility, remains open. Existing proposals, like password-protected secret sharing, target the same goal but are incompatible with existing cloud storage services. Specifically, they lack the simplicity needed to directly utilize existing cloud storage without requiring changes on the cloud side. Here, we propose a novel system for securely storing private data in existing cloud storage with the help of a key server (necessary, given the requirements). In our system, user data is secure against threats from the cloud server, the key server, and illegitimate users. Only the legitimate user can access the data on any device using a correct passphrase. Most importantly, our system does not require the storage server to support any newly programmable operations. Moreover, leveraging the existing App login, our system requires only one passphrase, which never leaves the user’s device and remains hidden from both servers. The security is proved under formal models, and its efficiency is demonstrated by experiments conducted on Amazon S3. Notably, a preliminary variant, based on our principles, was deployed by Snapchat in their My Eyes Only module, serving hundreds of millions of users!

The increased adoption of additive manufacturing (AM) and the acceptance of AM outsourcing created an ecosystem in which the sending and receiving of digital designs by different actors became normal. It has recently been shown that the STL design files---most commonly used in AM---contain steganographic channels. Such channels can allow additional data to be embedded within the STL files without changing the printed model. These factors create a threat of misusing the design files as a covert communication channel to either exfiltrate stolen sensitive digital data from organizations or infiltrate malicious software into a secure environment. This paper addresses this security threat by designing and evaluating a sanitizer that erases hidden content where steganographic channels might exist. The proposed sanitizer takes into account a set of specific constraints imposed by the application domain, such as not affecting the ability to manufacture part of the required quality using the sanitized design.

Causality-informed machine learning has been proposed as an avenue for achieving many of the goals of modern machine learning, from ensuring generalization under domain shifts to attaining fairness, robustness, and interpretability. A key component of causal machine learning is the inference of causal structures from observational data; in practice, this data may be incompletely observed. Prior work has demonstrated that adversarial perturbations of completely observed training data may be used to force the learning of inaccurate structural causal models (SCMs). However, when the data can be audited for correctness (e.g., it is cryptographically signed by its source), this adversarial mechanism is invalidated. This work introduces a novel attack methodology wherein the adversary deceptively omits a portion of the true training data to bias the learned causal structures in a desired manner (under strong signed sample input validation, this behavior seems to be the only strategy available to the adversary). Under this model, theoretically sound attack mechanisms are derived for the case of arbitrary SCMs, and a sample-efficient learning-based heuristic is given. Experimental validation of these approaches on real and synthetic datasets, across a range of SCMs from the family of additive noise models (linear Gaussian, linear non-Gaussian, and non-linear Gaussian), demonstrates the effectiveness of adversarial missingness attacks at deceiving popular causal structure learning algorithms.

Causality-informed machine learning has been proposed as an avenue for achieving many of the goals of modern machine learning, from ensuring generalization under domain shifts to attaining fairness, robustness, and interpretability. A key component of causal machine learning is the inference of causal structures from observational data; in practice, this data may be incompletely observed. Prior work has demonstrated that adversarial perturbations of completely observed training data may be used to force the learning of inaccurate causal structural models (SCMs). However, when the data can be audited for correctness (e.g., it is cryptographically signed by its source), this adversarial mechanism is invalidated. This work introduces a novel attack methodology wherein the adversary deceptively omits a portion of the true training data to bias the learned causal structures in a desired manner (under strong signed sample input validation, this behavior seems to be the only strategy available to the adversary). Under this model, theoretically sound attack mechanisms are derived for the case of arbitrary SCMs, and a sample-efficient learning-based heuristic is given. Experimental validation of these approaches on real and synthetic data sets demonstrates the effectiveness of adversarial missingness attacks at deceiving popular causal structure learning algorithms.

We study encrypted storage schemes where a client outsources data to an untrusted third-party server (such as a cloud storage provider) while maintaining the ability to privately query and dynamically update the data. We focus on encrypted multi-maps (EMMs), a structured encryption (STE) scheme that stores pairs of label and value tuples. EMMs allow queries on labels and return the associated value tuple. As responses are variable-length, EMMs are subject to volume leakage attacks introduced by Kellaris et al. [CCS'16]. To prevent these attacks, volume-hiding EMMs were introduced by Kamara and Moataz [Eurocrypt'19] that hide the label volumes (i.e., the value tuple lengths). As our main contribution, we present the first fully dynamic volume-hiding EMMs that are both asymptotically and concretely efficient. Furthermore, they are simultaneously forward and backward private which are the de-facto standard security notions for dynamic STE schemes. Additionally, we implement our schemes to showcase their concrete efficiency. Our experimental evaluations show that our constructions are able to add dynamicity with minimal to no additional cost compared to the prior best static volume-hiding schemes of Patel et al. [CCS'19].

As part of the responses to the ongoing crypto wars, the notion of Anamorphic Encryption was put forth. The notion allows private communication in spite of a dictator who is engaged in an extreme form of surveillance and or censorship, where it asks for all private keys and knows and may even dictate all messages. The original work pointed out efficient ways to use two known schemes in the anamorphic mode, bypassing the draconian censorship and hiding information from the all-powerful dictator. A question left open was whether these examples are outlier results or whether anamorphic mode is pervasive in existing systems. Here we answer the above question: we develop new techniques, expand the notion, and show that the notion of Anamorphic Cryptography is, in fact, very much prevalent. We first refine the notion of Anamorphic Encryption with respect to the nature of covert communication. Specifically, we distinguish Single-Receiver Encryption for many to one communication, and Multiple-Receiver Encryption for many to many communication within the group of conspiring users. We then show that Anamorphic Encryption can be embedded in the randomness used in the encryption, and we give families of constructions that can be applied to numerous ciphers. In total the families cover classical encryption schemes, some of which in actual use. Among our examples is an anamorphic channel with much higher capacity than the regular channel. In sum, the work shows the very large extent of the potential futility of control and censorship over the use of strong encryption by the dictator (typical for and even stronger than governments engaging in the ongoing crypto-wars): While such limitations obviously hurt utility which encryption typically brings to safety in computing systems, they essentially, are not helping the dictator. While the actual implications of what we show here and what it means in practice require further policy and legal analyses and perspectives, the technical aspects regarding the issues are clearly showing the futility of the war against Cryptography.

Google and Apple jointly introduced a digital contact tracing technology and an API called "exposure notification,'' to help health organizations and governments with contact tracing. The technology and its interplay with security and privacy constraints require investigation. In this study, we examine and analyze the security, privacy, and reliability of the technology with actual and typical scenarios (and expected typical adversary in mind), and quite realistic use cases. We do it in the context of Virginia's COVIDWISE app. This experimental analysis validates the properties of the system under the above conditions, a result that seems crucial for the peace of mind of the exposure notification technology adopting authorities, and may also help with the system's transparency and overall user trust.

While Security is universally needed, it is rarely plug-and-play. The new domain of Additive Manufacturing (a.k.a. 3D Printing) Security requires novel solutions to its unique security concerns. This workshop brings together researchers and practitioners working in this highly inter-disciplinary research field and closely related areas.

Beacons are small devices which are playing an important role in the Internet of Things (IoT), connecting “things” without IP connection to the Internet via Bluetooth Low Energy (BLE) communication. In this paper we present the first private end-to-end encryption protocol called the Eddystone-Ephemeral-ID (Eddystone-EID) protocol. This protocol enables connectivity from any beacon to its remote owner, while supporting beacon’s privacy and security, and essentially preserving the beacon’s low power consumption. We describe the Eddystone-EID development goals, discuss the design decisions, show the cryptographic solution, and analyse its privacy, security, and performance. Finally, we present three secure IoT applications built on Eddystone-EID, demonstrating its utility as a security and privacy infrastructure in the IoT domain. Further, Eddystone-EID is a prototypical example of security design for an asymmetric system in which on one side there are small power-deficient elements (the beacons) and on the other side there is a powerful computing engine (a cloud). The crux of the design strategy is based on: (1) transferring work from the beacon to the cloud, and then (2) building a trade-off between cloud online work against cloud offline work, in order to enable fast real-time reaction of the cloud. These two principles seem to be generic and can be used for other problems in the IoT domain.

Additive Manufacturing (AM) adoption is increasing in home and industrial settings, but information security for this technology is still immature. Thus far, three security threat categories have been identified: technical data theft, sabotage, and illegal part manufacturing. In this paper, we expand to a new threat category: misuse of digital design files as a subliminal communication channel. We identify and explore attacks by which arbitrary information can be embedded steganographically in the most common digital design file format, the STL, without distorting the printed object. Because the technique will not change the manufactured object’s geometry, it is likely to remain unnoticed and can be exploited for data transfer. Further, even with knowledge of our methods, defenders cannot distinguish between actual data transfer and random manipulation of the files. This is the first info-hiding attack on this system, conducted despite the fact that random changes may spoil the physical artifact and result in detection.

In this work, we discuss our successful efforts for industry deployment of a cryptographic secure computation protocol. The problem we consider is privately computing aggregate conversion rate of advertising campaigns. This underlying functionality can be abstracted as Private Intersection-Sum (PI-Sum) with Cardinality. In this setting two parties hold datasets containing user identifiers, and one of the parties additionally has an integer value associated with each of its user identifiers. The parties want to learn the number of identifiers they have in common and the sum of the integer values associated with these users without revealing any more information about their private inputs. We identify the major properties and enabling factors which make the deployment of a cryptographic protocol possible, practical, and uniquely positioned as a solution for the task at hand. We describe our deployment setting and the most relevant efficiency measure, which in our setting is communication overhead rather than computation. We also present a monetary cost model that can be used as a unifying cost measure and the computation model which reflect out use-case: a low-priority batch computing. We present three PI-Sum with cardinality protocols: our currently deployed protocol, which relies on a Diffie-Hellman style double masking, and two new protocols which leverage more recent techniques for private set intersection (PSI) that use Random Oblivious Transfer and encrypted Bloom filters. We compare the later two protocol with our original solution when instantiated with different additively homomorphic encryption schemes. We implement our constructions and compare their costs. We also compare with recent generic approaches for computing on the intersection of two datasets and show that our best protocol has monetary cost that is 20× less than the best known generic approach.

Volume leakage has recently been identified as a major threat to the security of cryptographic cloud-based data structures by Kellaris \em et al. [CCS'16] (see also the attacks in Grubbs \em et al. [CCS'18] and Lacharité \em et al. [S&P'18]). In this work, we focus on volume-hiding implementations of \em encrypted multi-maps as first considered by Kamara and Moataz [Eurocrypt'19]. Encrypted multi-maps consist of outsourcing the storage of a multi-map to an untrusted server, such as a cloud storage system, while maintaining the ability to perform private queries. Volume-hiding encrypted multi-maps ensure that the number of responses (volume) for any query remains hidden from the adversarial server. As a result, volume-hiding schemes can prevent leakage attacks that leverage the adversary's knowledge of the number of query responses to compromise privacy. We present both conceptual and algorithmic contributions towards volume-hiding encrypted multi-maps. We introduce the first formal definition of volume-hiding leakage functions. In terms of design, we present the first volume-hiding encrypted multi-map dprfMM whose storage and query complexity are both asymptotically optimal. Furthermore, we experimentally show that our construction is practically efficient. Our server storage is smaller than the best previous construction while we improve query complexity by a factor of 10-16x. In addition, we introduce the notion of differentially private volume-hiding leakage functions which strikes a better, tunable balance between privacy and efficiency. To accompany our new notion, we present a differentially private volume-hiding encrypted multi-map dpMM whose query complexity is the volume of the queried key plus an additional logarithmic factor. This is a significant improvement compared to all previous volume-hiding schemes whose query overhead was the maximum volume of any key. In natural settings, our construction improves the average query overhead by a factor of 150-240x over the previous best volume-hiding construction even when considering small privacy budget of ε=0.2.

Self-updatable encryption (SUE) is a new kind of public-key encryption, motivated by cloud computing, which enables anyone (i.e. cloud server with no access to private keys) to update a past ciphertext to a future ciphertext by using a public key. The main applications of SUE are revocable-storage attribute-based encryption (RS-ABE) that provides an efficient and secure access control to encrypted data stored in cloud storage. In this setting, there is a new threat such that a revoked user still can access past ciphertexts given to him by a storage server. RS-ABE solves this problem by combining user revocation and ciphertext updating functionalities. We propose the first SUE and RS-ABE schemes secure against a relevant form of chosen-ciphertext security (CCA). Due to the fact that some ciphertexts are easily derived from others, we employ a different notion of CCA that avoids easy challenge related messages. Specifically, we define “time extended challenge” CCA security for SUE which excludes ciphertexts that are easily derived from the challenge (over time periods) from being queried on. We then propose an efficient SUE scheme with such CCA security, and we also present an RS-ABE scheme with this CCA security.

The papers in this special section identify paradigm shifts in cryptographic engineering. Modern cryptography is almost five decades old, and we have seen some interesting breakthroughs throughout its relatively young history. These include the engineering foundations of symmetric key cryptography and block ciphers in particular (like the DES and the AES), the discovery of public-key cryptography, protocols for secure computations for general and specific tasks using interactions among parties and tools like homomorphic encryption (this line of work has been enhancing the use of cryptography beyond secure messaging into secure computing).

This tutorial will present a systematic overview of {\em kleptography}: stealing information subliminally from black-box cryptographic implementations; and {\em cliptography}: defending mechanisms that clip the power of kleptographic attacks via specification re-designs (without altering the underlying algorithms). Despite the laudatory history of development of modern cryptography, applying cryptographic tools to reliably provide security and privacy in practice is notoriously difficult. One fundamental practical challenge, guaranteeing security and privacy without explicit trust in the algorithms and implementations that underlie basic security infrastructure, remains. While the dangers of entertaining adversarial implementation of cryptographic primitives seem obvious, the ramifications of such attacks are surprisingly dire: it turns out that -- in wide generality -- adversarial implementations of cryptographic (both deterministic and randomized) algorithms may leak private information while producing output that is statistically indistinguishable from that of a faithful implementation. Such attacks were formally studied in Kleptography. Snowden revelations has shown us how security and privacy can be lost at a very large scale even when traditional cryptography seems to be used to protect Internet communication, when Kleptography was not taken into consideration. We will first explain how the above-mentioned Kleptographic attacks can be carried out in various settings. We will then introduce several simple but rigorous immunizing strategies that were inspired by folklore practical wisdoms to protect different algorithms from implementation subversion. Those strategies can be applied to ensure security of most of the fundamental cryptographic primitives such as PRG, digital signatures, public key encryptions against kleptographic attacks when they are implemented accordingly. Our new design principles may suggest new standardization methods that help reducing the threats of subverted implementation. We also hope our tutorial to stimulate a community-wise efforts to further tackle the fundamental challenge mentioned at the beginning.

Bitcoin seems to be the most successful cryptocurrency so far given the growing real life deployment and popularity. While Bitcoin requires clients to be online to perform transactions and a certain amount of time to verify them, there are many real life scenarios that demand for offline and immediate payments (e.g., mobile ticketing, vending machines, etc). However, offline payments in Bitcoin raise non-trivial security challenges, as the payee has no means to verify the received coins without having access to the Bitcoin network. Moreover, even online immediate payments are shown to be vulnerable to double-spending attacks. In this paper, we propose the first solution for Bitcoin payments, which enables secure payments with Bitcoin in offline settings and in scenarios where payments need to be immediately accepted. Our approach relies on an offline wallet and deploys several novel security mechanisms to prevent double-spending and to verify the coin validity in offline setting. These mechanisms achieve probabilistic security to guarantee that the attack probability is lower than the desired threshold. We provide a security and risk analysis as well as model security parameters for various adversaries. We further eliminate remaining risks by detection of misbehaving wallets and their revocation.

Notable recent security incidents have generated intense interest in adversaries which attempt to subvert---perhaps covertly---crypto\-graphic algorithms. In this paper we develop (IND-CPA) Semantically Secure encryption in this challenging setting. This fundamental encryption primitive has been previously studied in the "kleptographic setting," though existing results must relax the model by introducing trusted components or otherwise constraining the subversion power of the adversary: designing a Public Key System that is kletographically semantically secure (with minimal trust) has remained elusive to date. In this work, we finally achieve such systems, even when all relevant cryptographic algorithms are subject to adversarial (kleptographic) subversion. To this end we exploit novel inter-component randomized cryptographic checking techniques (with an offline checking component), combined with common and simple software engineering modular programming techniques (applied to the system's black box specification level). Moreover, our methodology yields a strong generic technique for the preservation of any semantically secure cryptosystem when incorporated into the strong kleptographic adversary setting.

Self-stabilization refers to the ability of systems to recover after temporal violations of conditions required for their correct operation. Such violations may lead the system to an arbitrary state from which it should automatically recover. Today, beyond recovering functionality, there is a need to recover security and confidentiality guarantees as well. To the best of our knowledge, there are currently no self-stabilizing protocols that also ensure recovering confidentiality, authenticity, and integrity properties. Specifically, self-stabilizing systems are designed to regain functionality which is, roughly speaking, desired input output relation, ignoring the security and confidentiality of computation and its state. Distributed (cryptographic) protocols for generic secure and privacy-preserving computation, e.g., secure Multi-Party Computation (MPC), usually ensure secrecy of inputs and outputs, and correctness of computation when the adversary is limited to compromise only a fraction of the components in the system, e.g., the computation is secure only in the presence of an honest majority of involved parties. While there are MPC protocols that are secure against a dishonest majority, in reality, the adversary may compromise all components of the system for a while; some of the corrupted components may then recover, e.g., due to security patches and software updates, or periodical code refresh and local state consistency check and enforcement based on self-stabilizing hardware and software techniques. It is currently unclear if a system and its state can be designed to always fully recover following such individual asynchronous recoveries. This paper introduces Secure Self-stabilizing Computation which answers this question in the affirmative. Secure self-stabilizing computation design ensures that secrecy of inputs and outputs, and correctness of the computation are automatically regained, even if at some point the entire system is compromised. We consider the distributed computation task as the implementation of virtual global finite satiate machine (FSM) to present commonly realized computation. The FSM is designed to regain consistency and security in the presence of a minority of Byzantine participants, e.g., one third of the parties, and following a temporary corruption of the entire system. We use this task and settings to demonstrate the definition of secure self-stabilizing computation. We show how our algorithms and system autonomously restore security and confidentiality of the computation of the FSM once the required corruption thresholds are again respected.

Digital signatures are perhaps the most important base for authentication and trust relationships in large scale systems. More specifically, various applications of signatures provide privacy and anonymity preserving mechanisms and protocols, and these, in turn, are becoming critical (due to the recently recognized need to protect individuals according to national rules and regulations). A specific type of signatures called "signatures with efficient protocols", as introduced by Camenisch and Lysyanskaya (CL), efficiently accommodates various basic protocols and extensions like zero-knowledge proofs, signing committed messages, or re-randomizability. These are, in fact, typical operations associated with signatures used in typical anonymity and privacy-preserving scenarios.

We formalize a cryptographic primitive called functional commitment (FC) which can be viewed as a generalization of vector commitments (VCs), polynomial commitments and many other special kinds of commitment schemes. A non-interactive functional commitment allows committing to a message in such a way that the committer has the flexibility of only revealing a function of the committed message during the opening phase. We provide constructions for the functionality of linear functions, where messages consist of vectors over some domain and commitments can later be opened to a specific linear function of the vector coordinates. An opening for a function thus generates a witness for the fact that the function indeed evaluates to a given value for the committed message. One security requirement is called function binding and requires that no adversary be able to open a commitment to two different evaluations for the same function. We propose a construction of functional commitment for linear functions based on constantsize assumptions in composite order groups endowed with a bilinear map. The construction has commitments and openings of constant size (i.e., independent of n or function description) and is perfectly hiding - the underlying message is information theoretically hidden. Our security proofs build on the Déjà Q framework of Chase and Meiklejohn (Eurocrypt 2014) and its extension by Wee (TCC 2016) to encryption primitives, thus relying on constant-size subgroup decisional assumptions. We show that FC for linear functions are sufficiently powerful to solve four open problems. They, first, imply polynomial commitments, and, then, give cryptographic accumulators (i.e., an algebraic hash function which makes it possible to efficiently prove that some input belongs to a hashed set). In particular, specializing our FC construction leads to the first pairing-based polynomial commitments and accumulators for large universes known to achieve security under simple assumptions. We also substantially extend our pairing-based accumulator to handle subset queries which requires a non-trivial extension of the Déjà Q framework.

In a secret sharing scheme a dealer shares a secret s among n parties such that an adversary corrupting up to t parties does not learn s, while any t+1 parties can efficiently recover s. Over a long period of time all parties may be corrupted thus violating the threshold, which is accounted for in Proactive Secret Sharing (PSS). PSS schemes periodically rerandomize (refresh) the shares of the secret and invalidate old ones. PSS retains confidentiality even when all parties are corrupted over the lifetime of the secret, but no more than t during a certain window of time, called the refresh period. Existing PSS schemes only guarantee secrecy in the presence of an honest majority with less than n2 total corruptions during a refresh period; an adversary corrupting a single additional party, even if only passively, obtains the secret. This work is the first feasibility result demonstrating PSS tolerating a dishonest majority, it introduces the first PSS scheme secure against t<n passive adversaries without recovery of lost shares, it can also recover from honest faulty parties losing their shares, and when tolerating e faults the scheme tolerates t<n-e passive corruptions. A non-robust version of the scheme can tolerate t

The mission of the 2nd ACM Workshop on Information Sharing and Collaborative Security is to advance the scientific foundations for sharing threat and security-related data among organizations. The call for better information sharing continues to be an important theme in the computer security community and with policy makers. The expectation is that sharing will significantly improve the ability of defenders to detect and mitigate attacks on their networks and systems. Several commercial offerings by security vendors that enable automated sharing have gone live and existing communities have begun to use them. Sharing of security and threat data at scale raises a number of interesting research questions, including on how to best collect, analyze and make use of these data to address important security concerns. In addition sharing raises privacy and other policy issues that need to be addressed.

Technological innovations in security and privacy are critical to advancing modern computing in our time. I will present an effort involving deployment of experimental commercial applications designed and built as a 'secure multi-party computation protocol for specific tasks,' to be used repetitively to achieve a number of concrete ubiquitous business goals. In these applications, the outputs are calculated in the presence of privacy constraints which prevent parties from sharing their individual inputs directly and openly. I will also discuss what I think are the reasons for the inherent difficulty of developing such routines in general (for achieving business goals). In particular, I will survey what I believe to be the reasons that almost 40 years since secure computation protocols was invented as a basic theoretical notion, capturing specific and then general computational tasks, and in spite of its theoretical and even experimentation success, the notion has not yet been widely and seriously used in achieving routine relevant business goals (in contrast with symmetric key and public key cryptosystems and protocols, which were also proposed 40 years ago and are used extensively, primarily to implement secure authenticated channels). The presentation will also cover the general bottom up methodology used in this effort leading to the design and development process. This exemplifying methodology includes: feasibility study of the specific domain, extraction of business needs which are limited by privacy constraints, application analysis from the perspective of utility metrics and secure computing. Then, the methodology further includes design, implementation, and experimentation, guided by the analysis and employing appropriate protocols, while considering scale and performance constraints, and cost overhead that is tolerable.

The notion of `mobile adversary,' where the opponent can capture parties in a multi-party protocol dynamically, as long as at any given point in time its capturing capability is limited by a bound on number of parties (processors) it can control, has been suggested as an extensions of the traditionally static adversary. The motivation for this adversary was a result of a few issues: First, it was originated in systems corruption phenomena like virus injection into a computer network (such as the Internet), where viruses are spread but also detected and eliminated at network computers. Secondly, it is natural to assume that for managed networks, there will be efforts to recover failed processors, so the adversary control may cease to exist in a node locally while its control of other nodes continues. Thirdly, the notion of self-stabilization implies that a system tries to get rid of failures and the notion represents a strong fault-tolerance aspect, and should be extended (i.e., augmented by assuming bound on faults and extending initial benign fault to adversarial perpetual ones). As a result, the mobile adversary notion and a methodology for coping with it (proactive fault-tolerance, or proactive security in security oriented protocols) and its perpetual self-healing character, have been suggested. This work will review the development and influence of this notion on fault-tolerant secure distributed computing.

Threshold cryptography is a fundamental distributed computational paradigm for enhancing the availability and the security of cryptographic public-key schemes. It does it by dividing private keys into n shares handed out to distinct servers. In threshold signature schemes, a set of at least t+1 ≤ n servers is needed to produce a valid digital signature. Availability is assured by the fact that any subset of t+1 servers can produce a signature when authorized. At the same time, the scheme should remain robust (in the fault tolerance sense) and unforgeable (cryptographically) against up to t corrupted servers; i.e., it adds quorum control to traditional cryptographic services and introduces redundancy. Originally, most practical threshold signatures have a number of demerits: They have been analyzed in a static corruption model (where the set of corrupted servers is fixed at the very beginning of the attack), they require interaction, they assume a trusted dealer in the key generation phase (so that the system is not fully distributed), or they suffer from certain overheads in terms of storage (large share sizes). In this paper, we construct practical fully distributed (the private key is born distributed), non-interactive schemes --- where the servers can compute their partial signatures without communication with other servers--- with adaptive security (i.e., the adversary corrupts servers dynamically based on its full view of the history of the system). Our schemes are very efficient in terms of computation, communication, and scalable storage (with private key shares of size O(1), where certain solutions incur O(n) storage costs at each server). Unlike other adaptively secure schemes, our schemes are erasure-free (reliable erasure is a hard to assure and hard to administer property in actual systems).

In the setting of cryptographic protocols, the corruption of a party has traditionally been viewed as a simple, uniform and atomic operation, where the adversary decides to get control over a party and this party immediately gets corrupted. In this paper, motivated by the fact that different players may require different resources to get corrupted, we put forth the notion of resource-based corruptions, where the adversary must invest some resources in order to corrupt a player.

Software-based attacks (e.g., malware) pose a big threat to cryptographic software because they can compromise the associated cryptographic keys in their entirety. In this paper, we investigate key-insulated symmetric key cryptography, which can mitigate the damage caused by repeated attacks against cryptographic software. To illustrate the feasibility of key-insulated symmetric key cryptography, we also report a proof-of-concept implementation in the Kernel-based Virtual Machine (KVM) environment.

An encryption scheme is Key Dependent Message (KDM) secure if it is secure even against an attacker who has access to encryptions of messages which depend on the secret key. Recent studies have revealed that this strong security notion is important both theoretically and practically. In this paper we review the defnition, and survey recent results and applications of KDM security.

Formal RFID security and privacy frameworks are fundamental to the design and analysis of robust RFID systems. In this paper, we develop a new definitional framework for RFID privacy in a rigorous and precise manner. Our framework is based on a zero-knowledge (ZK) formulation [The Foundations of Cr yptography, Cambridge Univ. Press, Cambridge, 2001; ACM Symposium on Theory of Computing, 1985, pp. 291–304] and incorporates the notions of adaptive completeness and mutual authentication. We provide meticulous justification of the new framework and contrast it with existing ones in the literature. In particular, we prove that our framework is strictly stronger than the ind-privacy model in International Conference on Pervasive Computing and Communications, 2007, which answers an open question posed in International Conference on Pervasive Computing and Communications, 2007, for developing stronger RFID privacy models. We also clarify certain confusions and rectify several defects in the existing frameworks. Finally, based on the protocol in Conference on Computer and Communications Security, 2009, we propose an efficient RFID mutual authentication protocol and analyze its security and privacy. The methodology used in our analysis can also be applied to analyze other RFID protocols within the new framework.

Enhancing user privacy while allowing the use of digital credentials in network-wide applications is a very active area. Group signatures are primary privacy-preserving credentials that enable both, non-repudiation and abuser-tracing.When embedding cryptographic tools in actual computing systems, it is important to ensure physical layer protection to cryptographic keys. A simple risk analysis shows that taking advantage of system (i.e., hardware, software, network) vulnerabilities is usually much easier than cryptanalyzing the cryptographic primitives themselves. Forward-secure cryptosystems, in turn, are one of the suggested protective measures, where private keys periodically evolve in such a way that, if a break-in occurs, past uses of those keys in earlier periods are protected.At CCS 2001, Song argued why key exposures may cause even more important concerns in the context of group signatures (namely, under the mask of anonymity within a group of other key holders). She then gave two examples of forward-secure group signatures, and argued their ad hoc properties based on the state of understanding of group security properties at that time (proper security models had not been formalized yet). These implementations are fruitful initial efforts, but still suffer from certain imperfections. In the first scheme for instance, forward security is only guaranteed to signers as long as the group manager's private key is safe. Another scheme recently described by Nakanishi et al. for static groups also fails to maintain security when the group manager is compromised.In this paper, we reconsider the subject and first formalize the notion of fully forward-secure group signature (FS-GS) in dynamic groups. We carefully define the correctness and security properties that such a scheme ought to have. We then give a realization of the primitive with quite attractive features: constant-size signatures, constant cost of signing/verifying, and at most polylog complexity of other metrics. The scheme is further proven secure in the standard model (no random oracle idealization is used).

Cryptographic systems and protocols are the core of many Internet security procedures (such as SSL, SSH, IPSEC, DNSSEC, secure mail, etc.). At the heart of all cryptographic functions is a good source of randomness, and for efficiency, the primitive of pseudorandom generator (PRG). PRG can also be used in the design of stream ciphers, for secure communications. The Internet is nowadays composed of many types of devices with very different hardware and software characteristics. Hence, one of the concerns in such open environments is the information "leakage" and its exploitation via the so-called "side channel attacks".

Forward-Secure Signatures (FSS) prevent forgeries for past time periods when an attacker obtains full access to the signer’s storage by evolving the private key in a one-way fashion. To simplify the integration of these primitives into standard security architectures, Boyen et al. [2006] recently introduced the concept of forward-secure signatures with untrusted updates where private keys are additionally protected by a second factor (derived from a password). Key updates can be made on encrypted version of signing keys so that passwords only come into play for signing messages and not at update time (since update is not user-driven). The scheme put forth by Boyen et al. relies on bilinear maps and does not require the random oracle. They also suggest the integration of untrusted updates in the Bellare-Miner forward-secure signature. Their work left open the problem of endowing other existing FSS systems with the same second factor protection, and a natural second question is whether the method can apply to other key-evolving paradigms. This article solves the first problem by showing an efficient generic construction that does not require to set a bound on the number of time periods at key generation. The article then extends the unprotected update model to other key-evolving primitives such as forward-secure public key encryption and key-insulated cryptosystems.

At CCS'07, a novel identity-based sequential aggregate signature scheme was proposed and the security of the scheme was proven under the hardness assumption of a new computational problem called modified LRSW problem. In the paper, unfortunately, we show that the scheme is universally forgeable, i.e., anyone can generate forged signatures on any messages of its choice. In addition, we show that the computational assumption is not correct by concretely presenting a constant-time algorithm solving the problem. The contribution of the new scheme and assumption is a natural step in cryptologic research that calls for further investigation, which is a step we perform in the current work.

Mutual authentication and authenticated key exchange are fundamental techniques for enabling secure communication over public, insecure networks. It is well known how to design secure protocols for achieving these goals when parties share high-entropy cryptographic keys in advance of the authentication stage. Unfortunately, it is much more common for users to share weak, low-entropy passwords which furthermore may be chosen from a known space of possibilities (say, a dictionary of English words). In this case, the problem becomes much more difficult as one must ensure that protocols are immune to off-line dictionary attacks in which an adversary exhaustively enumerates all possible passwords in an attempt to determine the correct one. We propose a 3-round protocol for password-only authenticated key exchange, and provide a rigorous proof of security for our protocol based on the decisional Diffie-Hellman assumption. The protocol assumes only public parameters—specifically, a “common reference string”—which can be “hard-coded” into an implementation of the protocol; in particular, and in contrast to some previous work, our protocol does not require either party to pre-share a public key. The protocol is also remarkably efficient, requiring computation only (roughly) 4 times greater than “classical” Diffie-Hellman key exchange that provides no authentication at all. Ours is the first protocol for password-only authentication that is both practical and provably-secure using standard cryptographic assumptions .

We study the security of a block cipher-based pseudorandom number generator (PRNG), both in the black box world and in the physical world, separately. We first show that the construction is a secure PRNG in the ideal cipher model. Then, we demonstrate its security against a Bayesian side-channel key recovery adversary. As a main result, we show that our construction guarantees that the success rate of the adversary does not increase with the number of physical observations, but in a limited and controlled way. Besides, we observe that, under common assumptions on side-channel attack strategies, increasing the security parameter (typically the block cipher key size) by a polynomial factor involves an increase of a side-channel attack complexity by an exponential factor, making the probability of a successful attack negligible. We believe this work provides a first interesting example of the way the algorithmic design of a cryptographic scheme influences its side-channel resistance.

Public-key traitor-tracing schemes is a supporting technology for content distribution that discourages abuse and resale of cryptographic keys used for the distribution. These schemes enable a system manager to maintain a set of subscribers so that any external content provider can use the public key nature of the method and transmit data to the subscribers, while assuring that if a coalition of users generate a pirate deciphering device, they can be identified via a procedure called "traitor tracing."

We investigate structural properties of interactive perfect zero-knowledge (PZK) proofs. Specifically, we look into the closure properties of PZK languages under monotone boolean formula composition. This gives rise to new protocol techniques. We show that interactive PZK for random self-reducible (RSR) (and for co-RSR) languages is closed under monotone boolean formula composition. Namely, we present PZK proofs for monotone boolean formulae whose atoms are statements about membership in a PZK language which is RSR (or whose complement is RSR). We also discuss extensions, recent applications, and generalizations of the techniques.

In this paper, we investigate the decoding problem of Reed–Solomon (RS) codes, also known as the polynomial reconstruction problem (PR), from a cryptographic hardness perspective. Namely, we deal with samplable PR instances over parameter choices for which decoding is not known to be feasibly solvable and where part of the solution polynomial is the hidden input. We put forth a natural decisional intractability assumption that relates to this decoding problem: distinguishing between a single randomly chosen error location and a single randomly chosen nonerror location for a given corrupted RS codeword with random noise. We prove that under this assumption, PR instances are entirely pseudorandom, i.e., they are indistinguishable from random vectors over the underlying finite field. Moreover, under the same assumption, we show that it is hard to extract any partial information related to the hidden input encoded by the corrupted PR instance, i.e., PR instances hide their message polynomial solution in the semantic security sense. The above results lay a framework for the exploitation of PR as an intractability assumption for provable security of cryptographic primitives. Based on this framework, we present provably secure cryptographic constructions for 1) a pseudorandom number generator, 2) a semantically secure version of the oblivious polynomial evaluation (OPE) protocol, and 3) a stateful cipher with a set of interesting properties that include: semantic security, forward secrecy, error-correcting decryption and an array of random self-reducibility properties with respect to the plaintext choice, key choice, and partial domain choice.

We introduce the concept of an elastic block cipher, which refers to stretching the supported block size of a block cipher to any length up to twice the original block size while incurring a computational workload that is proportional to the block size. We define a method for converting any existing block cipher into an elastic block cipher and mention our analysis of the construction.

Forward-secure signatures (FSS) prevent forgeries for past time periods when an attacker obtains full access to the signer’s storage. To simplify the integration of these primitives into standard security architectures, Boyen, Shacham, Shen and Waters recently introduced the concept of forwardsecure signatures with untrusted updates where private keys are additionally protected by a second factor (derived from a password). Key updates can be made on encrypted version of signing keys so that passwords only come into play for signing messages. The scheme put forth by Boyen et al. relies on bilinear maps and does not require the random oracle. The latter work also suggested the integration of untrusted updates in the Bellare-Miner forward-secure signature and left open the problem of endowing other existing FSS systems with the same second factor protection. This paper solves this problem by showing how to adapt the very efficient generic construction of Malkin, Micciancio and Miner (MMM) to untrusted update environments. More precisely, our modified construction- which does not use random oracles either- obtains a forward-secure signature with untrusted updates from any 2-party multi-signature in the plain public key model. In combination with Bellare and Neven’s multi-signatures, our generic method yields implementations based on standard assumptions such as RSA, factoring or the hardness of computing discrete logarithms. Like the original MMM scheme, it does not require to set a bound on the number of time periods at key generation.

User authentication in computing systems traditionally depends on three factors: something you have (e.g., a hardware token), something you are (e.g., a fingerprint), and something you know (e.g., a password). In this paper, we explore a fourth factor, the social network of the user, that is, somebody you know.Human authentication through mutual acquaintance is an age-old practice. In the arena of computer security, it plays roles in privilege delegation, peer-level certification, help-desk assistance, and reputation networks. As a direct means of logical authentication, though, the reliance of human being on another has little supporting scientific literature or practice.In this paper, we explore the notion of vouching, that is, peer-level, human-intermediated authentication for access control. We explore its use in emergency authentication, when primary authenticators like passwords or hardware tokens become unavailable. We describe a practical, prototype vouching system based on SecurID, a popular hardware authentication token. We address traditional, cryptographic security requirements, but also consider questions of social engineering and user behavior.

Secure communications between large number of sensor nodes that are randomly scattered over a hostile territory, necessitate efficient key distribution schemes. However, due to limited resources at sensor nodes such schemes cannot be based on post deployment computations. Instead, pairwise (symmetric) keys are required to be pre-distributed by assigning a list of keys, (a.k.a. key-chain), to each sensor node. If a pair of nodes does not have a common key after deployment then they must find a key-path with secured links. The objective is to minimize the keychain size while (i) maximizing pairwise key sharing probability and resilience, and (ii) minimizing average key-path length. This paper presents a deterministic key distribution scheme based on Expander Graphs. It shows how to map the parameters (e.g., degree, expansion, and diameter) of a Ramanujan Expander Graph to the desired properties of a key distribution scheme for a physical network topology.

We show software agents that operate on input plaintext, transmit the result, and have the property that characterizes the operation as theft of plaintext amounts to solving a hard cryptographic problem. Such agents employ what we call a "questionable encryption scheme" in which it is computationally intractable to determine if the output is an asymmetric ciphertext or nonce. We therefore show a fundamental computational limitation of information forensics

We put forth the notion of a dual receiver cryptosystem and implement it based on bilinear pairings over certain elliptic curve groups. The cryptosystem is simple and efficient yet powerful, as it solves two problems of practical importance whose solutions have proven to be elusive before:(1) A provably secure "combined" public-key cryptosystem (with a single secret key per user in space-limited environment) where the key is used for both decryption and signing and where encryption can be escrowed and recovered, while the signature capability never leaves its owner. This is an open problem proposed by the work of Haber and Pinkas. (2) A puzzle is a method for rate-limiting remote users by forcing them to solve a computational task (the puzzle). Puzzles have been based on cryptographic challenges in the past, but the successful design of embedding a useful cryptographic task inside a puzzle, originally posed by Dwork and Naor, remained an open problem till today. We model and present "useful security puzzles" applicable in two scenarios: a secure fileserver, and an online transaction server (such as a webserver).

The problem of privacy-preserving authentication has been extensively investigated in a set of diverse system settings. However, a full-fledged such mechanism called secret handshake, whereby two users (e.g., CIA agents) authenticate each other in a way that no one reveals its own membership (or credential) unless the peer's legitimacy was already ensured of, remains to be elusive because simultaneity of authentication must be guaranteed even in the presence of an active adversary that may act as a handshake initiator or responder. The state-of-the-art secret handshake scheme is very efficient, but imposes on the users the following restriction: either they have to use one-time credentials, or they have to suffer from the privacy degradation that all the sessions involving a same user (or credential are trivially linkable. In this paper, we present the first secret handshake schemes that achieve unlinkability while allowing the users to reuse their credentials (i.e., unlinkability is not achieved by means of one-time credentials). Specifically, we introduce the concept of $k$-anonymous secret handshakes where $k$ is an adjustable parameter indicating the desired anonymity assurance. We present a detailed construction based on public key cryptosystems, and sketch another based on symmetric key cryptosystems. Both schemes are efficient, and can even be seamlessly integrated into a standard public key infrastructure (PKI). Moreover, and their security analysis does not resort to any random oracle.

A "partial broadcast channel" enables one processor to send the same message---simultaneously and privately---to a fixed subset of processors. Suppose that a collection of processors are connected by an arbitrary network of partial broadcast channels (a hypergraph). We initiate the study of necessary and sufficient conditions, complexity bounds, and protocols for individual processors to exchange private messages across this network. Private message exchange, in turn, enables the realization of general secure computation primitives. The model (motivated by various environments such as multicast network architectures and group communication in distributed systems) is an intermediate setting between the private channels model and the full information model, both of which have been investigated extensively in the last few years. We assume a computationally unlimited adversary (i.e., the information theoretic notion of security), and our techniques are combinatorial. Both the possibility and the polynomial-time feasibility of private message exchange are investigated.

Traitor Tracing Schemes constitute a very useful tool against piracy in the context of digital content broadcast. In such multi-recipient encryption schemes, each decryption key is fingerprinted and when a pirate decoder is discovered, the authorities can trace the identities of the users that contributed in its construction (called traitors). Public-key traitor tracing schemes allow for a multitude of non trusted content providers using the same set of keys, which makes the scheme "server-side scalable." To make such schemes also "client-side scalable," i.e. long lived and usable for a large population of subscribers that changes dynamically over time, it is crucial to implement efficient Add-user and Remove-user operations. Previous work on public-key traitor tracing did not address this dynamic scenario thoroughly, and there is no efficient scalable public key traitor tracing scheme that allows an increasing number of Add-user and Remove-user operations.To address these issues, we introduce the model of Scalable Public-Key Traitor Tracing, and present the first construction of such a scheme. Our model mandates for deterministic traitor tracing and an unlimited number of efficient Add-user operations and Remove-user operations. A scalable system achieves an unlimited number of revocations while retaining high level of efficiency by dividing the run-time of the system into periods. Each period has a saturation level for the number of revocations. When a period becomes saturated, an efficient new-period operation is issued by the system server that resets the saturation level. We present a formal adversarial model for our system taking into account its periodic structure, and we prove our construction secure, both against adversaries that attempt to cheat the revocation mechanism as well as against adversaries that attempt to cheat the traitor tracing mechanism.

We investigate the problem of self-stabilizing round-robin token management on a bidirectional ring of identical processors. Each processor is an asynchronous probabilistic finite state (i.e., constant space) machine which sends and receives constant-size messages and whose state transition is triggered by the receipt of a message. We also show that this problem is equivalent to symmetry breaking (i.e., leader election). Wejustify and suggest a two-layer (hardware and software) solution to the token management problem: The subproblem of reducing an arbitrary but nonzero number of tokens (in an otherwise arbitrary initial system state) to exactly one token (and a legal system state) is solved in hardware and takes only small polynomial time. The detection of a complete lack of tokens (communication deadlock) is done by a software clock. In high-speed networks the hardware layer can be implemented using fast universal switches (i.e., finite state machines) independent of the size of the network. We note that randomization is essential, since Dijkstra showed that for arbitrary rings the subproblem does not have a deterministic solution (regardless of the computational power of the identical processors). The use of the software layer (deadlock detection) in our solution is minimized.

We investigate a simple method of fraud management for secure devices that may serve as an alternative or complement to conventional hardware-based tamper resistance. Under normal operating conditions in our scheme, a secure device includes an authentication code in its communications, e.g., in the digital signatures it issues. This code may be verified by a fraud management center under a pre-determined key σ. When the device detects an attempted break-in, it modifies σ. This results in a change to the authentication codes issued by the device such that the fraud management center can detect the apparent break-in. Hence, in contrast to the case with typical tamper-resistance schemes, the deployer of our proposed scheme seeks to trace break-ins, rather than prevent them. In reference to the wartime practice of physically capturing and subverting underground radio transmitters – a practice analogous to the capture and use of secret information on secure devices – we denote this idea by the German term funkspiel, meaning “radio game.” One challenge in constructing a funkspiel scheme is to ensure that an attacker privy to the authentication codes of the secure device both before and after the break-in, as well as the secrets of the device following the break-in, cannot detect the alteration to σ. Additional challenges ∗Some of this work was done while visiting RSA Laboratories.

Article On zero-knowledge proofs (extended abstract): "from membership to decision" Share on Authors: Giovanni Di Crescenzo Telcordia Technologies Inc., 445 South Street, Morristown, NJ Telcordia Technologies Inc., 445 South Street, Morristown, NJView Profile , Kouichi Sakurai Dept. of Computer Science, Kyushu University, Fukuoka 812-8581, Japan Dept. of Computer Science, Kyushu University, Fukuoka 812-8581, JapanView Profile , Moti Yung CertCo, New York, NY CertCo, New York, NYView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 255–264https://doi.org/10.1145/335305.335336Online:01 May 2000Publication History 3citation509DownloadsMetricsTotal Citations3Total Downloads509Last 12 Months8Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The development of precise definitions of security for encryption, as well as a detailed understanding of their relationships, has been a major area of research in modern cryptography. Here, we focus on the case of private-key encryption. Extending security notions from the public-key setting, we define security in the sense of both indistinguishability and non-malleability against chosen-plaintext and chosen-ciphertext attacks, considering both non-adaptive (i.e., “lunchtime”) and adaptive oracle access (adaptive here refers to an adversary’s ability to interact with a given oracle even after viewing the challenge ciphertext). We then characterize the 18 resulting security notions in two ways. First, we construct a complete hierarchy of security notions; that is, for every pair of definitions we show whether one definition is stronger than the other, whether the definitions are equivalent, or whether they are incomparable. Second, we partition these notions of security into two classes (computational or information-theoretic) depending on whether one-way functions are necessary in order for encryption schemes satisfying the definition to exist. Perhaps our most surprising result is that security against adaptive chosen-plaintext attack is (polynomially) equivalent to security against non-adaptive chosen-plaintext attack. On the other hand, the ability of an adversary to mount a (non-adaptive) chosen-plaintext attack is the key feature distinguishing computational and informationtheoretic notions of security. These results hold for all security notions considered here. 1

We initiate a graph-theoretic study of privacy in distributed environments with mobile eavesdroppers ("bugs"). For two privacy tasks—distributed database maintenance and message transmission—a computationally unbounded adversary “plays an eavesdrpping game,” coordinating the moment of the bugs among the sites to learn the current memory contents. Many different adversaries are considered, motivated by differences in eavesdropping technologies. We characterize the feasibility of the two privacy tasks combinatorially, construct protocols for the feasible cases, and analyze their computational complexity.

Typically, bandwidth reservation is not made for data applications. Therefore, the only way to provide minimum bandwidth guarantees to such an application is by using a fairness mechanism to regulate the access to the network and by controlling the packet loss (i.e., congestion) inside the network. There are numerous works treating fairness in ring networks, however, there are almost no such works on fairness in arbitrary topology networks. The context of this work is fairness in an arbitrary topology network, the MetaNet, which employs convergence routing, a loss-free routing technique which is a variant on deflection routing. We note that minimum bandwidth guarantee combined with loss-free routing are the desired quality-of-service (QoS) attributes for most data applications. While developing the mechanisms, we also present performance measures to assess the new access- and flow-control algorithm: i) locality and congestion-driven-only the subnetwork containing conflicting traffic streams becomes involved in the fairness regulation. Furthermore, the fairness regulation is activated only when congestion occurs. This implies that when there is no congestion, nodes can access the network immediately and freely, which is a key requirement for distributed computing. ii) Scalability-the data-structure sizes used in the algorithm are a function of the switching node degree, and use constant space control signals of two bits only (the ATM standard, for example, dedicates four bits in the header of each cell to generic flow-control). iii) Linear access time in the congested subnetwork-measured by "the maximal clique in what we call the conflict graph to which a node belongs," and a frequency which is inverse linear in this parameter (when the traffic pattern stabilizes).

The design of simple cryptographic protocols for elementary two-party (session oriented) tasks (such as entity authentication and key transport) has had a history (starting with [NS78]) where security has been quite evasive. Only recently we have seen protocol designs which are both provably secure and efficient

The area of "computing with encrypted data" has been studied by numerous authors in the past twenty years since it is fundamental to understanding properties of encryption and it has many practical applications. The related fundamental area of "secure function evaluation" has been studied since the mid 80's. In its basic two-party case, two parties (Alice and Bob) evaluate a known circuit over private inputs (or a private input and a private circuit). Much attention has been paid to the important issue of minimizing rounds of computation in this model. Namely, the number of communication rounds in which Alice and Bob need to engage in to evaluate a circuit on encrypted data securely. Advancements in these areas have been recognized as open problems and have remained open for a number of years. In this paper we give a one round, and thus round optimal, protocol for secure evaluation of circuits which is in polynomial time for NC/sup 1/ circuits. The protocol involves an input party sending encrypted input to a second party, a cryptocomputer, which evaluates the circuit (or a known circuit over its additional private input) non-interactively, securely and obliviously, and provides the output to the input party without learning it. This improves on previous (general) results that are specialized to the case of NC/sup 1/ circuits and require a constant number of communication rounds. We further suggest applications to network and mobile computing.

No abstract available.

In this paper we present an efficient general simulation strategy for computations designed for fully operational BSP machines of n ideal processors, on n-processor dynamic-fauhprone BSP machines.The fault occurrences are fail-stop and fully dynamic, i.e., they are ahowed to happen on-line 'This work was partially

The invention provides for robust efficient distributed generation of RSA keys. An efficient protocol is one which is independent of the primality test “circuit size”, while a robust protocol allows correct completion even in the presence of a minority of arbitrarily misbehaving malicious parties. The disclosed protocol is secure against any minority of malicious parties (which is optimal). The disclosed method is useful in establishing sensitive distributed cryptographic function sharing services (certification authorities, signature schemes with distributed trust, and key escrow authorities), as well as other applications besides RSA (namely: composite ElGamal, identification schemes, simultaneous bit exchange, etc.). The disclosed method can be combined with proactive function sharing techniques to establish the first efficient, optimal-resilience, robust and proactively-secure RSA-based distributed trust services where the key is never entrusted to a single entity (i.e., distributed trust totally “from scratch”). The disclosed method involves new efficient “robustness assurance techniques” which guarantee “correct computations” by mutually distrusting parties with malicious minority.

Emerging applications like electronic commerce and secure communications over open networks have made clear the fundamental role of public key cryptography as a unique enabler for world-wide scale security solutions. On the other hand, these solutions clearly expose the fact that the protection of private keys is a security bottleneck in these sensitive applications. This problem is further worsened in the cases where a single and unchanged private key must be kept secret for very long time (such is the case of certification authority keys, bank and e-cash keys, etc.). One crucial defense against exposure of private keys is offered by threshold cryptography where the private key functions (like signatures or decryption) are distributed among several parties such that a predetermined number of parties must cooperate in order to correctly perform these operations. This protects keys from any single point of failure. An attacker needs to break into a multiplicity of locations before it c...

We introduce new efficient techniques for sharing cryptographic functions in a distributed dynamic fashion. These techniques dynamically and securely transform a distributed function (or secret sharing) representation between t-out-of-l (polynomial sharing) and t-out-of-t (additive sharing). We call the techniques poly-to-sum and sum-to-poly, respectively. Employing these techniques, we solve a number of open problems in the area of cryptographic function sharing. We design a threshold function sharing scheme with proactive security for general functions with a "homomorphic property" (a class which includes all RSA variants and Discrete logarithm variants). The sharing has "optimal resilience" (server redundancy) and enables computation of the function by the servers assuring high availability, security and efficiency. Proactive security enables function sharing among servers while tolerating an adversary which is mobile and which dynamically corrupts and abandons servers (and perhaps visits all of them over the lifetime of the system, as long as the number of corruptions (faults) is bounded within a time period). Optimal resilience assures that the adversary can corrupt any minority of servers at any time-period.

This paper studies the issues of flexibility and scalability in the context of network security. In particular, it concentrates on authentication and key distribution services suited for a variety of communication paradigms, network environments, and end-devices. We present the design criteria, specification, and step-by-step construction of authentication and key distribution services based on experience in the KryptoKnight project. The central goal of the KryptoKnight project was the construction of basic network security functions in a minimal, flexible (thus, versatile) and scalable manner. Protocol minimality (in terms of resource usage) and flexibility are not merely theoretical goals; they have clear advantages in environments where computational resources are limited and connectivity is restricted. KryptoKnight was aimed at such environments: small and anemic wireless devices, simple network and data-link entities, embedded micro-devices and other special-purpose communication equipment and configurations. Furthermore, scalability of protocols makes their deployment possible in the presence of rapid network growth and inter-domain communication.

Cryptovirology has recently been introduced as a means of mounting active viral attacks using public key cryptography. It has been shown to be a tool for extortion attacks and "electronic warfare", where attacks are mounted against information resources. The natural question to ask is whether Cryptovirology is also useful in the area of spying via malware. We demonstrate that Cryptovirology does help in "electronic espionage" and allows the spy to conceal his or her identity (as well as past collected information). Specifically, we present an attack that can be mounted by a cryptotrojan that allows the attacker to gather information (passwords) from a system in such a way that the attacker cannot be proven guilty beyond reasonable doubt. That is, even if the attacker is under surveillance on the local machine from when he first attacks the target machine, to when he obtains the passwords, and even if the leaked information is made available to the attacker exclusively, he still cannot be caught. The threat is made possible by the combination of public key cryptography, probabilistic encryption, and the use of public information (I/O or communication) channels which together form a "secure receiver-anonymous channel". The machine can be standalone or networked. What we learn from the attack is extracted as general tools and basic principles for "espionage attacks".

The problem solved in this work is how multiple nodes in a network with an arbitrary topology can broadcast concurrently, in an asynchronous manner, to all other nodes. Asynchronous means that the nodes do not coordinate their broadcast, and, therefore, it is possible that all nodes will start to broadcast at the same time. Simultaneous broadcast by many nodes can cause traffic congestion, which can result in a traffic loss. The main property of the broadcast algorithms presented in this work is that under any arbitrary broadcast pattern there will be no packet or cell loss due to internal traffic congestion. The routing mechanism used by the broadcast algorithm can be viewed as a variant of deflection routing, which means that a node makes on-line routing decisions based on the local flow of traffic (i.e., internal load conditions). Unlike other deflection techniques, the MetaNet routing is along a global sense of direction, which guarantees that packets will reach their destinations. Thus, we call this method convergence routing (previous deflection algorithms did not guarantee deterministic routing convergence, i.e., a cell/packet can be deflected indefinitely inside the network). As a result of the convergence property, the deflection routing used in this work is the only one with broadcast capability.

We consider a family of jobs that are organized as a task-tree which, in particular, captures the behavior of divide-and-conquer algorithms in many typical cases (examples are Quicksort and Brute-Force Search jobs). These jobs can be described as a rooted task tree, where the cost of work at a node v in the tree is additive in the cost of v's children. We give a lower bound on the time to perform such jobs. We then provide a general algorithm that assigns these tasks to processors in a large set of parallel/distributed architectures (which includes: meshes, linear arrays, and rings). We analyze our scheme's time, showing when it is optimal or nearly optimal. We consider the cases when the tree structure is known at the node (i.e., the static case), when the division of work among children is known (the semi-dynamic case), and cases when no structure is known (i.e. fully dynamic cases).

This paper presents a new design methodology and tools to construct a packet switched network with bursty data sources. This network design combines two important properties for arbitrary traffic pattern: (1) the aggregate throughput is scalable and (2) there is no packet loss within the subnet. More specifically, given a bounded number of ports in every switching node, the design is based on the construction of multiple virtual rings under the following constraints: (1) the virtual rings are pairwise edge-disjoint and (2) there is at least one virtual ring between any pair of nodes. The target topology is obtained from the edge union of the multiple virtual rings. The two constraints ensure no loss due to congestion inside a network with arbitrary traffic pattern and that packets will reach (or converge) their destinations. The virtual rings are constructed by using combinatorial block designs together with an algorithm for realizing any size networks. It is shown that the bound on the maximum route length, under the two constraints, is O(/spl radic/N) for an N-node network, This sublinear bound facilitates the throughput scalability property.

We present an e-money system where both value of funds and user anonymity can be revoked or suspended unconditionally, but only by the cooperation of banks and consumer rights organizations.We introduce the "ultimate crime," where an active attacker gets the bank's key or forces the bank to give "unmarked bank notes".Our system, unlike all current anonymous systems, can prevent such a crime from successfully being perpetrated, and employs revocation to do so.The mechanisms introduced to balance the need for anonymity against the need to be able to revoke it, together with the notion of challenge semantics that we introduce, provide us with a very versatile system, a second important goal of our investigation.The proposed scheme is efficient and easily extends the basic needs of a practical payment scheme to allow for coin divisibility, checks, credit card purchases and surety bonds.Moreover, the system (unlike some previous ones) is robust against problems arising from spurious equipment.

We consider real-time traffic in a heterogeneous internetworking environment with IP routers, MAC bridges, hubs, switched LANs etc. We assume that the current routing protocols remain unchanged. However in this environment, in order to provide quality of service (QoS): bandwidth, delay, constant-bounded jitter and no-loss due to congestion, we suggest a new flow control function called time-driven priority, which is an internal traffic shaping mechanism. We show how it supports two classes of connections: constant bit rate (CBR) with deterministic guarantees, and variable bit rate (VBR) with statistical multiplexing. The mechanism does not require to identify and separate the packet flows of different real-time sessions/connections inside the network. As a result, it achieves lower switching complexity when compared with other internal traffic shaping methods. As consequences of the time-driven priority mechanism we further achieve: (1) QoS parameters which are independent of the connection bandwidth, (2) QoS parameters which are independent of the existing heterogeneous internetworking asynchronous data traffic and (3) the capability for policing and securing the network QoS.

Max-min fairness has been recognized as an optimal throughput-fairness definition. However, its realization in packet switching networks and its computational requirements have not yet been understood. We attempt to take a step in this direction, in the context of local area network (LAN) traffic. The max-min definition is given in terms of transmission rates of sources sending to their destinations (sessions). In order to realize max-min rates in a packet switching environment, transmission schedules of packets need to be realized. We first show that finding max-min fair schedules (with given rates) requires global state and timing information of all the nodes in the network. We then design a local scheduling algorithm for ring and bus networks with minimum transmission-delay, concurrent access, and spatial bandwidth reuse. This distributed algorithm uses only partial state information and is based on locally exchanging simple signals only between directly conflicting sessions (sessions which share at least one link) rather than collecting global information. The results of this algorithm are novel in various ways: (1) we prove that each session has an access-delay of at most twice its bottleneck link; (2) we show that the algorithm operates adaptively with an optimal access-delay in a dynamic environment (bursty traffic sources); and (3) by means of simulation experiments we further show that this algorithm achieves, in a steady-state, max-min fair rates for a vast majority of sessions and an average aggregate throughput which is 99 percent the throughput obtained by max-min fair rates.

No abstract available.

Traditionally, cryptography and its applications are defensive in nature, and provide privacy, authentication, and security to users. In this paper we present the idea of Cryptovirology which employs a twist on cryptography, showing that it can also be used offensively. By being offensive we mean that it can be used to mount extortion based attacks that cause loss of access to information, loss of confidentiality, and information leakage, tasks which cryptography typically prevents. In this paper we analyze potential threats and attacks that rogue use of cryptography can cause when combined with rogue software (viruses, Trojan horses), and demonstrate them experimentally by presenting an implementation of a cryptovirus that we have tested (we took careful precautions in the process to insure that the virus remained contained). Public-key cryptography is essential to the attacks that we demonstrate (which we call "cryptovirological attacks"). We also suggest countermeasures and mechanisms to cope with and prevent such attacks. These attacks have implications on how the use of cryptographic tools should be managed and audited in general purpose computing environments, and imply that access to cryptographic tools should be well controlled. The experimental virus demonstrates how cryptographic packages can be condensed into a small space, which may have independent applications (e.g., cryptographic module design in small mobile devices).

We suggest a new methodology for "result checking" that enables us to extend the notion of Blum's program result checking to the on-line checking of cryptographic functions. In our model, the checker not only needs to be assured of the correctness of the result but the owner of the program needs to be sure not to give away anything but the requested result on the (authorized) input. The existing approaches for program result checking of numerical problems often ask the program a number of extra queries (different from the actual input). In the case of cryptographic functions, this may be in contradiction with the security requirement of the program owner. Additional queries, in fact, may be used to gain unauthorized advantage (for example, imagine the implications of the on-line checking of a decryption device that requires the decryption of extra ciphertexts). In [Blum88], the notion of a simple checker was introduced where, for the purpose of efficiency, extra queries are not allowed...

Byzantine Agreement among processors is a basic primitive in distributed computing. It comes in a number of basic fault models: "Crash", "Omission" and "Malicious" adversarial behaviors. The message complexity of the primitive has been known for the strong failure models of Malicious and Omission adversary since the early 80's, while the question for the more benign Crash failure model has been open. We show how to solve agreement in the presence of crash failures using O(n) messages which is optimal, thus settling a thirteen year old open problem. Our solution has almost linear time and our new algorithmic techniques have further implications: a family of "early stopping" agreement protocols with improved message-complexity; and a new solution to "Checkpoint" yielding a substantial improvement of the protocol for distributed work performance under adaptive parallelism in a network of workstations.

The paper presents a new design methodology and tools to construct a switch-based LAN with (i) scalable throughput, (ii) no loss due to congestion, and (iii) two routing modes: FIFO or non-FIFO. More specifically, given a bounded degree (number of switch ports) at each node, the design is based on the construction of multiple virtual rings under the following constraints: (i) the virtual rings are pairwise edge-disjoint, and (ii) there is at least one virtual ring between any pair of nodes. The target topology is obtained from the edge union of the multiple virtual rings. The objectives of the above two constraints are (i) to ensure no loss due to congestion inside the network of bursty traffic sources, and (ii) to ensure convergence of packets/cells to their destinations. The virtual rings are constructed by a new methodology that employs combinatorial block designs together with a new algorithm for realizing any size networks. It is shown that the bound on the maximum route length, under the two constraints, is O(/spl radic/N) for an N-node network.

Article Secure hypergraphs: privacy from partial broadcast Share on Authors: Matthew Franklin AT&T Bell Laboratories, Holmdel, NJ AT&T Bell Laboratories, Holmdel, NJView Profile , Moti Yung IBM Research Division, T.J. Watson Center, Yorktown, NY IBM Research Division, T.J. Watson Center, Yorktown, NYView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 36–44https://doi.org/10.1145/225058.225077Online:29 May 1995Publication History 40citation399DownloadsMetricsTotal Citations40Total Downloads399Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

An essential function for achieving security in computer networks is reliable authentication of communicating parties and network components. Such authentication typically relies on exchanges of cryptographic messages between the involved parties, which in turn implies that these parties be able to acquire shared secret keys or certified public keys. Provision of authentication and key distribution functions in the primitive and resource-constrained environments of low-function networking mechanisms, portable, or wireless devices presents challenges in terms of resource usage, system management, ease of use, efficiency, and flexibility that are beyond the capabilities of previous designs such as Kerberos or X.509. This paper presents a family of light-weight authentication and key distribution protocols suitable for use in the low layers of network architectures. All the protocols are built around a common two-way authentication protocol. The paper argues that key distribution may require substantially different approaches in different network environments and shows that the proposed family of protocols offers a flexible palette of compatible solutions addressing many different networking scenarios. The mechanisms are minimal in cryptographic processing and message size, yet they are strong enough to meet the needs of secure key distribution for network entity authentication. The protocols presented have been implemented as part of comprehensive security subsystem prototype called KryptoKnight.>

The MetaNet is a scalable local area network (LAN) architecture with an arbitrary topology and a switch at each node (i.e., a switch based LAN). Its design provides on one hand a service in which any node can try to transmit asynchronously in a bursty manner without reservation as much as it can (as in traditional LAN), and on the other hand the network access and flow control ensure the following properties: (1) no packet loss due to congestion, (2) fair access to the network, (3) no deadlocks, and (4) self-routing with broadcast. The switching over this network requires only a (5) single buffer per input link. The MetaNet is asynchronous, distributed, and designed for transmission of fixed size cells or variable size packets. It can be viewed as a "general-topology buffer-insertion architecture with fairness," thus generalizing the MetaRing architecture.>

We investigate structural properties of statistical zero knowledge (SZK) both in the interactive and in the non-interactive model. Specifically, we look into the closure properties of SZK languages under monotone logical formula composition. This gives rise to new protocol techniques. We show that interactive SZK for random self reducible languages (RSR) (and for co-RSR) is closed under monotone Boolean operations. Namely, we give SZK proofs for monotone Boolean formulae whose atoms are statements about an SZK language which is RSR (or a complement of RSR). All previously known languages in SZK are in these classes. We then show that if a language L has a non-interactive SZK proof system then honest-verifier interactive SZK proof systems exist for all monotone Boolean formulae whose atoms are statements about the complement of L. We also discuss extensions and generalizations.>

This paper presents fault-tolerant protocols for fast packet switch networks with convergence routing. The objective is to provide, after a link or a node (switch) failure, fast reconfiguration and continuous host-to-host communication. Convergence routing is a variant of deflection routing, which combines in a dynamic fashion, the on-line routing decision with the traffic load inside the network. Unlike other deflection techniques, convergence routing guarantees that packets will reach or converge to their destinations. This fault-tolerant solution is designed for a switch-based (i.e., arbitrary topology) LAN architecture called MetaNet. The original MetaNet's convergence routing scheme has been modified in order to facilitate the property that the packet header need not be recomputed after a failure and/or a reconfiguration. This is achieved by having, at the network interface, a translator that maps the unique destination address to a virtual address. The virtual addresses are stored at the packet header, and used for convergence routing, with a global sense of direction over (i) a single spanning tree, and (ii) over two edge-disjoint spanning trees, for redundancy (fault tolerance) and greater efficiency.>

This work presents a coherent system solution for combining with no loss due to congestion, on one hand, bursty traffic with unpredictable pattern in time and space, and on the other hand, periodic real-time or connection-oriented traffic with bandwidth guaranteed requirements over fixed routes. This solution facilitates the implementation of a scalable high performance multimedia system for distributed/parallel computing with real-time interactive voice and video. The MetaNet real-time traffic has the following attributes: (1) guaranteed bandwidth with bounded delay, (2) fixed jitter-independent of the network size, (3) no loss due to congestion inside the network, (4) fixed path routing with FIFO order, and (5) support of complex periodicity scheduling. At the same time, the underlying MetaNet asynchronous (bursty) traffic properties (provided by previous works) remain unchanged. Namely, any node can try to transmit asynchronously (bursty traffic), without reservation as much as it can, and the network access and flow control ensure the following traditional LAN properties: (6) no loss with a single input buffer, (7) fair and deadlock-free access, and (8) self-routing with broadcast. The self-routing on the MetaNet is a variant of deflection routing. It makes on-line routing decisions based on the local flow of traffic (load conditions). Unlike other deflection techniques, the MetaNet routing is along a global sense of direction, which guarantees that cells will reach their destinations. Thus, this method is called convergence routing.>

A novel combinatorial approach to wait-free loadbalancing, counting, synchronization and buffer mancontention notion was only asymptotic (i.e., as achievable eventually).

Article Free Access Share on Time-optimal message-efficient work performance in the presence of faults Authors: Roberto De Prisco Dept. of Computer Science, Columbia University, New York, NY and Dipartimento di Informatica ed Applicazioni, Università di Salerno, 84081 Baronissi (SA), Italy Dept. of Computer Science, Columbia University, New York, NY and Dipartimento di Informatica ed Applicazioni, Università di Salerno, 84081 Baronissi (SA), ItalyView Profile , Alain Mayer Dept. of Computer Science, Columbia University, New York, NY Dept. of Computer Science, Columbia University, New York, NYView Profile , Moti Yung IBM Research Division T.J. Watson Research Center, Yorktown Heights, NY IBM Research Division T.J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computingAugust 1994 Pages 161–172https://doi.org/10.1145/197917.198082Published:14 August 1994Publication History 48citation208DownloadsMetricsTotal Citations48Total Downloads208Last 12 Months20Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on How to share a function securely Authors: Alfredo De Santis Dip. di Informatica ed Applicazioni Università di Salerno, Baronissi (SA), Italy Dip. di Informatica ed Applicazioni Università di Salerno, Baronissi (SA), ItalyView Profile , Yvo Desmedt Dept. of EE&CS, Univ. of Wisconsin Milwaukee, WI Dept. of EE&CS, Univ. of Wisconsin Milwaukee, WIView Profile , Yair Frankel GTE Laboratories Incorporated, Waltham, MA GTE Laboratories Incorporated, Waltham, MAView Profile , Moti Yung IBM T. J. Watson Research Center, Yorktown Heights, NY IBM T. J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 522–533https://doi.org/10.1145/195058.195405Published:23 May 1994Publication History 193citation1,775DownloadsMetricsTotal Citations193Total Downloads1,775Last 12 Months169Last 6 weeks18 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We initiate a graph-theoretic approach to study the (information-theoretic) maintenance of privacy in distributed environments in the presence of a bounded number of mobile eavesdroppers ("bugs"). For two fundamental privacy problems-secure message transmission and distributed database maintenance-we assume an adversary is "playing eavesdropping games," coordinating the movement of the bugs among the sites to learn the current memory contents. We consider various mobility settings (adversaries), motivated by the capabilities (strength) of the bugging technologies (e.g., how fast can a bug be reassigned). We combinatorially characterize and compare privacy maintenance problems, determine their feasibility (under numerous bug models), suggest protocols for the feasible cases, and analyze their computational complexity.>

Various virtual embedding configurations for the MetaNet architecture are examined. The suggested embedding structures are compared and contrasted, and design parameters and their trade-off are identified. Fairness is used as a mechanism to ensure that the network internally will not be overloaded. Therefore, packets can be sent from source to destination on a route which is close to the shortest path. The routing on the MetaNet is a variant of deflection routing. It makes online routing decisions based on the local flow of traffic (load conditions). MetaNet routing is along a global sense of direction, which guarantees that packets will reach their destinations. This method is called convergence routing. The MetaNet is a LAN/MAN architecture with an "arbitrary topology" (i.e., a switch-based LAN).

This paper studies the problem of perfectly secure communication in general network in which processors and communication lines may be faulty. Lower bounds are obtained on the connectivity required for successful secure communication. Efficient algorithms are obtained that operate with this connectivity and rely on no complexity-theoretic assumptions. These are the first algorithms for secure communication in a general network to simultaneously achieve the three goals of perfect secrecy, perfect resiliency, and worst-case time linear in the diameter of the network.

Most existing designs for two-way cryptographic authentication protocols suffer from one or more limitations. Among other things, they require synchronization of local clocks, they are subject to export restrictions because of the way they use cryptographic functions, and they are not amenable to use in lower layers of network protocols because of the size and complexity of messages they use. Designing suitable cryptographic protocols that cater to large and dynamic network communities but do not suffer from these problems presents substantial problems. It is shown how a few simple protocols, including one proposed by ISO, can easily be broken, and properties that authentication protocols should exhibit are derived. A methodology for systematically building and testing the security of a family of cryptographic two-way authentication protocols that are as simple as possible yet resistant to a wide class of attacks, efficient, easy to implement and use, and amenable to many different networking environments is described. Examples of protocols of that family that presents various advantages in specific distributed system scenarios are discussed.>

The authors extend the use of traditional point-to-point message authentication to multireceiver and/or multisender scenarios. They provide efficient cryptographic authentication methods for point-to-multipoint communication, where a single sender can broadcast (multicast) only one unconditionally secure authenticator for a message and which all receivers can verify. They further develop multipoint-to-point communication (incast) in which any subset (of a specified size) of a group of individuals can transmit a single authenticator (or a signature) for a message using the group's key. This method has been called threshold authentication. It is an application layer that is transparent to the receiver which only deals with the group as one entity. The bandwidth, computations, and storage overheads are reduced substantially when compared with the traditional approach. Threshold authentication hides some aspects of the internal structure of the group, which may be important in interenterprise communication.>

A secret-ballot vote for a single proposition is an example of a secure distributed computation. The goal is for m participants to jointly compute the output of some n-ary function (in this case, the sum of the votes), while protecting their individual inputs against some form of misbehavior.

We investigate the problem of self-stabilizing round-robin token management scheme on an anonymous bidirectional ring of identical processors, where each processor is an asynchronous probabilistic (coin-flipping) finite state machine which sends and receives messages. We show that the solution to this problem is equivalent to symmetry breaking (i.e., leader election). Requiring only constant-size messages and message-passing model has practical implications: our solution can be implemented in high-speed networks using a universal fast hardware switches (i.e., finite state machines) of size independent of the size of the network. Our automata-based message-passing model has inherent deadlock possibility (i.e., when all processors are waiting for a message) which we assume is detected by an external timeout mechanism. Provided that there is no deadlock to begin with, we show how starting from an arbitrary con guration, the system never enters a deadlock state and further stabilizes in polynomial time. We note that Dijkstra showed that the last problem does not have a deterministic solution (even when the identical processors possess an arbitrary power): starting from a ring with a multitude of tokens, any deterministic system will either not stabilize or will enter a deadlock state.

Broadcast and broadcast-with-feedback are presented for MetaNet, a novel network architecture which can be viewed as a LAN with an arbitrary topology. The broadcast and broadcast-with-feedback algorithms presented are functionally equivalent to the broadcast on current LANs, e.g. token-ring or Ethernet. The broadcast algorithms are completely loss free under the asynchronous access method. The broadcast is integrated into the routing mechanism such that it can coexist with any traffic pattern. The time complexity of broadcast on the MetaNet (measured in light-load) is O(log n), while on a ring-based LAN the complexity is n. The algorithms can be modified to serve as a multicast procedure.>

We initiate a study of distributed adversarial model of computation in which faults are non-stationary and can move through the net work, analogous to a spread of a virus or a worm.We show how local computations (at each processor) and global computations can be polynomial factor-redundancy in the

The problem of perfectly secure communication in a general network in which processors and communication lines may be faulty is studied. Lower bounds are obtained on the connectivity required for successful secure communication. Efficient algorithms that operate with this connectivity and rely on no complexity theoretic assumptions are derived. These are the first algorithms for secure communication in a general network to achieve simultaneously the goals of perfect secrecy, perfect resiliency, and a worst case time which is linear in the diameter of the network.>

A high-speed network is a new environment motivated by recent advances in transmission technology.The highspeed environment requires that the network node operate (fast) based solely on local information (at least most of the time).This fact implies properties that are much different than those existing in current architectures and algorithms for traditional large-area networks.The new environment poses new challenges for the network architect and the algorithm designer.In this paper we present principles of operation for the basic control functions of a high-speed nelvrorP with an arbitrary topology, we then suggest a design of such a network.In the architecture we design, on one hand a node can try to transmit asynchronously, without reservation, as much as it can, and on the other hand the network access and flow control will ensure no loss, fair access to the network, no deadlocks and self-routing.The switching over this network requires only a single buffer on each side of the full-duplex links.The transmission via the receiving buffer can be "cut through", i.e., the incoming packet can be sent to the next link before the entire packet has arrived (unlike "store-and-forward").A dynamic self-routing technique is implemented, in which the packet header contains only the destination identification when it leaves the source.This information is sufficient for reaching the destination, not necessarily on the same route each time, and to overcome congestions and failures.All these properties are implemented in a distributed manner.The system is asynchronous and designed for transmission of variable size packets.

We show how to construct a public-key cryptosystem (as originally defined by DiNe and Hellman) secure against chosen ciphertezt attacks, given a public-key cryptosystern secure against passive eavesdropping and a noninteractive zero-knowledge proof system in the shared string model.No such secure cryptosystems were known before.A concrete implementation can be based on quadratic residuosity intractability.

Computational resources necessary to generate pseudorandom strings are studied. In particular, lower bounds are proved for pseudorandom number generators, whereas previous research concentrated on upper bounds. The idea of separation of machine-based complexity classes on the basis of their ability (or inability) to generate pseudorandom strings is introduced and investigated.>

We define a Universal One-Way Hash Function family, a new primitive which enables the compression of elements in the function domain. The main property of this primitive is that given an element x. We prove constructively that universal one-way hash functions exist if any 1-1 one-way functions exist.

Interactive communication of knowledge from the point of view of resource-bounded computational complexity is studied. Extending the work of Goldwasser, Micali, and Rackof [Proc. 17th Annual ACM Symposium on the Theory of Computing, 1985, pp. 291–304; .,18 (1989), pp. 186–208], the authors define a protocol transferring the result of any fixed computation to be minimum-knowledge if it communicates no additional knowledge to the recipient besides the intended computational result. It is proved that such protocols may be combined in a natural way so as to build more complex protocols. A protocol is introduced for two parties, a prover and a verifier, with the following properties:(1) Following the protocol, the prover gives to the verifier a proof of the value, 0 or 1, of a particular Boolean predicate, which is (assumed to be) hard for the verifier to compute. Such a deciding “interactive proof-system” extends the interactive proof-systems of [op. cit.], which are used only to confirm that a certain predicate has value 1. (2) The protocol is minimum-knowledge. (3) The protocol is result-indistinguishable: an eavesdropper, overhearing an execution of the protocol, does not learn the value of the predicate that is proved. The value of the predicate is a cryptographically secure bit, shared by the two parties to the protocol. This security is achieved without the use of encryption functions, all messages being sent in the clear. These properties enable one to define a cryptosystem in which each user receives exactly the knowledge he is supposed to receive, and nothing more.

In this paper we introduce a new network model called a muZtimedia network.It combines the point-to-point message passing network and the multiaccess channel.To benefit from the combination we design algorithms which consist of two stages: a local stage which utilizes the parallelism of the point-to-point network and a global stage which utilizes the broadcast capability of the multiaccess channel.As a reasonable approach, one wishes to balance the complexities of the two stages by obtaining an efficient partition of the network 'AT&T Bell Labs.

In this paper we consider a synchronous broadcasting network, a distributed computation model which represents communication networks that are used extensively in practice. We consider a basic problem of information sharing: the computation of the multiple identification function. That is, given a network of p processors, each of which contains an n-bit string of information, how can every processor compute efficiently the subset of processors which have the same information as itself? The problem was suggested by Yao as a generalization of the two-processor case studied in his classic paper on distributed computing (Yao, 1979). The naive way to solve this problem takes O(np) communication time, where a time unit is the time to transfer one bit. We present an algorithm which takes advantage of properties of strings and is O(n log2 p + p) time. A simulation of sorting networks by the distributed model yields an O(n log p + p) (impractical) algorithm. By applying Yao's probabilistic implementation of the two-processor case to both algorithm we get probabilistic versions (with small error) where n is replaced by log n in the complexity expressions. We also present lower bounds for the problem: an Ω(n) and an Ω(p) bound are shown.

Article Distributing the power of a government to enhance the privacy of voters Share on Authors: Josh C Benaloh Yale University Yale UniversityView Profile , Moti Yung Columbia University Columbia UniversityView Profile Authors Info & Claims PODC '86: Proceedings of the fifth annual ACM symposium on Principles of distributed computingNovember 1986 Pages 52–62https://doi.org/10.1145/10590.10595Online:01 November 1986Publication History 138citation559DownloadsMetricsTotal Citations138Total Downloads559Last 12 Months23Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access