Advances in Cryptology -- ASIACRYPT 2011

Name: Advances in Cryptology -- ASIACRYPT 2011 | 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011, Proceedings

Dong Hoon Lee Xiaoyun Wang(Herausgeber*in)

Springer (Verlag)

Erschienen am 1. Dezember 2011

XIV, 760 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-25385-0 (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

Intro
Title
Preface
Table of Contents
Lattices and Quantum Cryptography
BKZ 2.0: Better Lattice Security Estimates
Introduction
Preliminaries
The Blockwise Korkine-Zolotarev (BKZ) Algorithm
Description
Enumeration Subroutine
Analysis
BKZ 2.0
Sound Pruning
Preprocessing of Local Blocks
Optimizing the Enumeration Radius
New Lattice Records
Darmstadt's Lattice Challenge
SVP Challenges
Predicting BKZ 2.0 by Simulation
Description
Consistency with Experiments
Enumeration Subroutine
Revising Security Estimates
NTRU Lattices
Gentry-Halevi's Fully-Homomorphic Encryption Challenges
References
Functional Encryption for Inner Product Predicates from Learning with Errors
Introduction
Overview of the Construction
Predicate Encryption
Security
Lattice Preliminaries
Lattices
Sampling Algorithms
The LWE Problem
A Functional Encryption Scheme for Inner Product Predicates
The Construction
Correctness
Security
Parameter Selection
Conclusion and Open Questions
References
Random Oracles in a Quantum World
Introduction
Our Contributions
Preliminaries
Quantum Computation
Quantum-Accessible Random Oracles
Hard Problems for Quantum Computers
Cryptographic Primitives
Separation Result
Construction
Signature Schemes in the Quantum-Accessible Random Oracle Model
Secure Signatures from Preimage Sampleable Trapdoor Functions (PSF)
Secure Signatures from Claw-Free Permutations
Encryption Schemes in the Quantum-Accessible Random Oracle Model
CPA Security of BR Encryption
CCA Security of Hybrid Encryption
Conclusion
References
Public Key Encryption I
Lossy Encryption: Constructions from General Assumptions and Efficient Selective Opening Chosen Ciphertext Security
Introduction
Background
Selective Opening Secure Encryption
Lossy Encryption
Constructing Lossy Encryption Schemes
Re-Randomizable Encryption Implies Lossy Encryption
Statistically-Hiding {Catalog} && /PageLabels&&/Nums[0&&/S/D /St 70&&]&& &&()21-OT Implies Lossy Encryption
Chosen-Ciphertext Security
Chosen-Ciphertext Security: Indistinguishability
Chameleon Hash Functions
A Special Use of the Canetti-Halevi-Katz Paradigm
Lossy and All-But-n Trapdoor Functions
An IND-SO-stag-wCCA2 TBE Construction
An All-But-n Function with Short Outputs
References
Structure Preserving CCA Secure Encryption and Applications
Introduction
Structure Preserving Encryption
Basic Notation
Construction
Correctness and Security
Secure Joint Ciphertext Computation
Preliminaries
Construction
Oblivious Third Parties
Conclusion
References
Decoding Random Linear Codes in (20.054n)
Introduction
Notation
Information Set Decoding Algorithms
Information Set Decoding
Stern's Algorithm
The Finiasz-Sendrier ISD Algorithm
Ball-collision Decoding
How to Solve the Submatrix Problem
The ColumnMatch Algorithm
Our New Decoding Algorithm
Experiments
References
Lower and Upper Bounds for Deniable Public-Key Encryption
Introduction
Deniable Public-Key Encryption
Security Notions
Full Bi-deniablity Implies Full Sender/Receiver-Deniability
Impossibility of Fully Receiver/Bi-deniable Encryption
Security of Parallel Self-composition
Lower Bound
From Multi-distributional to Poly Deniability
Poly-Sender-Deniability
Poly-Receiver-Deniability
Poly-Bi-Deniability
References
Public Key Encryption II
Bridging Broadcast Encryption and Group Key Agreement
Introduction
Our Contributions
Related Work
Paper Organization
Modeling Contributory Broadcast Encryption
Syntax
Security Definitions
Remarks on Complexity Bounds of CBE and BE Schemes
An Aggregatable BE Scheme
Review of Aggregatable Signature-Based Broadcast
An Aggregatable BE Scheme Based on ASBB
Useful Properties
Proposed CBE Scheme
High-Level Description
The Proposal
Discussion
Conclusions
References
On the Joint Security of Encryption and Signature, Revisited
Introduction
Our Contribution
Further Related Work
Preliminaries
Combined Signature and Encryption Schemes
A Cartesian Product Construction
An Insecure CSE Scheme whose Components are Secure
A Generic Construction from IBE
A More Efficient Construction
Comparison of Schemes
Conclusions and Future Research
References
Polly Cracker, Revisited
Introduction
Related Work
Preliminaries
Gr bner Basis and Ideal Membership Problems
Symmetric Polly Cracker: Noise-Free Version
Homomorphic Symmetric Encryption
The Scheme
Security
Symmetric-to-Asymmetric Conversion
Gr\"{o} bner Bases with Noise
Hardness Assumptions and Justifications
Polly Cracker with Noise
References
Database Privacy
Oblivious RAM with O((logN)3)Worst-Case Cost
Introduction
Our Contributions
Related Work
Preliminaries
Defining O-RAM with Enriched Operations
Relationship with the Standard O-RAM Definition
Implementing Enriched Semantics
Encryption and Authentication
Two Simple O-RAM Constructions with Deterministic Guarantees
Basic Construction
Overview of the Binary Tree Construction
Detailed Construction
Security Analysis
Asymptotic Performance of the Basic Construction
Recursive Construction and How to Achieve the Desired Asymptotics
Recursive O-RAM Construction: O(1) Client-Side Storage
References
Noiseless Database Privacy
Introduction
Our Privacy Notion
Boolean Queries
The No Auxiliary Information Setting
Handling Auxiliary Information
Handling Multiple Queries in Adversarial Refreshment Model
Real Queries
Sums of Functions of Database Rows
Privacy Analysis of fin(T)=j[n]aij tj
Privacy under Multiple Queries on Changing Databases
References
Hash Function
The Preimage Security of Double-Block-Length Compression Functions
Introduction
The Model
An Example Case
Preimage Security Results for Hirose's Scheme
Preimage Security Results for Abreast-DM
Preimage Security Results for Tandem-DM
Conclusion
References
Rebound Attack on JH42
Introduction
Preliminaries
The JH42 Hash Function
Properties of the Linear Transformation L
Observations on the Compression Function
The Rebound Attack
Semi-free-start Internal Near-Collisions
Matching the Active Bytes
Matching the Passive Bytes
Outbound Phase
Distinguishers on JH
Distinguishers on the Reduced Round Internal Permutation
Distinguishers on the Full Internal Permutation
Distinguishers on the Full Compression Function
Conclusion
References
Second-Order Differential Collisions for Reduced SHA-256
Introduction
Higher-Order Differential Collisions for Compression Functions
Second-Order Differential Collision for Block-Cipher-Based Compression Functions
Related Work
Application to SHA-256
Description of SHA-256
Differential Characteristics
Complexity of the Attack
Applications to Related Primitives
Application to SHA-512
Application to SHACAL-2
Conclusions
References
Finding SHA-2 Characteristics: Searching through a Minefield of Contradictions
Introduction
Description of SHA-256
Basic Attack Strategy
Determining a Starting Point
Searching for Valid Differential Characteristics and Conforming Message Pairs in SHA-2
Difference and Condition Propagation in SHA-2
Alternative Description of SHA-2
Generalized Conditions
Efficiently Implementing the Propagation of Generalized Conditions
Two-Bit Conditions
Inconsistency Checks
Searching for Differential Characteristics
Search Strategy
Results
Conclusions and Future Work
References
Symmetric Key Encryption
Cryptanalysis of ARMADILLO2
Introduction
Description of ARMADILLO2
Description
A Multi-purpose Cryptographic Primitive
Inverting the ARMADILLO2 Function
The Meet-in-the-Middle Technique
ARMADILLO2 Matching Problem: Matching Non-random Elements
Applying the Parallel Matching Algorithm to ARMADILLO2
Meet in the Middle Key Recovery Attacks
Key Recovery Attack in the FIL-MAC Setting
Key Recovery Attack in the Stream Cipher Setting
(Second) Preimage Attack on the Hashing Applications
Meet-in-the-Middle (Second) Preimage Attack
Inverting the Compression Function
Experimental Verifications
Generalization of the Parallel Matching Algorithm
The Generalized Problem 1
Generalized Parallel Matching Algorithm
Link with Formulas in the Case of ARMADILLO
Conclusion
References
An Experimentally Verified Attack on Full Grain-128 Using Dedicated Reconfigurable Hardware
Introduction
Preliminaries
Description on Grain-128
Previous Results on Grain-128
Cube Testers
Dynamic Cube Attacks
A Partial Simulation Phase
A New Approach for Attacking Grain-128
Description of the Dedicated Hardware Used to Attack Grain-128
Architectural Considerations
Hardware Implementation Results
Conclusions
References
Biclique Cryptanalysis of the Full AES
Introduction
Biclique Cryptanalysis
Basic Meet-in-the-Middle Attack
Bicliques
The Flow of Biclique Cryptanalysis
New Tools and Techniques for Bicliques
Bicliques from Independent Related-Key Differentials
Bicliques from Interleaving Related-Key Differential Trails
Matching with Precomputations
Two Paradigms of Key Recovery
Long-Biclique
Independent-Biclique
Description of AES
Independent-Biclique: Key Recovery for the Full AES-128
Key Partitioning
3-Round Biclique of Dimension 8
Matching over 7 Rounds
Complexities
Long-Biclique: 9-Round AES-256
On Practical Verification
Discussion and Conclusions
What Properties of the AES Allowed to Obtain These New Results
On the Computational Advantage of the Biclique Techniques
Open Problems
References
Tag Size Does Matter: Attacks and Proofs for the TLS Record Protocol
Introduction
Notation, Syntax and Basic Security Notions
MAC-Encode-Encrypt and the TLS Record Protocol
Length-Hiding Authenticated Encryption
Attacking TLS for Short Messages and Tags
The CRD Security Notion
The CRD Security of MEE-GEN-CBC
References
Zero Knowledge Proof
Resettable Cryptography in Constant Rounds - The Case of Zero Knowledge
Introduction
Definitions
Constructing Resettably-Sound Concurrent Zero Knowledge Arguments for NP in the BPK Model
Proof of Concurrent Zero-Knowledge
Proof of Resettable-Soundness
Simultaneous Resettable Zero-Knowledge Arguments for NP in the BPK model
References
Two Provers in Isolation
Introduction
Related Work
Preliminaries
Isolation
Bit Commitment
Two-Prover Bit Commitment scheme
BGKW's Notion of Isolation
Cheating sBGKW with an NL-box
Quantumly Insecure - Two-Prover Bit Commitments
Discussion
A Non-Local Box to Cheat the Original BGKW Scheme
Magic Square Non-locality Game
Magic Square Bit Commitment
Defining and Checking Isolation
Quantum Secure Bit Commitment in the Two-Prover Model
Conclusion and Open Problems
References
Efficient Zero-Knowledge Arguments from Two-Tiered Homomorphic Commitments
Introduction
Preliminaries
Two-tiered Homomorphic Commitments
Special Honest Verifier Zero-knowledge Arguments of Knowledge
Batch Product Argument
Inner Product Argument
Arguments for Circuit Satisfiability
Range Arguments
References
Universal Composability
A Framework for Practical Universally Composable Zero-Knowledge Protocols
Introduction
Preliminaries
The UC-Model
Running Examples
A Language for Specifying UC-ZK Protocols
Proving Existence Rather Than Knowledge
Compiling Specifications to Protocols
The Gullible ZK Functionality and a Composition Theorem
Enhancing the Basic Language
Using Macros to Specify Algebraic Properties of Witnesses
Proving Knowledge of Group Elements
Conclusion
References
Non-interactive and Re-usable Universally Composable String Commitments with Adaptive Security
Introduction
Our Results and Comparison to Prior Work
Preliminaries
Complexity Assumptions
Groth-Sahai Proof Systems
Cramer-Shoup Encryption Based on DLIN Assumption
Ideal Functionality for Multiple Commitments
Scheme I: A Tweak on Lindell's Scheme
Scheme II: A Tweak on the Camenisch-Shoup Scheme
Trapdoor Commitments to Group Elements
Construction
Security
Conclusion
References
Foundation
Cryptography Secure against Related-Key Attacks and Tampering
Introduction
Technical Approach
Preliminaries
Classes of RKDFs and RKA-PRFs
ICR PRGs: A Tool in Our Constructions
Relations
References
Counting Points on Genus 2 Curves with Real Multiplication
Introduction
Conventional Point Counting for Genus 2 Curves
The Characteristic Polynomial of Frobenius
The Classical Schoof-Pila Algorithm for Genus 2 Curves
Endomorphisms and Generic Kernel Elements
Complexity of Classical Schoof-Pila Point Counting
Baby-Step Giant-Step Algorithms
Point Counting in Genus 2 with Real Multiplication
The RM Characteristic Polynomial
An Efficiently Computable RM Relation
Exploiting Split Primes in Q()
Shrinking the BSGS Search Space
Examples of Families of Curves with Explicit RM
Correspondences and Endomorphisms
A 1-Dimensional Family with RM by Z[(to.1+5)to./2]
A 2-Dimensional Family with RM by Z[(to.1+5)to./2]
A 2-Dimensional Family with RM by Z[2]
Numerical Experiments
Cryptographic Curve Generation
A Kilobit Jacobian
References
On the Efficiency of Bit Commitment Reductions
Introduction
Contribution
Notation
Information Theory
Impossibility Results
Model and Security Definition
Lower Bound for Multiple Bit Commitments
Lower Bounds for Multiple String Commitments
Commitments with Restricted Openings
Commitments from Noisy Channels at a Constant Rate
Conclusions
References
Secure Communication in Multicast Graphs
Introduction
Model
Characterization of Multicast Graphs
Reliable Communication
Almost Perfect Reliability
Perfect Reliability
Secure Communication
Almost Perfect Security
Perfect Security
Corresponding Threshold Model
References
Secure Computation and Secret Sharing
Constant-Round Private Function Evaluation with Linear Complexity
Introduction
Contributions of Our Work
Overview of Our Techniques
Other Related Work
Definitions
Private Function Evaluation
Tools
A C-PFE Protocol for Semi-honest Adversaries
Description of the Protocol
A More Efficient Variant
Security for Malicious Adversaries
Protocol Modifications
Conclusions and Future Work
References
Constant-Rounds, Linear Multi-party Computation for Exponentiation and Modulo Reduction with Perfect Security
Introduction
Our Results
Related Work
Preliminaries
Notations and Conventions
Known Primitives
Multi-party Computation for Private Exponentiation with BD
The Public Exponentiation Protocol
The Bit Exponentiation Protocol
The Private Exponentiation Protocol with BD
Linear Multi-party Computation for Private Exponentiation
The Private Exponentiation Protocol without BD
A Further Improvement
Further Generalization of BD and Improved Solution for Public Modulo Reduction
Discussions
Future Work
References
Computational Verifiable Secret Sharing Revisited
Introduction
Preliminaries
Adversary Model
VSS and Variants
Commitment Schemes
VSS in the Synchronous Network Model
Synchronous Communication Model
2-Round VSS for n 2t+1 from Any Commitment
(Im)possibility Results for 1-Round VSS
An Efficient 2-round VSS Using Homomorphic Commitments
VSS in the Asynchronous Communication Model
Asynchronous Communication Model
VSS for n 3t+1 from Any Commitment
Discussion and Future Work
References
Natural Generalizations of Threshold Secret Sharing
Introduction
Preliminaries
Multipartite Access Structures and Their Geometric Representation
Polymatroids and Matroids
Integer Polymatroids and Multipartite Matroid Ports
Some Useful Integer Polymatroids
Operations on Polymatroids
Boolean and Uniform Polymatroids
Multipartite Access Structures from Bases of Integer Polymatroids
Compartmented Access Structures
Compartmented Access Structures with Upper and Lower Bounds
Compartmented Compartments
Ideal Partially Hierarchical Access Structures
Ideal Hierarchical Access Structures
Partial Hierarchies from Boolean Polymatroids
Compartmented Access Structures with Hierarchical Compartments
Ideal Uniform Multipartite Access Structures
Efficiency of the Constructions of Ideal Multipartite Secret Sharing Schemes
References
Public Key Signature
Separating Short Structure-Preserving Signatures from Non-interactive Assumptions
Introduction
Background
Black-Box Separations
Our Contribution
Preliminaries
Digital Signature Scheme
Bilinear Groups
Structure Preserving Signatures
Algebraic Algorithms
Non-interactive Hardness Assumptions
Black-Box Reduction and Meta-Reduction
Crucial Relation
Crucial Relation in Size-3 SPS
Conclusion and Open Problems
References
Short Signatures from Weaker Assumptions
Introduction
Summary of Our Contributions
Details of Our Contributions
Open Problems
Preliminaries
Digital Signatures
Prime Numbers, Factoring, and the RSA Assumption
Generalized Birthday Bound
Programmable Hash Functions
Definitions
Multi-generator Programmable Hash Function
A New Deterministic Programmable Hash Function
A Randomized Programmable Hash Function
A Weak Programmable Hash Function
Signatures from the RSA Problem
Construction
References
Practical Key-Recovery for All Possible Parameters of SFLASH
Introduction
Organization of the Paper
Mathematical Background
The C* and SFLASH Signature Schemes
Mathematical Properties of C*- Public Keys
Relations between the Kernel and the Secret-Key
Relations between the Kernel and the Public Key
Relations between the Secret-Key and the Public-Key
The Attack
Complexity
References
Leakage Resilient Cryptography
The Leakage-Resilience Limit of a Computational Problem Is Equal to Its Unpredictability Entropy
Introduction and Motivation
Leakage Resilience of Cryptographic Assumptions
Complexity Notions
Our Contributions
Organization of This Paper
Definitions
Computational Search Problems
Complexity Notions
Relations between Complexity Notions for Search Problems
Two Simple Results
The Witness Compression Lemma
The Main Result
PPT Algorithms for Problems Relevant in Cryptography
Factoring and Discrete Logarithms
Lattices
Learning with Errors and Its Relation to Lattice Problems
Conclusions and Open Problems
References
Leakage-Resilient Cryptography from the Inner-Product Extractor
Introduction
Leakage Resilient Standard Cryptographic Schemes
Our Contribution
Preliminaries
Model of Leakage
Leakage-Resilient Storage
Leakage-Resilient Refreshing of LRS
Identification and Signature Schemes
A Construction of a Leakage-Resilient Identification Protocol
Leakage Resilient Encryption
Definitions
Efficient IND-CCLA2-secure Encryption
A General Paradigm for Leakage-Resilient Cryptographic Schemes
References
Program Obfuscation with Leaky Hardware
Introduction
Minimally Hardware-Assisted Obfuscation
Obfuscation Using Universal Hardware Devices
Dealing with Leaky Hardware
From OCL+ to LDS
The End-Result: Obfuscation with Leaky Hardware
Related Work
Hardware Assisted Obfuscation
The Model
The Construction
General-Purpose (Sendable) Obfuscation
The Model
The Transformation
Obfuscation with Leaky Hardware
An Overview
The LDS Model
The Construction
References
BiTR: Built-in Tamper Resilience
Introduction
Our Contributions
Related Work
BiTR Definitions
Composition of BiTR ITMs
Affine BiTR Protocols without State Encoding
UC Secure Computation from Tamperable Tokens
Katz's Commitment Scheme and its Generalization.
UC-Secure Commitment Scheme from a Tamperable Token
BiTR Protocols against General Classes of Tampering Functions
BiTR Protocols from Non-malleable Codes
Constructing Deterministic Non-malleable Codes
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken