International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Amir Herzberg

Affiliation: Bar Ilan University

Publications

Year
Venue
Title
2019
PKC
Efficient Non-Interactive Zero-Knowledge Proofs in Cross-Domains Without Trusted Setup
With the recent emergence of efficient zero-knowledge (ZK) proofs for general circuits, while efficient zero-knowledge proofs of algebraic statements have existed for decades, a natural challenge arose to combine algebraic and non-algebraic statements. Chase et al. (CRYPTO 2016) proposed an interactive ZK proof system for this cross-domain problem. As a use case they show that their system can be used to prove knowledge of a RSA/DSA signature on a message m with respect to a publicly known Pedersen commitment $$g^m h^r$$. One drawback of their system is that it requires interaction between the prover and the verifier. This is due to the interactive nature of garbled circuits, which are used in their construction. Subsequently, Agrawal et al. (CRYPTO 2018) proposed an efficient non-interactive ZK (NIZK) proof system for cross-domains based on SNARKs, which however require a trusted setup assumption.In this paper, we propose a NIZK proof system for cross-domains that requires no trusted setup and is efficient both for the prover and the verifier. Our system constitutes a combination of Schnorr based ZK proofs and ZK proofs for general circuits by Giacomelli et al. (USENIX 2016). The proof size and the running time of our system are comparable to the approach by Chase et al. Compared to Bulletproofs (SP 2018), a recent NIZK proofs system on committed inputs, our techniques achieve asymptotically better performance on prover and verifier, thus presenting a different trade-off between the proof size and the running time.
2016
CRYPTO
2010
EPRINT
Robust Combiner for Obfuscators
Amir Herzberg Haya Shulman
Practical software hardening schemes are heuristic and are not proven to be secure. One technique to enhance security is {\em robust combiners}. An algorithm $C$ is a robust combiner for specification $S$, e.g., privacy, if for any two implementations $X$ and $Y$, of a cryptographic scheme, the combined scheme $C(X,Y)$ satisfies $S$ provided {\em either} $X$ {\em or} $Y$ satisfy $S$. We present the first robust combiner for software hardening, specifically for obfuscation \cite{barak:obfuscation}. Obfuscators are software hardening techniques that are employed to protect execution of programs in remote, hostile environment. Obfuscators protect the code (and secret data) of the program that is sent to the remote host for execution. Robust combiners are particularly important for software hardening, where there is no standard whose security is established. In addition, robust combiners for software hardening are interesting from software engineering perspective since they introduce new techniques of software only fault tolerance.
2010
EPRINT
Secure Guaranteed Computation
Amir Herzberg Haya Shulman
We introduce secure committed computation, where n parties commit in advance to compute a function over their private inputs; we focus on two party computations (n = 2). In committed computation, parties initially commit to the computation by providing some (validated) compensation, such that if a party fails to provide an appropriate input during protocol execution, then the peer receives the compensation. Enforcement of the commitments requires a trusted enforcement authority (TEA); however, the protocol protects confidentiality even from the TEA. Secure committed computation has direct practical applications, such as sensitive trading of financial products, and could also be used as a building block to motivate parties to complete protocols, e.g., ensuring unbiased coin tossing. The commitment can be either symmetric (both parties commit) or asymmetric (e.g., only a server commits to a client). Symmetric commitment should also be fair, i.e., one party cannot obtain commitment by the other party without committing as well. Our secure committed computation protocols are optimistic, i.e., the TEA is involved only if and when a party fails to participate (correctly). The protocols we present use two new building blocks, which may be of independent interest. The first is a protocol for optimistic fair secure computation, which is simpler and more efficient than previously known. The second is a protocol for two party computation secure against malicious participants, which is simple and efficient, and relies on a weakly-trusted third party. This protocol can be useful where a trusted third party is unavoidable, e.g., in secure committed or fair computation protocols.
2008
TCC
2008
EPRINT
Towards a Theory of White-Box Security
Program hardening for secure execution in remote untrusted environment is an important yet elusive goal of security, with numerous attempts and efforts of the research community to produce secure solutions. Obfuscation is the prevailing practical technique employed to tackle this issue. Unfortunately, no provably secure obfuscation techniques currently exist. Moreover, Barak et al., showed that not all programs can be obfuscated. We present a rigorous approach to {\em program hardening}, based on a new white box primitive, the {\em White Box Remote Program Execution (WBRPE)}, whose security specifications include confidentiality and integrity of both the local and the remote hosts. We then show how the {\em WBRPE} can be used to address the needs of a wide range of applications, e.g. grid computing and mobile agents. Next, we construct a specific program and show that if there exists a secure {\em WBRPE} for that program, then there is a secure {\em WBRPE} for {\em any} program, reducing its security to the underlying {\em WBRPE} primitive. This reduction among two white box primitives introduces new techniques that employ program manipulation.
2008
EPRINT
Robust Combiners for White-Box Security
Amir Herzberg Haya Shulman
{\em White-box} security techniques are employed to protect programs so that they can be executed securely in untrusted environments, e.g. for copyright protection. We present the first robust combiner for white-box primitive, specifically for {\em White-Box Remote Program Execution (WBRPE)} schemes. The {\em WBRPE} combiner takes two input candidate {\em WBRPE} schemes, $W'$ and $W''$, and outputs a third candidate $W=W'\circ W''$. The combiner is $(1,2)$-{\em robust}, namely, $W$ is secure as long as either $W'$ or $W''$ is secure. The security of the combined scheme is established by presenting a reduction to the security of the white-box candidates. %The combiner employs new techniques of code manipulation, which can be used by other {\em white-box} constructions. The {\em WBRPE} combiner is interesting since it presents new techniques of code manipulation, and in addition it provides both properties of confidentiality and authentication, even though it is a $(1,2)$-robust combiner. Robust combiners are particularly important for {\em white-box} security, since no secure candidates are known to exist. Furthermore, robust combiners for white-box primitives, are interesting since they introduce new techniques of reductions.
2007
EPRINT
The Delivery and Evidences Layer
Amir Herzberg Igal Yoffe
Evidences of delivery are essential for resolving (and avoiding) disputes on delivery of messages, in classical as well as electronic commerce. We present the first rigorous specifications and provably-secure implementation, for a communication layer providing time-stamped evidences for the message delivery process. This improves on existing standards for evidences (‘non-repudiation’) services, based on informal specifications and unproven designs. Our work also improves on the large body of analytical works on tasks related to evidences of delivery, such as certified mail/delivery protocols and fair exchange (of signatures). We improve by addressing practical needs and scenarios, using realistic synchronization and communication assumptions, supporting time-outs and failures, and providing well-defined interface to the higher-layer protocols (application). Furthermore, we use the layered specifications framework, allowing provably-secure use of our protocol, with lower and higher layer protocols, with complete re-use of our analysis (theorems).
2006
EPRINT
Browsers Defenses Against Phishing, Spoofing and Malware
Amir Herzberg
Web users are increasingly victims of phishing, spoofing and malware attacks. In this article, we discuss existing and proposed defense mechanisms. We highlight the vulnerabilities of current defenses, and the challenges of validating and adopting new defenses.
2006
EPRINT
Foundations of Secure E-Commerce: The Order Layer
Amir Herzberg Igal Yoffe
We present specifications and provable protocol, for secure ordering and provision of digital goods and services. Notably, our protocol includes fully automated resolution of disputes between providers and customers. Disputes may involve the timely receipt of orders and goods, due to communication failures and malicious faults, as well as disputes of fitness of goods and order. The protocol and specifications are modular, with precise yet general-purpose interfaces. This allows usage as an underlying service to different e-commerce scenarios and applications, in particular secure online banking and brokerage. The protocol is practical, efficient, reliable and secure, under realistic failure and delay conditions. Our design and specifications are a part of a layered architecture for secure e-commerce applications.
2006
EPRINT
The Layered Games Framework for Specifications and Analysis of Security Protocols
Amir Herzberg Igal Yoffe
We establish rigorous foundations to the use of modular, layered design for building complex distributed systems. Layering is key to the design of the Internet and other distributed systems, hence such solid, theoretical foundations are essential, especially when considering adversarial settings, such as for security and cryptographic protocols. We define the basic concepts for modular, layered design: protocols, systems, configurations, executions, and models, and three relations: indistinguishability (between two systems), satisfaction (of a model by a system), and realization (by protocol, of one model over another model). We prove several basic properties, including the {\em layering lemma} and the {\em indistinguishability lemma}. The indistinguishability lemma shows that if two systems \Gamma_L, \Gamma_R are indistinguishable, and \Gamma_L satisfies some model M, then \Gamma_R also satisfies M. The layering lemma shows that given protocols {\pi_i}^u_{i=1}, if every protocol \pi_i realizes model M_i over model M_{i-1}, then the composite protocol \pi_{1||...||u} realizes model M_u over M_0. This allows specification, design and analysis of each layer independently, and combining the results to ensure properties of the complete system. Our framework is based on {\em games}, following many works in applied cryptography. This differs from existing frameworks allowing compositions of cryptographic protocols, based on {\em simulatability of ideal functionality}. Game-based models are more general and flexible than ideal functionality specifications, supporting different adversarial models and avoiding over-specification, which is essential for practical distributed systems and networks.
2005
EPRINT
Cryptographic Protocols to Prevent Spam
Amir Herzberg
This is a survey of mechanisms to control or prevent spam, with emphsis on cryptographic protocols. We also present a new cryptographic protocol, Secure Automated Resolution Protocol, which can be used to penalize spammers (and for other applications).
2005
EPRINT
Keeping Denial-of-Service Attackers in the Dark
Gal Badishi Amir Herzberg Idit Keidar
We consider the problem of overcoming (Distributed) Denial of Service (DoS) attacks by realistic adversaries that have knowledge of their attack's successfulness, e.g., by observing service performance degradation, or by eavesdropping on messages or parts thereof. A solution for this problem in a high-speed network environment necessitates lightweight mechanisms for differentiating between valid traffic and the attacker's packets. The main challenge in presenting such a solution is to exploit existing packet filtering mechanisms in a way that allows fast processing of packets, but is complex enough so that the attacker cannot efficiently craft packets that pass the filters. We show a protocol that mitigates DoS attacks by adversaries that can eavesdrop and (with some delay) adapt their attacks accordingly. The protocol uses only available, efficient packet filtering mechanisms based mainly on (addresses and) port numbers. Our protocol avoids the use of fixed ports, and instead performs `pseudo-random port hopping'. We model the underlying packet-filtering services and define measures for the capabilities of the adversary and for the success rate of the protocol. Using these, we provide a novel rigorous analysis of the impact of DoS on an end-to-end protocol, and show that our protocol provides effective DoS prevention for realistic attack and deployment scenarios.
2004
EPRINT
Controlling Spam by Secure Internet Content Selection
Amir Herzberg
Unsolicited and undesirable e-mail (spam) is a growing problem for Internet users and service providers. We present the Secure Internet Content Selection (SICS) protocol, an efficient cryptographic mechanism for spam-control, based on allocation of responsibility (liability). With SICS, e-mail is sent with a content label, and a cryptographic protocol ensures labels are authentic and penalizes falsely labeled e-mail (spam). The protocol supports trusted senders (penalized by loss of trust) and unknown senders (penalized financially). The recipient can determine the compensation amount for falsely labeled e-mail (spam)). SICS is practical, with negligible overhead, gradual adoption path, and use of existing relationships; it is also flexible and appropriate for most scenarios, including deployment by end users and/or ISPs and support for privacy and legitimate, properly labeled commercial e-mail. SICS improves on other crypto-based proposals for spam controls, and complements non-cryptographic spam controls
2004
EPRINT
Security and Identification Indicators for Browsers against Spoofing and Phishing Attacks
Amir Herzberg Ahmad Gbara
In spite of the use of standard web security measures (SSL/TLS), users enter sensitive information such as passwords into scam web sites. Such scam sites cause substantial damages to individuals and corporations. In this work, we analyze these attacks, and find they often exploit usability failures of browsers. We developed and describe TrustBar, a browser extension for improved secure identification indicators. Users can assign a name/logo to a secure site, presented by TrustBar when the browser presents that secure site; otherwise, TrustBar presents the certified site's owner name, and the name/logo of the Certificate Authority (CA) who identified the owner. Some of these ideas are already adopted by browsers, following our work. We describe usability experiments, which measure, and prove the effectiveness, of TrustBar's improved security and identification indicators. We derive general secure-usability principles from our experiments and experience with TrustBar
2003
EPRINT
Committing Encryption and Publicly-Verifiable SignCryption
Yitchak Gertner Amir Herzberg
Encryption is often conceived as a committing process, in the sense that the ciphertext may serve as a commitment to the plaintext. But this does not follow from the standard definitions of secure encryption. We define and construct symmetric and asymmetric committing encryption schemes, enabling publicly verifiable non-repudiation. Committing encryption eliminates key-spoofing attacks and has also the robustness to be signed afterwards. Our constructions are very efficient and practical. In particular, we show that most popular asymmetric encryption schemes, e.g. RSA, are committing encryption schemes; we also have an (efficient) construction given an arbitrary asymmetric encryption scheme. Our construction of symmetric committing encryption retains the efficiency of the symmetric encryption for real-time operations, although it uses few public key signatures in the setup phase. Finally, we investigate how to achieve both confidentiality and non-repudiation, and present a publicly verifiable signcryption scheme. Contrary to previous signcryption schemes, which are not publicly verifiable, our publicly verifiable signcryption supports non-repudiation. We construct a simple and efficient publicly verifiable signcryption scheme based on a new composition method which we call ?commit-encrypt-then-sign? (CEtS) that preserves security properties of both committing encryption and digital signature schemes.
2002
EPRINT
Towards Provably-Secure Timed E-Commerce: The Trusted Delivery Layer
Amir Herzberg
Certified exchange of messages is an essential mechanism for e-commerce; the timing aspects (timeouts and timestamps) are very important for practical applications. However existing formal methods for security analysis assume simplified completely synchronous or completely asynchronous models, and cannot deal with the timing aspects of these (and other e-commerce) protocols. We present model for realistic, Δ-synchronized adversarial settings. We then present a simple, efficient and provably-secure protocol for certified, time-stamped message delivery, providing precise guarantees of delay and timestamps. Our model and analysis use concrete (rather than asymptotic) notions of security.
2002
EPRINT
Tolerant Combiners: Resilient Cryptographic Design
Amir Herzberg
Cryptographic schemes are often designed as a combination of multiple component cryptographic modules. Such a combiner design is tolerant for a (security) specification if it meets the specification, provided that a sufficient subset of the components meet their specifications. A folklore combiner for encryption is cascade; we show that cascade is indeed a tolerant combiner for encryption schemes, under chosen plaintext attack, non-adaptive chosen ciphertext attack (CCA1) and (adaptive) replayable chosen ciphertext attack (rCCA). However, cascade is not tolerant for adaptive CCA (CCA2), and we show it is also not tolerant for generalized CCA (gCCA). This is an interesting difference between rCCA and gCCA. We also analyze few other folklore tolerant combiners, including the parallel combiner for one-way functions, and the copy combiner for integrity tasks such as Message Authentication Codes (MAC) and signature schemes. Cascade is also tolerant for the hiding property of commitment schemes, and the copy combiner is tolerant for the binding property, but neither provides tolerant for both properties. We present (new) tolerant combiners for commitment schemes; these new combiners can be viewed as a composition of the cascade and the copy combiners. We prove tolerance of the composite combiners via a general Composition Lemma, possibly applicable for other tasks. Our combiners are simple, efficient and practical. To ensure practicality, we use concrete security analysis and definitions, in addition to the simpler asymptotic analysis. Our definitions of security may be of independent interest.
2000
JOFC
1998
EPRINT
Maintaining Authenticated Communication in the Presence of Break-ins
Ran Canetti Shai Halevi Amir Herzberg
We study the problem of maintaining authenticated communication over untrusted communication channels, in a scenario where the communicating parties may be occasionally and repeatedly broken into for transient periods of time. Once a party is broken into, its cryptographic keys are exposed and perhaps modified. Yet, we want parties whose security is thus compromised to regain their ability to communicate in an authenticated way aided by other parties. In this work we present a mathematical model for this highly adversarial setting, exhibiting salient properties and parameters, and then describe a practically-appealing protocol for the task of maintaining authenticated communication in this model. A key element in our solution is devising {\em proactive distributed signature (PDS) schemes} in our model. Although PDS schemes are known in the literature, they are all designed for a model where authenticated communication and broadcast primitives are available. We therefore show how these schemes can be modified to work in our model, where no such primitives are available a-priori. In the process of devising the above schemes, we also present a new definition of PDS schemes (and of distributed signature schemes in general). This definition may be of independent interest.
1995
CRYPTO
1994
CRYPTO
1992
CRYPTO
1992
CRYPTO
1991
CRYPTO
1985
CRYPTO

Program Committees

PKC 2014
PKC 2009