PKC 2006

April 24-26, 2006
New York City, USA

iacr logo

front page

call for papers

local information




golden sponsors

eads logo

morgan stanley logo

silver sponsors






pkc 2006 logo


All talks are in Davis Auditorium on the 4th floor (campus level) of the Schapiro CEPSR Building at Columbia University.

Sunday April 23, 2006
  No activities planned.
Monday April 24, 2006
  8:00am-8:50 Breakfast and Registration
  8:50am-9:00 Opening Remarks
Moti Yung, PKC 2006 Program Chair

  Session 1: Cryptanalysis and protocol Weaknesses Chair: Moti Yung
  9:00am-9:25 New Attacks on RSA with Small Secret CRT-Exponents
Daniel Bleichenbacher and Alex May (TU Darmstadt)
  9:25am-9:50 An Attack on a Modified Niederreiter Encryption Scheme
Christian Wieschebrink (Federal Office for Information Security (BSI))
  9:50am-10:15 Cryptanalysis of an Efficient Proof of Knowledge of Discrete Logarithm
Sébastien Kunz-Jacques and Gwenaëlle Martinet and Guillaume Poupard and Jacques Stern (DCSSI Crypto lab and ENS)
  10:15am-10:45 Morning Break
  Session 2: Distributed Crypto-Computing Chair: Juan Garay
  10:45am-11:10 Efficient Polynomial Operations in the Shared-Coefficients Setting
Payman Mohassel and Matthew Franklin (Department of Computer Science, University of California, Davis)
  11:10am-11:35 Generic On-line/Off-line Threshold Signatures
Chris Crutchfield and David Molnar and David Turner and David Wagner (UC Berkeley)
11:35am-12:00 Linear Integer Secret Sharing and Distributed Exponentiation
Ivan Damgard and Rune Thorbek (BRICS, Aarhus University)
  12:00pm-1:30 Lunch break
  Session 3: Encryption Methods Chair: Ron Steinfeld
  1:30pm-1:55 Encoding-Free ElGamal Encryption Without Random Oracles
Benoît Chevallier-Mames, Pascal Paillier, David Pointcheval (Gemplus, ENS)
  1:55pm-2:20 Parallel Key-Insulated Public Key Encryption
Goichiro Hanoaka and Yumiko Hanaoka and Hideki Imai (AIST and NTT DoCoMo and U. of Tokyo)
  2:20pm-2:45 Provably Secure Steganography with Imperfect Sampling
Anna Lysyanskaya and Mira Meyerovich (Brown University)
  2:45pm-3:05 Afternoon Break
  Session 4: Cryptographic Hash and Applications Chair: Y. Lisa Yin
  3:05pm-3:30 Collision-resistant no more: Hash-and-sign paradigm revisited
Ilya Mironov (Microsoft Research)
  3:30pm-3:55 Higher Order Universal One-Way Hash Functions from the Subset Sum Assumption
Ron Steinfeld and Josef Pieprzyk and Huaxiong Wang (Macquarie
  5:30pm-7:00 INDEPENDENT CAMPUS EVENT: Talk by Nobel Laureate Robert John Aumann organized by the Fu Foundation School of Engineering and Applied Sciences. This event requires an independent RSVP and approval via email; participation is not guaranteed in advance. PKC attendees can designate themselves as visitors of the Columbia Computer Science department.
Tuesday April 25, 2006
  8:30am-9:00 Breakfast and Registration
  Session 5: Number Theory Algorithms Chair: Nick Howgrave-Graham
  9:00am-9:25 An Algorithm to Solve the Discrete Logarithm Problem with the Number Field Sieve
 An Commeine (Katholieke Universiteit Leuven) and Igor Semaev
(Universitetet Bergen)
  9:25am-9:50 Efficient Scalar Multiplication by Isogeny Decompositions
C. Doche (Macquarie University) and T. Icart (Ecole Polytechnique), and D. R. Kohel (University of Sydney).
  9:50am-10:15 Curve25519: new Diffie-Hellman speed records
Daniel J. Bernstein (University of Illinois at Chicago)
  10:15am-10:45 Morning Break
  Session 6: Pairing-based Cryptography Chair: Masayuki Abe
  10:45am-11:10 Strongly Unforgeable Signatures Based on Computational Diffie-Hellman
Dan Boneh and Emily Shen and Brent Waters (Stanford University and SRI)
  11:10am-11:35 Generalization of the Selective-ID Security Model for HIBE Protocols
Sanjit Chatterjee and Palash Sarkar (Indian Statistical Institute and Indian
Statistical Institute)
11:35am-12:00 Identity-Based Aggregate Signatures
Craig Gentry and Zulfikar Ramzan (Stanford University and DoCoMo USA Labs)
12:00pm-12:25 On the Limitations of the Spread of a IBE-to-PKE Transformation
Eike Kiltz (CWI, Amsterdam)
12:25pm-2:00 Lunch Break
  Session 7: Cryptosystems Design and Analysis Chair: Alexander May
  2:00pm-2:25 Inoculating Multivariate Schemes Against Differential Attacks
Jintai Ding and Jason E. Gower (University of Cincinnati)
  2:25pm-2:50 Random subgroups of braid groups: cryptanalysis of a braid group based cryptographic protocol
Alexei Myasnikov and Vladimir Shpilrain and Alexander Ushakov (McGill University, The City College of New York, Stevens Institute of Technology)
  2:50pm-3:15 High-order Attacks against the Exponent Splitting Protection
Frederic Muller and Frederic Valette (DCSSI Crypto Lab and CELAR)
  3:15pm-3:45 Afternoon Break
  Session 8: Signature and Identification Chair: Wen-Guey Tzeng
  3:45am-4:15 New Online/Offline Signature Schemes Without Random Oracles
Kaoru Kurosawa and Katja Schmidt-Samoa (Ibaraki University, Japan and Darmstadt, University of Technology, Germany)
  4:15pm-4:40 Anonymous Signature Schemes
Guomin Yang and Duncan S. Wong and Xiaotie Deng (City University of Hong Kong) and Huaxiong Wang (Macquarie University)
  4:40pm-5:05 The Power of Identification Schemes
Kaoru Kurosawa and Swee-Huay Heng (Ibaraki University and Multimedia University)
Wednesday April 26, 2006
  8:30am-9:00 Breakfast and Registration
  Session 9: Authentication and Key Establishment Chair: Susanne Wetzel
  9:00am-9:25 Security Analysis of KEA Authenticated Key Exchange Protocol
Kristin Lauter and Anton Mityagin (Microsoft Research and University of California, San Diego)
  9:25am-9:50 SAS-Based Authenticated Key Agreement
Sylvain Pasini and Serge Vaudenay (EPFL)
  9:50am-10:15 The Twist-Augmented Technique for Key Exchange
Olivier Chevassut and Pierre-Alain Fouque and Pierrick Gaudry and David Pointcheval (Lawrence Berkeley National Lab. and Ecole normale superieure, and INRIA)
10:15am-10:40 Password-based Group Key Exchange in a Constant Number of Rounds
Michel Abdalla and Emmanuel Bresson and Olivier Chevassut and David Pointcheval (Ecole normale superieure and CELAR and Lawrence Berkeley National Laboratory and Ecole normale superieure)
  10:40am-11:10 Morning Break
  Session 10: Multi-Party Computation Chair: Rosario Gennaro
  11:10am-11:35 Conditional Oblivious Cast
Cheng-Kang Chu and Wen-Guey Tzeng (National Chiao Tung University)
  11:35am-12:00 Efficiency Tradeoffs for Malicious Two-Party Computation
Payman Mohassel and Matthew Franklin (University of California, Davis)
12:00pm-1:30 Lunch Break
Session 11: Invited Talk Chair: Tal Malkin
1:30pm-2:30 "Cryptography and the Internet: Where It Is, Where It Isn't, Where it Should Be --- and Why It Isn't There"
Steven M. Bellovin (Columbia University)
2:30pm-3:00 Afternoon Break
  Session 12: PKI Techniques Chair: Pierre-Alain Fouque
  3:00pm-3:25 On Constructing Certificateless Cryptosystems from Identity Based

Benoit Libert and Jean-Jacques Quisquater (UCL, Louvain-la-Neuve)
  3:25pm-3:50 Building Better Signcryption Schemes with Tag-KEMs
Tor E. Bjorstad (University of Bergen, Norway) and Alexander W. Dent (Royal Holloway, University of London.)
  3:50pm-4:15 Security-Mediated Certificateless Cryptography
Sherman S.M. Chow and Colin Boyd and Juan Manuel Gonzalez Nieto (New York University and Queensland University of Technology)
4:15pm-4:40 k-times Anonymous Authentication with a Constant Proving Cost
Isamu Teranishi and Kazue Sako (NEC)
  4:40pm Conference Adjourns