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

Cynthia Dwork (auth.), Michele Bugliesi, Bart Preneel, Vladimiro Sassone, Ingo Wegener (eds.)3540359079, 9783540359074

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, in July 2006.

This is Volume II (LNCS 4052) comprising 2 invited papers and 2 additional conference tracks with 24 papers each – rigorously selected from numerous submissions – focusing on algorithms, automata, complexity and games as well as on security and cryptography foundation respectively. The papers are organized in topical sections on zero-knowledge and signatures, cryptographic protocols, secrecy and protocol analysis, cryptographic promitives, bounded storage and quantum models, foundations, multi-party protocols, games, semantics, automata, models, equations, and logics.

Volume I (LNCS 4051) presents 61 revised full papers together with 1 invited lecture that were carefully reviewed and selected from 230 submissions. Those papers have a special focus on algorithms, automata, complexity and games and are organized in topical sections on graph theory, quantum computing, randomness, formal languages, approximation algorithms, graph algorithms, algor

---

Table of contents :
Front Matter….Pages –
Differential Privacy….Pages 1-12
The One Way to Quantum Computation….Pages 13-21
Efficient Zero Knowledge on the Internet….Pages 22-33
Independent Zero-Knowledge Sets….Pages 34-45
An Efficient Compiler from Σ-Protocol to 2-Move Deniable Zero-Knowledge….Pages 46-57
New Extensions of Pairing-Based Signatures into Universal Designated Verifier Signatures….Pages 58-69
Corrupting One vs. Corrupting Many: The Case of Broadcast and Multicast Encryption….Pages 70-82
Cryptographically Sound Implementations for Communicating Processes….Pages 83-94
A Dolev-Yao-Based Definition of Abuse-Free Protocols….Pages 95-106
Preserving Secrecy Under Refinement….Pages 107-118
Quantifying Information Leakage in Process Calculi….Pages 119-131
Symbolic Protocol Analysis in Presence of a Homomorphism Operator and Exclusive Or ….Pages 132-143
Generalized Compact Knapsacks Are Collision Resistant….Pages 144-155
An Efficient Provable Distinguisher for HFE….Pages 156-167
A Tight Bound for EMAC….Pages 168-179
Constructing Single- and Multi-output Boolean Functions with Maximal Algebraic Immunity….Pages 180-191
On Everlasting Security in the Hybrid Bounded Storage Model….Pages 192-203
On the Impossibility of Extracting Classical Randomness Using a Quantum Computer….Pages 204-215
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding….Pages 216-227
Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions….Pages 228-239
Hardness of Distinguishing the MSB or LSB of Secret Keys in Diffie-Hellman Schemes….Pages 240-251
A Probabilistic Hoare-style Logic for Game-Based Cryptographic Proofs….Pages 252-263
Generic Construction of Hybrid Public Key Traitor Tracing with Full-Public-Traceability….Pages 264-275
An Adaptively Secure Mix-Net Without Erasures….Pages 276-287
Multipartite Secret Sharing by Bivariate Interpolation….Pages 288-299
Identity-Based Encryption Gone Wild….Pages 300-311
Deterministic Priority Mean-Payoff Games as Limits of Discounted Games….Pages 312-323
Recursive Concurrent Stochastic Games….Pages 324-335
Half-Positional Determinacy of Infinite Games….Pages 336-347
A Game-Theoretic Approach to Deciding Higher-Order Matching….Pages 348-359
Descriptive and Relative Completeness of Logics for Higher-Order Functions….Pages 360-371
Interpreting Polymorphic FPC into Domain Theoretic Models of Parametric Polymorphism….Pages 372-383
Typed GoI for Exponentials….Pages 384-395
Commutative Locative Quantifiers for Multiplicative Linear Logic….Pages 396-407
The Wadge Hierarchy of Deterministic Tree Languages….Pages 408-419
Timed Petri Nets and Timed Automata: On the Discriminating Power of Zeno Sequences….Pages 420-431
On Complexity of Grammars Related to the Safety Problem….Pages 432-443
Jumbo λ -Calculus….Pages 444-455
λ – RBAC : Programming with Role-Based Access Control….Pages 456-467
Communication of Two Stacks and Rewriting….Pages 468-479
On the Axiomatizability of Priority….Pages 480-491
A Finite Equational Base for CCS with Left Merge and Communication Merge….Pages 492-503
Theories of HNN-Extensions and Amalgamated Products….Pages 504-515
On Intersection Problems for Polynomially Generated Sets….Pages 516-527
Invisible Safety of Distributed Protocols….Pages 528-539
The Complexity of Enriched μ -Calculi….Pages 540-551
Interpreting Tree-to-Tree Queries….Pages 552-564
Constructing Exponential-Size Deterministic Zielonka Automata….Pages 565-576
Flat Parametric Counter Automata….Pages 577-588
Lower Bounds for Complementation of ω -Automata Via the Full Automata Technique….Pages 589-600
Back Matter….Pages –