Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II

by Michele Bugliesi (Editor), Bart Preneel (Editor), Vladimiro Sassone (Editor), Ingo Wegener (Editor)

Overview

The two-volume set LNCS 4051 and LNCS 4052 constitutes the refereed proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, held in Venice, Italy, July 2006. In all, these volumes present more 100 papers and lectures. Volume II (4052) presents 2 invited papers and 2 additional conference tracks with 24 papers each, focusing on algorithms, automata, complexity and games as well as on security and cryptography foundation.

Product Details

ISBN-13:	9783540359074
Publisher:	Springer Berlin Heidelberg
Publication date:	07/28/2006
Series:	Lecture Notes in Computer Science , #4052
Edition description:	2006
Pages:	612
Product dimensions:	6.10(w) x 9.25(h) x 0.05(d)

Table of Contents

Invited Papers.- Differential Privacy.- The One Way to Quantum Computation.- Zero-Knowledge and Signatures.- Efficient Zero Knowledge on the Internet.- Independent Zero-Knowledge Sets.- An Efficient Compiler from—-Prool to 2-Move Deniable Zero-Knowledge.- New Extensions of Pairing-Based Signatures into Universal Designated Verifier Signatures.- Cryptographic Prools.- Corrupting One vs. Corrupting Many: The Case of Broadcast and Multicast Encryption.- Cryptographically Sound Implementations for Communicating Processes.- A Dolev-Yao-Based Definition of Abuse-Free Prools.- Secrecy and Prool Analysis.- Preserving Secrecy Under Refinement.- Quantifying Information Leakage in Process Calculi.- Symbolic Prool Analysis in Presence of a Homomorphism Operator and Exclusive Or.- Cryptographic Primitives.- Generalized Compact Knapsacks Are Collision Resistant.- An Efficient Provable Distinguisher for HFE.- A Tight Bound for EMAC.- Constructing Single- and Multi-output Boolean Functions with Maximal Algebraic Immunity.- Bounded Storage and Quantum Models.- On Everlasting Security in the Hybrid Bounded Storage Model.- On the Impossibility of Extracting Classical Randomness Using a Quantum Computer.- Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding.- Foundations.- Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions.- Hardness of Distinguishing the MSB or LSB of Secret Keys in Diffie-Hellman Schemes.- A Probabilistic Hoare-style Logic for Game-Based Cryptographic Proofs.- Multi-party Prools.- Generic Construction of Hybrid Public Key Traitor Tracing with Full-Public-Traceability.- An Adaptively Secure Mix-Net Without Erasures.- Multipartite Secret Sharing by Bivariate Interpolation.- Identity-Based Encryption GoneWild.- Games.- Deterministic Priority Mean-Payoff Games as Limits of Discounted Games.- Recursive Concurrent Shastic Games.- Half-Positional Determinacy of Infinite Games.- A Game-Theoretic Approach to Deciding Higher-Order Matching.- Semantics.- Descriptive and Relative Completeness of Logics for Higher-Order Functions.- Interpreting Polymorphic FPC into Domain Theoretic Models of Parametric Polymorphism.- Typed GoI for Exponentials.- Commutative Locative Quantifiers for Multiplicative Linear Logic.- Automata I.- The Wadge Hierarchy of Deterministic Tree Languages.- Timed Petri Nets and Timed Automata: On the Discriminating Power of Zeno Sequences.- On Complexity of Grammars Related to the Safety Problem.- Models.- Jumbo—-Calculus.-—-RBAC: Programming with Role-Based Access Control.- Communication of Two Stacks and Rewriting.- Equations.- On the Axiomatizability of Priority.- A Finite Equational Base for CCS with Left Merge and Communication Merge.- Theories of HNN-Extensions and Amalgamated Products.- On Intersection Problems for Polynomially Generated Sets.- Logics.- Invisible Safety of Distributed Prools.- The Complexity of Enriched—-Calculi.- Interpreting Tree-to-Tree Queries.- Automata II.- Constructing Exponential-Size Deterministic Zielonka Automata.- Flat Parametric Counter Automata.- Lower Bounds for Complementation of—-Automata Via the Full Automata Technique.