Ramarathnam Venkatesan

I am a Principal Researcher with Microsoft Research, India and I am located in MSR Redmond.

I am interested in mathematical and practical aspects of Complexity Theory, Cryptography and Cryptanalysis, Algorithms and Security. Recently I have been working on Machine Learning, Data Mining, Program Analysis and Synthesis from an adversarial/security view point.

I am currently working on cryptographic and security issues related to the cloud, and in particular as applicable to the migration of databases to the cloud.

Publications

## 2013

Arvind Arasu, Ken Eguro, Raghav Kaushik, Donald Kossmann, Ravi Ramamurthy, and Ramarathnam Venkatesan, A Secure Coprocessor for Database Applications, in IEEE International Conference on Field Programmable Logic and Applications (FPL), September 2013

The scalability and availability of cloud computing makes it an ideal platform for many database applications. However, it is challenging to secure sensitive client information in a practical and rigorous manner against both external attackers and curious cloud administrators. In this paper, we describe a novel secure FPGA-based query coprocessor and discuss how it can be tightly integrated with a commercial database system such as SQL Server. This combination, called Cipherbase, leverages efficient division of labor – using a conventional untrusted cloud server to handle mundane database operations while sensitive data is segregated and processed in trusted hardware to ensure confidentiality. We examine the architectural design issues that affect the achievable performance of the system and report initial results demonstrating the effectiveness for real-world cloud database applications.

Rajalakshmi Nandakumar, Krishna Kant Chintalapudi, Venkat Padmanabhan, and Ramarathnam Venkatesan, Dhwani: Secure Peer-to-Peer Acoustic NFC, in SIGCOMM, ACM, 12 August 2013

Near Field Communication (NFC) enables physically proximate devices to communicate over very over short ranges in a peer-to-peer manner, without incurring the overhead of any complex network configuration effort. However, the adoption of NFC-enabled applications has been stymied by the low levels of penetration of NFC hardware. In this paper, we address the challenge of enabling NFClike capability on the existing base of mobile phones. To this end, we develop Dhwani, a novel, acoustics-based NFC system that uses the microphone and speakers on mobile phones, thus eliminating the need for any specialized NFC hardware. A key feature of Dhwani is the Jam-Secure technique, which uses self-jamming coupled with self-interference cancellation at the receiver, to provide an information-theoretically secure communication channel between the devices. Our experiments show that Dhwani can achieve data rates of up to 2.4 Kbps, which is sufficient for most existing NFC applications.

Ken Eguro, Kaushik Rajan, Abhishek Ranjan, Ravi Ramamurthy, Kapil Vaswani, and Ramarathnam Venkatesan, Automatic Secure Partitioning For Database Applications, no. MSR-TR-2013-74, August 2013

Ensuring security is a significant challenge for applications deployed on public cloud platforms. On these platforms, applications are open to several attacks, both from physically co-located applications, and from the cloud administrator. In this paper, we consider a hybrid architecture based on the notion of a trusted client - in this architecture, data is stored on the untrusted server with sensitive columns encrypted and the encryption keys are stored with a trusted client, which is a node hosted in a trusted environment, perhaps on-premises. This separation between the encrypted data and the keys provides a simple guarantee that sensitive information is only accessed in the trusted client and never decrypted in the cloud. In this paper, we investigate whether database applications can be securely and transparently migrated to this architecture without compromising performance. Towards this end, we develop a novel "secure" query compiler for T-SQL, which partitions an application (a set of stored procedures) automatically between the trusted client and the untrusted server given an input encryption policy for encrypting columns. The compiler exploits the observation that some encryption schemes are partially homomorphic i.e. permit some computations to be performed on encrypted data without changing semantics.We then report results on benchmarking this architecture on transactional benchmarks including TPC-A and TPC-C.

Suman Nath and Ramarathnam Venkatesan, Publicly Verifiable Grouped Aggregation Queries on Outsourced Data Streams, in ICDE'13: 29th IEEE International Conference on Data Engineering , International Conference on Data Engineering, April 2013

Arvind Arasu, Spyros Blanas, Ken Eguro, Raghav Kaushik, Donald Kossmann, Ravi Ramamurthy, and Ramaratnam Venkatesan, Orthogonal Security With Cipherbase, in 6th Biennial Conference on Innovative Data Systems Research (CIDR'13), , 8 January 2013

This paper describes the design of the Cipherbase system. Cipherbase is a full-fledged SQL database system that achieves high performance and high data confidentiality by storing and processing strongly encrypted data. The Cipherbase system incorporates customized trusted hardware, extending Microsoft’s SQL Server for efficient execution of queries using both secure hardware and commodity servers. This paper presents the design of the Cipherbase secure hardware and its implementation using FPGAs. Furthermore, this paper shows how we addressed hardware / software co-design in the Cipherbase system.

Ken Eguro, Kaushik Rajan, Ravi Ramamurthy, Kapil Vaswani, and Ramarathnam Venkatesan, Migration to the Cloud Made Safe and Secure, in Off the Beaten Track (OBT) Workshop, ACM, January 2013

In the last few years, cloud computing has evolved from a buzzword to a critical infrastructure component of many enterprise and consumer services. The cloud provides virtually limitless compute, storage and network resources at low cost, allowing services to scale on demand. The cloud absolves organizations from managing IT infrastructure, and allows them to focus on their core competencies. However, the benefits of cloud computing do not come for free; building and running applications for the cloud comes with significant challenges. Arguably the most significant challenge is security. By their very nature, applications deployed on a public cloud expose a larger attack surface when compared to their inhouse counterparts. Applications on the cloud are hosted in a multitenant environment, where they share physical resources such as memory, disk, network and CPU. This model, which is key to cloud providers achieving benefits of scale, enables a variety of attacks from co-located malicious applications. Another security threat are is the cloud operator, who can both observe and tamper with an application’s execution. These limitations have precluded the migration of security sensitive applications to public cloud platforms, forcing organizations to consider more expensive and less scalable alternatives such as the private cloud.

## 2012

Arvind Arasu, Spyros Blanas, Manas Joglekar, Ken Eguro, Raghav Kaushik, Donald Kossmann, Ravi Ramamurthy, Prasang Upadhyaya, and Ramarathnam Venkatesan, Engineering Performance and Security with Cipherbase, in Data Engineering Bulletin, IEEE, December 2012

Cipherbase is a full-fledged relational database system that leverages novel customized hardware to store and process encrypted data. This paper outlines the space of physical design options for Cipherbase and shows how application developers can implement their data confidentiality requirements by specifying the encryption method for static data storage and the acceptable information leakage for runtime data processing. The goal is to achieve a physical database design with the best possible performance that fulfills the application’s confidentiality requirements.

Ken Eguro and Ramarathnam Venkatesan, FPGAs for Trusted Cloud Computing, in International Conference on Field-Programmable Logic and Applications, IEEE, August 2012

FPGA manufacturers have offered devices with bitstream protection for a number of years. This feature is currently primarily used to prevent IP piracy through cloning. However, in this paper we describe how protected bitstreams can also be used to create a root of trust for the clients of cloud computing services. Unlike related software-based solutions, this hardware-based approach solves a fundamental problem that currently impedes the greater adoption of cloud computing: how to secure client data and computation from both potential external attackers and an untrusted system administrator. We examine how this approach can be applied to the specific application of handling sensitive health data. This system maintains the advantages of the cloud with minimal additional hardware. We also describe how this system can be extended to provide a more generic secure cloud architecture.

## 2011

Sandeep Karanth, Srivatsan Laxman, Prasad Naldurg, Ramarathnam Venkatesan, J. Lambert, and Jinwook Shin, ZDVUE: Prioritization of JavaScript Attacks To Discover New Vulnerabilities, in Proceedings of the Fourth ACM Workshop on Artificial Intelligence and Security (AISEC 2011), ACM, October 2011

Suman Nath and Ramarathnam Venkatesan, Group-by Query Verification by Untrusted Clients on Outsourced Data Streams, no. MSR-TR-2011-104, 28 July 2011

Outsourcing data streams and desired computations to a third party such as the cloud is practical for many companies due to overwhelming flow of information and excessively high resource requirements of their data stream applications. However, data outsourcing and remote computations intrinsically raise issues of trust, making it crucial to verify results returned by third parties. In this context, we propose a novel solution to verify outsourced "Group-By, Sum" (or histogram) queries that are common in many business applications. We consider a setting where a data owner employs an untrusted remote server to run continuous Group-By, Sum queries on a data stream it forwards to the server. Untrusted clients then query the server for the computed results. More importantly, a client can efficiently verify the correctness of the results by using a small and easy-to-compute signature provided by the data owner. Our work complements previous works on authenticating remote computation of selection and aggregation queries. Moreover, unlike prior work on remote Group-by queries, we support untrusted clients (who can collude with other clients or with the server) and provide stronger cryptographic guarantees. Experimental results on real and synthetic data show that our solution is practical and efficient.

## 2010

Sandeep Karanth, Srivatsan Laxman, Prasad Naldurg, Ramarathnam Venkatesan, J Lambert, and Jinwook Shin, Pattern Mining for Future Attacks, no. MSR-TR-2010-100, July 2010

Malware writers are constantly looking for new vulnerabilities in popular software applications to exploit for profit, and discovering such a flaw is literally equivalent to find- ing a gold mine. When a completely new vulnerability is found, and turned into what are called Zero Day attacks, they can often be critical and lead to data loss or breach of privacy. Zero Day vulnerabilities, by their very nature are notoriously hard to find, and the odds seem to be stacked in favour of the attacker. However, before a Zero Day attack is discovered, attackers stealthily test different payload delivery methods and their obfuscated variants, in an attempt to outsmart anti-malware protection, with varying degrees of success. Evidence of such failed attempts, if any, are available on the victim machines, and the challenge is to discover their signatures before they can be turned into exploits. Our goal in this paper is to search for such vulnerabilities and straighten the odds. We focus on Javascript files, and using a combination of pattern mining and learning, effectively and two new Zero Day vulnerabilities in Microsoft Internet Explorer, using code collected between June and November 2009.

Sumit Gulwani, Susmit Jha, Ashish Tiwari, and Ramarathnam Venkatesan, Component Based Synthesis Applied to Bitvector Circuits, no. MSR-TR-2010-12, February 2010

We define "component-based synthesis" to be the problem of synthesis of (straight-line) programs from appropriate composition of base components from a specified library of software components. The functional specification of the desired program and the library components is provided in the form of logical formulas that relate the respective input and output variables. This has applications in design of intricate circuits or algorithms, superoptimization, and API mining. Furthermore, automated synthesis provides the promise of correctness by construction, generation of efficient systems, and improvement in developer's productivity. We solve the component-based synthesis problem using a constraint-based approach that involves first generating a "synthesis constraint", and then solving the constraint. The synthesis constraint is a first-order logic formula whose size is quadratic in the number of components, but has quantifier alternation. We present a novel algorithm for solving such constraints. Our algorithm is based on counterexample guided iterative synthesis paradigm and uses off-the-shelf SMT solvers. We present experimental results on synthesizing a variety of bitvector algorithms that involve unintuitive composition of standard bitvector operations and are difficult to synthesize manually. We also compare our technique with existing synthesis approaches based on sketching and superoptimization. Our tool Brahma can efficiently synthesize highly nontrivial 10-20 line loop-free programs. These programs represent a state space of approximately $20^{10}$ programs, and are beyond the reach of the other tools.

## 2009

Mariusz H. Jakubowski, Nick Saw, and Ramarathnam Venkatesan, Tamper-Tolerant Software: Modeling and Implementation, in International Workshop on Security (IWSEC 2009), Springer Verlag, 28 October 2009

Common software-protection systems attempt to detect malicious observation and modification of protected applications. Upon tamper detection, anti-hacking code may produce a crash or gradual failure, rendering the application unusable or troublesome. Such a response is designed to complicate attacks, but has also caused problems for developers and end users, particularly when bugs or other problems invoke anti-tampering measures accidentally. To address these issues, an alternative approach is to detect and fix malicious changes. This paper presents a scheme to transform programs into tamper-tolerant versions that use self-correcting operation as a response against attacks. Combining techniques from the fields of fault tolerance and software security, the approach transforms programs via code individualization and redundancy. We also describe security enhancements through error correction, delayed responses and checkpointing. For security analysis, we adapt a graph-based model of attacks and defenses in the context of software tamper-resistance. This helps to estimate the difficulty of breaking our scheme in practical scenarios.

Mariusz Jakubowski, Ramarathnam Venkatesan, and Yacov Yacobi, Quantifying Trust, no. MSR-TR-2009-119, October 2009

Trust is a central concept in public-key cryptography infrastructure and in security in general. We study its initial quantication 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 sepa- rate 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. Specically, 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.

Mariusz H. Jakubowski, Nick Saw, and Ramarathnam Venkatesan, Iterated Transformations and Quantitative Metrics for Software Protection, in International Conference on Security and Cryptography (SECRYPT 2009), 7 July 2009

This paper describes a new framework for design, implementation and evaluation of software-protection schemes. Our approach is based on the paradigm of {\em iterated protection}, which repeats and combines simple transformations to build up complexity and security. Based on ideas from the field of complex systems, iterated protection is intended as an element of a comprehensive obfuscation and tamper-resistance system, but not as a full-fledged, standalone solution. Our techniques can (and should) be combined with previously proposed approaches, strengthening overall protection. A long-term goal of this work is to create protection methods amenable to analysis or estimation of security in practice. As a step towards this, we present security evaluation via {\em metrics} computed over transformed code. Indicating the difficulty of real-life reverse engineering and tampering, such metrics offer one approach to move away from ad hoc, poorly analyzable approaches to protection.

Bertrand Anckaert, Mariusz H. Jakubowski, Ramarathnam Venkatesan, and Chit Wei Saw, Runtime Protection via Dataflow Flattening, in The Third International Conference on Emerging Security Information, Systems and Technologies (SECURWARE 2009), 22 June 2009

Software running on an open architecture, such as the PC, is vulnerable to inspection and modification. Since software may process valuable or sensitive information, many defenses against data analysis and modification have been proposed. This paper complements existing work and focuses on hiding data location throughout program execution. To achieve this, we combine three techniques: (i) periodic reordering of the heap, (ii) migrating local variables from the stack to the heap and (iii) pointer scrambling. By essentialy flattening the dataflow graph of the program, the techniques serve to complicate static dataflow analysis and dynamic data tracking. Our methodology can be viewed as a data-oriented analogue of control-flow flattening techniques. Dataflow flattening is useful in practical scenarios like DRM, information-flow protection, and exploit resistance. Our prototype implementation compiles C programs into a binary for which every access to the heap is redirected through a memory management unit. Stack-based variables may be migrated to the heap, while pointer accesses and arithmetic may be scrambled and redirected. We evaluate our approach experimentally on the SPEC CPU2006 benchmark suite.

Bertrand Anckaert, Mariusz H. Jakubowski, Ramarathnam Venkatesan, and Nick Saw, Practical Data Location Obfuscation, no. MSR-TR-2009-3, 8 January 2009

Software running on an open architecture, such as the PC, is vulnerable to inspection and modification. This is a concern, as software may consist of or provide access to valuable information. As a result, several defenses against program understanding and modification have been proposed in literature. The approach discussed in this paper complements existing work and focuses on hiding the actual location of data throughout the execution of the program. To achieve this, we combine three techniques: (i) periodic reordering of the heap, (ii) migrating local variables from the stack to the heap and (iii) pointer scrambling. The techniques serve to complicate static data flow analysis and dynamic data tracking. Our prototype implementation compiles C programs into a binary for which every access to the heap is redirected through a memory management unit. In order to protect traditionally stack-based variables as well, a mechanism is provided to migrate them to the heap and to adapt all accesses to those variables. Finally, an option is provided to enable pointer scrambling. If this is turned on, the program can no longer operate directly on the pointers; therefore, pointer arithmetic is intercepted as well. Experimental evaluation on benchmarks from the SPEC CPU2006 benchmark suite illustrates the type of trade-off that needs to be made for this type of protection. Balance must be struck between comprehensive protection and cost in terms of execution time and (to a lesser extent) static and dynamic memory footprint.

David Jao, Stephen D. Miller, and Ramarathnam Venkatesan, Expander graphs based on GRH with an application to elliptic curve cryptography, in Journal of Number Theory, vol. 129, no. 6, pp. 1491 - 1504, 2009

Stephen D. Miller and Ramarathnam Venkatesan, Non-Degeneracy of Pollard Rho Collisions, in Int Math Res Notices, vol. 2009, no. 1, pp. 1-10, 2009

Srivatsan Narayanan, Ananth Raghunathan, and Ramarathnam Venkatesan, Obfuscating straight line arithmetic programs, in Digital Rights Management Workshop, 2009

Raghav Bhaskar, Karthekeyan Chandrasekaran, Satyanaryana V. Lokam, Peter L. Montgomery, Ramarathnam Venkatesan, and Yacov Yacobi, An observation about variations of the Diffie-Hellman assumption, in Serdica Journal of Computing, 2009

Sumit Gulwani, Saurabh Srivastava, and Ramarathnam Venkatesan, Constraint-Based Invariant Inference over Predicate Abstraction, in VMCAI, 2009

## 2008

Matthias Jacob, Mariusz H. Jakubowski, Prasad Naldurg, Chit Wei (Nick) Saw, and Ramarathnam Venkatesan, The Superdiversifier: Peephole Individualization for Software Protection, in 3rd International Workshop on Security (IWSEC 2008), Springer Verlag, Kagawa, Japan, November 2008

Matthew Cary, Matthias Jacob, Mariusz H. Jakubowski, and Ramarathnam Venkatesan, The Long-Short-Key Primitive and Its Applications to Key Security, in 3rd International Workshop on Security (IWSEC 2008), Kagawa, Japan, November 2008

Sumit Gulwani, Saurabh Srivastava, and Ramarathnam Venkatesan, Constraint-based Invariant Inference over Predicate Abstraction, no. MSR-TR-2008-163, October 2008

This paper describes a constraint-based invariant generation technique for proving the validity of safety assertions over the domain of predicate abstraction in an interprocedural setting. The key idea of the technique is to represent each invariant in bounded DNF form by means of boolean indicator variables, one for each predicate \pred and each disjunct \disj denoting whether \pred is present in \disj or not. The verification condition of the program is then encoded by means of a boolean formula over these boolean indicator variables such that any satisfying assignment to the formula yields the inductive invariants for proving the validity of given program assertions. This paper also describes how to use the constraint-based methodology for generating maximally-weak preconditions for safety assertions. An interesting application of maximally-weak precondition generation is to produce maximally-general counterexamples for safety assertions. We also present preliminary experimental evidence demonstrating the feasibility of this technique.

Sumit Gulwani, Saurabh Srivastava, and Ramarathnam Venkatesan, Program Analysis as Constraint Solving, no. MSR-TR-2008-44, March 2008

A constraint-based approach to invariant generation in programs translates a program into constraints that are solved using off-the-shelf constraint solvers to yield desired program invariants. In this paper we show how the constraint-based approach can be used to model a wide spectrum of program analyses in an expressive domain containing disjunctions and conjunctions of linear inequalities. In particular, we show how to model the problem of context-sensitive interprocedural program verification. We also present the first constraint-based approach to weakest precondition and strongest postcondition inference. The constraints we generate are boolean combinations of quadratic inequalities over integer variables. We reduce these constraints to SAT formulae using bit-vector modeling and use off-the-shelf SAT solvers to solve them. Furthermore, we present interesting applications of the above analyses, namely bounds analysis and generation of most-general counter-examples for both safety and termination properties. We also present encouraging preliminary experimental results demonstrating the feasibility of our technique on a variety of challenging examples.

Dimitar Jetchev and Ramarathnam Venkatesan, Bits Security of the Elliptic Curve Diffie-Hellman Secret Keys, in CRYPTO, 2008

Adi Akavia and Ramarathnam Venkatesan, Perturbation Codes, in 46th Annual Allerton Conference, Sep 2008, Univ. of Ill. Urbana-Champaign, 2008

## 2007

Mariusz H. Jakubowski and Ramarathnam Venkatesan, Randomized Radon transforms for biometric authentication via fingerprint hashing, in 7th ACM Workshop on Digital Rights Management, Alexandria, VA, October 2007

Bertrand Anckaert, Mariusz H. Jakubowski, Ramarathnam Venkatesan, and Koen De Bosschere, Run-time randomization to mitigate tampering, in 2nd International Workshop on Security (IWSEC 2007), Nara, Japan, October 2007

Srivatsan Laxman, Prasad Naldurg, Raja Sripada, and Ramarathnam Venkatesan, Connections between Mining Frequent Itemsets and Learning Generative Models, in Proceedings of Seventh IEEE International Conference on Data Mining, 2007 (ICDM 2007), Omaha, USA, IEEE, October 2007

Frequent itemsets mining is a popular framework for pattern discovery. In this framework, given a database of customer transactions, the task is to unearth all patterns in the form of sets of items appearing in a sizable number of transactions. We present a class of models called Itemset Generating Models (or IGMs) that can be used to formally connect the process of frequent item- sets discovery with the learning of generative models. IGMs are specified using simple probability mass functions (over the space of transactions), peaked at specific sets of items and uniform everywhere else. Under such a connection, it is possible to rigorously associate higher frequency patterns with generative models that have greater data likelihoods. This enables a generative model-learning interpretation of frequent itemsets mining. More importantly, it facilitates a statistical significance test which prescribes the minimum frequency needed for a pattern to be considered interesting. We illustrate the effectiveness of our analysis through experiments on standard benchmark data sets.

Matthias Jacob, Mariusz H. Jakubowski, and Ramarathnam Venkatesan, Towards integral binary execution: Implementing oblivious hashing using overlapped instruction encodings, in 2007 ACM Multimedia and Security Workshop, Dallas, TX, September 2007

Srivatsan Laxman, Prasad Naldurg, Raja Sripada, and Ramarathnam Venkatesan, Connections between mining frequent itemsets and learning generative models, no. MSR-TR-2007-100, August 2007

Frequent itemsets mining is a popular framework for pattern discovery. In this framework, given a database of customer transactions, the task is to unearth all pat- terns in the form of sets of items appearing in a sizable number of transactions. We present a class of models called Itemset Generating Models (or IGMs) that can be used to formally connect the process of frequent item- sets discovery with the learning of generative models. IGMs are specified using simple probability mass func- tions (over the space of transactions), peaked at spe- cific sets of items and uniform everywhere else. Under such a connection, it is possible to rigorously associate higher frequency patterns with generative models that have greater data likelihoods. This enables a generative model-learning interpretation of frequent itemsets min- ing. More importantly, it facilitates a statistical sig- nificance test which prescribes the minimum frequency needed for a pattern to be considered interesting. We illustrate the effectiveness of our analysis through ex- periments on standard benchmark data sets.

Mariusz H. Jakubowski, Prasad Naldurg, Vijay Patankar, and Ramarathnam Venkatesan, Software integrity checking expressions (ICEs) for robust tamper detection, in Information Hiding 2007, Saint Malo, France, June 2007

Nenad Dedic, Mariusz H. Jakubowski, and Ramarathnam Venkatesan, A graph game model for software tamper protection, in Information Hiding 2007, Saint Malo, France, June 2007

Nathan Keller, Stephen D. Miller, Ilya Mironov, and Ramarathnam Venkatesan, MV3: A new word based stream cipher using rapid mixing and revolving buffers, in Topics in Cryptology (CT-RSA 2007), Springer, February 2007

Debapratim De, Abishek Kumarasubramanian, and Ramarathnam Venkatesan, Inversion Attacks on Secure Hash Functions Using satSolvers, in SAT, 2007

David Jao, Dimitar Jetchev, and Ramarathnam Venkatesan, On the Bits of Elliptic Curve Diffie-Hellman Keys, in INDOCRYPT, 2007

David Jao, S. Ramesh Raju, and Ramarathnam Venkatesan, Digit Set Randomization in Elliptic Curve Cryptography, in SAGA, 2007

## 2006

Ganesh Ananthanarayanan, Ramarathnam Venkatesan, Prasad Naldurg, Sean Blagsvedt, and A. Hemakumar, SPACE: Secure Protocol for Address-Book based Connection Establishment, in ACM HotNets, Irvine, CA, USA, Association for Computing Machinery, Inc., November 2006

Bertrand Anckaert, Mariusz H. Jakubowski, and Ramarathnam Venkatesan, Proteus: Virtualization for diversified tamper-resistance, in 6th ACM Workshop on Digital Rights Management, Alexandria, VA, October 2006

Stephen D. Miller and Ramarathnam Venkatesan, Spectral Analysis of Pollard Rho Collisions, in ANTS, 2006

## 2005

Ramarathnam Venkatesan and Mariusz H. Jakubowski, Randomized detection for spread-spectrum watermarking: Defending against sensitivity and other attacks, in IEEE International Conference on Acoustics, Speech and Signal Processing: ICASSP 2005, Philadelphia, PA, March 2005

David Jao, Stephen D. Miller, and Ramarathnam Venkatesan, Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?, in ASIACRYPT, 2005

Mehmet Kucukgoz, Oztan Harmanci, Mehmet Kivanç Mihçak, and Ramarathnam Venkatesan, Robust video watermarking via optimization algorithm for quantization of pseudo-random semi-global statistics, in Security, Steganography, and Watermarking of Multimedia Contents, 2005

Mehmet Kivanç Mihçak, Ramarathnam Venkatesan, and Tie Liu, Watermarking via optimization algorithms for quantizing randomized semi-global image statistics, in Multimedia Syst., vol. 11, no. 2, pp. 185-200, 2005

Mustafa Kesal, Mehmet Kivanç Mihçak, and Ramarathnam Venkatesan, An improved attack analysis on a public-key spread spectrum watermarking, in Multimedia Syst., vol. 11, no. 2, pp. 133-142, 2005

Michael Malkin and Ramarathnam Venkatesan, Comparison of Texts Streams in the Presence of Mild Adversaries, in ACSW Frontiers, 2005

M. Malkin and Ramarathnam Venkatesan, Robust Image Watermarking with the randlet transform, in 43rd Annual Allerton Conference on Communications, Control, and Computing, 2005

## 2004

Suleyman Serdar Kozat, Ramarathnam Venkatesan, and Mehmet Kivanç Mihçak, Robust perceptual image hashing via matrix invariants, in ICIP, 2004

David Jao, Stephen D. Miller, and Ramarathnam Venkatesan, Ramanujan Graphs and the Random Reducibility of Discrete Log on Isogenous Elliptic Curves, in CoRR, vol. math.NT/0411378, 2004

Mustafa Kesal, Mehmet Kivanç Mihçak, and Ramarathnam Venkatesan, An improved attack analysis on a public-key spread spectrum watermarking, in MM&Sec, 2004

M. Malkin and Ramarathnam Venkatesan, The randlet transform: Applications to universal perceptual hash- ing and image identi¯cation, in 42nd Annual Allerton Conference on Communications, Control, and Computing, 2004

Tie Liu, Ramarathnam Venkatesan, and Mehmet Kivanç Mihçak, Scale-invariant image watermarking via optimization algorithms for quantizing randomized statistics, in MM&Sec, 2004

## 2003

Kamal Jain and Ramarathnam Venkatesan, Efficient Codes Via Cryptographic Assumptions, in 41st Annual Allerton Conference on Communications, Control, and Computing, 2003

Matthew Cary and Ramarathnam Venkatesan, A Message Authentication Code Based on Unimodular Matrix Groups, in CRYPTO, 2003

## 2002

Yuqun Chen, Ramarathnam Venkatesan, Matthew Cary, Ruoming Pang, Saurabh Sinha, and Mariusz H. Jakubowski, Oblivious hashing: A stealthy software integrity verification primitive, in Information Hiding 2002, Noordwijkerhout, The Netherlands, October 2002

Jeremy Horwitz and Ramarathnam Venkatesan, Random Cayley Digraphs and the Discrete Logarithm, in ANTS, 2002

Kivanc Mihcak and Ramarathnam Venkatesan, Blind Image Watermarking Via Derivation and Quantization of Robust Semi–Global Statistics, in Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2002), 2002

Mehmet Kivanç Mihçak, Ramarathnam Venkatesan, and Mustafa Kesal, Cryptanalysis of Discrete-Sequence Spread Spectrum Watermarks, in Information Hiding, 2002

## 2001

Mehmet Kivanç Mihçak and Ramarathnam Venkatesan, A Perceptual Audio Hashing Algorithm: A Tool for Robust Audio Identification and Information Hiding, in Information Hiding, 2001

Ramarathnam Venkatesan Microsoft, Ramarathnam Venkatesan, Vijay Vazirani, and Saurabh Sinha, A Graph Theoretic Approach to Software Watermarking, in In 4th International Information Hiding Workshop, Springer-Verlag, 2001

Mehmet Kivanç Mihçak and Ramarathnam Venkatesan, New Iterative Geometric Methods for Robust Perceptual Image Hashing, in Digital Rights Management Workshop, 2001

Amod Agashe, Kristin Lauter, and Ramarathnam Venkatesan, Constructing elliptic curves with a given number of points over a finite field, in Fields Insitute Communications Series, Volume 42, vol. 2001, pp. 96, American Mathematical Society, 2001

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(X) modulo some integer p for a certain fundamental discriminant D. The usual way of doing this is to compute H(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(X) modulo p directly from the knowledge of H(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.

## 2000

Ramarathnam Venkatesan and Mariusz H. Jakubowski, Image watermarking with better resilience, in IEEE International Conference on Image Processing: ICIP 2000, Vancouver (BC), CA, September 2000

Ramarathnam Venkatesan, S.-M. Koon, Mariusz H. Jakubowski, and P. Moulin, Robust image hashing, in IEEE International Conference on Image Processing: ICIP 2000, Vancouver (BC), CA, September 2000

Ramarathnam Venkatesan and Mariusz H. Jakubowski, Image hashing, in DIMACS Workshop on Protection of Intellectual Property, New Brunswick, NJ, April 2000

## 1998

Mariusz H. Jakubowski and Ramarathnam Venkatesan, The chain & sum primitive and its applications to MACs and stream ciphers, in Advances in Cryptology – Eurocrypt '98, Espoo, Finland, May 1998

Victor Boyko, Marcus Peinado, and Ramarathnam Venkatesan, Speeding up Discrete Log and Factoring Based Schemes via Precomputations, in EUROCRYPT, 1998

William Aiello, Mihir Bellare, Giovanni Di Crescenzo, and Ramarathnam Venkatesan, Security amplification by composition: The case of doubly-iterated ideal ciphers, in CoRR, vol. cs.CR/9809031, 1998

Dan Boneh and Ramarathnam Venkatesan, Breaking RSA May Not Be Equivalent to Factoring, in EUROCRYPT, 1998

William Aiello, Stuart Haber, and Ramarathnam Venkatesan, New Constructions for Secure Hash Functions, in FSE, 1998

William Aiello, Sivaramakrishnan Rajagopalan, and Ramarathnam Venkatesan, Design of Practical and Provably Good Random Number Generators, in J. Algorithms, vol. 29, no. 2, pp. 358-389, 1998

Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, and Moti Yung, Perfect Zero-Knowledge Arguments for P Using Any One-Way Permutation, in J. Cryptology, vol. 11, no. 2, pp. 87-108, 1998

## 1997

Dan Boneh and Ramarathnam Venkatesan, Rounding in Lattices and its Cryptographic Applications, in SODA, 1997

Marcus Peinado and Ramarathnam Venkatesan, Highly Parallel Cryptographic Attacks, in PVM/MPI, 1997

## 1996

Dan Boneh and Ramarathnam Venkatesan, Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes, in CRYPTO, 1996

William Aiello and Ramarathnam Venkatesan, Foiling Birthday Attacks in Length-Doubling Transformations - Benes: A Non-Reversible Alternative to Feistel, in EUROCRYPT, 1996

## 1995

William Aiello, Sivaramakrishnan Rajagopalan, and Ramarathnam Venkatesan, Design of Practical and Provably Good Random Number Generators (Extended Abstract), in SODA, 1995

Dennis Grinberg, Sivaramakrishnan Rajagopalan, Ramarathnam Venkatesan, and Victor K. Wei, Splay Trees for Data Compression, in SODA, 1995

William Aiello, Mihir Bellare, and Ramarathnam Venkatesan, Knowledge on the average-perfect, statistical and logarithmic, in STOC, 1995

## 1994

William Aiello, Ramarathnam Venkatesan, and Moti Yung, Coins, Weights and Contention in Balancing Networks, in PODC, 1994

## 1993

Rafail Ostrovsky, Ramarathnam Venkatesan, and Moti Yung, Interactive Hashing Simplifies Zero-Knowledge Protocol Design, in EUROCRYPT, 1993

## 1992

Rafail Ostrovsky, Ramarathnam Venkatesan, and Moti Yung, Secure Commitment Against A Powerful Adversary, in STACS, 1992

Ramarathnam Venkatesan and Sivaramakrishnan Rajagopalan, Average Case Intractability of Matrix and Diophantine Problems (Extended Abstract), in STOC, 1992

Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, and Moti Yung, Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions (Extended Abstract), in CRYPTO, 1992

## 1990

Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, and David Zuckerman, Security Preserving Amplification of Hardness, in FOCS, 1990

## 1988

Ramarathnam Venkatesan and Leonid A. Levin, Random Instances of a Graph Coloring Problem Are Hard, in STOC, 1988

More publications...