Gene Itkis |
Computer Science Department,
http://www.cs.bu.edu/~itkis/ |
The following are some of the selected papers representing my research interests.
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.
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.
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.
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.
S. Even, G.
Itkis and S. Rajsbaum.
On Mixed Connectivity
Certificates, in Journal
of Theoretical Computer Science 203 (1998) 253-269. Also
appeared in proceedings of the European Symposium
on Algorithms (ESA, keynote address paper), Lecture Notes in
Computer Science, Springer-Verlag, 1995.
(local:
ps)
Vertex and edge connectivity are special cases of mixed connectivity,
which treats equally edges and vertices from a specified set. A k-connectivity
certificate is a spanning subgraph preserving the
graph's connectivity up to k. We unify previous results on the certificates and
extend them to handle mixed connectivity and arbitrary parallel edges. We also
present a new distributed algorithm, finding such certificates, with better
than the previously known time and communication complexities (in fact, the last
is optimal).
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.