Caught in the act of shooting this photo

Yacov Yacobi

Principal Researcher and Cryptographer at Microsoft Research

Short Bio

Yacov Yacobi is a Principal Researcher at Microsoft Research. Founder and head of the Cryptography & Anti-Piracy research group in Microsoft Research (from 1997 to October 2007). Current personal research includes cryptography, economic analysis of anti-piracy systems and electronic payment systems. Member of the editorial boards of the Journal of Computer Security, and of ACM Wireless Networks. Member of the  CISaC Technical Advisory Panel. Guest co-editor of two issues on security of IEEE Wireless Communications. Prior to joining Microsoft in 1995 was a Senior-Researcher at the Applied Research Division of Bellcore (now Telcordia). PhD in EE from the Technion Israel Inst. of Tech.

Selected Publications and Notes

(The reference numbers are those of the DBLP below.)

Complexity Theory

In [6] we show that any problem that is not solvable in probabilistic polynomial time has infinite “hard core” (every probabilistic polynomial time algorithm has infinite subset of instances on which it stumbles).

In [4,5] we invented “promise problems.” They now find applications in Quantum Computations among others (see a tutorial by Oded Goldreich: A Promise Problem Survey, in Theoretical Computer Science, Essays in Memory of Shimon Even, LNCS 3895).

In [3] we show that some problems not in the union of NP and CoNP are not that hard (they must be harder that polynomial-time by def. but if P≠NP at all then they are easier than NP-Complete).

In [2] we showed the first cryptosystem provably in NP-complete and then broke it (I did the invention and the proof; Abraham Lempel broke it and published the whole thing ahead of us).

In [1] we show that problems with unique solutions cannot be in NP-complete (that includes all of public key cryptography).

Cryptography

In [31, 32] we show a new more efficient attack on RSA by a factor log²e, where e is the public exponent (excluding off-line computation that can be amortized over many instances). The surprise is that after so many years one can still improve on RSA attacks.

In [11, 12, 25] I show that the Lempel-Ziv compression algorithm can be used to speed up long exponentiations (e.g. all the exponentiations used public key crypto), and that asymptotically this method is as fast as the best known methods for exponents of maximal entropy. Below some entropy this method becomes superior. This in fact applies to any repeated group operation, such as multiplication by a scalar in elliptic curve crypto.

[14, 16, 22] are about Identity Based encryption. Not as computationally efficient as the much more modern Boneh-Franklin method, but relies on old assumptions. In [8] I broke the Koyama-Ohta ID-based system.

Papers [23, 17] shows how a server can simultaneously agree on many Diffie-Hellman session keys at the cost of one agreement.

[21] Got me Erdös number 2.

In [20] I use a quirk of El-Gamal signature systems (that using the same random element twice kills you) to catch double spenders in e-cash system.

[19] Was the first to use the complementary asymmetry of RSA and DSA to help small devices. The asymmetry is that in RSA the secret operation is expensive and the public operation is cheap, and in DSA it is the other way round (at least when counting only real time ops). We put the small device always on the easy side of the job.

[10, 15] Shows how to design and analyze crypto protocols using the same tools that we use for the design and analysis of crypto algorithms, namely reductions from established (believed to be) hard problems (alternative methods, such as BAN logic have more axioms than anyone is able to prove consistency of the axioms).

In [13] I show that the Rabin “paradox” (a proof of security against one attack is the attack-tool for another scenario) exists in some discrete-log systems as well. I then show a system that does not have this problem.

In [7] we broke all known privacy homeomorphisms that were known at the time.

Together with Shimon Even and Oded Goldreich we invented the Electronic Wallet. I just noticed that these papers do not appear in the DBLP. Electronic wallet; Crypto 83, S Even, O Goldreich, Y Yacobi - 1984 - Plenum Press, New York

A new paper appeared in STM 2007: R. Bhaskar, K. Chandrasekaran, S. Lokam, P.L. Montgomery, R. Venkatesan, Y. Yacobi: Vulnerabilities in Anonymous Credential Systems, were we show (i) In existing anonymous credential revocation systems, the revocation authority can link the transactions of any user in a subset T, in O(log |T|) fake failed sessions. (ii) A concern about Brands' DLREP-I anonymous credentials system.

Info hiding

In [29] we lay the grounds for public key watermarking (PKWM). The particular example uses spread spectrum, but the same philosophy applies to the more modern embedding methods. PKWM is essential for BORE-resist DRM. The paper got the best paper award in ACM Multimedia 2002.

[27] Improves the collusion-resistance of the [BS] fingerprinting method by an order of magnitude for a typical movie.

E-commerce

[24,26] show upper bounds on theft when partial real time audit is used to control damage in e-cash systems.

In [30] we show that sometimes the gain from introducing forensics to fight counterfeiting of SW and content goes down as the penalty grows.

The next one is not in the DBLP:

Y. Yacobi: Risk Management for E-Cash Systems with Partial Real-Time Audit. Netnomics 3, 119-127, 2001. Kluwer Academic Publishers.

I proved that for ``coin wallet'' if we audit a fraction m<<1 of the transactions, then the upper bound on theft is m^-2.

List of Publications

From DBLP: Yacov Yacobi
Coauthor Index - Ask others: ACM DL - ACM Guide - CiteSeer - CSB - Google

Coauthor Index

Colors in the list of coauthors

DBLP: [Home | Search: Author, Title | Conferences | Journals] Michael Ley (ley@uni-trier.de) Wed Apr 19 19:52:50 2006