## CryptoDB

### Ramarathnam Venkatesan

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Founding Cryptography on Tamper-Proof Hardware Tokens
Abstract

A number of works have investigated using tamper-proof hardwaretokens as tools to achieve a variety of cryptographic tasks. In particular, Goldreich and Ostrovsky considered the goal of software protection via oblivious RAM. Goldwasser, Kalai, and Rothblum introduced the concept of \emph{one-time programs}: in a one-time program, an honest sender sends a set of {\em simple} hardware tokens to a (potentially malicious) receiver. The hardware tokens allow the receiver to execute a secret program specified by the sender's tokens exactly once (or, more generally, up to a fixed $t$ times). A recent line of work initiated by Katz examined the problem ofachieving UC-secure computation using hardware tokens. Motivated by the goal of unifying and strengthening these previous notions, we consider the general question of basing secure computation on hardware tokens. We show that the following tasks, which cannot be realized in the ``plain'' model, become feasible if the parties are allowed to generate and exchange tamper-proof hardware tokens.
Unconditional non-interactive secure computation: We show that by exchanging simple stateful hardware tokens, any functionality can be realized with unconditional security against malicious parties. In the case of two-party functionalities $f(x,y)$ which take their inputs from a sender and a receiver and deliver their output to the receiver, our protocol is non-interactive and only requires a unidirectional communication of simple stateful tokens from the sender to the receiver. This strengthens previous feasibility results for one-time programs both by providing unconditional security and by offering general protection against malicious senders. As is typically the case for unconditionally secure protocols, our protocol is in fact UC-secure. This improves over previous works on UC-secure computation based on hardware tokens, which provided computational security under cryptographic assumptions.
Interactive Secure computation from stateless tokens based on one-way functions: We show that stateless hardware tokens are sufficient to base general secure (in fact, UC-secure) computation on the existence of one-way functions. One cannot hope for security against unbounded adversaries with stateless tokens since an unbounded adversary could query the token multiple times to ``learn" the functionality it contains.
Non-interactive secure computation from stateless tokens: We consider the problem of designing non-interactive secure computation from stateless tokens for stateless oblivious reactive functionalities, i.e., reactive functionalities which allow unlimited queries from the receiver (these are the only functionalities one can hope to realize non-interactively with stateless tokens). By building on recent techniques from resettably secure computation, we give a general positive result for stateless oblivious reactive functionalities under standard cryptographic assumption. This result generalizes the notion of (unlimited-use) obfuscation by providing security against a malicious sender, and also provides the first general feasibility result for program obfuscation using stateless tokens.

2010

EPRINT

Quantifying Trust
Abstract

Trust is a central concept in public-key cryptography infrastruc-
ture and in security in general. We study its initial quantification and its spread patterns. There is empirical evidence that in trust-based reputation model for virtual communities, it pays to restrict the clusters of agents to small sets with high mutual trust. We propose and motivate a mathematical model, where this phenomenon emerges naturally. In our model, we separate trust values from their weights. We motivate this separation using real examples, and show that in this model, trust converges to the extremes, agreeing with and accentuating the observed phenomenon. Specifically, in our model, cliques of agents of maximal mutual trust are formed, and the trust between any two agents that do not maximally trust each other, converges to zero. We offer initial practical relaxations to the model that preserve some of the theoretical flavor.

2006

EPRINT

MV3: A new word based stream cipher using rapid mixing and revolving buffers
Abstract

MV3 is a new word based stream cipher for encrypting long streams of data. A direct adaptation of a byte based cipher such as RC4 into a 32- or 64-bit word version will obviously need vast amounts of memory. This scaling issue necessitates a look for new components and principles, as well as mathematical analysis to justify their use. Our approach, like RC4's, is based on rapidly mixing random walks on directed graphs (that is, walks which reach a random state quickly, from any starting point). We begin with some well understood walks, and then introduce nonlinearity in their steps in order to improve security and show long term statistical correlations are negligible. To minimize the short term correlations, as well as to deter attacks using equations involving successive outputs, we provide a method for sequencing the outputs derived from the walk using three revolving buffers. The cipher is fast --- it runs at a speed of less than 5 cycles per byte on a Pentium IV processor. A word based cipher needs to output more bits per step, which exposes more correlations for attacks. Moreover we seek simplicity of construction and transparent analysis. To meet these requirements, we use a larger state and claim security corresponding to only a fraction of it. Our design is for an adequately secure word-based cipher; our very preliminary estimate puts the security close to exhaustive search for keys of size < 256 bits.

2004

EPRINT

Ramanujan Graphs and the Random Reducibility of Discrete Log on Isogenous Elliptic Curves
Abstract

Cryptographic applications using an elliptic curve over a finite field
filter curves for suitability using their order as the primary criterion: e.g. checking that their order has a large prime divisor before accepting it. It is therefore natural to ask whether the discrete log problem (DLOG) has the same difficulty for all curves with the same order; if so it would justify the above practice. We prove that this is essentially true by showing random reducibility of dlog among such curves, assuming the Generalized Riemann Hypothesis (GRH). Our reduction proof works for curves with (nearly) the same endomorphism rings, but it is unclear if such a reduction exists in general. This suggests that in addition to the order, the conductor of its endomorphism ring may play a role. The random self-reducibility for dlog over finite fields is well known; the non-trivial part here is that one must relate non-isomorphic algebraic groups of two isogenous curves. We construct certain expander graphs with elliptic curves as nodes and low degree isogenies as edges, and utilize the rapid mixing of random walks on this graph. We also briefly look at some recommended curves, compare ?random? type NIST FIPS 186-2 curves to other special curves from this standpoint, and suggest a parameter to measure how generic a given curve is.

2001

EPRINT

Constructing elliptic curves with a given number of points over a finite field
Abstract

In using elliptic curves for cryptography, one often needs to construct elliptic curves with a given or known number of points over a given finite field. In the context of primality proving, Atkin and Morain suggested the use of the theory of complex multiplication to construct such curves. One of the steps in this method is the calculation of the Hilbert class polynomial
$H_D(X)$ modulo some integer $p$ for a certain fundamental discriminant $D$. The usual way of doing this is to compute
$H_D(X)$ over the integers and then reduce modulo $p$. But this involves computing the roots with very high accuracy and subsequent rounding of the coefficients to the closest integer. (Such accuracy issues also arise for higher genus cases.) We present a modified version of the Chinese remainder theorem (CRT) to compute $H_D(X)$ modulo $p$ directly from the knowledge of $H_D(X)$ modulo enough small primes. Our algorithm is inspired by Couveigne's method for computing square roots in the number field sieve, which is useful in other scenarios as well. It runs in heuristic expected time less than
the CRT method in [CNST]. Moreover, our method requires very few digits of precision to succeed, and avoids calculating the exponentially large coefficients of the Hilbert class polynomial over the integers.

1998

EPRINT

Security amplification by composition: The case of doubly-iterated, ideal ciphers
Abstract

We investigate, in the Shannon model, the security of constructions
corresponding to double and (two-key) triple DES. That is, we
consider F<sub>k1</sub>(F<sub>k2</sub>(.)) and
F<sub>k1</sub>(F<sub>k2</sub><sup>-1</sup>(F<sub>k1</sub>(.))) with
the component functions being ideal ciphers. This models the
resistance of these constructions to ``generic'' attacks like meet
in the middle attacks.
We obtain the first proof that composition actually
increases the security in some meaningful sense. We compute a bound
on the probability of breaking the double cipher as a function of
the number of computations of the base cipher made, and the number
of examples of the composed cipher seen, and show that the success
probability is the square of that for a single key cipher. The
same bound holds for the two-key triple cipher. The first bound
is tight and shows that meet in the middle is the best possible
generic attack against the double cipher.

1996

CRYPTO

1996

EUROCRYPT

1992

CRYPTO

#### Program Committees

- PKC 2010
- PKC 2008
- Crypto 2003

#### Coauthors

- Amod Agashe (1)
- William Aiello (5)
- Evgeni Begelfor (1)
- Mihir Bellare (2)
- Dan Boneh (2)
- Victor Boyko (1)
- Matthew Cary (1)
- Giovanni Di Crescenzo (2)
- Vipul Goyal (2)
- Stuart Haber (1)
- Yuval Ishai (2)
- Mariusz H. Jakubowski (2)
- David Jao (2)
- Dimitar Jetchev (1)
- Nathan Keller (1)
- Kristin E. Lauter (1)
- Stephen D. Miller (4)
- Ilya Mironov (1)
- Moni Naor (2)
- Rafail Ostrovsky (3)
- Marcus Peinado (1)
- Sivaramakrishnan Rajagopalan (1)
- Amit Sahai (2)
- Akshay Wadia (2)
- Yacov Yacobi (1)
- Moti Yung (3)