Advances in Cryptology - EUROCRYPT 2012

Name: Advances in Cryptology - EUROCRYPT 2012 | 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012, Proceedings

David Pointcheval Thomas Johansson(Herausgeber*in)

Springer (Verlag)

Erschienen am 5. April 2012

XIV, 758 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-29011-4 (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
Invited Talks
A Tutorial on High Performance Computing Applied to Cryptanalysis
Typical Cryptanalytic Applications
Hardware Context
Running Record Computations
Algorithmic Challenges
Conclusion
References
Another Look at Provable Security
References
Index Calculus
Cover and Decomposition Index Calculus on Elliptic Curves Made Practical
Introduction
Survey of Previous Work
Weil Descent and Cover Attacks
Decomposition Attack
Cover and Decomposition Attack
Description of the Attack
Sieving for Quadratic Extensions
Complexity Analysis
Application to Elliptic Curves Defined over Fp6
Using a Genus 3 Cover
Using a Genus 2 Cover
Complexity and Comparison with Other Attacks
A 149-Bit Example
Conclusion and Perspectives
References
Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields
Introduction
Preliminaries
Definition and Notation
Gröbner Bases [10]
Solving Multivariate Polynomials with Linear Constraints
Modeling the Linear Constraints
Low-Degree Equations
Linear Dependencies
Description of the Linearization Algorithm
Complexity Bounds for Solving Problem 2
Application to ECDLP over Binary Fields
Diem's Variant of Index Calculus
A Linearization Strategy for Solving ECDLP over F2n
Experimental Results
Validation of the Heuristic Assumption
Gröbner Basis Computations
Conclusion and Perspectives
References
Symmetric Constructions I
Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations
Introduction
Related Work
Our Contribution
The Construction
Indistinguishability Analysis
An Upper Bound
Attacks
Daemen's Attack for t = 1
A Meet in the Middle Attack
Statistical Properties
Fourier Coefficients over All Permutations
Fourier Coefficients in the Single-Round Even-Mansour Cipher
Fourier Coefficients in the t-Round Key-Alternating Cipher
Practical Constructions
AES2: A Block Cipher Proposal Based on AES
Conclusion, Open Problems and Future Work
References
Efficient and Optimally Secure Key-Length Extension for Block Ciphers via Randomized Cascading
Introduction
Key-Length Extension for Block Ciphers
Existing Approaches to Key-Length Extension
Our Results
Preliminaries
Basic Notation
Random Systems
Generic Attacks against Efficient Key-Length Extension Schemes
One-Query Constructions
Two-Query Constructions
The Double XOR-Cascade Construction
References
Secure Computation
Fair Computation with Rational Players
Introduction
Our Results
Other Related Work
Model and Definitions
Execution in the Ideal World
Execution in the Real World
Positive Results for Rational Fair Computation
The Fail-Stop Setting
The Byzantine Setting
Conclusions and Future Work
References
Concurrently Secure Computation in Constant Rounds
Introduction
Our Contributions
The Main Technique
Other Related Work
Our Definitions
UC Security and SPS
Input Indistinguishable Computation
Building Blocks
Our Construction
References
Identity-Based Encryption Resilient to Continual Auxiliary Leakage
Introduction
Background
Identity-Based Encryption with Auxiliary Inputs
Auxiliary Input Model for Confidentiality
Intuition
Concrete Construction
Security
IBE with Continual Auxiliary Inputs
Continual Auxiliary Leakage Model
Construction in the Continual Auxiliary Leakage Model
Further Discussions on the Continual Auxiliary Input Model
Construction Supporting Leakage-Resilient Setup
References
Protocols
Quantum Proofs of Knowledge
Introduction
Our Techniques
Preliminaries
Quantum Proofs of Knowledge
Definitions
Discussion
Elementary Constructions
QPoKs for All Languages in NP
References
On Round-Optimal Zero Knowledge in the Bare Public-Key Model
Introduction
Our Results and Techniques
Issues in Security Proofs of Previous Results
The Case of ?MR [18]
Replacing Simulation in Phases by Threads
Round-Optimal cZK and rZK in the BPK Model
Concurrent Zero Knowledge in the BPK Model
Resettable Zero Knowledge in the BPK Model
Efficient Instantiations
References
Robust Coin Flipping
Introduction
Preliminaries and Definitions
Results
Yao's Robust Coin Flipping
Simulating Finite Random Sources
Cooperative Numbers
Restatement Using Multilinear Algebra
Two Players
Three or More Players: What Can't Be Done
Three Players: What Can Be Done
Higher-Order Robustness
Application to Secure Multiparty Computation and Mental Poker
References
Unconditionally-Secure Robust Secret Sharing with Compact Shares
Introduction
Preliminaries
Robust Secret Sharing
Message Authentication Codes
Reed-Solomon Error Correction
The New Scheme and Its Analysis
Conclusion and Open Questions
References
Lossy Trapdoor Functions
All-But-Many Lossy Trapdoor Functions
Introduction
Preliminaries
Definition of ABM-LTFs
A DCR-Based ABM-LTF
Setting and Assumptions
Our Construction
Security Analysis
Application: Selective Opening Security
ABM-LTFs with Explainable Tags
Selective Opening Security
IND-SO-CCA Security from ABM-LTFs
References
Identity-Based (Lossy) Trapdoor Functions and Applications
Introduction
Definitions
IB-TDFs from Pairings
References
Dual Projective Hashing and Its Applications - Lossy Trapdoor Functions and More
Introduction
Our Contributions
PreviousWork
Dual Projective Hashing
Lossy Trapdoor Functions
Deterministic Encryption
Deterministic Encryption
Extractors
Our Construction
Instantiations from DDH and DLIN
Instantiations from QR
Instantiations from DCR
Instantiations from LWE
References
Tools
Efficient Zero-Knowledge Argumentfor Correctness of a Shuffle
Introduction
RelatedWork
Our Contribution
Preliminaries
Special Honest Verifier Zero-Knowledge Argument of Knowledge
Shuffle Argument
Multi-exponentiation Argument
The Prover's Computation
Trading Computation for Interaction
Product Argument
Implementation and Comparison
References
Malleable Proof Systems and Applications
Introduction
Definitions and Notation
Derivation Privacy for Proofs
Controlled Malleability for NIZKs
Instantiating cm-NIZKs Using Groth-Sahai Proofs
Malleability for Groth-Sahai Proofs
An Efficient Instantiation of Controlled Malleable NIZKs
Controlled Malleability for Encryption
Definition of Controlled-Malleable CCA Security
Compactly Proving Correctness of a Shuffle
References
Group to Group Commitments Do Not Shrink
Introduction
Preliminaries
Bilinear Groups
Notations
Commitment Schemes
Strictly Structure-Preserving Commitments
Algebraic Algorithms
Assumptions
Lower Bounds
Commitment Size
Number of Verification Equations
Optimal Constructions
In Asymmetric Setting
In Symmetric Setting
Efficiency
References
Tools for Simulating Features of Composite Order Bilinear Groups in the Prime Order Setting
Introduction
Background
Composite Order Bilinear Groups
Prime Order Bilinear Groups
OurMainTools
Parameter Hiding in Dual Orthonormal Bases
The Subspace Assumption
Analog of the Boneh-Boyen IBE Scheme
Our Construction
Semi-functional Algorithms
Further Applications
References
Symmetric Constructions II
Minimalism in Cryptography: The Even-Mansour Scheme Revisited
Introduction
The Even-Mansour Scheme
Definition of the EM Scheme and Its Notation
The Lower Bound Security Proof
Previous Attacks on the Even-Mansour Scheme
The Slidex Attack and a Tight Bound on the Security of the Even-Mansour Scheme
The Slide with a Twist Attack
The New Slidex Attack
The Single-Key Even-Mansour Scheme
Definition of the Scheme and Its Security Proof
A Simple Optimal Attack on SEM
The Security of Other Variants of the Even-Mansour Scheme
Even-Mansour with Addition
Even-Mansour with a Random Involution as the Permutation
Addition Even-Mansour with an Involution as the Permutation
Memoryless Attacks on the Even-Mansour Scheme
OpenProblems
References
Message Authentication, Revisited
Introduction
Our Results
Definitions
Notation
Message Authentication Codes
Transformations for MACs
From One to Multiple Verification Queries: uf-cma + ind-cma uf-cmva
Domain Extension for ind-cma MACs
From Selective to Full Security: suf-cma ? uf-cma
Constructions of Authentication Protocols
Constructions from CCA-Secure Encryption
Constructions from Hash Proof Systems
Construction from Key-Homomorphic Weak-PRFs
Constructions from Signatures
Constructions from the LPN Assumption
Three-Round Authentication from Any Weak PRF
References
Property Preserving Symmetric Encryption
Introduction
Our Contribution
Related Work
Property Preserving Encryption
Security Notions
Relations among Security Notions
LoR vs. FtG
Constructions of Property-Preserving Encryption
An Explicit Construction for Testing Orthogonality
References
Symmetric Cryptanalysis
Narrow-Bicliques: Cryptanalysis of Full IDEA
Introduction
Cryptanalytic Attacks on IDEA and Our Contribution
Description of IDEA
Biclique Attack
Biryukov-Demirci Relation
KeyRecoveryfortheFullIDEA
New 5 Round Attack
New 6 Round Attack
New 7.5 Round Attack
On Practical Verification
Concluding Discussion
References
Cryptanalyses on a Merkle-Damgard Based MAC - Almost Universal Forgery and Distinguishing-H Attacks
Introduction
Related Work
LPMAC with Narrow-Pipe Merkle-Damg°ard Hash Functions
Summary of Previous Analyses on MAC Algorithms
Multi-collision Attack
Generic Distinguishing-H Attack on LPMAC
Main Idea
Attack Procedure
Generic almost Universal Forgery Attack on LPMAC
Easiness and Hardness of almost Universal Forgery Attack
Overall Strategy
Multi-collision with Diamond Structure
Forging Procedure
Comparison between Simple Method and Diamond Structure
Concluding Remarks
References
Statistical Tools Flavor Side-Channel Collision Attacks
Introduction
Preliminaries
Notations and Side-Channel Model
Correlation Collision Attack
Shortcomings and Our Solutions
Higher-Order Moments
Collision Detection Using Probability Density Functions
Practical Experiments
Canright-Batina's Masked AES S-Box
Threshold Implementation of PRESENT
Threshold Implementation of AES
Boolean Masking in Software
Conclusions
References
Fully Homomorphic Encryption
Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers
Introduction
The DGHV Scheme over the Integers
The New DGHV Public Key Compression Technique
Description
Semantic Security
Extension of DGHV Encryption to Higher Degrees
Adaptation of the BGV Framework to the DGHV Scheme
The BGV Framework for Leveled FHE
Modulus-Switching for DGHV
The Modulus-Switching Algorithm for DGHV
The DGHV Scheme without Bootstrapping
Correctness and Security
Improved Attack against the Approximate GCD Algorithm
Experimental Results
Implementation of DGHV with Compressed Public Key
Implementation of Leveled DGHV
Faster Ciphertext Expansion
Bootstrapping: The Decryption Circuit
Implementation Results
References
Fully Homomorphic Encryption with Polylog Overhead
Introduction
Packing Plaintexts and Batched Homomorphic Computation
Permuting Plaintexts within the Plaintext Slots
FHE with Polylog Overhead
Computing on (Encrypted) Arrays
Computing with -Fold Gates
Permutations over Hyper-rectangles
Batch Selections, Swaps, and Permutation Networks
Cloning: Handling High Fan-Out in the Circuit
Permutation Networks from Abelian Group Actions
Permutation Networks from Cyclic Rotations and Swaps
Generalizing to Sharply-Transitive Abelian Groups
FHE with Polylog Overhead
The Basic Setting of FHE Schemes Based on Ideal Lattices and Ring LWE
Implementing Group Actions on FHE Plaintext Slots
Low-Overhead FHE
References
Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE
Introduction
Our Results
Related Work
Organization
Preliminaries
Homomorphic Encryption from LWE
Fully Homomorphic Encryption from LWE
Threshold Fully Homomorphic Encryption
Construction of TFHE
Secure MPC via TFHE
Variants and Optimizations
References
Asymmetric Cryptanalysis
Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers
Introduction
A Square-Root Algorithm for Partial Approximate Common Divisors
Overview
Description
Logarithmic Speedup
Application to GACD
Implementation of the Square-Root PACD Algorithm
Obstructions
Tricks
Logarithmic Speedup and Further Tricks
New Security Estimates for the FHE Challenges
Applications to Noisy Factoring
Known Positions
Unknown Positions
Applications to Low-Exponent RSA
References
Decoding Random Binary Linear Codes in 2n/20: How 1 + 1 = 0 Improves Information Set Decoding
Introduction
Generalized Information Set Decoding
The Merge-Join Building Block
Our New Algorithm for Solving the Submatrix Matching Problem
Our COLUMNMATCH Algorithm
Comparison of Asymptotic Complexity
References
Efficient Reductions
Optimal Security Proofs for Full Domain Hash, Revisited
Introduction
An Overview of Our Results
Full Domain Hash and Coron's Impossibility Result
A Tight Security Reduction for FDH Signatures
Extensions
Related Work
Open Problems
Definitions
Notations and Conventions
Games
Signature Schemes
Trapdoor Permutations
The RSA Trapdoor Permutation
Full Domain Hash Signatures
The Scheme
Classical Security Results of TDP-FDH
A Corrected Version of Coron's Optimality Result
A Tight Security Proof for TDP-FDH
Lossiness of RSA from the F-Hiding Assumption
Lossiness of RSA
References
On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model
Introduction
Preliminaries
Security Proof with the Forking Lemma
Description of the New Meta-reduction
Proof of the Main Theorem
Successful Simulation of the Forger
Success of the Meta-reduction
Main Theorem and Discussion
References
Tightly-Secure Signatures from Lossy Identification Schemes
Introduction
Related Work and Contributions
Overview of Our Signature Schemes
Preliminaries
The Decisional Short Discrete Logarithm Problem
The Ring-LWE Problem and Lattices
The Subset Sum Problem
Signature Schemes
Lossy Identification Schemes
A Signature Scheme Based on the DSDL Problem
A Signature Scheme Based on Lattices
A Signature Scheme Based on Subset Sum
References
Public-Key Schemes
Adaptively Attribute-Hiding (Hierarchical) Inner Product Encryption
Introduction
Background
Our Results
Key Techniques
Notations
Dual Pairing Vector Spaces (DPVS) and the Decisional Linear (DLIN) Assumption
Definition of Inner Product Encryption (IPE)
Proposed (Basic) IPE Scheme
Construction
Security
A Variant for Achieving Shorter Public and SecretKeys
Comparison
References
Scalable Group Signatures with Revocation
Introduction
Related Work
Our Contribution
Background
Bilinear Maps and Complexity Assumptions
Groth-Sahai Proof Systems
Structure-Preserving Signatures
The NNL Framework for Broadcast Encryption
Revocable Group Signatures
A Revocable Group Signature Based on the Subset Difference Method
Construction
References
Incremental Deterministic Public-Key Encryption
Introduction
Our Contributions
Related Work
Overview of Our Approach
Preliminaries
Probability Distributions
Deterministic Public-Key Encryption
Modeling Incremental Deterministic Public-Key Encryption
A Generic Construction via Random Partitioning
A Construction Based on the Decisional Diffie-Hellman Assumption
References
Security Models
Standard Security Does Not Imply Security against Selective-Opening
Introduction
Technical Approach
Preliminaries
SOA-C Insecurity of CE Schemes
SOA-K Insecurity of Encryption Schemes
References
Detecting Dangerous Queries: A New Approach for Chosen Ciphertext Security
Introduction
Related Work
Detectable Chosen Ciphertext Security
Detectable Encryption
Facts about DCCA Security
The Construction: CCA2 Security from DCCA Security
Proof of Security
Proof That Bad Query Event Does Not Happen
Putting the Proof of the Main Theorem together
References
Security of Symmetric Encryption in the Presence of Ciphertext Fragmentation
Introduction
Preliminaries
Symmetric Encryption Supporting Fragmentation
Unified Syntax
Security for Stateful Schemes
Realizations and Non-realizations
Boundary Hiding
Denial-of-Service Attacks
Conclusions
References
Lattices
Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller
Introduction
Contributions
Techniques
Primitive Lattices
Trapdoor Generation and Operations
A New Trapdoor Notion
Trapdoor Generation
LWE Inversion
Gaussian Sampling
Trapdoor Delegation
References
Pseudorandom Functions and Lattices
Introduction and Main Results
Results and Techniques
Discussion and Open Questions
Other Related Work
Preliminaries
The Learning with Rounding Problem
Reduction from LWE
Synthesizer-Based PRFs
Synthesizer Constructions
The PRF Construction
Security
Direct PRF Constructions
Efficiency
Security under LWE
References
Lattice Signatures without Trapdoors
Introduction
Related Work and Our Results
Techniques
A Practical Comparison with Hash-and-Sign Signatures
Notation
TheSIS Problem and Its Variants
Relations between the SIS Variants
Rejection Sampling and the Normal Distribution
Signature Scheme Based on SIS
Setting the Parameters
Signatures Based on Low-Density SIS and LWE
The LWE Problem
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken