Public Key Cryptography -- PKC 2011
14th International Conference on Practice and Theory in Public Key Cryptography, Taormina, Italy, March 6-9, 2011, Proceedings
Published on 28. February 2011
XIII, 495 pages
978-3-642-19379-8 (ISBN)
Description
This book constitutes the thoroughly refereed proceedings of the 14th International Conference on Practice and Theory in Public Key Cryptography, PKC 2011, held in Taormina, Italy, in March 2011.
The 28 papers presented were carefully reviewed and selected from 103 submissions. The book also contains one invited talk. The papers are grouped in topical sections on signatures, attribute based encryption, number theory, protocols, chosen-ciphertext security, encryption, zero-knowledge, and cryptanalysis.
More details
Other editions
Additional editions
Dario Catalano | Nelly Fazio | Rosario Gennaro
Public Key Cryptography -- PKC 2011
14th International Conference on Practice and Theory in Public Key Cryptography, Taormina, Italy, March 6-9, 2011, Proceedings
Book
02/2011
1st Edition
Springer
€53.49
Shipment within 5-7 days
Content
- Title
- Preface
- Table of Contents
- Signatures I
- Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures
- Introduction
- Linearly Homomorphic Signatures
- Background on Lattices
- New Tools
- A ``One-More'' SIS Problem
- Tight Bounds on the Length of Gaussian Samples
- Removing Linear Independence from the k-SIS Problem
- Linear Combinations of Discrete Gaussians
- A Linearly Homomorphic Signature Scheme over F2
- k-Time GPV Signatures without Random Oracles
- Further Directions
- References
- Homomorphic Network Coding Signatures in the Standard Model
- Introduction
- Background and Definitions
- Network Coding
- Definitions
- Complexity Assumptions
- Homomorphic NCS Scheme in the Standard Model
- Construction
- Security Proof
- References
- Efficient Attribute-Based Signatures for Non-monotone Predicates in the Standard Model
- Introduction
- Background
- Our Results
- Related Works
- Notations
- Preliminaries
- Dual Pairing Vector Spaces by Direct Product of Symmetric Pairing Groups
- Decisional Linear (DLIN) Assumption
- Collision Resistant (CR) Hash Functions
- ABS for Non-monotone Predicates
- Span Programs and Non-monotone Access Structures
- Definitions and Security of ABS
- Proposed ABS Scheme
- Construction Ideas
- Construction
- Security
- Performance
- Multi-Authority ABS (MA-ABS)
- Definitions and Security of MA-ABS
- Construction
- Security
- References
- Attribute Based Encryption
- Ciphertext-Policy Attribute-Based Encryption: An Expressive, Efficient, and Provably Secure Realization
- Introduction
- Related Work
- Background
- Access Structures
- Linear Secret Sharing Schemes
- Ciphertext-Policy ABE
- Bilinear Maps
- Our Most Efficient Construction
- Proof
- Constructions from Weaker Assumptions
- Bilinear Diffie-Hellman Construction
- Proof
- Large Universe of Attributes
- References
- Generic Constructions for Chosen-Ciphertext Secure Attribute Based Encryption
- Introduction
- Definitions
- Syntax and Security Definition for Functional Encryption
- Definitions for Attribute-Based Encryption
- Two Properties: Verifiability and Delegatability
- General Constructions of CCA-Secure ABE
- Security of Our Constructions from Verifiability
- Security of Our Construction from Delegatability
- Applications to Existing Schemes
- The Case of ABE by Lewko et al.
- Summary for Applications to Existing Schemes
- Remark on Verifiability
- References
- Expressive Key-Policy Attribute-Based Encryption with Constant-Size Ciphertexts
- Introduction
- Background and Definitions
- Syntax and Security Definition for Functional Encryption
- Key-Policy Attribute-Based Encryption
- Identity-Based Broadcast Encryption and Revocation Scheme
- Complexity Assumptions
- Monotonic KP-ABE with Short Ciphertexts
- Linear ID-Based Broadcast Encryption Template
- Generic Conversion from Linear IBBE to KP-ABE
- IBBE Instantiation with Short Ciphertexts
- Revocation Scheme with Very Short Ciphertexts
- Non-monotonic KP-ABE with Short Ciphertexts
- Comparisons
- Concluding Remarks
- References
- Number Theory
- Faster and Lower Memory Scalar Multiplication on Supersingular Curves in Characteristic Three
- Introduction
- Digit Sets and the Structure of the Unit Group
- Scalar Multiplication Using a Factored Digit Set
- Group Operations on the Curve
- Explicit Formulae for (1 + µt) in Affine Coordinates
- Projective Coordinates
- Jacobian Coordinates
- Modified Jacobian Coordinates
- Costs of Operations in Different Systems
- Further Improvements to Scalar Multiplication
- Conclusions and Final Remarks
- References
- On the Correct Use of the Negation Map in the Pollard rho Method
- Introduction
- Review of Pollard's rho Method
- How to Use Negation in Pollard's rho Method
- Low-Cost Arithmetic in Z/(2^128 - 3)
- Fast Iterations on the PlayStation 3
- Experimental Results and Evaluation
- References
- Cryptanalysis of the RSA Subgroup Assumption from TCC 2005
- Introduction
- The New Attack
- Attack Complexity
- Algorithmic Details
- Implementation
- Conclusion
- References
- Protocols
- (If) Size Matters: Size-Hiding Private Set Intersection
- Introduction
- Why Size Matters?
- Size Hiding with Current Tools?
- Roadmap and Contributions
- Related Work
- Definitions
- SHI-PSI Construction
- Protocol Description
- Reducing Client Complexity
- Extensions
- Linear-Complexity SHI-PSI
- SHI-PSI with Data Transfer
- Cost of Hiding Size
- Conclusions and Future Work
- References
- Sub-linear, Secure Comparison with Two Non-colluding Parties
- Introduction
- Related Work
- Contribution
- An Overview of This Paper
- Primitives and Notation
- The Arithmetic Black-Box
- Required Extensions of the ABB
- Realizing the Arithmetic Black-Box
- Passively Secure, Two-Party Paillier-Based Arithmetic
- The Multiparty Case
- Active Security
- Secure Equality Testing
- The log-Rounds Protocol
- The Constant-Rounds Protocol
- Variations
- Concluding Remarks
- References
- Oblivious Transfer with Hidden Access Control Policies
- Introduction
- Our Contribution
- Related Work
- Randomizing and Extending Groth-Sahai Proofs
- Our Construction
- Issuer Setup
- Issuing Credentials
- Revoking Credentials
- Database Setup
- Accessing a Record
- Security Analysis
- Conclusion
- References
- Chosen-Ciphertext Security
- Chosen Ciphertext Secure Encryption under Factoring Assumption Revisited
- Introduction
- Contributions
- Preliminaries
- Key Encapsulation Mechanism
- Target Collision Resistant Hash Function
- Semi-smooth Subgroup
- Signed Quadratic Residues
- Some Lemmas
- The Instantiation of HK09 over Semi-smooth Subgroup
- Scheme Description
- Security Proof
- Scheme Based on ElGamal Encryption over Composite Modulus
- Scheme Description
- Security Proof
- References
- Chameleon All-But-One TDFs and Their Application to Chosen-Ciphertext Security
- Introduction
- Our Contributions
- Related Work
- Organization
- Preliminaries
- Hashing
- Extracting Randomness
- Public Key Encryption
- Lossy Trapdoor Functions
- Chameleon ABO-TDFs and Its Constructions
- Chameleon ABO-TDFs
- Generic Construction
- A Concrete Construction
- Definition of OT with Hidden Access Control Policies
- Setting and Procedures
- Security Definitions
- CCA-Secure PKE Scheme
- Conclusions
- References
- Parallel Decryption Queries in Bounded Chosen Ciphertext Attacks
- Introduction
- Our Contributions
- Preliminaries
- Extending Bounded CCA: Mixed CCA Security
- Definition of Mixed CCA Security
- General Properties of Mixed CCA Security
- Relations among Mixed CCA Security Notions
- "is-Simulatable-by" Relation for Query Sequences
- Separation Results
- Implication Results
- Necessary and Sufficient Conditions for Implication/Separation
- Feasibility Results from IND-CPA Secure PKE Schemes
- Open Problems
- References
- Secure Blind Decryption
- Introduction
- Related Work
- Intuition
- Technical Preliminaries
- Bilinear Groups and Cryptographic Assumptions
- Proofs of Knowledge
- Linear Encryption
- A One-Time F-Signature on Multiblock Messages
- Definitions
- Constructions
- Extensions
- Applications
- References
- Invited Talk
- New Developments in Leakage-Resilient Cryptography
- Encryption
- On the Security of a Bidirectional Proxy Re-encryption Scheme from PKC 2010
- Introduction
- Preliminaries
- All-but-One Trapdoor Function
- Re-applicable (n,k)-Lossy Trapdoor Functions
- Realization of Re-applicable LTDFs
- Bidirectional Multi-hop PRE
- Review of the Matsuda-Nishimaki-Tanaka PRE Scheme
- Security Analysis
- Discussions and Conclusion
- References
- Fully Secure Accountable-Authority Identity-Based Encryption
- Introduction
- Our Contributions
- Preliminaries
- Bilinear Maps
- Security Assumption
- Fully-Simulatable Oblivious Transfer
- Accountable Authority IBE (A-IBE)
- Security Requirements
- Preliminary Reduction
- Dummy Identity-Based Encryption
- D-IBE Implies Dishonest-User Security
- Tracing Algorithm
- Running in Parallel for PKG Security
- Tracing Algorithm for the Parallel Scheme
- A Modification for IND-ID-CPA Security
- A Dummy-IBE Scheme
- Proof of Security
- Conclusion
- References
- One-Pass HMQV and Asymmetric Key-Wrapping
- Introduction
- Security Model for One-Pass Key-Exchange Protocols
- The Basic HOMQV Protocol
- Notes on Security
- Using HOMQV for Encryption and Key-Wrapping
- Security Analysis of HOMQV
- XCR Signatures and Gap-DH
- Proof of Basic Security
- Resilience of HOMQV to Disclosure of Ephemeral Exponents
- Sender's Forward Secrecy
- Extensions in the Interactive Setting
- References
- Signatures II
- Linear Recurring Sequences for the UOV Key Generation
- Introduction
- The (Unbalanced) Oil and Vinegar Signature Scheme
- The Approach of PB10
- Preliminaries
- Linear Recurring Sequences (LRS)
- Golomb's Randomness Postulates Go67
- Description of the Scheme
- Construction
- The Scheme
- Choice of the Parameter L
- General Remarks
- Choice of L for Smaller Fields
- Security
- Direct Attacks
- UOV-Reconciliation
- Rank Attacks
- UOV Attack KP99
- Summary
- Parameters
- Conclusion
- References
- On the Impossibility of Instantiating PSS in the Standard Model
- Introduction
- Our Results
- Overview of Our Technique
- Previous Results
- Differences from Dodis et al's Crypto'05 Paper DodisOP05
- Preliminaries
- Notations
- Trapdoor Permutations (TDPs)
- Hard Games
- Ideal Trapdoor Permutations
- Lossy Trapdoor Permutations(LTDPs)
- Signature Schemes
- Security of a Signature Scheme
- Probabilistic Signature Scheme(PSS)
- No Blackbox Reduction from One Way Trapdoor Permutations
- No Blackbox Reduction from an Ideal Trapdoor Permutation
- No Reduction from Lossy Trapdoor Permutations
- No Reduction from Hard Games with Inversion
- Conclusion
- References
- On-line Non-transferable Signatures Revisited
- Introduction
- On-line Non-transferable Signatures
- Security Model
- Construction of an ONS Scheme
- Core Confirmer Signature Scheme
- On-line Non-transferable Protocols
- Combined Scheme
- Concrete Instantiation
- Comparison
- References
- Zero-Knowledge
- Round-Efficient Sub-linear Zero-Knowledge Arguments for Linear Algebra
- Introduction
- Preliminaries
- SHVZK Arguments for Equations with Vectors and Matrices
- SHVZK Arguments for z=i=1mxiYi
- SHVZK Arguments for z=i=1mxi*yi
- General Transformation for Reducing Rounds of SHVZK Arguments
- Applying Transformation to SHVZK Arguments for Linear Algebra
- Application I: SHVZK Arguments for z=i=1mxi Yi
- Application II: SHVZK Arguments for z=i=1mxi*yi
- Comparison
- References
- Signatures on Randomizable Ciphertexts
- Introduction
- Definitions
- Notations for Signature and Encryption
- Signatures on Ciphertexts
- Signatures on Randomizable Ciphertexts
- Extractable Signatures on Randomizable Ciphertexts
- Strong Extractability
- A First Instantiation
- Assumptions
- Basic Primitives
- Waters Signature on Linear Ciphertexts
- An Efficient Instantiation
- Revisited Waters Signature
- Signatures on Encrypted Messages
- Applications
- Non-interactive Receipt-Free E-voting
- Blind Signatures and Variants
- References
- Revocation for Delegatable Anonymous Credentials
- Introduction
- Background
- Homomorphic Proofs
- Formalization
- GS Homomorphic Proofs
- Comparison with the DHLW Homomorphic NIZK
- Accumulator with Delegatable NM Proofs - ADNMP
- An ADNMP Scheme
- NM Proof
- NM Proofs Are Strongly Homomorphic
- Delegating NM Proof
- Revocable Delegatable Anonymous Credentials - RDAC
- Model
- An RDAC Scheme
- Overview
- Description
- References
- Cryptanalysis
- Cryptanalysis of Multivariate and Odd-Characteristic HFE Variants
- Introduction
- Multivariate HFE
- Direct Algebraic Attack
- Original Kipnis-Shamir (KS) Attack
- Improvement and Generalization of KS Attack
- Improving the Univariate Case
- Attacking Multi-HFE
- About Equivalent Keys and Induced Degrees of Freedom
- Complexity Analysis of the Attack
- Recovering the Transformation on the Variables
- Weaknesses of Multi-HFE Relative to the Original HFE
- Multivariate HFE-
- Multivariate HFE with Embedding
- Experimental Results
- Conclusion
- References
- Cryptanalysis of Cryptosystems Based on Non-commutative Skew Polynomials
- Introduction
- General Strategy of the Attack
- The Invertible Case
- The Setting of Our Attack
- The Attack
- Application to Skew Polynomials Cryptosystems
- Skew Polynomials
- Generation of the Scheme
- Commutativity among Skew Polynomials
- Unrolling the Attack
- The Case of Modular Skew Polynomials
- Constructing Modular Skew Polynomial Rings
- The Modified Scheme
- First Remarks
- Attacking the Modular Decomposition
- Beyond the Case of Skew Polynomials?
- References
- Practical Cryptanalysis of the Identification Scheme Based on the Isomorphism of Polynomial with One Secret Problem
- Introduction
- The IP1S Problem
- Patarin's IP1S-Based Identification Scheme
- Cryptanalysis of Quadratic IP1S
- Counting Linearly Independent Equations
- Solving Very Overdefined Quadratic Systems
- Implementation
- Cryptanalysis of Cubic IP1S
- Application to the Linear Inhomogeneous Case
- Implementation and Application to the Other Cases
- An Interesting Failure
- Conclusion
- References
- Author Index
