Gene Itkis

Computer Science Department, Boston University 111 Cummington St., Boston, MA 02215 http://www.cs.bu.edu/~itkis/

 

 

The following are some of the selected papers representing my research interests.

Selected Publications

 

 Gene Itkis and Leonid A. Levin. Flat Holonomies on Automata Networks. An invited paper, International Symposium on Theoretical Aspects of Computer Science (STACS), 2006.

We consider asynchronous dynamic networks of identical finite (independent of the network size) automata. A useful data structure on such networks is a partial orientation of its edges. It needs to be straight, i.e., have null holonomy (the difference between the number of up and down edges in each cycle). It also needs to be centered, have a unique node with no down edges. Using such orientation, any feasible computational task can be efficiently implemented with self-stabilization and synchronization. There are (interdependent) self-stabilizing asynchronous finite automata protocols assuring straight and centered orientation. Such protocols may vary in assorted efficiency parameters and it is desirable to have each replaceable with any alternative, responsible for a simple limited task. We describe an efficient reduction of any computational task to any such set of protocols compliant with our interface conditions.

 

 Gene Itkis and Leonid Reyzin. SiBIR: Signer-Base Intrusion-Resilient Signatures, CRYPTO-2002.

We propose a new notion of intrusion-resilient signature schemes, which generalizes and improves upon both forward-secure key-insulated signature schemes.
Specifically, as in the prior notions, time is divided into predefined time periods (e.g., days); each signature includes the number of the time time period in which it was generated; while the public key remains the same, the secret keys evolve with time. Also, as in key-insulated schemes, the user has two modules, signer and home base: the signer generates signatures on its own, and the base is needed only to help update the signer's key from one period to the next.
The main strength of intrusion-resilient schemes, as opposed to prior notions, is that they remain secure even after arbitrarily many compromises of both modules, as long as the compromises are not simultaneous. Moreover, even if the intruder does compromise both modules simultaneously, she will still be unable to generate any signatures for the previous time periods. We provide an efficient intrusion-resilient signature scheme, provably secure in the random oracle model based on the strong RSA assumption.
We also discuss how such schemes can eliminate the need for certificate revocation in the case of on-line authentication.

 

 Gene Itkis and Leonid Reyzin. Forward Secure Signatures with Optimal Signing and Verifying, CRYPTO-2001.
Also published as MIT Technical Report, April 2001, and as an invited paper in Cryptobytes v.5 #2, 2002.

Ordinary digital signatures have an inherent weakness: if the secret key is leaked, then all signatures, even the ones generated before the leak, are no longer trustworthy. Forward-secure digital signatures were recently proposed to address this weakness: they ensure that past signatures remain secure even if the current secret key is leaked.
We propose the first forward-secure signature scheme for which both signing and verifying are as efficient as for one of the most efficient ordinary signature schemes (Guillou-Quisquater): each requiring just two modular exponentiations with a short exponent. The previously proposed forward-secure signature schemes had significant costs overhead for signing and verifying, compared with ordinary schemes. Our scheme requires only fractional increases to the sizes of keys and signatures, and no additional public storage.
 

Gene Itkis. Cryptographic Tamper Evidence. The ACM Conference on Computer and Communications Security (CCS), 2003.

What can be done when all your secrets have been stolen without your knowledge? It may seem that your security is lost, since the attacker now knows everything you do. You might not even realize that you need to revoke your keys.
This paper challenges this perception. We propose a new notion: cryptographic tamper evidence. A tamper-evident signature scheme includes a mechanism which can detect forger's activity and produce a proof that the secret keys have been exposed. In some contexts, it might even allow to continue functioning safely, even after the adversary has stole your keys. At the very least, it can signal the key exposure.
More formally, a tamper-evident signature scheme includes an additional procedure Div, which given two signatures can detect whether they were both generated by a legitimate signer, or one by the legitimate signer and the other by a forger. The surprising property is that this is possible even after the forger had exposed all the secrets in the system. In this case, it might, of course, be impossible to tell which signature is generated by the legitimate signer and which by the forger. But at least the fact of the tampering will be made evident.
We define several variants of tamper-evidence, differing in their power to detect tampering. In all of these, we assume equally powerful adversary: she adaptively controls the choices of all messages (including timing), chooses and supplies all the inputs to the legitimate signer and observes all his outputs; she also can adaptively expose all the secrets at arbitrary times.
We present tamper-evident signature schemes for these variants, and prove their optimality.
We stress that our mechanisms are purely cryptographic: the tamper-detection algorithm Div is stateless and takes no inputs except the two signatures (in particular, it keeps no logs), we use no infrastructure (or other ways to conceal additional secrets), and we use no hardware properties (we do assume those implied by the standard cryptographic assumptions, including use of random number generators).
Our constructions are based on arbitrary ordinary signature schemes and do not require random oracles.

 

 R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas. Multicast Security: A Taxonomy and Efficient Authentication, IEEE INFOCOM-99. (ps)

This paper presents a taxonomy of multicast scenarios with the relevant security concerns, and addresses two major security problems of multicast: source authentication, and key revocation. The approach of Asymmetric MACs (proposed in CRYPTO-96 rump-session presentation below) is further developed and applied to authenticating the multicast sources. An improvement of the previous solution for the key revocation problem is also presented. This paper is also the basis for a recent internet-draft, prepared for the Secure Multicast Group (SMuG) of the IRTF.

 

G. Itkis and L. A. Levin. Power of Fast VLSI Models is Insensitive to Wires' Thinness, in proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), 1989.

Comparing VLSI models we show when the effect of wires' speed overtakes any effect of wires' width. We give the best possible (slightly super-linear) threshold at which all effects of wires' width vanish. These results can also be viewed in terms of routing.