Public Key Cryptography -- PKC 2012

Name: Public Key Cryptography -- PKC 2012 | 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012, Proceedings

Marc Fischlin Johannes Buchmann Mark Manulis(Herausgeber*in)

Springer (Verlag)

Erschienen am 19. Mai 2012

XIV, 734 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-30057-8 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken