Arrow Research search

Author name cluster

Moti Yung

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

35 papers
2 author rows

Possible papers

35

AAAI Conference 2026 Conference Paper

Exploiting Missing Data Remediation Strategies Using Adversarial Missingness Attacks

  • Deniz Koyuncu
  • Alex Gittens
  • Bülent Yener
  • Moti Yung

Adversarial Missingness (AM) attacks aim to manipulate model fitting by carefully engineering a missing data problem to achieve a specific malicious objective. AM attacks are significantly different from prior data poisoning attacks in that no malicious data inserted and no data is maliciously perturbed. Current AM attacks are feasible only under the assumption that the modeler (victim) uses full-information maximum likelihood methods to handle missingness. This work aims to remedy this limitation of AM attacks; in the approach taken here, the adversary achieves their goal by solving a bi-level optimization problem to engineer the adversarial missingness mechanism, where the lower level problem incorporates a differentiable approximation of the targeted missingness remediation technique. As instantiations of this framework, AM attacks are provided for three popular techniques: (i) complete case analysis, (ii) mean imputation, and (iii) regression-based imputation for general empirical risk minimization (ERM) problems. Experiments on real-world data show that AM attacks are successful with modest levels of missingness (less than 20%). Furthermore, we show on the real-world Twins dataset that AM attacks can manipulate the estimated average treatment effect (ATE) as an instance of the general ERM problems: the adversary succeeds in not only reversing the sign, but also in substantially inflating the ATE values from a true value of -1.61% to a manipulated one as high as 10%. These experimental results hold when the ATE is calculated using multiple regression-based estimators with different architectures, even when the adversary is restricted to modifying only a subset of the training data. The goals of this work are to: (i) establish the vulnerability to AM attacks of a significantly wider class of missingness remediation strategies than established in prior work, and (ii) brings the AM threat model to the attention of the community, as there are currently no defense strategies for these attacks.

PDF Details DOI

TIST Journal 2024 Journal Article

Adversarial Missingness Attacks on Causal Structure Learning

  • Deniz Koyuncu
  • Alex Gittens
  • Bülent Yener
  • Moti Yung

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.

Details DOI

TCS Journal 2020 Journal Article

The combinatorics of hidden diversity

  • Juan Garay
  • David Johnson
  • Aggelos Kiayias
  • Moti Yung

In this paper, we study the following “balls in buckets” problem. Suppose there is a sequence B 1, B 2, …, B n of buckets having integer sizes s 1, s 2, …, s n, respectively. For a given target fraction α, 0 < α < 1, our goal is to sequentially place balls in buckets until at least ⌈ α n ⌉ buckets are full, so as to minimize the number of balls used, which we shall denote by O P T α ( I ) for a given instance I. If we knew the size of each bucket, we could obtain an optimal assignment, simply by filling the buckets in order of increasing size until the desired number had been filled. Here we consider the case where, although we know n and α, we do not know the specific bucket sizes s i, and when we place a ball in bucket B j, we only learn whether or not the bucket B j is now full. We study what can be done under four variants of incomplete information: 1. We know nothing at all about the bucket sizes; 2. we know the maximum bucket size; 3. we know the sizes s 1 ≤ s 2 ≤ ⋯ ≤ s m that occur in the instance; and 4. we know the profile of the sizes: the size list as above, and, for each size, s i, the number k i of buckets that have that size, providing both algorithmic performance guarantees and lower bounds on the best that any algorithm can achieve. The game above showcases the rich variety of interesting combinatorial and algorithmic questions that this setup gives rise to, and in addition has applications in an area of cryptography known as secure multi-party computation, where taking over (“corrupting”) a party by an adversary has a cost, and where a hidden diversity—corresponding to lack of information on the amount of computational resources the adversary should invest to corrupt a participant—translates into robustness and efficiency benefits.

Details DOI

TCS Journal 2017 Journal Article

Self-updatable encryption: Time constrained access control with hidden attributes and better efficiency

  • Kwangsu Lee
  • Seung Geol Choi
  • Dong Hoon Lee
  • Jong Hwan Park
  • Moti Yung

Revocation and key evolving paradigms are central issues in cryptography, and in PKI in particular. A novel concern related to these areas was raised in the recent work of Sahai, Seyalioglu, and Waters (CRYPTO 2012) who noticed that revoking past keys should at times (e. g. , the scenario of cloud storage) be accompanied by revocation of past ciphertexts (to prevent unread ciphertexts from being read by revoked users). They introduced revocable-storage attribute-based encryption (RS-ABE) as a good access control mechanism for cloud storage. RS-ABE protects against the revoked users not only the future data by supporting key-revocation but also the past data by supporting ciphertext-update, through which a ciphertext at time T can be updated to a new ciphertext at time T + 1 using only the public key. Motivated by this pioneering work, we ask whether it is possible to have a modular approach, which includes a primitive for time managed ciphertext update as a primitive. We call encryption which supports this primitive a “self-updatable encryption” (SUE). We then suggest a modular cryptosystems design methodology based on three sub-components: a primary encryption scheme, a key-revocation mechanism, and a time-evolution mechanism which controls the ciphertext self-updating via an SUE method, coordinated with the revocation (when needed). Our goal in this is to allow the self-updating ciphertext component to take part in the design of new and improved cryptosystems and protocols in a flexible fashion. Specifically, we achieve the following results: We first introduce a new cryptographic primitive called self-updatable encryption (SUE), realizing a time-evolution mechanism. In SUE, a ciphertext and a private key are associated with time. A user can decrypt a ciphertext if its time is earlier than that of his private key. Additionally, anyone (e. g. , a cloud server) can update the ciphertext to a ciphertext with a newer time. We also construct an SUE scheme and prove its full security under static assumptions. Following our modular approach, we present a new RS-ABE scheme with shorter ciphertexts than that of Sahai et al. and prove its security. The length efficiency is mainly due to our SUE scheme and the underlying modularity. We apply our approach to predicate encryption (PE) supporting attribute-hiding property, and obtain a revocable-storage PE (RS-PE) scheme that is selectively-secure. We further demonstrate that SUE is of independent interest, by showing it can be used for timed-release encryption (and its applications), and for augmenting key-insulated encryption with forward-secure storage.

Details DOI

TCS Journal 2016 Journal Article

Born and raised distributively: Fully distributed non-interactive adaptively-secure threshold signatures with short shares

  • Benoît Libert
  • Marc Joye
  • Moti Yung

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 hard to assure and hard to administer properly in actual systems). To the best of our knowledge, such a fully distributed highly constrained scheme has been an open problem in the area. In particular, and of special interest, is the fact that Pedersen's traditional distributed key generation (DKG) protocol can be safely employed in the initial key generation phase when the system is born—although it is well-known not to ensure uniformly distributed public keys. An advantage of this is that this protocol only takes one round optimistically (in the absence of faulty player).

Details DOI

TCS Journal 2015 Journal Article

Sequential aggregate signatures with short public keys without random oracles

  • Kwangsu Lee
  • Dong Hoon Lee
  • Moti Yung

The notion of aggregate signature has been motivated by applications and it enables any user to compress different signatures signed by different signers on different messages into a short signature. Sequential aggregate signature, in turn, is a special kind of aggregate signature that only allows a signer to add his signature into an aggregate signature in sequential order. This latter scheme has applications in diversified settings such as in reducing bandwidth of certificate chains and in secure routing protocols. Lu, Ostrovsky, Sahai, Shacham, and Waters (EUROCRYPT 2006) presented the first sequential aggregate signature scheme in the standard model. The size of their public key, however, is quite large (i. e. , the number of group elements is proportional to the security parameter), and therefore, they suggested as an open problem the construction of such a scheme with short keys. In this paper, we propose the first sequential aggregate signature schemes with short public keys (i. e. , a constant number of group elements) in prime order (asymmetric) bilinear groups that are secure under static assumptions in the standard model. Furthermore, our schemes employ a constant number of pairing operations per message signing and message verification operation. Technically, we start with a public-key signature scheme based on the recent dual system encryption technique of Lewko and Waters (TCC 2010). This technique cannot directly provide an aggregate signature scheme since, as we observed, additional elements should be published in a public key to support aggregation. Thus, our constructions are careful augmentation techniques for the dual system technique to allow it to support sequential aggregate signature schemes. We also propose a multi-signature scheme with short public parameters in the standard model.

Details DOI

TCS Journal 2013 Journal Article

Adaptively secure non-interactive threshold cryptosystems

  • Benoît Libert
  • Moti Yung

Threshold cryptography aims at enhancing the availability and security of decryption and signature schemes by splitting private keys into several (say n ) shares (typically, each of size comparable to the original secret key). In these schemes, a quorum of at least ( d ≤ n ) servers needs to act upon a message to produce the result (decrypted value or signature), while corrupting less than d servers maintains the scheme’s security. For about two decades, extensive study was dedicated to this subject, which created a number of notable results. So far, most practical threshold signatures, where servers act non-interactively, were analyzed in the limited static corruption model (where the adversary chooses which servers will be corrupted at the system’s initialization stage). Existing threshold encryption schemes that withstand the strongest combination of adaptive malicious corruptions (allowing the adversary to corrupt servers at any time based on its complete view), and chosen-ciphertext attacks (CCA) all require interaction (in the non-idealized model) and attempts to remedy this problem resulted only in relaxed schemes. The same is true for threshold signatures secure under chosen-message attacks (CMA). To date (for about 10 years), it has been open whether there are non-interactive threshold schemes providing the highest security (namely, CCA-secure encryption and CMA-secure signature) with scalable shares (i. e. , as short as the original key) and adaptive security. This paper answers this question affirmatively by presenting such efficient decryption and signature schemes within a unified algebraic framework.

Details DOI

TCS Journal 2011 Journal Article

Efficient traceable signatures in the standard model

  • Benoît Libert
  • Moti Yung

Traceable signatures (TS), suggested by Kiayias, Tsiounis and Yung (Eurocrypt’04), extend group signatures to address various basic traceability issues beyond merely identifying the anonymous signer of a rogue signature. Namely, they enable the efficient tracing of all signatures produced by a misbehaving party without opening the identity of other parties. They also allow users to provably claim ownership of a previously signed anonymous signature. To date, known TS systems all rely on the random oracle model. In this work we present the first realization of the primitive that avoids resorting to the random oracle methodology in its security proofs. Furthermore, our realization’s efficiency is comparable to that of the latest fastest and shortest standard model group signatures.

Details DOI

TCS Journal 2007 Journal Article

Decoding interleaved Reed–Solomon codes over noisy channels

  • Daniel Bleichenbacher
  • Aggelos Kiayias
  • Moti Yung

We consider error correction over the Non-Binary Symmetric Channel (NBSC) which is a natural probabilistic extension of the Binary Symmetric Channel (BSC). We propose a new decoding algorithm for interleaved Reed–Solomon codes that attempts to correct all “interleaved” codewords simultaneously. In particular, interleaved encoding gives rise to multi-dimensional curves and more specifically to a variation of the Polynomial Reconstruction Problem, which we call Simultaneous Polynomial Reconstruction. We present and analyze a novel probabilistic algorithm that solves this problem. Our construction yields a decoding algorithm for interleaved RS codes that allows efficient transmission arbitrarily close to the channel capacity in the NBSC model.

Details DOI

TCS Journal 2002 Journal Article

Adaptively secure distributed public-key systems

  • Yair Frankel
  • Philip MacKenzie
  • Moti Yung

When attacking a distributed protocol, an adaptive adversary is able to determine its actions (e. g. , which parties to corrupt) at any time based on its entire view of the protocol including the entire communication history. Proving security of cryptographic protocols against adaptive adversaries is a fundamental problem in cryptography. In this paper, we consider distributed public-key systems which are secure against an adaptive adversary. Specifically, we construct distributed discrete-log-based and RSA-based public-key systems secure against an adaptive adversary. We also extend the discrete-log-based systems to have proactive security, that is, security against an (adaptive) mobile adversary that has an upper bound on the number of servers it may corrupt at any one time, but no upper bound on the number of servers it may corrupt over the lifetime of the system.

Details DOI

FOCS Conference 1999 Conference Paper

Non-Interactive CryptoComputing For NC 1

  • Tomas Sander
  • Adam L. Young
  • Moti Yung

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.

Details

FOCS Conference 1997 Conference Paper

Optimal Resilience Proactive Public-Key Cryptosystems

  • Yair Frankel
  • Peter Gemmell
  • Philip D. MacKenzie
  • Moti Yung

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.

Details

TCS Journal 1997 Journal Article

Scheduling task-trees with additive scales on parallel/distributed machines

  • Xiangdong Yu
  • Moti Yung

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).

Details DOI

TCS Journal 1997 Journal Article

The local detection paradigm and its applications to self-stabilization

  • Yehuda Afek
  • Shay Kutten
  • Moti Yung

A new paradigm for the design of self-stabilizing distributed algorithms, called local detection, is introduced. The essence of the paradigm is in defining a local condition based on the state of a processor and its immediate neighborhood such that the system is in a globally legal state if and only if the local condition is satisfied at all the nodes. In this work we also extend the model of self-stabilizing networks traditionally assuming memory failure to include the model of dynamic networks (assuming edge failures and recoveries). We apply the paradigm to the extended model which we call “dynamic self-stabilizing networks”. Without loss of generality, we present the results in the least restrictive shared memory model of read/write atomicity, to which end we construct basic information transfer primitives. Using local detection, we develop deterministic and randomized self-stabilizing algorithms that maintain a rooted spanning tree in a general network whose topology changes dynamically. The deterministic algorithm assumes unique identities while the randomized assumes an anonymous network. The algorithms use a constant number of memory words per edge in each node; and both the size of memory words and of messages is the number of bits necessary to represent a node identity (typically O(log n) bits where n is the size of the network). These algorithms provide for the easy construction of self-stabilizing protocols for numerous tasks: reset, routing, topology-update and self-stabilization transformers that automatically self-stabilize existing protocols for which local detection conditions can be defined.

Details DOI

FOCS Conference 1995 Conference Paper

Resolving Message Complexity of Byzantine Agreement and beyond

  • Zvi Galil
  • Alain J. Mayer
  • Moti Yung

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.

Details

FOCS Conference 1994 Conference Paper

On Monotone Formula Closure of SZK

  • Alfredo De Santis
  • Giovanni Di Crescenzo
  • Giuseppe Persiano
  • Moti Yung

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. >

Details

FOCS Conference 1993 Conference Paper

Eavesdropping Games: A Graph-Theoretic Approach to Privacy in Distributed Systems

  • Matthew K. Franklin
  • Zvi Galil
  • Moti Yung

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. >

Details

TCS Journal 1991 Journal Article

Constant-round perfect zero-knowledge computationally convincing protocols

  • Gilles Brassard
  • Claude Crépeau
  • Moti Yung

A perfect zero-knowledge interactive protocol allows a prover to convince a verifier of the validity of a statement in a way that does not give the verifier any additional information. Such protocols take place by the exchange of messages back and forth between the prover and the verifier. An important measure of efficiency for these protocols is the number of rounds in the interaction. In previously known perfect zero-knowledge protocols for statements concerning NP-complete problems, at least k rounds were necessary in order to prevent one party from having a probability of undetected cheating greater than 2−k. In this paper, we give the first perfect zero-knowledge protocol that offers arbitrarily high security for any statement in NP with a constant number of rounds. The protocol is computationally convincing (rather than statistically convincing as would have been an interactive proof-system in the sense of Goldwasser, Micali and Rackoff) because the verifier's belief in the prover's claim is partly based on the assumption that it is feasible to find a prime p with known factorization of p − 1 such that it is infeasible to compute discrete logarithms modulo p even for someone who knows the factors of p − 1. Our protocol can also be based on the more general assumption that one-way certified group actions exist. It is still open whether it would be sufficient to assume the existence of one-way functions in order to obtain perfect zero-knowledge computationally convincing interactive protocols for all statements in NP.

Details DOI

FOCS Conference 1990 Conference Paper

Perfectly Secure Message Transmission

  • Danny Dolev
  • Cynthia Dwork
  • Orli Waarts
  • Moti Yung

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. >

Details

FOCS Conference 1989 Conference Paper

Lower Bounds for Pseudorandom Number Generators

  • Michael Kharitonov
  • Andrew V. Goldberg
  • Moti Yung

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. >

Details