Gene Itkis |
Computer Science Department, Boston University |
|
111 Cummington St., Boston, MA 02215 |
EXPERTISE: Systems and Information Security and Fault-Tolerance, Applied Cryptography, Evolving/Self-Healing Crypto-systems, Secure Multicast, Digital Signatures, Key Management, Public Key Infrastructures and Certificate Management, Content Protection, Distributed Computation
EXPERIENCE:
1999 - present
Boston University, Computer Science Department, Boston, MA
Assistant Professor. Perform research (see some follow up: over 950 citations) and teach in the areas Network Security, Applied Cryptography, and Secure Distributed Computing. Defined and supervised a number of graduate and undergraduate projects. Developed and taught a course in Network Security; also taught Cryptography, Algorithms, Topics in Internet Security, Intro to CS II, Combinatoric Structures, Algebraic Algorithms. Program committee member and reviewer for various conferences and journals.
Associate Director
for Research. The Center for Reliable Information Systems and
Cyber Security (RISCS).
Principal Investigator. NSF Trusted Computing grant: Systems
Security Through Fault-Tolerant Cryptography.
2006 Massachusetts
Institute of Technology,
Cambridge, MA
Spring Visiting Scientist. Cryptography and Information Security Group.
1995 - 1999 NDS Technologies,
Jerusalem, Israel
Senior Researcher. As a security expert, participated in the design and
development of smart-card-based Conditional Access systems for pay-TV, including
interactive systems and electronic commerce. Responsible for design and
implementation of security features, provided consulting help to developers.
Designed an ASIC generator of hard-to-analyze and hard-to-emulate functions. As
Chief Architect of Content Protection, defined NDS strategy and lead efforts
in this area. Represented NDS and prepared proposals for Copy Protection
Technical Working Group (CPTWG), Digital Audio and Video International Council (DAVIC)
and MPEG-4. In DAVIC, served as Vice-Chair, and led the Security and Content
Protection work. Performed research in cryptography and computer security;
developed new methods for Asymmetric Message Authentication, Secure Multicast
over the Internet.
1993 -
1995 Technion, Computer Science Department, Haifa, Israel
Postdoctoral Fellow. Research
on distributed fault-tolerant computations and graph algorithms.
1987 -
1993 Boston University, Computer Science Department, Boston, MA
Research Assistant. Research
in the areas of distributed, parallel and fault-tolerant computations, VLSI, and
graph algorithms. Studied modern cryptology and interactive (zero-knowledge)
proofs.
1989 Charles River Analytics,
Cambridge, MA
Summer Scientist. Investigated innovative
approaches to software engineering using new results in theoretical computer
science (in particular, Prof. M. Blum’s theory of program checkers) as a part of
NASA sponsored study of fault-tolerant computations.
1988 Prime Computer Inc.,
Natick, MA
Summer Consultant. Developed UNIX tools
for conversion, parallelization, optimization and testing of large scientific
application packages. Developed partial prototypes for system re-design to
include some learning capabilities. Developed enhancement for an expert system
for financial applications.
1986 -
1993 Boston University,
Boston, MA
Instructor. Taught graduate and undergraduate courses in Algorithms, Data
Structures, Theory of Computation, Theory of Computer Languages, and
Computational Complexity.
1986 Wentworth Institute Of Technology, Boston, MA
Instructor. Taught undergraduate course in Expert Systems.
1983 -
1986 Computervision Corporation,
Bedford, MA
Software Engineer. Designed
and implemented algorithms for 3-D geometric modeling. Developed new tools for
CAD/CAM applications. Developed postprocessors for CAD/CAM NC packages.
EDUCATION: Boston
University,
Boston, MA
PhD in Computer Science, 1993
MS in Computer Science, 1987
Massachusetts
Institute Of Technology, Cambridge, MA
BS
in Physics, 1983
PERSONAL:
US Citizen
REFERENCES: Available upon request
Self-Organizing Computing Media: Communication, Fault-Tolerance and Asynchrony
in Parallel and Distributed Computation,
Ph.D. thesis. Adviser: Prof. L. Levin.
G. Itkis and L. A. Levin.
Power of
Fast VLSI Models is Insensitive to Wires' Thinness,
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.
G. Itkis and L. A. Levin.
Fast and
Lean Self-Stabilizing Asynchronous Protocols,
IEEE Symposium on Foundations of Computer Science (FOCS), 1994. (also
Technion T.R.#829)
We consider asynchronous general topology dynamic networks of identical
nameless processors with worst-case transient faults. Our protocols require only
constant space at each processor and, starting from any faulty configuration,
self-stabilize any computation in (expected) time polynomial in the (unknown)
network diameter. In particular, we present deterministic breadth-first forest
and randomized leader election and breadth-first spanning tree self-stabilizing
protocols, and give a robust characterization of the computational power of
distributed networks.
G. Itkis, C. Lin and J. Simon.
Deterministic, Constant Space, Self-Stabilizing Leader Election on Uniform Rings,
International Workshop on Distributed Algorithms
(WDAG), LNS 972, 1995.
A deterministic self-stabilizing protocol (starting from any faulty
configuration) for leader election is presented for uniform bi-directional rings
with an (unknown) prime number of identical nameless processors of constant size
(i.e. independent of the ring size). Randomization is known to be necessary for
rings of non-prime size. Self-stabilizing leader election on unidirectional
rings requires processors of logarithmic size.
S. Even, G.
Itkis and S. Rajsbaum.
On Mixed Connectivity Certificates,
Journal of
Theoretical Computer Science
203(2), pp:253-269, 1998.
Also appears in
Proceedings of the Third European Symposium on Algorithms (ESA,
keynote address paper),
LNS 979, pp:1-16, Springer-Verlag, 1995.
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, I.
Newman and A. Schuster.
Broadcasting on a Budget in the Multi-Service Communication Model,
International Conference on High Performance Computing (HiPC), 1998.
In this paper we introduce the multi-service model of network
communication. This model attempts to capture recent communication
technology trends, such as some aspects of quality-of-service and their
relation to the emerging technology of automatic pricing, e.g. for Internet
services. The multi-service model differs from related models by taking into
account communication and service activation time, thus restricting
parallelism to better fit reality. We apply this model to heterogeneous
communication environment, which includes different communication media or
connection providers, with respective pricing policies. We give some
analysis and algorithms for optimal dissemination of information, given a
limited budget.
R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and
B. Pinkas.
Multicast Security: A Taxonomy and Some Efficient Constructions, IEEE INFOCOM 1999.
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. Reyzin.
Forward Secure Signatures with Optimal Signing and Verifying,
CRYPTO 2001.
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 cost 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 and Leo 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 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.
Intrusion-Resilient Signatures: Generic Constructions, or Defeating Strong
Adversary with Minimal Assumptions. Conference on Security in
Communication Networks '02 (SCN'02), Amalfi, 2002.
This paper provides the first generic implementation, called
gSiBIR, of the intrusion-resilient signature schemes: it can be based on
any ordinary signature scheme used as a black-box. gSiBIR is also the
first Signer-Base Intrusion-Resilient (SiBIR) scheme secure against
fully-adaptive adversary and does not require a random oracle. Our
construction does require one-way (and cryptographic hash) functions.
We also provide a mechanism extending gSiBIR (or other similar
tree-based constructions) to avoid the limit on the total number of periods
(required by the previous SiBIR and other schemes, including many
forward-secure ones). With this mechanism, gSiBIR becomes a generic
intrusion-resilient signature scheme with no limit on the number of
periods. This mechanism is based on explicit use of prefixless (or
self-delimiting) encodings and can be also applied to the previous generic
forward-secure signature constructions, yielding some modest but noticeable
improvements to their schemes.
Gene Itkis.
Cryptographic Tamper Evidence. 10th ACM Conference on Computer
and Communications Security (CCS), 2003.
This paper proposes 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 stolen 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.
Gene Itkis and Peng Xie.
Generalized Key-Evolving Signature Schemes, or How to Foil an Armed
Adversary. International Conference on Applied Cryptography
and Network Security (ACNS), 2003.
Key exposures, known or inconspicuous, are a real security threat. Recovery
mechanisms from such exposures are required. For digital signatures such a
recovery should ideally --and when possible-- include invalidation of the
signatures issued with the compromised keys. We present new signature
schemes with such recovery capabilities.
We consider two models for key exposures: full and partial reveal. In the
first, a key exposure reveals all the secrets currently existing in
the system. This model is suitable for the pessimistic inconspicuous
exposures scenario. The partial reveal model permits the signer to conceal
some information under exposure: e.g., under coercive exposures the signer
is able to reveal a ``fake'' secret key.
We propose a definition of generalized key-evolving signature scheme,
which unifies security against the coercive and inconspicuous key exposures
with forward-security (these two problems were previously considered
separately).
The new models also help us address repudiation problems inherent in the
monotone signatures, and achieve performance improvements.
Nenad Dedic, Gene Itkis,
Leonid Reyzin, and Scott Russell.
Upper and Lower Bounds on Black-Box Steganography. Theory of
Cryptography Conference, 2005.
We study the limitations of steganography when the sender is not using any
properties of the underlying channel beyond its entropy and the ability to
sample from it. On the negative side, we show that the number of samples the
sender must obtain from the channel is exponential in the rate of the
stegosystem. On the positive side, we present the first secret-key
stegosystem that essentially matches this lower bound regardless of the
entropy of the underlying channel. Furthermore, for high-entropy channels,
we present the first secret-key stegosystem that matches this lower bound
statelessly (i.e., without requiring synchronized state between the sender
and receiver).
Gene Itkis, Robert McNerney Jr., and
Scott Russell.
Intrusion-Resilient Secure Channels,
Applied Cryptography and Network Security (ACNS), 2005 (more complete
version appears in Cryptology ePrint Archive,
Report 2005/114).
This paper defines a new secure communication primitive called an
Intrusion-Resilient Channel (IRC) whose goal is to provide maximum
damage containment and recovery capability from security compromises. We
construct such channels using (as a black box) existing public key
cryptosystems via an intuitive generic construction. The simplicity of the
construction belies the significant technical challenges encountered in
proving it secure.
We also outline a general strategy for increasing security of two-party
protocols: given a protocol proven secure against adversaries with
restricted access to the protocol messages, we use IRC to remove some of
these restrictions on the adversaries. Once again, our intuitive approach
turns out to be non-trivial to prove. We use this strategy to improve
security of a previous intrusion-resilient signature scheme.
Gene Itkis.
Forward Security: Adaptive Cryptography – Time Evolution.
Invited chapter for the Handbook of Information Security, John Wiley and Sons,
2006.
We survey the development of forward security and relate it to other
concepts and trends in modern cryptography.
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 proposed to
address this weakness: they ensure that past signatures remain secure even
if the current secret key is leaked. Similarly for the case of ordinary
encryption, an adversary that successfully exposed a secret key is typically
able to expose even the old messages sent long before exposure.
Forward-secure encryption ensures that the past messages are protected even
if the current secret key is exposed.
We discuss forward security as a special case of key-evolving cryptography.
John Byers, Mei Chin Cheng, Jeffrey Considine,
Gene Itkis, Alex Yeung.
Securing Bulk Content Almost for Free.
Computer
Communications, special issue on Internet Security 29(3), pp:280-290, 2006.
Content providers often consider the costs of security to be greater than
the losses they might incur without it; many view "casual piracy" as their
main concern. Our goal is to provide a low cost defense against such attacks
while maintaining rigorous security guarantees.
Our defense is integrated with and leverages fast forward error-correcting
codes, such as Tornado codes, which are widely used to facilitate reliable
delivery of rich content. We tune one such family of codes -- while
preserving their original desirable properties -- to guarantee that none of
the original content can be recovered whenever a key subset of encoded
packets is missing. Ultimately we encrypt only these key codewords (only 4%
of all transmissions), making the security overhead negligible.
Gene Itkis and Leonid A. Levin. Flat Holonomies on Automata Networks. An invited paper, International Symposium on Theoretical Aspects of Computer Science (STACS), pp:23-49, 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.
Miscellaneous project reports and white papers