Boneh and Franklin proposed one of the first constructions of the very elegant concept of identity-based encryption (IBE) two decades ago. Despite many research advances and its several potential applications, IBE has not achieved enough in real-life use. One likely reason is that it puts too much trust in the key derivation server, also known as the IBE key escrow problem or the problem of reducing server trust in IBE schemes. Specifically, its PKG (private key generator) can implicitly decrypt all ciphertexts. In this paper, we propose a new approach to address the IBE key escrow/server trust problem: enhance IBE schemes by distributing key derivation across all receivers, and thus moving most or even all of the key derivation capability from the server to the decrypting receivers. Specifically, we target solutions with minimal server needs: either no central server or a repository server that only maintains a master public key of size independent of the number of users, but does not maintain any secret data or secret keys. Indeed, we show protocols based on well-known conventional IBE schemes, which work in a public parameter model (i.e., including neither a common reference string with private data kept by the server, nor a common random string model generated by a third party). Our main performance objective is to have no or minimal modification to the encryption algorithm, so as to make the resulting schemes usable for Internet of Things (IoT) applications and minimize any extra resource cost at encrypting sensors in this domain. No previous work achieved this performance goal in conjunction with minimal server needs before, and our solutions are optimal on our performance goal, while achieving essentially minimal server needs. The closest results from previous work consist of either replicating the key derivation server into many of which only a threshold is trusted, or of the recent notion of registration-based encryption, whose main performance goal is to reduce the number of receiver accesses to the server during key derivation.

Advances in wireless networking, such as 5G, continue to enable the vision of the Internet of Things (IoT), where everything is connected, and much data is collected by IoT devices and made available to interested parties (i.e., application servers). However, events such as botnet attacks (e.g., [1]) demonstrate that there are important challenges in this evolution.In this paper we consider the problem of scalable and secure data publication from IoT devices, with included mechanisms that help towards device attacks prevention and detection. We propose SEDIMENT, a system and methodology which look more specifically at problems that arise in a network with a broad variety of devices, some of which have limited resources and some of which were designed for a less hostile environment. SEDIMENT uses a combination of software root of trust, remote attestation and resource-efficient cryptography, to build a system that scales across heterogeneous computing platforms. It allows for devices that range from battery-powered devices that are intended to operate for long periods up to server-class machines without power constraints. SEDIMENT provides a secure application layer that can be used for common communication paradigms such as publish-subscribe while following zero-trust principles in both protecting the end hosts from the network and other end hosts, as well as protecting the network from the end hosts.

We investigate the problem of delegating operations in cryptography solutions from client devices that only perform quasilinear-time or lower-order computations (e.g., additions/subtractions, modular reductions with a small modulus, etc.) to a single, possibly malicious, server. All previous work considered clients capable of computing higher-order operations, such as fully homomorphic encryption, group exponentiations or several group multiplications. In this model, we show protocols to delegate the computation of ring multiplications while satisfying desirable result correctness, input privacy and result security requirements. The main technical component, of independent interest, is a family of probabilistic tests that extends a classical test by Pippenger. The asymptotic improvement in our multiplication delegation protocols is also backed up by concrete implementation results, demonstrating that the client's online computation is strictly smaller than non-delegated computation of the same function, for input lengths of interest in cryptography solutions.

As research of lightweight cryptographic primitives keeps widening, so does the need for different approaches towards rigorous analysis of their properties. In this paper we investigate the use of suitable variations of the ideal cipher analysis methodology to a class of lightweight stream ciphers. Our case study is a suite of lightweight cryptographic techniques proposed in the industry domain to efficiently target communication security while meeting use cases such as interconnected devices working in Low Power Wide Area networks. First of all, we isolate these lightweight techniques as non-linear, additive, stream ciphers. Then, we describe theoretical analysis to support some evidence of plausible security: (a) high-period stream ciphers rule out certain classes of attacks; (b) idealized versions of the analyzed lightweight stream ciphers have high period. Finally, we show empirical performance results, demonstrating effective cipher methods that easily fit into the limited resources of constrained environments, while outperforming state-of-the-art methods in unconstrained environments (e.g., the AES block cipher) by almost one order of magnitude.

We address the practicality challenges of secure program obfuscation by implementing, optimizing, and experimentally assessing an approach to securely obfuscate conjunction programs proposed in [1]. Conjunction programs evaluate functionsf(x1,...,xL) = Λi∈Iyi, whereyiis eitherxior ¬xiandI⊆ [L], and can be used as classifiers. Our obfuscation approach satisfies distributional Virtual Black Box (VBB) security based on reasonable hardness assumptions, namely an entropic variant of the Ring Learning with Errors (Ring-LWE) assumption. Prior implementations of secure program obfuscation techniques support either trivial programs like point functions, or support the obfuscation of more general but less efficient branching programs to satisfy Indistinguishability Obfuscation (IO), a weaker security model. Further, the more general implemented techniques, rather than relying on standard assumptions, base their security on conjectures that have been shown to be theoretically vulnerable. Our work is the first implementation of non-trivial program obfuscation based on polynomial rings. Our contributions include multiple design and implementation advances resulting in reduced program size, obfuscation runtime, and evaluation runtime by many orders of magnitude. We implement our design in software and experimentally assess performance in a commercially available multi-core computing environment. Our implementation achieves runtimes of 6.7 hours to securely obfuscate a 64-bit conjunction program and 2.5 seconds to evaluate this program over an arbitrary input. We are also able to obfuscate a 32-bit conjunction program with 53 bits of security in 7 minutes and evaluate the obfuscated program in 43 milliseconds on a commodity desktop computer, which implies that 32-bit conjunction obfuscation is already practical. Our graph-induced (directed) encoding implementation runs up to 25 levels, which is higher than previously reported in the literature for this encoding. Our design and implementation advances are applicable to obfuscating more general compute-and-compare programs and can also be used for many cryptographic schemes based on lattice trapdoors.

We study the problem of privately performing database queries (i.e., keyword searches and conjunctions over them), where a server provides its own database for a client’s query-based access. We propose a cryptographic model for the study of such protocols, by expanding previous well-studied models of keyword search and private information retrieval to incorporate a more practical data model: a time-varying, multi-attribute and multiple-occurrence database table. Our first result is a 2-party private database retrieval protocol. This is the first protocol that preserves query and data privacy on such a practical data model. Like all previous work in private information retrieval and keyword search, this protocol still satisfies server time complexity linear in the database size. Our main result is a private database retrieval protocol in a 3-party model where encrypted data is outsourced to a third party (i.e., a cloud server), satisfying highly desirable privacy and efficiency properties; most notably: (1) no unintended information is leaked to clients or servers, and only minimal ‘access pattern’ information is leaked to the third party; (2) for each query, all parties run in time only logarithmic in the number of database records; (3) the protocol’s runtime is practical for real-life applications, as shown in our implementation where we achieve response time that is only a small constant slower than commercial non-private protocols like MySQL. This is the first protocol that achieves privacy of database and query content with practical performance. Finally, we show a second private database retrieval protocol in the 3-party model for which we can show that no unintended information is leaked to an adversary corrupting both clients and third parties, at an only constant additional performance overhead cost.

Random graphs are often used to model vehicular networks. However, their applicability has been limited because it is difficult to express and instantiate parameters of graph models of vehicular networks using real-life data. In this paper, we consider using random geometric graphs to model vehicular networks where vehicle movements are constrained to a road system. We show that vehicles form a random geometric graph with edge probability p that can be expressed as a closed-form expression or as an algorithmically computable expression with parameters that are known or easily measurable in real life. This enables one to answer essential questions, such as questions related to routing and placement of mobile nodes required to detect malicious parties in vehicular communications, as a function of practically measurable and computable parameters.

Motivated by vehicular networking applications, we study a novel type of privacy-preserving public-key infrastructures where the server that distributes public and private keys to clients need not be trusted by clients to protect its secret data against intruders. We target three main requirements for these public-key infrastructures: privacy preservation of the client's identity (or, anonymity), traceability of malicious messages to clients corrupted by an attacker rather than honest clients (or, traceability) and communication and computation time constant with respect to the number of users (or, efficiency). This combination of properties was not achieved in previously studied areas such as broadcast or multicast encryption, group signatures and ring signatures. This paper designs a public key infrastructure that achieves satisfactory performance on all three requirements, based on key pools and a novel probabilistic key revocation and update strategy. Perhaps surprisingly, we use a careful design of our revocation protocol to achieve a combination of properties for public-key infrastructures that was not previously achieved.

Abstract As vehicular networks approach deployment phases, there is wide recognition for challenges and pressing needs for solutions with respect to the areas of security, privacy, and performance. The requirement of participation in applications such as traffic safety, combined with the intrinsically ad hoc network environment, poses rather novel challenges to the modeling, design, and analysis of security solutions for vehicular networks. One particularly stringent requirement in this area is that of protecting the privacy of vehicle owners (i.e., their anonymity and their vehicle's location unlinkability) during their participation in a vehicular network such as in traffic safety applications. In this paper, we present novel models of concrete anonymity and unlinkability requirements for vehicular networks that can be built using state‐of‐the‐art options for communication network deployment (e.g., road‐side short‐range radio networks and hotspot networks). One key aspect of our modeling consists of recognizing the existence and impact of additional certification authorities managed by vehicle manufacturers. In particular, we consider a simple variant of a previously proposed public‐key infrastructure (PKI) for vehicular networks and present two techniques to augment it so that it provides improved anonymity and unlinkability properties. The resulting vehicular‐network key infrastructures satisfy desirable combinations of anonymity, unlinkability, bad actor detection, and performance requirements. Copyright © 2010 John Wiley & Sons, Ltd.

PKI-based security in Vehicular Networks has to heavily rely on revoking the malicious user by adding his certificates to a Certificate Revocation List and broadcasting it to all the nodes. In a vehicular network with minimal infrastructure there is a need for a quick and reliable delivery or this CRL to all the nodes. While vehicle-to-vehicle or infrastructure-to-vehicle flooding could seem a natural way to deliver the CRL to all the nodes, existing flooding techniques either are unreliable, generate overwhelming unnecessary retransmission or incur excessive network control overhead. In this paper we study the problem of efficient distribution of CRLs in a vehicular network with minimal infrastructure by analyzing the performance of several broadcast protocols for CRL distribution. Our overall result is the definition and analysis of efficient CRL geo-cast protocols over vehicular networks with realistic scenarios of maps with varying density regions. Previous results did not consider the case of varying density regions or required a significant number of infrastructure servers. In the process, we reduce the problem of efficient geo-cast over a practical geographic map to the much more tractable problem of efficient broadcast over a region with an arbitrary vehicle density, which is solved via natural variants of known broadcasting protocols.

Vehicular networks require secure communication, especially for safety applications. A public key infrastructure using a Combinatorial Certificate Scheme was implemented in the US Vehicle Infrastructure Integration (VII) Proof-of- Concept (PoC) trial to secure V2V communication and preserve vehicle privacy. This paper analyzes the privacy and scalability of the Combinatorial Certificate approach for a nationwide network of 200 million vehicles. It examines the tradeoffs between privacy, the ability to efficiently detect and remove bad actors, and the need to minimize the impact on innocent vehicles due to revocation and replacement of compromised shared certificates. Key findings include the level of vehicle anonymity that exists in situations of low vehicular density and the impact that certificate revocations have on innocent vehicles. A refinement to the Combinatorial Certificate Scheme is described that improves the innocent vehicle re-key quota lifetime by an order of magnitude.

Halftone visual cryptography (HVC) enlarges the area of visual cryptography by the addition of digital halftoning techniques. In particular, in visual secret sharing schemes, a secret image can be encoded into halftone shares taking meaningful visual information. In this paper, HVC construction methods based on error diffusion are proposed. The secret image is concurrently embedded into binary valued shares while these shares are halftoned by error diffusion-the workhorse standard of halftoning algorithms. Error diffusion has low complexity and provides halftone shares with good image quality. A reconstructed secret image, obtained by stacking qualified shares together, does not suffer from cross interference of share images. Factors affecting the share image quality and the contrast of the reconstructed image are discussed. Simulation results show several illustrative examples.

Abstract We propose the notion of a Secure Virtual Point of Service (SVPOS) as a network‐centric transaction server that facilitates the enhancement of 3G cell phones with a ‘mobile wallet’ capability allowing 3G subscribers to use their cell phones (or, in fact, other preferred mobile gadgets) for their daily transactions and payments. This paper shows how to design an SVPOS and an associated operator/subscriber/merchant protocol for purchasing digital media content over 3G networks. The resulting protocol guarantees a number of desirable privacy and security properties, such as privacy/anonymity of 3G subscribers (i.e. no identities, credit information or credit card numbers are revealed by subscriber to merchants), and protection of 3G operator, merchant, subscriber against various types of malicious behaviour, including transaction repudiation. The proposed SVPOS is ‘built’ on top of the Hypertext Transfer Protocol (HTTP), utilizes the 3rd Generation Partnership Project (3GPP) Generic Authentication Architecture (GAA) for subscriber and merchant authentication, and has an implicit key distribution mechanism that easily provides necessary encryption keys for the novel non‐repudiation mechanism of SVPOS. It also sends the necessary records of the transactions to the accounting entity of the network for charging and billing through standard protocols (e.g. Parlay‐X). Copyright © 2008 John Wiley & Sons, Ltd.

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.

As vehicular networks approach practicality, there is wide recognition for security challenges in their use, and pressing need for security solutions. The intrinsically mobile and ad-hoc nature of vehicular networks pose rather novel challenges to the modeling, design and analysis of security solutions for them. One particularly stringent requirement in this area is that of protecting the anonymity of vehicle owners during their participation in a vehicular network, such as in traffic safety applications. In this paper we present novel models of concrete anonymity requirements for vehicular networks. We consider a case study of a simple variant of a public-key infrastructure for vehicular networks and present two techniques to augment it so that it provides improved anonymity properties. The resulting vehicular-network key infrastructures satisfy desirable combinations of anonymity, unlinkability, bad actor detection, and efficiency requirements.

Securing multicast communications in ad hoc networks has become one of the most challenging research directions in the areas of wireless networking and security. This is especially true as ad hoc networks are emerging as the desired environment for an increasing number of civilian, commercial and military applications, also addressing an increasingly large number of users. In this paper we study a very basic security question for Ad Hoc Networks: Key Agreement against passive adversaries. Despite being a widely studied area in wired networks, the problem becomes significantly more challenging for ad hoc networks, and even more for sensor networks, due to lack of trusted entities, infrastructures, full connectivity, routing structures, and due to severe limitations on the resources and capabilities of network nodes. In this paper we perform a comprehensive investigation of Key Agreement over resource constrained ad hoc networks. First, we formally model the key agreement problem over multi-hop ad hop networks, and we directly extend known key agreement protocols for wired networks, and evaluate the efficiency of such approaches. We then go beyond natural extensions of such protocols, by proposing non-trivial extensions based on efficient topology-driven simulations of logical networks over an arbitrary physical network, in order to optimize the most significant metrics of interest for such networks: i.e. bandwidth, latency, processing cost. Indeed, the resulting protocols are significantly more efficient in some or all of the above metrics, as our analytical results indicate.

Virtual backbone structures are of fundamental importance in mobile ad hoc networks (MANET) as they are essential to support various applications such as service discovery and provision, multicast, routing, etc. In this paper we consider a very natural approach for the creation of virtual backbones, based on weakly-dominating sets, and investigate its security properties against Byzantine adversaries that can corrupt up to a given threshold of nodes. We formalize the notion of secure protocols for the creation and management of virtual backbones, and design a distributed protocol generating weakly-dominating virtual backbones, that is both efficient, according to standard MANET metrics, and secure against Byzantine adversaries corrupting up to a given threshold of nodes

Reliable server pooling (rSerPool) is an architecture and a set of protocols allowing a service provider to run several servers that can reliably provide the same service. Should a particular server fail while providing its service, another server can efficiently replace it. This property is attractive not only for wired but also for wireless networks. However, the unique characteristics of mobile ad hoc networks (MANETs) bring serious reliability and security challenges to the application of rSerPool. In this paper, we perform a comprehensive investigation of the security of rSerPool in MANET against both server failures and, especially, Byzantine attacks. We formulate security requirements for rSerPool in MANET and design efficient, distributed, and survivable security solutions for both main phases of rSerPool: service discovery and service provision. Specifically, we secure the service discovery phase by using a secure multiple-dominating set creation protocol, and the service provision phase by using a novel type of threshold signature scheme. Both protocols address novel security goals and are of independent interest as they can find applications to other areas; most notably, the construction of a distributed and survivable public-key infrastructure in MANET.

Approximate message authentication codes (AMACs) for binary alphabets have been introduced recently as noise-tolerant authenticators. Different from conventional “hard” message authentications that are designed to detect even the slightest changes in messages, AMACs are designed to tolerate a small amount of noise in messages for applications where slight noise is acceptable, such as in multimedia communications. Binary AMACs, however, have several limitations. First, they do not naturally deal with messages having$N$-ary alphabets$(N≫2)$. AMACs are distance-preserving codes; i.e., the distance between two authentication tags reflects the distance between two messages. Binary representation of$N$-ary alphabets, however, may destroy the original distance information between$N$-ary messages. Second, binary AMACs lack a means to adjust authentication sensitivity. Different applications may require different sensitivities against noise. AMACs for$N$-ary alphabets are designed as a cryptographic primitive to overcome the limitations of binary AMACs.$N$-ary AMACs not only directly process messages having$N$-ary alphabets but also provide sensitivity control on the authentication of binary and of$N$-ary messages. The generalized$N$-ary AMAC algorithm and its probabilistic model are developed. A statistical analysis characterizing the behavior of$N$-ary AMACs is provided along with the simulations illustrating their properties. Security analysis under chosen message attack is also developed.

Visual cryptography encodes a secret binary image (SI) into n shares of random binary patterns. If the shares are xeroxed onto transparencies, the secret image can be visually decoded by superimposing a qualified subset of transparencies, but no secret information can be obtained from the superposition of a forbidden subset. The binary patterns of the n shares, however, have no visual meaning and hinder the objectives of visual cryptography. Extended visual cryptography [1] was proposed recently to construct meaningful binary images as shares using hypergraph colourings, but the visual quality is poor. In this paper, a novel technique named halftone visual cryptography is proposed to achieve visual cryptography via halftoning. Based on the blue-noise dithering principles, the proposed method utilizes the void and cluster algorithm [2] to encode a secret binary image into n halftone shares (images) carrying significant visual information. The simulation shows that the visual quality of the obtained halftone shares are observably better than that attained by any available visual cryptography method known to date.

We embark into theoretical approaches for the investigation of intrusion detection schemes. Our main motivation is to provide rigorous security requirements for intrusion detection systems that can be used by designers of such systems. Our model captures and generalizes well-known methodologies in the intrusion detection area, such as anomaly-based and signature-based intrusion detection, and formulates security requirements based on both well-known complexity-theoretic notions and well-known notions in cryptography (such as computational indistinguishability). Under our model, we present two efficient paradigms for intrusion detection systems, one based on nearest neighbor search algorithms, and one based on both the latter and clustering algorithms. Under formally specified assumptions on the representation of network traffic, we can prove that our two systems satisfy our main security requirement for an intrusion detection system. In both cases, while the potential truth of the assumption rests on heuristic properties of the representation of network traffic (which is hard to avoid due to the unpredictable nature of external attacks to a network), the proof that the systems satisfy desirable detection properties is rigorous and of probabilistic and algorithmic nature. Additionally, our framework raises open questions on intrusion detection systems that can be rigorously studied. As an example, we study the problem of arbitrarily and efficiently extending the detection window of any intrusion detection system, which allows the latter to catch attack sequences interleaved with normal traffic packet sequences. We use combinatoric tools such as time and space-efficient covering set systems to present provably correct solutions to this problem. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

The paper introduces a new construct of message authentication codes called DBMAC. It can not only provide the message authentication functionality but also localize a few errors in the message. DBMAC uses a conventional MAC in its construction such that it inherits the conventional MACs resistance to forgeries. Furthermore, the division and butterfly structure gives the capability of localizing a few errors. Our construction can be proved to have almost optimal asymptotic tag length. We also extensively analyze the error correction capabilities of our construction for small message length values.

Visual cryptography encodes a secret image SI into n shares of random patterns. If the shares are xeroxed onto transparencies, we can visually decode the secret image by superimposing a qualified subset of transparencies, but no secret information can be obtained from the superposition of a forbidden subset. Such a scheme is mathematically secure, however, it produces random patterns which have no visual meaning, raising the suspicion of data encryption. In this paper, to achieve a higher level of security, we propose halftone visual cryptography, where all shares are halftones of grey level images carrying significant visual information. The proposed methods utilize blue-noise dithering principles to construct halftone shares having visually pleasing attributes.

Security is a critical consideration for an enterprise communications system. Different work contexts and corporate cultures may have different security requirements. In fact, such requirements may range from "no security" to protection from all possible attacks. In addition, as a communications session progresses, its context may dynamically change, and its security requirements may need to be changed accordingly. In this paper, we present our approach to providing security in enterprise communications in an efficient manner and report on the results of our initial performance study, which shows that encrypting and decrypting real-time media payloads end-to-end does not significantly degrade the quality of the end-user experience in real-time communications. Our approach is implemented in an enterprise communications system, called SEC, which is designed to enable enterprise employees to conduct secure, spontaneous, multimedia, and multi-party conferencing.

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

Identification schemes allow a user to identify herself to a verifying authority in a secure way (i.e., without revealing her secret key). Group identification schemes allow a user to identify herself as a member of a group of users in a secure and anonymous way (i.e., without revealing her identity nor her secret key). Several identification schemes and group identification schemes have been proposed in the literature. In this paper we consider the problem of constructing communication-efficient group identification schemes. Assuming factoring Blum integers is hard, we construct a secure and anonymous group identification scheme having communication complexity \\Theta(m+n), where m is the size of the group and n is the security parameter (previous results achieved complexity \\Theta(mn)). In fact, we show our protocol to be perfect zero-knowledge. We extend this scheme to the case of groups of t ? 1 users and obtain a protocol that improves on the communication complexity of previous ...

We investigate the relationship between interactive proofs of membership and interactive proofs of knowledge. Previous results in this area show that many proofs of membership for some languages are also proofs of knowledge of an associated relation, raising the question of whether all proofs of membership are proofs of knowledge. In this paper we clarify the relationship between these two notions of proofs. It turns out that a precise relationship depends on the kind of relation considered. Clearly, any proof of membership is a proof of knowledge for some easy to compute relation. On the other hand, we define a notion of tight relations, referring to relations that capture the computational advantage communicated by a prover to a poly-time verifier in an interactive protocol.

We consider the question of private information retrieval in the so-called "commodity-based" model.This model was recently proposed by Beaver for practically-oriented service-provider internet applications.In this paper, we show the following, somewhat surprising, results regarding this model for the problem of private information retrieval: (1) the service-provider model allows to dramatically reduce the overall communication involving the user, using off-line pre-processing messages from "service-providers" to databases, where the service-providers need not know the database contents, nor the future user's requests; (2) our service-provider solutions are resilient against more than a majority (in fact, all-but-one) coalitions of serviceproviders; and (3) these results hold for bath the computational and the information-theoretic setting.

AbotractA commilmcnt protocol is a fundamental cryptographic primitive uacd a0 D basic building block throughout modem cryptography.In STOC 1991, Dolov Dwork and Naor showed that in many settings the Implemontotion of this fundamental primitive requires a strong non-malh6ility property in order not to be sueceptible to a certain clmoa of nttacke, In this paper, aeeuming that a common random ntrlng lo available to all playere, we show how to implement nonmalleablo commitment without any interaction and based on any one-way function, In contrast, all previous solutions required eithor logorlthmically many rounds of interaction or strong algebraic aaaumptlono, I lntroductlon COMMITMENT:One of the most fundamental crypt* graphic protocols is the commitment protocol.A commitment protocol involves two probabilistic polynomial-time players: the committer and the receiver.Very informally, it consists of two stages, a commitment stage and a decommitment stage.In the commitment stage, the committcr with a secret input x engages in a protocol with the receiver, In the end of this protocol, receiver still does not know what z is (i.e.z is computationally hidden), and at the same time, the committer can subsequently (i.e., during the de-commitment stage) open only one possible value of 2.Commitment is used as a sub-protocol in a vast variety of cryptographic applications, including, to name a few, contract signing [8], zero-knowledge proofs for all of

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