We introduce the first El Gamal based mix-net in which each mix-server partially decrypts and permutes its input, i.e., no reencryption is necessary. An interesting property of the construction is that a sender can verify non-interactively that its message is processed correctly. We call this sender verifiability. The mix-net is provably UC-secure against static adversaries corrupting any minority of the mix-servers. The result holds under the decision Diffie-Hellman assumption, and assuming an ideal bulletin board and an ideal zero-knowledge proof of knowledge of a correct shuffle. Then we construct the first proof of a decryption-permutation shuffle, and show how this can be transformed into a zero-knowledge proof of knowledge in the UC-framework. The protocol is sound under the strong RSA-assumption and the discrete logarithm assumption. Our proof of a shuffle is not a variation of existing methods. It is based on a novel idea of independent interest, and we argue that it is at least as efficient as previous constructions.
Vijayalakshmi Atluri, Soon Ae Chun, Pietro Mazzoleni
Workflow systems are gaining importance as an infrastructure for automating inter-organizational interactions, such as those in Electronic Commerce. In such an environment, a centralized Workflow Management System is not desirable because: (i) it can be a performance bottleneck, and (ii) the system s are inherently distributed, heterogeneous, and autonomous in nature. Decentralized execution of inter-organizational workflows may raise a number of security issues including those related to conflict-of-interest among competing organizations. In this paper, we first provide an approach to realize decentralized workflow execution, in which the workflow is divided into partitions, called self-describing workflows, and handled by a light weight workflow management component, called workflow stub, located at each organizational agent. Second, we identify the limitations of the traditional workflow model with respect to expressing the various types of join dependencies and extend the traditional workflow model suitably. Distinguishing the different types of dependencies among tasks is essential in the efficient execution of self-describing workflows. Finally, we recognize that placing the task execution agents that belong to the same conflict-of-interest class in one self-describing workflow may lead to unfair, and in some cases, undesirable results, akin to being on the wrong side of the Chinese wall. Therefore, to address the conflict-of-interest issues that arise in competitive business environments, we propose a decentralized workflow Chinese wall security model. We propose a restrictive partitioning solution to enforce the proposed model.
Information, as an expression of knowledge is probably the most valuable asset of humanity today. By enabling relatively cost-free, fast, and accurate access channels to information in digital form, computers have radically changed the way we think and express ideas. As increasingly more of it is produced, packaged and delivered in digital form in a fast, networked environment, one of its main features threatens to become its worst enemy: zero-cost verbatim copies. The inherent ability to produce duplicates of digital Works at virtually no cost can be now misused e.g. for illicit profit. This dramatically increases the requirement for effective protection mechanisms. Different avenues are available, each with its advantages and drawbacks. Enforcement by legal means is usually ineffective, unless augmented by a digital counter-part such as Information Hiding. Digital Watermarking deploys Information Hiding as a method of Rights Protection to conceal an indelible rights witness (watermark) within the digital Work to be protected. The soundness of such a method relies on the assumption that altering the Work in the process of hiding the mark does not destroy the value of the Work, and that it is difficult for a malicious adversary (Mallory) to remove or alter the mark beyond detection without destroying the value of the Work. The ability to resist attacks from such an adversary (mostly aiming at removing the embedded watermark) is one of the major concerns in the design of a sound watermarking solution.
With the notable exception of software watermarking, the overwhelming majority of research efforts have been invested in the framework of multimedia data (e.g. images, video and audio). In this work, I analyze digital watermarking from a higher level, domain-independent perspective. I propose a theoretical model [Sion et al, IEEE ITCC 2002] and in [Sion et al, SPIE 2004] ask: are there any limitations to what watermarking can do? What are these and when can they be reached? I then propose, design and analyze watermarking solutions for (i) numeric sets [Sion et al, IWDW 2002], (ii) numeric relational data [Sion et al, SIGMOD 2003, ICDE 2004], (iii) categorical data [Sion, ICDE 2004], (iv) streams [Sion et al, under review] and (v) semi-structures [Sion et al, IWDW 2003, NSF EIA-9903545]. I also explored the ability to hide information in natural language text [Atallah et. al., IHW02, Springer-Verlag], and developed a text tamper-proofing proof-of-concept [Naval Research grant N00014-02-1-0364/2002].
Internet Traffic Analysis and Secure E-voting
Advanced Steganography and Watermarking Techniques
We consider the basic cryptographic primitive known as zero-knowledge proofs on committed bits. In this primitive, a prover P commits to a set of bits, and then at a later time convinces a verifier V that some property /spl Pscr/ holds for a subset of these bits. It is known how to implement this primitive based on an ordinary bit-committal primitive, but the standard implementations involve a great deal of interaction between the prover and the verifier. We introduce new implementations that require markedly less interaction. We implement bounded-interaction proofs on committed bits, generalizing a model of A. De Micali et al. (1988). For all security parameters, our implementations require only a lg/sup 2/ (n) overhead over the best known circuit-based interactive implementations; for sufficiently large security parameters this gap drops to a lg(n) factor.>
A zap is a 2‐round, public coin witness‐indistinguishable protocol in which the first round, consisting of a message from the verifier to the prover, can be fixed “once and for all” and applied to any instance. We present a zap for every language in NP, based on the existence of noninteractive zero‐knowledge proofs in the shared random string model. The zap is in the standard model and hence requires no common guaranteed random string. We present several applications for zaps, including 3‐round concurrent zero‐knowledge and 2‐round concurrent deniable authentication, in the timing model of Dwork, Naor, and Sahai [J. ACM, 51 (2004), pp. 851–898], using moderately hard functions. We also characterize the existence of zaps in terms of a primitive called verifiable pseudorandom bit generators.
The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain constant-round zero-knowledge proofs and proofs of knowledge (for NP), one had to allow simulators and knowledge-extractors to run in time which is only polynomial on the average (i.e., expected polynomial time). Whether or not allowing expected polynomial-time is necessary for obtaining constant-round zero-knowledge proofs and proofs of knowledge, has been posed as an important open question. This question is interesting not only for its theoretical ramifications, but also because expected polynomial time simulation is not closed under composition. Therefore, in some cases security is not maintained when a protocol that utilizes expected polynomial time simulation (or extraction) is used as a part of a larger protocol.A partial answer to the question of the necessity (or non-necessity) of expected polynomial-time was provided recently by Barak, who gave the first constant-round zero-knowledge argument with a strict (in contrast to expected) polynomial-time simulator. His was also the first protocol that is not black-box zero-knowledge. That is, the simulator in his protocol utilizes the description of the code of the verifier in an essential way.In this paper, we completely resolve the question of expected polynomial-time in zero-knowledge arguments and arguments of knowledge. First, we show that there exist constant-round zero-knowledge arguments of knowledge with strict polynomial-time extractors. As in the simulator of Barak's zero-knowledge protocol, the extractor for our proof of knowledge is not black-box and uses the code of the prover in an essential way.On the negative side, we show that non-black-box techniques are essential to both strict polynomial-time simulation and extraction. That is, we show that no constant-round zero-knowledge argument (or proof) can have a strict polynomial-time black-box simulator. Similarly, we show that no constant-round zero-knowledge argument (or proof) of knowledge can have a strict polynomial-time black-box knowledge extractor. Thus, for constant-round black-box zero-knowledge arguments (resp., arguments of knowledge), it is imperative that the simulator (resp., extractor) be allowed to run in expected polynomial-time.
Vijayalakshmi Atluri, Soon Ae Chun, Pietro Mazzoleni
Workflow systems are gaining importance as an infrastructure for automating inter-organizational interactions, such as those in Electronic Commerce. Execution of inter-organiz-ational workflows may raise a number of security issues including those related to conflict-of-interest among competing organizations. Moreover, in such an environment, a centralized Workflow Management System is not desirable because: (i) it can be a performance bottleneck, and (ii) the systems are inherently distributed, heterogeneous and autonomous in nature. In this paper, we propose an approach to realize decentralized workflow execution, in which the workflow is divided into partitions called self-describing workflows, and handled by a light weight workflow management component, called workflow stub, located at each organizational agent. We argue that placing the task execution agents that belong to the same conflict-of-interest class in one self-describing workflow may lead to unfair, and in some cases, undesirable results, akin to being on the wrong side of the Chinese wall. We propose a Chinese wall security model for the decentralized workflow environment to resolve such problems, and a restrictive partitioning solution to enforce the proposed model.
. An interactive proof system (or argument) (P; V ) is concurrent zero-knowledge if whenever the prover engages in polynomially many concurrent executions of (P; V ), with (possibly distinct) colluding polynomial time bounded veriers V1 ; : : : ; V poly(n) , the entire undertaking is zero-knowledge. Dwork, Naor, and Sahai recently showed the existence of a large class of concurrent zero-knowledge arguments, including arguments for all of NP, under a reasonable assumption on the behavior of clocks of nonfaulty processors. In this paper, we continue the study of concurrent zero-knowledge arguments. After observing that, without recourse to timing, the existence of a trusted center considerably simpli- es the design and proof of many concurrent zero-knowledge arguments (again including arguments for all of NP), we design a preprocessing protocol, making use of timing, to simulate the trusted center for the purposes of achieving concurrent zero-knowledge. Once a particular p...
Concurrent executions of a zero-knowledge protocol by a single prover (with one or more verifiers) may leak information and may not be zero-knowledge in toto . In this article, we study the problem of maintaining zero-knowledge.We introduce the notion of an (α, β) timing constraint : for any two processors P 1 and P 2 , if P 1 measures α elapsed time on its local clock and P 2 measures β elapsed time on its local clock, and P 2 starts after P 1 does, then P 2 will finish after P 1 does. We show that if the adversary is constrained by an (α, β) assumption then there exist four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in NP . We also address the more specific problem of Deniable Authentication , for which we propose several particularly efficient solutions. Deniable Authentication is of independent interest, even in the sequential case; our concurrent solutions yield sequential solutions without recourse to timing , that is, in the standard model.
We look at the question of how powerful a prover must be to give a zero-knowledge proof.We present the first unconditional bounds on the complexity of a statistical ZK prover.The result is that if a language possesses a statistical zero-knowledge then it also possesses a statistical zero-knowledge proof in which the prover runs in probabilistic, polynomial time with an NP oracle.Previously this was only known given the existence of one-way permutations. Extendingthese techniques to protocols of knowledge complexity k(n) >0, we derive bounds on the time complexity of languages of "small" knowledge complexity.Underlying these results is a technique for efficiently generating an "almost" random element of a set S E P.Namely, we construct a probabilistic machine with an NP oracle which, on input 1" and 6 > 0 runs in time polynomial in n and lg 6-1, and outputs a random string from a distribution within distance 6 of the uniform distribution on S n {O, l}~.
While the intuition underlying a zero knowledge proof system [GMR85] is that no “knowledge” is leaked by the prover to the verifier, researchers are just beginning to analyze such proof systems in terms of formal notions of knowledge. In this paper, we show how interactive proof systems motivate a new notion of practical knowledge, and we capture the definition of an interactive proof system in terms of practical knowledge. Using this notion of knowledge, we formally capture and prove the intuition that the prover does not leak any knowledge of any fact (other than the fact being proven) during a zero knowledge proof. We extend this result to show that the prover does not leak any knowledge of how to compute any information (such as the factorization of a number) during a zero knowledge proof. Finally, we define the notion of a weak interactive proof in which the prover is limited to probabilistic, polynomial-time computations, and we prove analogous security results for such proof systems. We show that, in a precise sense, any nontrivial weak interactive proof must be a proof about the prover's knowledge, and show that, under natural conditions, the notions of interactive proofs of knowledge defined in [TW87] and [FFS87] are instances of weak interactive proofs.