Provable and Practical Security: 17th International Conference, ProvSec 2023, Wuhan, China, October 20–22, 2023, Proceedings (Lecture Notes in Computer Science)

Preface
Organization
Contents
Fundamentals and Cryptographic Primitives
Efficient Zero-Knowledge Arguments for Matrix Relations over Rings and Non-malleable Enhancement
	1 Introduction
		1.1 Basic Problems and Related Works
	2 Preliminaries
		2.1 Zero-Knowledge Proofs/Arguments
		2.2 Commitment Scheme
		2.3 Basic Facts About Galois Ring
		2.4 Vector Commitments over Galois Ring
	3 Efficient ZKA Protocol for Matrix Relation A U=B
		3.1 Basics
		3.2 Compressed Protocol with Logarithmic Message Complexity
		3.3 Vector-Oriented Approach and Comparisons
		3.4 Matrix-Oriented Construction
	4 Concurrently Non-malleable Enhancement
		4.1 Basic Tools
		4.2 Concurrently Non-malleable ZKA Protocol
		4.3 Concurrently Non-malleable ZKA Protocol\'s Construction
	5 Summaries and Future Works
	References
Reversible Data Hiding in Encrypted Images Based on Block Classification Coding of Sparse Representation
	1 Introduction
	2 Proposed Scheme
		2.1 Image Encryption
		2.2 Data Hiding in Encrypted Images
		2.3 Data Extraction and Image Recovery
	3 Experimental Results and Analysis
		3.1 Analysis of Adaptive Threshold
		3.2 Comparison and Analysis with Related Methods
	4 Conclusion
	References
Signcryption-Based Encrypted Traffic Detection Scheme for Fast Establishing Secure Connections
	1 Introduction
	2 System Overview
		2.1 System Model
		2.2 Threat Model
	3 The Proposed System
		3.1 Rule Signcryption Algorithm
		3.2 Preprocessing Protocol
		3.3 Session Rule Generation Algorithm
		3.4 Client Signcryption Message Algorithm
		3.5 Token Detection
		3.6 Token Validation
	4 Scheme Analysis
		4.1 Formal Security Model
		4.2 Correctness Analysis
		4.3 Security Analysis
	5 Efficiency Analysis
		5.1 Theoretical Efficiency Analysis
		5.2 Experiment Analysis
	6 Conclusion
	References
Cryptanalysis
Improved Key-Recovery Attacks Under Imperfect SCA Oracle for Lattice-Based KEMs
	1 Introduction
	2 Preliminaries
		2.1 Lattices
		2.2 Lattice Algorithms
		2.3 The Learning with Errors (LWE) Problem
		2.4 Kyber
	3 Previous PC-Based Side-Channel-Attack Against Kyber and Our Main Strategy
		3.1 Previous PC-Based Side-Channel-Attack Against Kyber
		3.2 Our Main Strategy
	4 Analysis with Respect to Known Attacks
		4.1 Primal Attack
		4.2 Dual Attack
		4.3 Meet in the Middle Attack
		4.4 Decoding Approach
		4.5 Hybrid Dual Attack
	5 Solving LWE for Different Accuracy Levels
	6 Estimating the Security for Different Accuracy Levels
	7 Conclusions
	References
Linear Cryptanalysis of Lightweight Block Cipher WARP
	1 Introduction
	2 A Brief Review of WARP
	3 SAT-Based Automatic Search Algorithms for WARP
	4 Linear Cryptanalysis on 23-Round WARP
	5 Conclusion
	References
Linicrypt in the Ideal Cipher Model
	1 Introduction
	2 Preliminaries
		2.1 Ideal Cipher Model
		2.2 Linicrypt
	3 Characterizing Collision Resistance
		3.1 Efficiently Finding Collision Structures
	4 Rate-1 Compression Functions
	5 Discussion
	6 Conclusion and Future Work
	A Missing Proofs
	B Motivating Example
	References
Signature
SMHSDVS: A Secure and Mutual Heterogeneous Strong Designated Signature Between PKI and IBC
	1 Introduction
	2 Related Work
	3 The SMHDVS Scheme
		3.1 Setup and KeyGen Algorithm
		3.2 PKIIBC HSDVSS
		3.3 IBCPKI HSDVSS
	4 Security
		4.1 Correctness
		4.2 Non-Transferability
		4.3 The Security Model of Unforgeability
		4.4 Strongness
		4.5 Source-Hiding
		4.6 Non-delegatability
	5 Performance
	6 Conclusion
	References
Key-Range Attribute-Based Signatures for Range of Inner Product and Its Applications
	1 Introduction
		1.1 Contribution
	2 Preliminaries
		2.1 Non-Interactive Witness Indistinguishable Proof (NIWI)
		2.2 Linearly Homomorphic Signatures (LHS) ch8BFKW09,ch8ALP13
		2.3 Append-Only Signatures (AOS) ch8KMPR05
	3 Key-Range ABS for Range of Inner-Product (KARIP)
	4 Our 1st Generic Construction of KARIP
		4.1 Construction
		4.2 Our AOS Scheme
		4.3 Instantiation
	5 Our 2nd Construction of KARIP
		5.1 Construction
		5.2 Instantiation
	6 Our 3rd Construction of KARIP
		6.1 Construction
		6.2 Instantiation
	7 Applications of KARIP
	Appendix 1 Formal Definition of the Covering Algorithm Cover
	References
A Certificateless Aggregate Signature Scheme with Better Security
	1 Introduction
	2 Certificateless Aggregate Signature Scheme
		2.1 Formal Definition
		2.2 Security Model
	3 Our Proposed CLAS Scheme
		3.1 Concrete Construction
		3.2 Security Proof
	4 Conclusions
	References
Constant-Size Group Signatures with Message-Dependent Opening from Lattices
	1 Introduction
	2 Background
		2.1 Decompositions
		2.2 Lattice Problems
		2.3 Constant-Size Group Signature with Message-Dependent Opening from Lattices
		2.4 Stern-Like Protocols for Lattices
	3 The Underlying Zero-Knowledge Argument System
		3.1 Zero-Knowledge Protocol for the CSGS-MDO Scheme
	4 Scheme Construction
	5 Analysis of the Scheme
		5.1 Security
		5.2 Efficiency and Correctness
	6 Conclusion
	References
Post-quantum Sigma Protocols and Signatures from Low-Rank Matrix Completions
	1 Introduction
	2 Preliminaries
		2.1 Hard Problems
		2.2 Commitment Schemes
	3 Sigma Protocol and LRMC-Based Construction
		3.1 Standard Sigma Protocol Based on LRMC
		3.2 Sigma Protocol with Helper Based on LRMC
		3.3 Removing the Helper
		3.4 Optimizations
	4 Signature and LRMC-Based Construction
		4.1 From Sigma Protocol to Signature
		4.2 Evaluation of the Signature Scheme
	5 Conclusion
	References
Threshold Ring Signature Scheme from Cryptographic Group Action
	1 Introduction
	2 Preliminaries
		2.1 -Protocol
		2.2 Threshold Ring Signature Scheme
		2.3 Group Actions
		2.4 Isogenies and Ideal Class Group Actions
		2.5 Lattices
	3 Threshold -Protocol from OR-Proof of Group Action
		3.1 Base Threshold OR-Proof of Group Action
		3.2 Construction
		3.3 Security Proof
	4 Threshold Ring Signature Scheme from OR-Proof of Group Action
	5 Instantiations
		5.1 Isogeny-Based
		5.2 Lattice-Based
	References
Encryption
Homomorphic Witness Encryption from Indistinguishable Obfuscation
	1 Introduction
	2 Preliminaries
		2.1 Notations and Conventions
		2.2 Public Key Encryption for NPInstance
		2.3 Indistinguishability Obfuscation
		2.4 SSS-Noninteractive Zero-Knowledge Proofs
	3 Homomorphic Witness Encryption
	4 HWE from Indistinguishability Obfuscation
	5 MHWE for Subset-Sum
		5.1 Multiplicatively Homomorphic Witness Encryption
	6 Discussion
	7 Conclusion
	References
Identity-Based Matchmaking Encryption Secure Against Key Generation Center
	1 Introduction
		1.1 Background and Motivation
		1.2 Our Contribution
		1.3 Related Works
		1.4 Organization
	2 Preliminaries
		2.1 Notation
		2.2 Digital Signature
		2.3 Bilinear Groups
	3 Blind Identity-Based Matchmaking Encryption with Certified Identities
	4 Construction Based on Bilinear Groups
	5 Security Analysis
	6 Experimental Result
	References
Multi-input Functional Encryption for Unbounded Inner Products
	1 Introduction
	2 Preliminaries
		2.1 Notation
		2.2 Bilinear Groups and Related Assumptions
		2.3 Multi-input IPFE with Variable Vector Size
	3 Our Variable Vector Length MIPFE Scheme
		3.1 Construction
		3.2 Proof of Security
	4 Conclusion
	References
FleS: A Compact and Parameter-Flexible Supersingular Isogeny Based Public Key Encryption Scheme
	1 Introduction
	2 Preliminaries
		2.1 Supersingular Elliptic Curves and Isogenies
		2.2 Class Group Action
		2.3 CSIDH
		2.4 Public Key Encryption
		2.5 Pohlig-Hellman Algorithm
	3 Our Scheme
		3.1 Overlook
		3.2 The FleS Public Key Encryption Scheme
		3.3 Finding the Point of Wanted Order
		3.4 Correctness Analysis
	4 Security Analysis
		4.1 Some Concepts and Theorems
		4.2 Security Proof
	5 Implementation Result
	6 Conclusion and Future Work
	References
A New Revocable Attribute Based Encryption on Lattice
	1 Introduction
		1.1 Related Work
		1.2 Contribution
		1.3 Paper Organization
	2 Preliminaries
		2.1 Notations
		2.2 Lattice
		2.3 Related Algorithms
		2.4 The LWE Hardness Assumption
		2.5 Binary Tree
		2.6 LSSS
	3 System Model and Security Model
		3.1 System Architecture
		3.2 Model Definition
		3.3 Security Model
	4 Construction of RL-ABE Scheme
	5 Correctness and Parameter Analysis
		5.1 Correctness
		5.2 Update Ciphertext
		5.3 Parameters
	6 Security Analysis
	7 Performance Analysis
	8 Conclusion
	References
An Efficient Keyword-Based Ciphertext Retrieval Scheme
	1 Introduction
	2 Preliminaries
	3 The Proposed Scheme
		3.1 System Model
		3.2 Attack Model
		3.3 Design Objects
		3.4 Scheme Details
	4 Correctness Analysis
	5 Confidentiality Analysis
	6 Experiment
		6.1 Experiment Evaluation
		6.2 Performance Analysis
	7 Conclusion
	References
Privacy Preservation
Privacy Preserving Outsourced K-means Clustering Using Kd-tree
	1 Introduction
		1.1 Our Contribution
	2 Preliminary
		2.1 Additive Secret Sharing
		2.2 K-means Clustering Based on Kd-tree
	3 System Model and Design Goal
		3.1 System Model
		3.2 Threat Model
		3.3 Design Goals
	4 Building Blocks
		4.1 Secure Euclidean Distance (SED)
		4.2 Secure Comparison (SC)
		4.3 Secure Minimum (SMin(S/L))
		4.4 Secure Filtering (SF)
	5 The Proposed Secure Clustering Scheme
		5.1 Privacy-Preserving Outsourced K-means Clustering Scheme
		5.2 Discussion
	6 Security Analysis
	7 System Evaluation and Performance Analysis
		7.1 Experimental Setup
		7.2 Datasets
		7.3 Experiments for Real-World Dataset
		7.4 Experiments for Synthetic Dataset
	8 Related Work
	9 Conclusion
	References
Fuzzy Deduplication Scheme Supporting Pre-verification of Label Consistency
	1 Introduction
	2 Preliminaries
		2.1 Hamming Distance and Threshold
		2.2 Perceptual Hashing
		2.3 Hash Collisions
		2.4 Zero-Knowledge Proof
	3 Models and Design Goals
		3.1 System Model
		3.2 Threat Model
		3.3 Design Goals
	4 Proposed Scheme
		4.1 Upload Preparation
		4.2 First Upload
		4.3 Deduplication
		4.4 Download
	5 Security Analysis
		5.1 Data Confidentiality
		5.2 Brute-Force Attacks Resistance
		5.3 Resistance to Replay Attacks
		5.4 Collusion Resistance
		5.5 Tag Consistency
	6 Experiment and Performance Analysis
		6.1 Simulation Settings
		6.2 Simulation Results
	7 Conclusion and Discussion
	References
A Privacy-Preserving Takeaway Delivery Service Scheme
	1 Introduction
	2 Related Work
	3 Preliminaries
		3.1 Homomorphic Encryption
		3.2 Non-interactive Key Exchange
		3.3 Identity-Based Elgamal Signature
		3.4 Manhattan Distance
		3.5 Improved Point Location Judgment
	4 Scheme Design
		4.1 The Description of System
		4.2 Privacy Threat Model
		4.3 The PP-TDS Protocol
	5 Security Analysis
		5.1 Privacy Analysis
		5.2 Manhattan Distance
	6 Performance Evaluation
		6.1 Computational Cost
		6.2 Communication Overhead
		6.3 Experiment Evaluation
	7 Conclusion
	References
Blockchain Security
CDRF: A Detection Method of Smart Contract Vulnerability Based on Random Forest
	1 Introduction
	2 Related Work
	3 Preliminaries
		3.1 Ethereum
		3.2 Smart Contract Bytecode and Opcode
		3.3 Vulnerability Introduction.
	4 Detection Models
		4.1 Data Preprocessing
		4.2 Feature Extraction
		4.3 Opcode Fragment Extraction
		4.4 Training Sets, Classification Algorithms and Model Selection
	5 Experiment
		5.1 Experiment Setup
		5.2 Test Sets and the Comparison of Classifiers
		5.3 Model Analysis
	6 Analysis and Discussion
	7 Conclusion
	References
simuBits: Pool Security Verification of Novel Mining Attacks
	1 Introduction
		1.1 Related Work
		1.2 Contribution
	2 Preliminary
		2.1 BWH Attack
		2.2 BWD Attack
		2.3 Man-in-the-Middle Attack
	3 Combined Attacks
		3.1 BWH with Man-in-the-Middle
		3.2 BWD with Man-in-the-Middle
	4 Simulation System
	5 Pool Attacks in simuBits
	6 Countermeasures
		6.1 BWH Attack Defense Verification
		6.2 Combined Attack Defense Verification
	7 Conclusion
	References
Author Index