The book in front of you contains the proceedings of SAC 2008, the 15th - nual Workshop on Selected Areas in Cryptography. SAC 2008 took place during August 14-15 at Mount Allison University, Sackville, New Brunswick, Canada. This was the ?rst time that SAC was hosted in New Brunswick, and the second time in an Atlantic Canadian province. Previous SAC workshops were held at Queen's University in Kingston (1994, 1996, 1998, 1999, and 2005), at Carleton University in Ottawa (1995, 1997, 2003), at the University of Waterloo (2000, 2004), at the Fields Institute in Toronto (2001), at Memorial University of N- foundland at St. John's (2002), at Concordia University in Montreal (2006) and at the University of Ottawa (2007). The intent ofthe workshopseriesis to provide a relaxedatmospherein which researchers in cryptography can present and discuss new work on selected areas of current interest. The SAC workshop series has ?rmly established itself as an international forum for intellectual exchange in cryptological research. Theresponsibilityforchoosingthe venueofeachSACworkshopandappoi- ingtheCo-chairslieswiththeSACOrganizingBoard.TheCo-chairsthenchoose the Program Committee in consultation with the Board. Hence, we would like to expressour gratitudeto the SAC OrganizingBoardfor giving usthe mandate to organize SAC 2008, and for their invaluable feedback while assembling the Program Committee.

The 8th International Conference on Ad-Hoc Networks and Wireless (ADHOC-NOW 2009) was held September 22-25, 2009 in Murcia, Spain. Since ADHOCNOW started as a workshop in 2002, it has become a well-established and well-known international conference dedicated to wireless and mobile c- puting. During the last few years it has been held in Toronto, Canada (2002), Montreal, Canada (2003), Vancouver, Canada (2004), Cancun, Mexico (2005), Ottawa, Canada (2006), Morelia, Mexico (2007) and Sophia Antipolis, France (2008). The conference serves as a forum for interesting discussions on ongoing research and new contributions addressing both experimental and theoretical research in the area of ad hoc networks, mesh networks, sensor networks and vehicular networks. In 2009, we recived 92 submissions from 28 di?erent countries around the globe: Algeria, Australia, Brazil, Canada, China, Egypt, Finland, France, G- many, Greece, India, Iran, Ireland, Italy, Japan, Korea, Luxembourg, Malaysia, Mexico,Norway,Poland,Portugal,Serbia,SouthAfrica,Spain,Tunisia,UKand USA. Of the submitted papers, we selected 24 full papers and 10 short papers for publication in the proceedings and presentation in the conference.

These proceedings contain the papers presented at VoteID 2009, the Second - ternationalConferenceonE-votingandIdentity.TheconferencewasheldinL- embourgduring September 7-8,2009, hostedbythe Universityof Luxembourg. VoteID 2009 built on the success of the 2007 edition held in Bochum. Events have moved on dramatically in the intervening two years: at the time of writing, people are in the streets of Tehran protesting against the claimed outcome of the June12thpresidentialelectionin Iran.Banners bearingthe words"Whereis my vote?" bear testimony to the strength of feeling and the need for elections to be trusted. These events show that the search for high-assurance voting is not a purely academic pursuit but one of very real importance. We hope that VoteID 2009 will help contribute to our understanding of the foundations of democracy. TheProgramCommitteeselected11papersforpresentationattheconference out of a total of 24 submissions. Each submission was reviewed by at least four Program Committee members. The EasyChair conference management system proved instrumental in the reviewing process as well as in the preparation of these proceedings. The selected papers cover a wide range of aspects of voting: proposals for high-assurancevotingsystems, evaluationofexistingsystems, assessmentofp- lic response to electronic voting and legal aspects. The program also included a keynote by Mark Ryan.

The Annual (ICGS) International Conference is an established platform in which se- rity, safety and sustainability issues can be examined from several global perspectives through dialogue between academics, students, government representatives, chief executives, security professionals, and research scientists from the United Kingdom and from around the globe. The 2009 two-day conference focused on the challenges of complexity, rapid pace of change and risk/opportunity issues associated with modern products, systems, s- cial events and infrastructures. The importance of adopting systematic and systemic approaches to the assurance of these systems was emphasized within a special stream focused on strategic frameworks, architectures and human factors. The conference provided an opportunity for systems scientists, assurance researchers, owners, ope- tors and maintainers of large, complex and advanced systems and infrastructures to update their knowledge with the state of best practice in these challenging domains while networking with the leading researchers and solution providers. ICGS3 2009 received paper submissions from more than 20 different countries around the world. Only 28 papers were selected and were presented as full papers. The program also included three keynote lectures by leading researchers, security professionals and government representatives. June 2009 Hamid Jahankhani Ali Hessami Feng Hsu

This book constitutes the refereed proceedings of the Fourth International Conference on Rough Sets and Knowledge Technology, RSKT 2009, held in Gold Coast, Australia, in July 2009. The 85 revised full papers presented together with 3 keynote papers and 2 special sessions were carefully reviewed and selected from 229 submissions. The papers are organized in topical sections on rough sets and computing, rough sets and data reduction, data mining and knowledge discovery, granular computing and cognitive computing, fuzzy sets and computing, knowledge technology and intelligent systems, computational intelligence and applications, image processing and understanding, and formal concept analysis.

This book constitutes the refereed proceedings of the 18th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-18, held in Tarragona, Spain, in June 2009.

The 22 revised full papers presented together with 7 extended abstracts were carefully reviewed and selected from 50 submissions. Among the subjects addressed are block codes, including list-decoding algorithms; algebra and codes: rings, fields, algebraic geometry codes; algebra: rings and fields, polynomials, permutations, lattices; cryptography: cryptanalysis and complexity; computational algebra: algebraic algorithms and transforms; sequences and boolean functions.

It is commonly assumed that computers process information. But what is inf- mation? In a technical, important, but nevertheless rather narrow sense, Sh- non'sinformationtheorygivesa?rstanswertothisquestion.Thistheoryfocuses on measuring the information content of a message. Essentially this measure is the reduction of the uncertainty obtained by receiving a message. The unc- tainty of a situation of ignorance in turn is measured by entropy. This theory hashad an immense impact on the technologyof information storage,data c- pression, information transmission and coding and still is a very active domain of research. Shannon's theory has also attractedmuch interest in a more philosophic look at information, although it was readily remarked that it is only a "syntactic" theory of information and neglects "semantic" issues. Several attempts have been made in philosophy to give information theory a semantic ?avor, but still mostly based on or at least linked to Shannon's theory. Approaches to semantic informationtheoryalsoveryoftenmakeuseofformallogic.Thereby,information is linked to reasoning, deduction and inference, as well as to decision making. Further, entropy and related measure were soon found to have important connotations with regard to statistical inference. Surely, statistical data and observation represent information, information about unknown, hidden para- ters. Thus a whole branch of statistics developed around concepts of Shannon's information theory or derived from them. Also some proper measurements - propriate for statistics, like Fisher's information, were proposed.

This book constitutes the proceedings of the Second International Conference on Cryptology in Africa, AFRICACRYPT 2009, held in Gammarth, Tunisia, on June 21-25, 2009.

The 25 papers presented together with one invited talk were carefully reviewed and selected from 70 submissions. The topics covered are hash functions, block ciphers, asymmetric encryption, digital signatures, asymmetric encryption and anonymity, key agreement protocols, cryptographic protocols, efficient implementations, and implementation attacks.

Replication is a topic of interest in the distributed computing, distributed systems, and database communities. Although these communities have traditionally looked at replication from different viewpoints and with different goals (e.g., performance versus fault tolerance), recent developments have led to a convergence of these different goals. The objective of this state-of-the-art survey is not to speculate about the future of replication, but rather to understand the present, to make an assessment of approximately 30 years of research on replication, and to present a comprehensive view of the achievements made during this period of time.

This book is the outcome of the seminar entitled A 30-Year Perspective on Replication, which was held at Monte Verit, Ascona, Switzerland, in November 2007. The book is organized in 13 self-contained chapters written by most of the people who have contributed to developing state-of-the-art replication techniques. It presents a comprehensive view of existing solutions, from a theoretical as well as from a practical point of view. It covers replication of processes/objects and of databases; replication for fault tolerance and replication for performance - benign faults and malicious (Byzantine) faults - thus forming a basis for both professionals and students of distributed computing, distributed systems, and databases.

This book constitutes the thoroughly refereed post-conference proceedings of the 4th International Conference on Information Security and Cryptology, Inscrypt 2008, held in Beijing, China, in December 2008.

The 28 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 183 submissions. The papers are organized in topical sections on digital signature and signcryption schemes, privacy and anonymity, message authentication code and hash function, secure protocols, symmetric cryptography, certificateless cryptography, hardware implementation and side channel attack, wireless network security, public key and identity based cryptography, access control and network security, as well as trusted computing and applications.

This book constitutes the refereed proceedings of the Cryptographers' Track at the RSA Conference 2009, CT-RSA 2009, held in San Francisco, CA, USA in April 2009.

The 31 revised full papers presented were carefully reviewed and selected from 93 submissions. The papers are organized in topical sections on identity-based encryption, protocol analysis, two-party protocols, more than signatures, collisions for hash functions, cryptanalysis, alternative encryption, privacy and anonymity, efficiency improvements, multi-party protocols, security of encryption schemes as well as countermeasures and faults.

It is our pleasure to welcome you to the proceedings of the Second International Symposium on Engineering Secure Software and Systems. This unique event aimed at bringing together researchersfrom softwareen- neering and security engineering, which might help to unite and further develop the two communities in this and future editions. The parallel technical spons- ships from the ACM SIGSAC (the ACM interest group in security) and ACM SIGSOF (the ACM interest group in software engineering) is a clear sign of the importance of this inter-disciplinary research area and its potential. The di?culty of building secure software systems is no longer focused on mastering security technology such as cryptography or access control models. Other important factors include the complexity of modern networked software systems, the unpredictability of practical development life cycles, the intertw- ing of and trade-o? between functionality, security and other qualities, the d- culty of dealing with human factors, and so forth. Over the last years, an entire research domain has been building up around these problems. The conference program included two major keynotes from Any Gordon (Microsoft Research Cambridge) on the practical veri?cation of security pro- cols implementation and Angela Sasse (University College London) on security usability and an interesting blend of research, industry and idea papers.

This book constitutes the refereed proceedings of the 12th International Conference on Practice and Theory in Public-Key Cryptography, PKC 2009, held in Irvine, CA, USA, in March 2009.

The 28 revised full papers presented were carefully reviewed and selected from 112 submissions. The papers are organized in topical sections on number theory, applications and protocols, multi-party protocols, identity-based encryption, signatures, encryption, new cryptosystems and optimizations, as well as group signatures and anonymous credentials.

This book constitutes the refereed proceedings of the 11th International Conference on Information Security and Cryptology, ICISC 2008, held in Seoul, Korea, during December 3-5, 2008.

The 26 revised full papers presented have gone through two rounds of reviewing and improvement and were carefully selected from 131 submissions. The papers are organized in topical sections on public key encryption, key management and secret sharing, privacy and digital rights, digital signature and voting, side channel attack, hash and mac, primitives and foundations, as well as block and stream ciphers.

This book constitutes the refereed proceedings of the 10th International Conference on Cryptology in India, INDOCRYPT 2009, held in New Dehli, India, in December 2009.

The 28 revised full papers were carefully reviewed and selected from 104 submissions. The papers are organized in topical sections on post-quantum cryptology, key agreement protocols, side channel attacks, symmetric cryptology, hash functions, number theoretic cryptology, lightweight cryptology, signature protocols, and multiparty computation.

This book contains the best papers of the Third International Conference on Software and Data Technologies (ICSOFT 2008), held in Porto, Portugal, which was organized by the Institute for Systems and Technologies of Information, Communication and Control (INSTICC), co-sponsored by the Workflow Management Coalition (WfMC), in cooperation with the Interdisciplinary Institute for Collaboration and Research on Enterprise Systems and Technology (IICREST). The purpose of ICSOFT 2008 was to bring together researchers, engineers and practitioners interested in information technology and software development. The conference tracks were "Software Engineering", "Information Systems and Data Management", "Programming Languages", "Distributed and Parallel Systems" and "Knowledge Engineering". Being crucial for the development of information systems, software and data te- nologies encompass a large number of research topics and applications: from imp- mentation-related issues to more abstract theoretical aspects of software engineering; from databases and data-warehouses to management information systems and kno- edge-base systems; next to that, distributed systems, pervasive computing, data qu- ity and other related topics are included in the scope of this conference.

th It is our great pleasure to present in this volume the proceedings of the 6 Inter- tional Workshop on Digital Watermarking (IWDW), which was held in Guangzhou, China, during December 3-5, 2007. The workshop was hosted by the Sun Yat-sen University and sponsored by both the National Science Foundation of China and the Korea Institute of Information Security and Cryptology. Since its birth in the early 1990s, digital watermarking has become a mature e- bling technology for solving security problems associated with multimedia distribution schemes. Digital watermarks are now used in applications such as broadcast monit- ing, movie fingerprinting, digital rights management, and document authentication, to name but a few. Still, many research challenges remain open, among them security and robustness issues, reversibility and authentication. Continuing the tradition of previous workshops, IWDW 2007 also featured-besides papers dealing with digital watermarking-contributions from other related fields, such as steganography, ste- nalysis and digital forensics.

The conference Mathematical Methods in Computer Science (MMICS) was held in the memory of Thomas Beth during December 17-19 in Karlsruhe. The c- ference was meant to re?ect the many interests of Thomas Beth. Even though these interests might seem diverse the mathematical methods employed and - pecially algebra as a language were the common denominator of all his scienti?c achievements. The 12 contributed talks reaching from t-designs to integrated circuits were selected from 30 submissions from 14 countries. The contributed talks were complemented by three invited talks. Teo Mora gave a talk on "Decoding Cyclic Codes: The Cooper Philosophy" embracing the areas of coding theory and symbolic computation. These areas were especially appreciated by Thomas Beth, because they combine algebra and algorithmics. Richard Jozsa lectured about "Embedding Classical into Quantum Compu- tion" in the area of quantum information. Quantum information was a focus of research of Tomas Beth since 1993 when he co-organized one of the e- liest workshops on quantum cryptography in Dagstuhl. Quantum information became his passion in 1994 when the connection between the Fourier transf- mation and breaking the RSA crypto system became apparent via Shor's al- rithm, which can factor integers in polynomial time on a quantum computer. The Fourier transform and cryptography were topics that played an important role in Thomas Beth's research and this connection, once again, justi?ed his broad view on computer science.

MobiSec 2009 was the first ICST conference on security and privacy in mobile information and communication systems. With the the vast area of mobile technology research and application, the intention behind the creation of MobiSec was to make a small, but unique contribution to build a bridge between top-level research and large scale application of novel kinds of information security for mobile devices and communication.

The papers at MobiSec 2009 dealt with a broad variety of subjects ranging from issues of trust in and security of mobile devices and embedded hardware security, over efficient cryptography for resource-restricted platforms, to advanced applications such as wireless sensor networks, user authentication, and privacy in an environment of autonomously communicating objects. With hindsight a leitmotif emerged from these contributions, which corrobarated the idea behind MobiSec; a set of powerful tools have been created in various branches of the security discipline, which await combined application to build trust and security into mobile (that is, all future) networks, autonomous and personal devices, and pervasive applications

This book constitutes the refereed proceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2008, held in Melbourne, Australia, in December 2008.

The 33 revised full papers presented together with the abstract of 1 invited lecture were carefully reviewed and selected from 208 submissions. The papers are organized in topical sections on muliti-party computation, cryptographic protocols, cryptographic hash functions, public-key cryptograhy, lattice-based cryptography, private-key cryptograhy, and analysis of stream ciphers.

This book constitutes the proceedings of the International Conference on Personal Satellite Services (PSATS 2009) in Rome, Italy in March 2009.

The 17 papers papers demonstrate recent advances in Internet applications over satellites, satellites technologies, and future satellite location-based systems.

This volume contains the post-proceedings of the Second International Workshop on Critical Information Infrastructure Security (CRITIS 2007), that was held during October 3-5, 2007 in Benalmadena-Costa (Malaga), Spain, and was hosted by the University of Malaga, Computer Science Department. In response to the 2007 call for papers, 75 papers were submitted. Each paper was reviewed by three members of the Program Committee, on the basis of significance, novelty, technical quality and critical infrastructures relevance of the work reported therein. At the end of the reviewing process, only 29 papers were selected for pres- tation. Revisions were not checked and the authors bear full responsibility for the content of their papers. CRITIS 2007 was very fortunate to have four exceptional invited speakers: Adrian Gheorghe (Old Dominion University, USA), Paulo Verissimo (Universidade de L- boa, Portugal), Donald Dudenhoeffer (Idaho National Labs, USA), and Jacques Bus (European Commission, INFSO Unit "Security"). The four provided a high added value to the quality of the conference with very significant talks on different and int- esting aspects of Critical Information Infrastructures. In 2007, CRITIS demonstrated its outstanding quality in this research area by - cluding ITCIP, which definitively reinforced the workshop. Additionally, the solid involvement of the IEEE community on CIP was a key factor for the success of the event. Moreover, CRITIS received sponsorship from Telecom Italia, JRC of the European Commission, IRRIIS, IFIP, and IABG, to whom we are greatly indebted."

This volumecontainsthe paperspresented atthe 15thString Processingand - formation Retrieval Symposium (SPIRE), held in Melbourne, Australia, during November 10-12, 2008. The papers presented at the symposium were selected from 54 papers s- mitted in response to the Call For Papers. Each submission was reviewed by a minimum of two, and usually three, Program Committee members, who are expertsdrawnfromaroundthe globe. Thecommittee accepted25papers (46%), with the successful authors also covering a broad rangeof continents. The paper "An E?cient Linear Space Algorithm for Consecutive Su?x Alignment Under Edit Distance" by Heikki Hyyr] o was selected for the Best Paper Award, while Dina Sokol was awarded the Best Reviewer Award for excellent contributions to the reviewing process. The program also included two invited talks: David Hawking, chief scientist at the Internet and enterprise search company Funn- back Pty. Ltd. based in Australia; and Gad Landau, from the Department of Computer Science at Haifa University, Israel. SPIRE has its origins in the South American Workshop on String Proce- ing which was ?rst held in 1993. Starting in 1998, the focus of the symposium was broadened to include the area of information retrieval due to the c- mon emphasis on information processing. The ?rst 14 meetings were held in Belo Horizonte, Brazil (1993); Valparaiso, Chile (1995); Recife, Brazil (1996); Valparaiso, Chile (1997); Santa Cruz, Bolivia (1998); Cancun, Mexico (1999); A Corun a, Spain(2000);LagunaSanRafael, Chile(2001);Lisbon, Portugal(2002); Manaus, Brazil (2003); Padova, Italy (2004); Buenos Aires, Argentina (2005); Glasgow, UK (2006); and Santiago, Chile (2007)."

TheWorkshoponTheoryofQuantumComputation, Communication, andCr- tography (TQC) focuses on theoretical aspects of quantum computation, qu- tum communication, and quantum cryptography, which are part of a larger interdisciplinary ?eld that casts information science in a quantum mechanical framework. The third TQC was held from January 30 to February 1, 2008, at the U- versity of Tokyo, Tokyo, Japan. It consisted of invited talks, contributed talks and a poster session. A selection of these contributors were invited to submit a paper to this Lecture Notes in Computer Science (LNCS) proceedings. The ?eld of quantum information processing is rapidly growing in depth and in breadth. TQC is a workshop dedicated to the presentation and discussion of original research. While most research in quantum information is published in a wide range of journals and conference proceedings in computer science, physics, mathematics and other traditional areas of science, there is a growing nicheforhigh-qualityjournalsandproceedingsdedicatedtoresearchinquantum information. TQC is one of the ?rst such conferences or workshops that has decided to publish a selection of the submissions in an o?cial proceedings of the workshop to be published in the LNCS series. We are extremely fortunate to have had the support and advice of our P- gramCommittee(listedhere)andareverygratefulforalltheirhardwork.Wealso appreciatethehelpofthefollowingadditionalreviewers: Jean-ChristianBoileau, Jop Briet, David Feder, Francois Le Gall, Hector Garcia, Tohya Hiroshima, and CaseyMyers. WealsoextendoursincerethankstothelocalOrganizingCommitteeforpulling togetherallthelocalandlogisticalaspectsoftheworkshopsosuccessfully. Lastly, many thanks to NTT for sponsoring TQC 2008, to the University of Tokyo for their generous support, and to Springer for agreeing to publish these proceedings in the LNCS seri

Threedecadesagopublic-keycryptosystemsmadea revolutionarybreakthrough in cryptography. They have developed into an indispensable part of our m- ern communication system. In practical applications RSA, DSA, ECDSA, and similar public key cryptosystems are commonly used. Their security depends on assumptions about the di?culty of certain problems in number theory, such as the Integer Prime Factorization Problem or the Discrete Logarithm Problem. However, in 1994 Peter Shor showed that quantum computers could break any public-key cryptosystembased on these hard number theory problems. This means that if a reasonably powerful quantum computer could be built, it would put essentially all modern communication into peril. In 2001, Isaac Chuang and NeilGershenfeldimplemented Shor'salgorithmona7-qubitquantumcomputer. In 2007 a 16-qubit quantum computer was demonstrated by a start-up company with the prediction that a 512-qubit or even a 1024-qubit quantum computer would become available in 2008. Some physicists predicted that within the next 10 to 20 years quantum computers will be built that are su?ciently powerful to implement Shor's ideas and to break all existing public key schemes. Thus we need to look ahead to a future of quantum computers, and we need to prepare the cryptographic world for that future.