Public Key Cryptography -- PKC 2012
15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012, Proceedings
Published on 19. May 2012
XIV, 734 pages
978-3-642-30057-8 (ISBN)
Description
This book constitutes the refereed proceedings of the 15th International Conference on Practice and Theory in Public Key Cryptography, PKC 2012, held in Darmstadt, Germany, in May 2012. The 41 papers presented were carefully reviewed and selected from 188 submissions. The book also contains one invited talk. The papers are organized in the following topical sections: homomorphic encryption and LWE, signature schemes, code-based and multivariate crypto, public key encryption: special properties, identity-based encryption, public-key encryption: constructions, secure two-party and multi-party computations, key exchange and secure sessions, public-key encryption: relationships, DL, DDH, and more number theory, and beyond ordinary signature schemes.
More details
Other editions
Additional editions
Marc Fischlin | Johannes Buchmann | Mark Manulis
Public Key Cryptography -- PKC 2012
15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012, Proceedings
Book
05/2012
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Homomorphic Encryption and LWE
- Better Bootstrapping in Fully Homomorphic Encryption
- Introduction
- A Simpler Decryption Formula
- Basic Homomorphic Decryption
- Extracting the Top and Bottom Bits
- Packing the Coefficients
- Lower-Degree Bit Extraction
- Homomorphic Decryption with Packed Ciphertexts
- Using SIMD Techniques for Bootstrapping
- Encrypting the qL-Secret-Key
- Step One: Computing Z Homomorphically
- Step Two: Switching to CRT Representation
- Step Three: Extracting the Relevant Bits
- Step Four: Switching Back to Coefficient Representation
- Details of Step Two
- An Alternative Variant
- References
- Polly Cracker, Revisited, Revisited
- Introduction
- The Polly Cracker with Noise Cryptosystem
- Gröbner Bases
- Polly Cracker with Noise
- Homomorphic Properties and Public Key Version
- Security Assumptions
- Relations to LWE and Regev's Scheme
- Security Proofs
- Attack on Low-Dimensional Noise
- Conclusion and Open Problems
- References
- Ring-LWE in Polynomial Rings
- Introduction
- Our Results
- Preliminaries
- The Main Result
- Mapping Z[m] to Z[m]
- Geometry and Error Sampling
- Analysis of , the Reduction Modulo m
- Ring-LWE Encryption Scheme
- Definition
- Security
- Correctness
- Practical Improvements
- References
- On Homomorphic Encryption and Chosen-Ciphertext Security
- Introduction
- Previous Work
- Our Contributions
- Preliminaries
- Notation
- Homomorphic Encryption
- Diverse Group Systems
- Lossy Trapdoor Functions
- Implications of Homomorphic Encryption
- Constructing Lossy Trapdoor Functions
- Constructing Diverse Group Systems
- Conclusion
- References
- Signature Schemes
- Waters Signatures with Optimal Security Reduction
- Introduction
- Technical Overview
- Outline
- Preliminaries
- Digital Signatures
- The Computational Diffie-Hellman Problem
- Waters Signatures
- A Variant of Waters' Signature Scheme
- A Better Bound on the Success Probability of the Simulation
- The Full Simulation
- Lower Tightness Bounds for Re-randomizable Signatures
- Re-randomizable Signatures
- Computational Problems and Reductions
- Lower Tightness Bound for Re-randomizable Signature Schemes
- Reductions That Run F More Than Once
- Waters Signatures are Re-randomizable
- References
- Strong Security from Probabilistic Signature Schemes
- Introduction
- Preliminaries and Notation
- Signature Scheme
- From Weakly to Fully Secure Schemes
- A New Transformation to Weakly Secure Signature Schemes
- Proof of Theorem 2
- A Target Randomness Secure Signature Scheme Based on the RSA Assumption
- Accumulation of Signature Schemes
- Final RSA Signature Scheme
- Comparison with the Hohenberger-Waters Scheme
- References
- Space Efficient Signature Schemes from the RSA Assumption
- Introduction
- Background
- Our Approach
- Preliminaries
- Digital Signature and Its EUF-CMA Security
- Prime Numbers, the RSA-Assumption, and Generalized Birthday Bounds
- Overview of the Idea of Our Constructions
- Our First Scheme
- Basic Idea
- Construction
- Security
- Our Second Scheme
- Our Third Scheme
- Comparison
- References
- The Construction of Ambiguous Optimistic Fair Exchange from Designated Confirmer Signature without Random Oracles
- Introduction
- Our Contributions
- Paper Organization
- Related Work
- Ambiguous Optimistic Fair Exchange
- Definition
- Security Models
- Our Construction of iAOFE
- Security Analysis
- A New Construction of Designated Confirmer Signature
- The Construction
- Non-interactive AOFE
- Comparison
- Conclusion
- References
- Code-Based and Multivariate Crypto
- Efficient Implementation of a CCA2-Secure Variant of McEliece Using Generalized Srivastava Codes
- Introduction
- Code-Based Public-Key Encryption Schemes
- The McEliece Cryptosystem
- The Niederreiter Cryptosystem
- Structured Matrices
- Secure Parameters
- CCA-Secure Schemes
- CCA2 Security Conversions
- Applying Fujisaki-Okamoto to McEliece
- Efficient Implementation
- Conclusions
- References
- Solving Underdetermined Systems of Multivariate Quadratic Equations Revisited
- Introduction
- Related Work
- Achievement and Organization
- Notation
- Transformation of Variables
- How to Determine
- Algorithm of Kipnis-Patarin-Goubin
- Tight Analysis for n=m and Improvement
- Equivalent Solutions S and Their Impact on bj
- Equivalent Solutions
- Our Algorithm in Its Most General Form
- Complexity Analysis
- Odd Cases
- Conclusions and Open Questions
- References
- Public-Key Identification Schemes Based on Multivariate Cubic Polynomials
- Introduction
- Multivariate Cubic Functions
- A 3-Pass Protocol
- A 5-Pass Protocol
- Security and Efficiency
- Security
- Efficiency
- On the Security against Active Attack in Parallel Repetition
- Concluding Remarks
- Conclusion
- References
- Public-Key Cryptography from New Multivariate Quadratic Assumptions
- Introduction
- Preliminary
- Notation
- Public-Key Encryption Schemes for Bits
- The Assumption
- Construction of a Public-Key Encryption Scheme for Bits
- Hardness of MQ Problems Implies Pseudorandom Distributions
- Key Encapsulation Mechanism
- Longer Pseudorandom Strings
- Construction of the KEM Scheme
- Concrete Parameters
- References
- Public-Key Encryption: Special Properties
- Anonymous Broadcast Encryption: Adaptive Security and Efficient Constructions in the Standard Model
- Introduction
- Anonymous Broadcast Encryption
- Generic Constructions for ANOBE from PKE
- ANOBE from Minimal Assumptions
- Adaptively Secure ANOBE from Robust, Anonymous PKE
- Generic Construction for ANOBE from IBE
- Efficient Decryption in the Standard Model
- Tag-Based Anonymous Hint Systems
- ANOBE with Efficient Decryption
- Shortening Ciphertexts with Randomness Re-use
- Conclusions and Open Problems
- References
- Outsider-Anonymous Broadcast Encryption with Sublinear Ciphertexts
- Introduction
- Background
- The Subset Cover Framework
- Anonymous Identity-Based Encryption (AIBE)
- Outsider-Anonymous Broadcast Encryption (oABE)
- The Setting
- The Security Model
- Our Constructions
- A Generic CPA Public-Key Construction
- A Generic CCA Public-Key Construction
- An Enhanced CCA Public-Key Construction
- An Enhanced CCA Symmetric-Key Construction
- Conclusions and Future Work
- References
- Verifiable Predicate Encryption and Applications to CCA Security and Anonymous Predicate Authentication
- Introduction
- Definition of Verifiable Predicate Encryption
- Definition of Predicate Encryption
- Definition of Verifiability
- CCA-Secure VPE from CPA-secure VPE
- Definitions
- Generic Conversion
- Qualifying Relations
- Anonymous Deniable Predicate Authentication
- Definition of Anonymous Deniable Predicate Authentication
- Construction from CCA-Secure VPE
- Security Analysis
- Instantiations
- References
- Public Key Encryption against Related Key Attacks
- Introduction
- RKA Security
- Our Results
- Discussion
- Preliminaries
- RKA Security
- Realization from Adaptive Trapdoor Relations
- Our Construction
- Instantiations from Hardness of Factoring
- Strong One-Time Signature
- Adaptive Trapdoor Relations
- Instantiations from Diffie-Hellman Assumptions
- Strong One-Time Signature from Hardness of Discrete Log
- Instantiations from BDDH
- Weakly CC-RKA-Secure Schemes from DDH
- Instantiations from LWE
- References
- Related-key Attacks on Cramer-Shoup
- Strong One-Time Signatures from Protocols
- Identity-Based Encryption
- Functional Encryption for Threshold Functions (or Fuzzy IBE) from Lattices
- Introduction
- Overview of our Construction
- Preliminaries
- Definition: Fuzzy IBE
- Security Model for Fuzzy IBE
- Preliminaries: Lattices
- Random Integer Lattices
- Trapdoors for Lattices: The Algorithm TrapGen
- Discrete Gaussians
- Preimage Sampling
- Sampling from an ``Encryption" Matrix
- Hardness Assumption
- The Fuzzy IBE Scheme
- Construction
- Proof of Security
- Parameters
- Conclusion
- References
- Variants of Waters' Dual System Primitives Using Asymmetric Pairings
- Introduction
- Prerequisites
- Bilinear Maps
- Hardness Assumption
- Framework for Conversion
- An Analysis
- Constructions
- Scheme 6
- Broadcast Encryption
- Security Proof for Scheme 6
- Conclusion
- References
- From Selective to Full Security: Semi-generic Transformations in the Standard Model
- Introduction
- Basic Definitions
- Fully-Secure HIBE from Selective-Secure WIBE
- Selective WIBE Schemes from Selective HIBE
- Lattice-Based WIBE
- Future Directions
- References
- Circular and KDM Security for Identity-Based Encryption
- Introduction
- Our Contributions
- Preliminaries
- Lattices and Gaussians
- Trapdoors for Lattices
- Learning With Errors
- Key-Dependent Message Security
- Hardness of Extended LWE
- Background and the Problem
- Reduction from LWE
- KDM-CPA Secure Public-Key Scheme
- All-But-d Trapdoor Functions
- Algebraic Background
- Basic Construction
- Puncturing
- Circular-Secure IBE
- References
- Public-Key Encryption: Constructions
- NTRUCCA: How to Strengthen NTRUEncrypt to Chosen-Ciphertext Security in the Standard Model
- Introduction
- Preliminaries
- Notation
- Lattice Background
- ABO Lossy Trapdoor Functions
- An ABO Lossy Trapdoor Function from pNE
- Modifying pNE for Full Randomness Recovery in Decryption
- Our ABO Lossy Trapdoor Function
- The NTRUCCA Scheme
- Generalized Peikert-Waters Construction
- Instantiation and Choice of Parameters
- Conclusions
- References
- Generating Provable Primes Efficiently on Embedded Devices
- Introduction
- Prime Number Generation Based on Primality Testing
- Pseudo-primality Tests
- True Primality Tests
- Constructive Generation of Provable Primes
- The Square Root Method
- The Cube Root Method
- Estimating the Output Entropy
- Implementation Results and Practical Aspects
- On-board Generation of Probable Primes
- Generating Provable Primes
- Comparing Generators for Probable and Provable Primes
- Achieving Leakage-Resistant Prime Number Generation
- Conclusion
- References
- Invited Talk
- Password-Based Authenticated Key Exchange
- Introduction
- Security Models
- Game-Based Security
- Simulation-Based Security
- Universal Composability
- Constructions
- Two-Party Password-Based Authenticated Key Exchange
- Group Password-Based Authenticated Key Exchange
- References
- Secure Two-Party and Multi-party Computations
- Constant-Round Multi-party Private Set Union Using Reversed Laurent Series
- Introduction
- Overview of Our Techniques
- Related Work
- Outline of the Paper
- Reversed Laurent Series
- Reversed Laurent Series and Rational Functions
- Conversion from a Rational Function to Its RLS
- Conversion from an RLS Representation to a Rational Function
- Privacy-Preserving Set Union
- Representing Sets and Computing Their Union
- (Verifiable) Secret Sharing of Polynomials
- A Protocol Secure against Honest-But-Curious Adversaries
- A Protocol Secure against Malicious Adversaries
- Conclusion
- References
- Policy-Enhanced Private Set Intersection: Sharing Information While Enforcing Privacy Policies
- Introduction
- Results and Contributions
- Technical Challenges and Highlight of Our Techniques
- Related Work
- Problem Definitions
- Notations and Terminology
- Basic Problem Definitions
- Security Definitions
- Construction
- Strawman Schemes
- Preliminaries
- Main Construction
- Encodings for Symmetric Policies
- Extensions for Richer Policies
- Asymmetric Policies
- Attributes
- Bundles
- Disjunctions and DNFs
- Proofs of Security
- Performance
- Asymptotic Complexities
- Empirical Performance
- Performance for Rich Policies
- Conclusion
- References
- Efficiently Shuffling in Public
- Introduction
- Improving the Efficiency and Robustness of Mixnets
- Shuffling in Public
- Our Contributions
- Outline
- Preliminaries
- Notation
- Homomorphic Encryption
- The Damgård-Jurik Cryptosystem
- Privacy of a Shuffle
- Permutation Networks
- Rotation
- Shuffling
- Biased Networks
- Obfuscation of a Paillier Shuffle
- Matrix Notation
- Obfuscation of Damgård-Jurik Shuffles
- Obfuscation of Shuffle Networks
- Distributed Sampling and Obfuscation of a Shuffle
- Mixnet Properties
- Privacy
- Complexity
- Parallelisation
- Conclusion
- References
- Key Exchange and Secure Sessions
- Efficient Password Authenticated Key Exchange via Oblivious Transfer
- Introduction
- Our Contributions
- Overview of Our Constructions
- UC-Secure PAKE from Oblivious Transfer
- The Randomized Equality-Testing Functionality
- Randomized Equality Testing Protocol 1
- Implementing the Split Fre Functionality without Authenticated Channels
- Concurrent PAKE from OT
- A General Framework
- Instantiating the Underlying OT
- References
- Strongly Secure Authenticated Key Exchange from Factoring, Codes, and Lattices
- Introduction
- Background
- Motivating Problem
- Our Contribution
- Security Model
- CK+ vs. eCK
- CK+ Security Model
- Generic AKE Construction from KEM without Random Oracles
- Preliminaries
- Construction
- Instantiations
- Diffie-Hellman-Based
- Factoring-Based
- Code-Based
- Lattice-Based
- References
- Relatively-Sound NIZKs and Password-Based Key-Exchange
- Introduction
- NIZK Definitions
- Relative Soundness
- Smooth Projective Hash Functions
- Bilinear Assumptions
- A Publicly-Verifiable CCA2-Encryption Scheme
- l-SRS-NIZK for the DDH Language
- Secure Protocol in the PAK Model
- Secure Protocol in the UC Model
- A Single Round UC Password-Based Key Exchange Protocol
- The Simulator for the UC Protocol
- Proof of Indistinguishability for the UC Protocol
- References
- Multi-location Leakage Resilient Cryptography
- Introduction
- Multi-location Leakage Resilient Signature
- Multi-location Symmetric-Key Authentication
- Related Work
- Multi-location Leakage Resilience in the Public Key Setting
- Signature Schemes
- Construction
- Authenticated Session Protocols
- Security Definition
- Our Construction
- Stream Cipher Construction
- Security Analysis
- References
- Public-Key Encryption: Relationships
- On Definitions of Selective Opening Security
- Introduction
- Preliminaries
- SIM-SO-CPA Security Does Not Imply Full IND-SO-CPA Security
- PKE' is SIM-SO-CPA Secure
- PKE' Is Not Fully IND-SO-CPA Secure
- Full IND-SO-CPA Does Not Imply SIM-SO-CPA
- Outline
- Non-interactive Statistically Hiding Commitments
- The Separating Scheme
- SIM-SO-CPA Insecurity of the Scheme
- Full IND-SO-CPA Security of the Scheme
- References
- New Definitions and Separations for Circular Security
- Introduction
- Related Work
- Definitions of Security
- Standard Security Definitions
- Circular Security Definitions
- Counterexample for Symmetric Encryption
- Counterexamples for Public-Key Encryption
- Preliminaries and Algebraic Setting
- Encryption Scheme cpa
- The Attack
- Extension: A Counterexample for CCA Security
- Conclusion and Open Problems
- References
- Correlated Product Security from Any One-Way Function
- Introduction
- Our Results
- Previous Work
- Preliminaries
- Correlated Product Security
- Decisional Correlated Product Security
- Relations to (Computational) Correlated Product Security
- Equivalence of OWF and (Decisional) Correlated Product Secure Families of OWFs
- DCP with Trapdoor from Lossy Trapdoor Functions
- Decisional Correlated Product Security Is Deterministic Encryption
- Conclusion and Open Problems
- References
- Relations between Constrained and Bounded Chosen Ciphertext Security for Key Encapsulation Mechanisms
- Introduction
- Preliminaries
- Relations between Constrained and Bounded Chosen Ciphertext Security
- Separations
- Slightly Stronger CCCA Security and Its Implication
- KEMs from Computational Hash Proof Systems, Revisited
- Definitions for Computational HPS
- HPS-Based KEM and Bounded CCA Security
- References
- DL, DDH, and More Number Theory
- Solving a Discrete Logarithm Problem with Auxiliary Input on a 160-Bit Elliptic Curve
- Introduction
- Preliminaries
- Cheon's Algorithm
- Pollard's -Method
- Implementation
- Evaluating F(X)
- Using Automorphisms
- Parallelization
- Experimental Results
- Parameters
- Results
- Discussion
- Feedback to Cryptographic Schemes
- Boneh, Gentry, and Waters' Broadcast Encryption Scheme
- Boneh and Boyen's ID-Based Encryption Scheme
- Boneh and Boyen's Signature Scheme
- Concluding Remarks
- References
- Inferring Sequences Produced by Nonlinear Pseudorandom Number Generators Using Coppersmith's Methods
- Introduction
- Preliminaries
- Lattices
- Coppersmith's Techniques
- Attacking a Non-linear Generator
- Case F Known
- Case F Unknown
- Application: Attacking the Quadratic Generator
- The Inversive Generator
- The Pollard Generator
- Case F Known
- Case F Unknown
- References
- Extended-DDH and Lossy Trapdoor Functions
- Introduction
- Previous Work
- Our Contributions
- Preliminaries
- Notation
- Lossy Trapdoor Functions
- Subset Membership Problems
- Smooth Hash Proof Systems
- Lossy Trapdoor Functions from Smooth Homomorphic Hash Proof Systems
- The Extended DDH Assumption
- Conclusion
- References
- DDH-Like Assumptions Based on Extension Rings
- Introduction
- Preliminaries
- Notation
- Extension Rings and DDH
- The f-DDH Problem
- The d-DDH Problem
- Applications of d-DDH
- Pseudorandom Functions
- Public Key Encryption
- Applications in General
- Efficiency
- The Vector DDH Problem
- Applications of d-VDDH
- Public Key Encryption
- Generalized BHHO Encryption
- Pseudorandom Functions
- References
- Beyond Ordinary Signature Schemes
- Security of Blind Signatures Revisited
- Introduction
- Blind Signatures
- Security of Blind Signatures
- Honest-User Unforgeability
- Defining Honest-User Unforgeability
- Unforgeability Does Not Imply Honest-User Unforgeability
- Probabilistic Verification
- Adapting the Definition
- From Unforgeability to Honest-User Unforgeability
- References
- Efficient Network Coding Signaturesin the Standard Model
- Introduction
- Background and Definitions
- Computational Assumptions
- Background on Linear Network Coding
- Network Coding Signatures
- An Efficient Linear Network Coding Scheme
- A Construction Based on SDH
- A (Strong) RSA Based Realization
- Efficiency and Comparisons
- References
- Improved Security for Linearly Homomorphic Signatures: A Generic Framework
- Introduction
- Our Contributions
- Overview of Our Construction
- Concurrent Work
- Homomorphic Signatures
- Building Blocks
- A Generic Conversion
- Security
- Example Instantiation: Boneh-Boyen Signatures
- References
- On the Security of Dynamic Group Signatures: Preventing Signature Hijacking
- Introduction
- Preliminaries
- Group Signatures
- Other Primitives
- Opening Soundness
- Opening Soundness of Existing Schemes
- Achieving Opening Soundness
- The Modified Groth Scheme
- Conclusion
- References
- Author Index
