## CryptoDB

### Amitabh Saxena

#### Publications

Year
Venue
Title
2008
EPRINT
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
We study the relationship between obfuscation and white-box cryptography. We capture the requirements of any white-box primitive using a \emph{White-Box Property (WBP)} and give some negative/positive results. Loosely speaking, the WBP is defined for some scheme and a security notion (we call the pair a \emph{specification}), and implies that w.r.t. the specification, an obfuscation does not leak any useful'' information, even though it may leak some useless'' non-black-box information. Our main result is a negative one - for most interesting programs, an obfuscation (under \emph{any} definition) cannot satisfy the WBP for every specification in which the program may be present. To do this, we define a \emph{Universal White-Box Property (UWBP)}, which if satisfied, would imply that under \emph{whatever} specification we conceive, the WBP is satisfied. We then show that for every non-approximately-learnable family, there exist certain (contrived) specifications for which the WBP (and thus, the UWBP) fails. On the positive side, we show that there exists an obfuscator for a non-approximately-learnable family that achieves the WBP for a certain specification. Furthermore, there exists an obfuscator for a non-learnable (but approximately-learnable) family that achieves the UWBP. Our results can also be viewed as formalizing the distinction between useful'' and useless'' non-black-box information.
2006
EPRINT
Let $G_1$ be a cyclic multiplicative group of order $n$. It is known that the Diffie-Hellman problem is random self-reducible in $G_1$ with respect to a fixed generator $g$ if $\phi(n)$ is known. That is, given $g, g^x\in G_1$ and having oracle access to a Diffie-Hellman Problem' solver with fixed generator $g$, it is possible to compute $g^{1/x} \in G_1$ in polynomial time. On the other hand, it is not known if such a reduction exists when $\phi(n)$ is unknown. We exploit this gap'' to construct a cryptosystem based on hidden order groups by presenting a practical implementation of a novel cryptographic primitive called \emph{Strong Associative One-Way Function} (SAOWF). SAOWFs have interesting applications like one-round group key agreement. We demonstrate this by presenting an efficient group key agreement protocol for dynamic ad-hoc groups. Our cryptosystem can be considered as a combination of the Diffie-Hellman and RSA cryptosystems.
2006
EPRINT
Let $G_1$ be a cyclic multiplicative group of order $n$. It is known that the Diffie-Hellman problem is random self-reducible in $G_1$ with respect to a fixed generator $g$ if $\phi(n)$ is known. That is, given $g, g^x\in G_1$ and having oracle access to a Diffie-Hellman Problem solver'' with fixed generator $g$, it is possible to compute $g^{1/x} \in G_1$ in polynomial time (see theorem 3.2). On the other hand, it is not known if such a reduction exists when $\phi(n)$ is unknown (see conjuncture 3.1). We exploit this gap'' to construct a cryptosystem based on hidden order groups and present a practical implementation of a novel cryptographic primitive called an \emph{Oracle Strong Associative One-Way Function} (O-SAOWF). O-SAOWFs have applications in multiparty protocols. We demonstrate this by presenting a key agreement protocol for dynamic ad-hoc groups.
2005
EPRINT
A mobile agent is a mobile program capable of maintaining its execution states as it migrates between different execution platforms. A key security problem in the mobile agent paradigm is that of trust: How to ensure that the past itinerary (of execution platforms) claimed by the agent is correct. This is necessary in order to establish a reasonable level of trust for the agent before granting execution privileges. In this paper we describe a protocol using bilinear pairings that enables trust relationships to be formed between agent platforms in an ad-hoc manner without actively involving any trusted third party. This protocol can be used to authenticate agents before granting execution privileges. The main idea behind our approach is the concept of one-way' chaining. Our scheme has chosen ciphertext security assuming the hardness of the Bilinear Diffie Hellman Problem (BDHP).
2005
EPRINT
In this paper, we describe a new cryptographic primitive called \emph{(One-Way) Signature Chaining}. Signature chaining is essentially a method of generating a chain of signatures on the same message by different users. Each signature acts as a link'' of the chain. The \emph{one-way}-ness implies that the chaining process is one-way in the sense that more links can be easily added to the chain. However, it is computationally infeasible to remove any intermediate links without removing all the links. The signatures so created are called chain signatures. We give precise definitions of chain signatures and discuss some applications in trust transfer. We also present a practical construction of a CS scheme that is secure under the Computational Diffie-Hellman (CDH) assumption in bilinear maps.
2005
EPRINT
Identification protocols based on the Computational Diffie Hellman Problem (CDHP) generally assume the intractability of the underlying Decisional Diffie Hellman Problem (DDHP). Due to this, the security of all such schemes in a pairing based scenario is doubtful. In this paper, we propose a two-round zero-knowledge identification protocol using bilinear pairings. Our proposed protocol has two contrasting features to traditional identification schemes: (1) The scheme requires the verifier to toss his coins before the prover. (2) The coin tosses of the verifier are secret while the coin tosses of the prover are not. As a consequence, we obtain a \emph{blind} identification scheme with complete zero knowledge. Traditionally in an identification scheme, a passive adversary watching the communication gains information intended only for the verifier. For instance, from watching the transcript in the Fiat-Shamir zero knowledge identification scheme, an adversary also learns the outcome of the protocol (i.e. whether the identification succeeds or not). The blinding property of our scheme eliminates this disadvantage while still ensuring zero knowledge. Finally, as a natural extension of our scheme, we present the concept of `all or none' group identification protocol that can be used to authenticate together an arbitrary number of users in a batch such that if the identification fails, it is impossible for the users to know which one cheated. We also prove the security of our scheme and give some interesting applications including anonymous seller credit card payments. The cryptographic primitives can be efficiently encapsulated in smart cards designed for Elliptic Curve Cryptography (ECC). The private key must be included in a tamperproof device inside the smart card.
2005
EPRINT
In this paper, we study the opacity property of verifiably encrypted signatures (VES) of Boneh et al. (proposed in Eurocrypt 2003). Informally, opacity implies that although some given aggregate signatures can verified, no useful information about the individual signatures is leaked. However, the very fact that an aggregate signature can be verified leaks certain information - that the individual signature is indeed well-formed. Apart from this, is there any other information leaked? In this paper, we show that there is absolutely no other information leaked about the individual signatures when the aggregation contains only two signatures. In more formal terms, we show that VES are Zero-Knowledge (ZK). We then extend the ZK property of VES to propose efficient Additive Non-Interactive Witness-Indistinguishable (A-NIWI) proofs. Intuitively an A-NIWI proof can be considered as a Proof of Knowledge (PoK) of another A-NIWI proof.

#### Coauthors

Bruno Crispo (1)
Amir Herzberg (1)
Serguey Priymak (1)
Haya Shulman (1)
Ben Soh (5)
Brecht Wyseur (1)