Advances in Cryptology - ASIACRYPT 2015

Name: Advances in Cryptology - ASIACRYPT 2015 | 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 -- December 3, 2015, Proceedings, Part II
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 -- December 3, 2015, Proceedings, Part II

Tetsu Iwata Jung Hee Cheon(Herausgeber*in)

Springer (Verlag)

Erschienen am 26. November 2015

XXV, 802 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-662-48800-3 (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
Preface
ASIACRYPT 2015
Invited Talks
Structure-Preserving Cryptography
Computer-Aided Cryptography: Status and Perspectives
The Moral Character of Cryptographic Work
Contents - Part II
Contents - Part I
Attacks on ASASA
Key-Recovery Attacks on ASASA
1 Introduction
1.1 Our Contribution
1.2 Structure of the Article
1.3 Implementation and Full Version
2 Notation and Preliminaries
3 Description of ASASA schemes
3.1 Presentation and Notations
3.2 Description of the Black-Box Scheme
3.3 Description of the White-Box Scheme
3.4 Description of the -based Public-Key Scheme
4 Structural Attack on Black-Box ASASA
4.1 Attack Overview
4.2 Description of the Attack
5 Attacks on the -based Public-Key Scheme
5.1 Algebraic Attack on the Scheme
5.2 LPN-based attack on the scheme
5.3 Peeling Off the Remaining ASAS layers
6 A Practical Attack on White-Box ASASA
6.1 Attack Overview
7 Conclusion
References
Number Field Sieve
The Tower Number Field Sieve
1 Introduction
2 Overview of TNFS
3 Detailed Description and Analysis
3.1 Polynomial Selection
3.2 Relation Collection
3.3 Writing and Solving Linear Equations
3.4 Overall Complexity of the Main Phase
3.5 Individual Logarithms
4 Variants
5 Comparison for Cryptographically Relevant Sizes
5.1 The Case of General Primes
5.2 The Case of Primes of Special Shape (SNFS)
6 Cryptographic Consequences
7 Appendix: Technicalities
7.1 Special-q Sieving
7.2 Using a Cyclotomic Field for Q()
7.3 The Waterloo Improvement
References
Hashes and MACs
On the Impact of Known-Key Attacks on Hash Functions
1 Introduction
1.1 Our Contributions
1.2 Outline
2 Weak Cipher Model
2.1 Security Model
2.2 Random Weak Cipher
2.3 Random Abortable Weak Cipher
3 Modeling Known-Key Attacks
4 Application to PGV Compression Functions
4.1 Collision Security
4.2 Preimage Security
5 Application to Grøstl Compression Function
5.1 Collision Security
5.2 Preimage Security
6 Application to Shrimpton-Stam Compression Function
6.1 Collision Security
6.2 Preimage Security
7 Conclusions
A Proof of Theorem 2
References
Generic Security of NMAC and HMAC with Input Whitening
1 Introduction
2 Preliminaries
3 The Whitened NMAC Construction
3.1 Basic Notation, Message Trees and Repetition Patterns
3.2 Interactions and Transcripts
3.3 The H-Coefficient Method
3.4 Good and Bad Transcripts
3.5 Probability of a C-f-collision
3.6 Probability of Repeated Outer Invocations
3.7 Good Transcripts and Putting Pieces Together
3.8 Tightness
3.9 Distinguishing-H Security of WNMAC
3.10 State Recovery for WNMAC
4 Whitening HMAC
5 The Dual WNMAC Construction
References
Symmetric Encryption
On the Optimality of Non-Linear Computations of Length-Preserving Encryption Schemes
1 Introduction
1.1 Brief Literature Survey
1.2 Our Contribution
2 Preliminaries
2.1 Useful Properties of Matrices
2.2 Security Definitions and Notation
2.3 Tools for Proving Security
3 Linear Mode
3.1 Linear Query and Mode
3.2 Keyed Constructions Based on Linear Mode
4 PRP and SPRP Distinguishing Attacks
4.1 PRP Distinguishing Attack on E with = 2a-2
4.2 SPRP Distinguishing Attack on E with = 2a-1
5 Security Analysis of Inverse-Free Single Key Construction
5.1 PRP Attack of Single-Key Inverse-Free Constructions Without Masking
5.2 PRP Security of Single-Key Luby-Rackoff with Masking
6 Conclusion
References
Beyond-Birthday-Bound Security for Tweakable Even-Mansour Ciphers with Linear Tweak and Key Mixing
1 Introduction
2 Preliminaries
2.1 Notation and General Definitions
2.2 Security Definitions
2.3 The H-Coefficients Technique
2.4 An Extended Sum-Capture Lemma
3 Beyond-Birthday-Bound Security
3.1 Statement of the Result and Discussion
3.2 Definition and Probability of Bad Transcripts
3.3 Analysis of Good Transcripts
References
An Inverse-Free Single-Keyed Tweakable Enciphering Scheme
1 Introduction
1.1 Our Contribution
2 Preliminaries
2.1 Tweakable Encryption Schemes
2.2 Pseudorandomness and Distinguishing Games
2.3 Domain Extensions and Coefficient H Technique
3 The FMix Construction
4 TSPRP Security Analysis of FMix
4.1 Good Views and Interpolation
4.2 Extension of FMix for Partial Block Input
5 Proof of Proposition 1
5.1 Simulations
5.2 Admissibility
5.3 Basis and Extension
5.4 Extension Equations
5.5 Bringing It All Together
5.6 Proof of Lemma 1
6 Conclusion and Future Works
References
Foundations
On Black-Box Complexity of Universally Composable Security in the CRS Model
1 Introduction
1.1 Our Results
2 Preliminaries
2.1 Oblivious Transfer
2.2 UC Commitment Schemes
2.3 Extractable Commitments
3 Static UC Secure Computation
3.1 Static UC Oblivious Transfer
4 One-Sided Adaptive UC Secure Computation
5 Adaptive UC Secure Computation
5.1 UC Commitments from PKE with Oblivious Ciphertext Generation
References
Public Verifiability in the Covert Model (Almost) for Free
1 Introduction
1.1 Our Contribution
2 Preliminaries
2.1 Publicly Verifiable Covert Security
2.2 Signed Oblivious Transfer
3 Signed Oblivious Transfer Extension
3.1 Intuition for the Construction
3.2 Towards a Proof of Security
3.3 An EU-CMPRA Signature Scheme
3.4 Proof of Security
4 Our Complete PVC Protocol
5 Comparison with Prior Work
References
Limits of Extractability Assumptions with Distributional Auxiliary Input
1 Introduction
1.1 Proof Techniques
1.2 Removing Auxiliary Input in diO
1.3 Other Applications of the ``Succinct Punctured Program'' Technique
1.4 Overview of Paper
2 Preliminaries
2.1 Public-Coin Differing-Inputs Obfuscation
2.2 Extractable One-Way Functions
2.3 Succinct Non-Interactive Arguments of Knowledge (SNARKs)
2.4 Puncturable PRFs
3 Public-Coin Differing-Inputs Obfuscation or Extractable One-Way Functions
3.1 From PC-diO to Impossibility of Z-Auxiliary-Input EOWF
3.2 PC-diO or SNARKs
References
Composable and Modular Anonymous Credentials: Definitions and Practical Constructions
1 Introduction
2 Definitions of Unlinkable Redactable Signatures
2.1 Property-Based Definitions for Unlinkable Redactable Signatures
2.2 Ideal Functionality for Unlinkable Redactable Signatures
2.3 Key Registration and UC Realizability
3 The Construction of Our Redactable Signature Scheme
3.1 Vector Commitments Simplified
3.2 Non-interactive Zero-Knowledge and Witness Indistinguishable Proof Systems
3.3 Our Redactable Signature Scheme
4 From Unlinkable Redactable Signatures to Anonymous Credentials
4.1 Algorithms of Our Anonymous Credential System
4.2 Ideal Functionality for Credentials
4.3 Instantiation and Efficiency Analysis
References
Side-Channel Attacks
ASCA, SASCA and DPA with Enumeration: Which One Beats the Other and When?
1 Introduction
2 Background
2.1 Measurement Setup
2.2 Information Detection Tools
2.3 Gaussian Templates Attacks
2.4 Key Enumeration and Rank Estimation
2.5 Algebraic Side-Channel Attacks
2.6 Soft Analytical Side-Channel Attacks
3 Comparison with ASCA
3.1 Our Representation for SASCA
3.2 Comparison Setup
3.3 Experimental Results
4 SASCA Against a Concrete AES Implementation
4.1 Profiling Step
4.2 Experimental Results
5 Comparison with DPA and Enumeration
5.1 Evaluation of Profiled Template Attacks
5.2 Comparing SASCA and DPA with Enumeration
6 Conclusion and Open Problems
References
Counting Keys in Parallel After a Side Channel Attack
1 Introduction
1.1 Evaluating Resistance Against Differential Power Analysis
1.2 Problem Statement and Notation
1.3 Outline and Our Contributions
1.4 Previous Work
2 Casting the Key Enumeration as a Knapsack
3 An Accurate Key Rank Algorithm
3.1 Key Rank Graph
3.2 Counting Valid Paths
4 Parallelisable Key Enumeration Algorithm
4.1 Time Complexity
4.2 Memory Efficiency
4.3 Parallelisation
5 Practical Evaluation and Comparison with Previous Work
5.1 Evaluating and Comparing Precision
5.2 Evaluating and Comparing Run Times for Key Rank
5.3 Evaluating and Comparing Run Times for Key Enumeration
A Computing Environment
References
A Unified Metric for Quantifying Information Leakage of Cryptographic Devices Under Power Analysis Attacks
1 Introduction
2 Leakage Metrics for Cryptosystems with Masking Countermeasure
2.1 Notations and Existing First-Order Metrics
2.2 Our Proposed Information Leakage Metric
2.3 Analysis of the Metrics Under Boolean Masking
3 Relating `39`42`"613A``45`47`"603AILA to DPA and CPA Success Rates
3.1 First-Order Power Analysis Attack Model
3.2 Second-Order Power Analysis Attack Model
3.3 Approximation Errors in the Simple Success Rate Formulas
3.4 Comparing Effectiveness of the First-Order Attack and the Second-Order Attack
3.5 Extension to Higher-Order Power Analysis Attack Model
4 Numerical Results
4.1 Numerical Comparison of Metrics Versus Success Rates
4.2 Experimental Results on Physical Implementations
5 Conclusion
A Derivation of `39`42`"613A``45`47`"603AILA, `39`42`"613A``45`47`"603AQMS and `39`42`"613A``45`47`"603AMIA for DPA Model
B Derivation of `39`42`"613A``45`47`"603AILA1O and `39`42`"613A``45`47`"603AILA2O for CPA Model
C Theorem 1: and in the first-order CPA (12)
D Proof of Lemma 1
E Theorem 2: and in the Second-order CPA (12)
F Algorithms for Calculating `39`42`"613A``45`47`"603AILA1O
References
How Secure is AES Under Leakage
1 Introduction
1.1 Background: Black Box, Grey Box and White Box
1.2 Leakage and AES
1.3 Our Contributions
2 Preliminaries
2.1 Notations of AES
2.2 Dinur-Shamir Chosen-Plaintext Attack on AES-128 with Leakage
3 AES Under Leakage with Fixed Time and Space
3.1 Bitwise Multiset Characteristic
3.2 Chosen-Plaintext Bitwise Multiset Attack
3.3 Partial Key Recovery Attack Using Leaked Bits from #3
3.4 Chosen-Ciphertext Bitwise Multiset Attack
3.5 Combined Key Recovery Attacks on AES
4 Uncertainty and Differential Bias Attacks
4.1 Truncated Differential Characteristic
4.2 Biased Differential State
4.3 Bitwise Differential Bias in Biased Differential State
4.4 Bitwise Differential Biases in the Stream of Leaked Bits
4.5 Chosen-Plaintext Differential Bias Attack
4.6 Chosen-Ciphertext Differential Bias Attack
4.7 Known-Plaintext Differential Bias Attack
5 AES Under Leakage with Uncertainty in Time/Space
5.1 Uncertainty in Space
5.2 Uncertainty in Time
5.3 Uncertainty in Both Space and Time
6 AES Under Noisy Leakage
7 Towards More Alignment: Bytewise Leakage
7.1 Fixed Time/space: Bytewise Multiset Attack
7.2 Uncertain Time/Space: Differential Bias Attack
8 Some Extensions
8.1 AES-192 and 256
8.2 Multiple-Bit Leakage
8.3 Other Granularities
References
Design of Block Ciphers
A Synthetic Indifferentiability Analysis of Interleaved Double-Key Even-Mansour Ciphers
1 Introduction
2 Preliminaries and Notations
3 Indifferentiability for 15-Round IDEM
3.1 The Simulator
3.2 The Key Points of the Proof
4 Seq-indifferentiability for 7-Round IDEM
5 Conclusion
References
Midori: A Block Cipher for Low Energy
1 Introduction
1.1 Our Contributions
1.2 Organization of the Paper
2 Design Considerations for Low Energy
2.1 S-Box: 4-Bit Vs 8-Bit
2.2 Feistel Vs SPN and Complex Vs Simple Round Function
2.3 Effect of Key Schedule
2.4 Main Conclusion: Low-Energy Design Choices
3 Specification
3.1 S-Boxes and Matrices
3.2 Round Function
3.3 Data Processing Part
3.4 Round Key Generation
3.5 Midori Ciphers
4 Design Decision
4.1 Linear Layer
4.2 S-Box Layer
4.3 Key Scheduling Function
4.4 Round Constant
5 Security Evaluation
5.1 Differential/Linear Cryptanalysis
5.2 Boomerang-Type Attack
5.3 Impossible Differential Attacks
5.4 Meet-in-the-Middle Attacks
5.5 Other Attacks
6 Implementation
6.1 Evaluation
7 Conclusion
References
Optimally Secure Block Ciphers from Ideal Primitives
1 Introduction
1.1 First Contribution: Full-Domain Security
1.2 Second Contribution: Related-Key Security
2 Preliminaries
2.1 Notation
2.2 Ideal Models
2.3 Block Ciphers and (related-Key) Pseudorandomness
3 The Whitened Swap-or-Not Construction
3.1 The Construction
3.2 Security of the WSN Construction
3.3 Proof of Theorem1
4 Related-Key Security
4.1 Related-Key Secure Key Derivation
4.2 Efficient RKA-KDF-secure Construction
A Indifferentiability
B From Permutations to Functions
C Proof of Lemma3
References
Authenticated Encryption
Security of Full-State Keyed Sponge and Duplex: Applications to Authenticated Encryption
1 Introduction
2 Notations and Conventions
3 Sponge Constructions
3.1 Full-State Keyed Sponge
3.2 Full-State Keyed Duplex
4 Security Models and Tools
4.1 Adversaries and Patarin's Coefficient-H Technique
4.2 Security Models for FKS and FKD
4.3 Security Model for Even-Mansour
5 Security Analysis of FKS
6 Security Analysis of FKD
7 Full-State SpongeWrap and its Security
7.1 Authenticated Encryption for Sequences of Messages
7.2 Full-State SpongeWrap
7.3 Security of FSW
8 Discussion
References
Heuristic Tool for Linear Cryptanalysis with Applications to CAESAR Candidates
1 Introduction
2 Linear Cryptanalysis
3 An Automated Tool for Linear Cryptanalysis
3.1 Implementation Requirements for the Search Tool
3.2 Propagation of Linear Masks
3.3 Search for Linear Characteristics
4 Application to CAESAR Candidates
4.1 Keyak
4.2 Ascon
4.3 ICEPOLE
4.4 Minalpher
4.5 Prøst
5 Conclusion
References
Collision Attacks Against CAESAR Candidates
1 Introduction
2 Collision Attack Against AEZ
2.1 Short Description of AEZ
2.2 Collision Attack on AEZ
3 Description of Marble
4 A Universal Forgery Attack on Marble
4.1 Recover the Mask L
4.2 An Attack Against Marble 1.2
4.3 Computing Forgeries on Marble Without Whitening Keys
5 Key-Recovery Attack
5.1 Gathering Pairs
5.2 Extracting the Key
6 Conclusion
References
Symmetric Analysis
Optimized Interpolation Attacks on LowMC
1 Introduction
2 Preliminaries
2.1 Boolean Algebra
2.2 High-Order Differential Cryptanalysis and Interpolation Attacks
2.3 Model of Computation
3 Description of LowMC
4 A Basic 9-Round Attack on LowMC-80
4.1 The High-Order Differential Property
4.2 Bounding the Number of Variables
4.3 Obtaining the Data
4.4 The Basic Interpolation Attack
5 The Optimized Interpolation Attack
5.1 Transformation of Variables
5.2 Details of the Optimized Interpolation Attack
6 Optimized Interpolation Attacks on LowMC-80
6.1 A 9-Round Attack
6.2 A 10-Round Attack
6.3 An Attack on Full LowMC-80 for Weak Instances
7 Optimized Interpolation Attacks on LowMC-128
7.1 An 11-Round Attack and Weak Instances of LowMC-128
7.2 An Attack on Full LowMC-128
8 Conclusions
References
Another Tradeoff Attack on Sprout-Like Stream Ciphers
1 Introduction
2 Sprout-Like Stream Ciphers
2.1 Description of Sprout
2.2 A Model for Sprout-Like Stream Ciphers
3 A TMD Tradeoff Attack Framework
3.1 Pre-Processing Phase
3.2 Processing Phase
3.3 Complexity Analysis
4 Cryptanalysis of Sprout
4.1 Fitting into the Model
4.2 Cryptanalysis
4.3 Detailed Workload for x=16, y=15
5 Practical Implementation
5.1 The Reduced Version of Sprout
5.2 Attack Process
5.3 Simulation Results
6 Conclusion
References
Reverse-Engineering of the Cryptanalytic Attack Used in the Flame Super-Malware
1 Introduction
1.1 End-of-Life of a Cryptographic Primitive
1.2 Collisions for MD5
1.3 The Super-Malware `Flame'
2 Our Contributions
3 MD5 Chosen-Prefix Collision Attacks
3.1 MD5
3.2 General Approach
3.3 Differential Cryptanalysis
3.4 Differential Paths
3.5 Tunnels
4 Reverse-Engineering Flame's Attack
4.1 Breakdown of Data
4.2 Our Reconstruction of the Chosen-Prefix Collision Attack
4.3 Cost Estimation
5 Conclusion
A Flame Differential Paths
B Message Blocks and IH Vs
References
Analysis of SHA-512/224 and SHA-512/256
1 Introduction
2 Description of SHA-512 and Other SHA-2 Variants
3 Attack Strategy
3.1 Guess-and-Determine Search Tool
3.2 Finding Starting Points for SHA-2
4 Collision Attacks for Truncated SHA-512 Variants
4.1 Semi-free-start Collisions
4.2 Free-Start Collisions
4.3 Collisions
A Examples
References
Cryptanalysis
Tradeoff Cryptanalysis of Memory-Hard Functions
1 Introduction
2 Preliminaries
2.1 Syntax
2.2 Time-Space Tradeoff
2.3 Attackers and Cost Estimates
3 Cryptanalysis of Catena-Dragonfly
3.1 Description
3.2 Our Tradeoff Attack on Catena-D
3.3 Other Results for Catena
4 Generic Precomputation Tradeoff Attack
5 Generic Ranking Tradeoff Attack
6 Cryptanalysis of yescrypt
6.1 Description
6.2 Tradeoff Attack on yescrypt
7 Future Work
8 Conclusion
A Cryptanalysis of Lyra2 V1
A.1 Description of Lyra2 V1
A.2 Tradeoff Attack on the Setup and Wandering Phases of Lyra2
A.3 Tradeoff for the Full Lyra2 with T=1
References
Property Preserving Symmetric Encryption Revisited
1 Introduction
2 Definitions
2.1 Security Notions
3 Separation Results: A Closer Look
3.1 Equivalence Testing via Equality
3.2 Natural LoR Secure Equality Testing
3.3 Separation Between FtG and LoR Notions for Equality
3.4 The Bottom Line
4 Orthogonality: Relation Between FtG and LoR and with Equality
4.1 FtG2n implies LoRn
4.2 A Direct Test for Equality from Orthogonality
5 Cryptanalysis of Pandey and Rouselakis Construction
5.1 Pandey and Rouselakis Construction
5.2 A Valid FtG Adversary
5.3 Insecurity Beyond Indistinguishability
6 Concluding Remarks
A Appendix
A.1 Separation Result for Polynomial Size Message Space
A.2 Proof of Lemma1
References
Refinements of the k-tree Algorithm for the Generalized Birthday Problem
1 Introduction
2 The Generalized Birthday Problem
3 Improved Algorithm for the 3-List Problem
4 Improved Time-Memory Tradeoffs
4.1 Improved Time-Memory Tradeoffs for the 4-List Problem
4.2 Improved Time-Memory Tradeoff for the k-list Problem
5 Conclusion
References
How to Sequentialize Independent Parallel Attacks?
1 Introduction
2 The STEP Game
3 Optimal Strategy
3.1 Proof of Theorem17
3.2 Proof of Theorem21
3.3 Finding the Optimal m
4 Applications
4.1 Solving Sparse LPN
4.2 Password Recovery
5 On the Phase Transition
6 Conclusions
A Composite Distributions
B Proof of Lemma25
References
Privacy and Lattices
Pure Differential Privacy for Rectangle Queries via Private Partitions
1 Introduction
1.1 Differentially Private Query Release: Interval and Rectangle Queries
1.2 Counting Under Continual Observation
1.3 Differentially Private Online Partition
2 Differentially Private Online Partition
3 From Partitions to Counting, Intervals and Rectangles
3.1 Online Counting Under Continual Observation
3.2 Interval Queries
3.3 Rectangle Queries
References
Implementing Candidate Graded Encoding Schemes from Ideal Lattices
1 Introduction
2 Preliminaries
3 GGH-like Asymmetric Graded Encoding Scheme
3.1 Using GGH to Construct Jigsaw Puzzles
4 Modifications to and Parameters for GGH-like Schemes
4.1 Non-prime (g)
4.2 Reducing the size of q
4.3 Lattice Attacks
4.4 Putting Everything Together
5 Implementation
5.1 Polynomial Multiplication in Zq[X]/(X**n+1)
5.2 Computing Norms in Z[X]/(X**n+1)
5.3 Checking if (g) is a prime ideal
5.4 Verifying that ,[2]1) = (g)
5.5 Computing the Inverse of a Polynomial Modulo X**n+1
5.6 Small Remainders
5.7 Sampling from a Discrete Gaussian
5.8 Approximate Square Roots
References
New Circular Security Counterexamples from Decision Linear and Learning with Errors
1 Introduction
2 Preliminaries
2.1 The k-LIN Assumption
2.2 Lattices and LWE
3 Security Definitions
3.1 Circular Security
4 A Framework for Generating Circular Counterexamples
4.1 Proving IND-CCA Security via a Sequence of Games
4.2 Adversary's Probability of Outputting 1 in These Games
5 A 2-Cycle Tester from the k-DLIN Assumption
6 A 2-Cycle Tester from Learning with Errors
6.1 Construction
6.2 IND-CPA Security of the Tester
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken