Zhengyi Li, Yakai Wang, Jingwen Leng, Kang Yang, Yu Yu, Jiaping Gui, Yu Feng, Ning Liu, Minyi Guo. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Probabilistic truncation has been widely used in a broad range of privacy-preserving machine learning (PPML) platforms, such as EdaBits (Crypto 20), ABY 2.0 (Usenix 21), Crypten (NIPS 21), Piranha-Falcon (Usenix 22), and Bicoptor (S&P 23), etc. In this work, we examine the problems of common probabilistic truncation protocols in PPML, and propose solutions from the perspectives of accuracy and efficiency. With regard to accuracy, we found the recommended precision parameters in many existing works are incorrect, leading to extremely low inference accuracy. We conducted a thorough analysis of their open-source code and found that their errors were mainly caused by simplified implementation; more specifically, random numbers are not correctly sampled in probabilistic truncation protocols. Based on this, we provide a detailed theoretical analysis to validate our views. With regard to efficiency, we identify limitations in the state-of-the-art secure comparison, Bicoptor’s (S&P 2023) DReLU protocol, which relies on the probabilistic truncation and is heavily constrained by the security parameter to eliminate errors, significantly impacting its performance. To address these challenges, we introduce a non-interactive deterministic truncation technique, replacing the original probabilistic truncation. Additionally, we propose a new technique for speeding up the ReLU/DReLU evaluation, which can be applied to the other non-linear functions as well. When the input size of DReLU is reduced to 7 bits, we can speed up approximately 5x the ReLU protocols w.r.t. ABY3, ABY2.0, EdaBits, and Bicoptor without compromising model accuracy. The improved protocol can complete a ReLU evaluation within 2 rounds and 704 bits overall communication when the input/output is secretly shared over the 64-bit ring, which yields a 92% communication reduction on original Bicoptor. Compared to existing PPML platforms with GPU acceleration, our benchmark indicates a 10x improvement in the DReLU protocol, and a 6x improvement in the ReLU protocol over Piranha-Falcon and a 3.7x improvement over Bicoptor. As a result, the overall PPML model inference could be sped up by 3-4 times.

We introduce the notion of committed vector oblivious linear evaluation (C-VOLE), which allows a party holding a pre-committed vector to generate VOLE correlations with multiple parties on the committed value. It is a unifying tool that can be found useful in zero-knowledge proofs (ZKPs) of committed values, actively secure multi-party computation, private set intersection (PSI), etc.

The wide deployment of the generative pre-trained transformer (GPT) has raised privacy concerns for both clients and servers. While cryptographic primitives can be employed for secure GPT inference to protect the privacy of both parties, they introduce considerable performance overhead. To accelerate secure inference, this study proposes a public decoding and secure verification approach that utilizes public GPT models, motivated by the observation that securely decoding one and multiple tokens takes a similar latency. The client uses the public model to generate a set of tokens, which are then securely verified by the private model for acceptance. The efficiency of our approach depends on the acceptance ratio of tokens proposed by the public model, which we improve from two aspects: (1) a private sampling protocol optimized for cryptographic primitives and (2) model alignment using knowledge distillation. Our approach improves the efficiency of secure decoding while maintaining the same level of privacy and generation quality as standard secure decoding. Experiments demonstrate a $2.1\times \sim 6.0\times$ speedup compared to standard decoding across three pairs of public-private models and different network conditions.

Abstract We propose a generic compiler that can convert any zero-knowledge (ZK) proof for SIMD circuits to general circuits efficiently, and an extension that can preserve the space complexity of the proof systems. Our compiler can immediately produce new results improving upon state of the art. By plugging in our compiler to Antman, an interactive sublinear-communication protocol, we improve the overall communication complexity for general circuits from $$\mathcal {O}(C^{3/4})$$ O ( C 3 / 4 ) to $$\mathcal {O}(C^{1/2})$$ O ( C 1 / 2 ) . Our implementation shows that for a circuit of size $$2^{27}$$ 2 27 , it achieves up to $$83.6\times $$ 83.6 × improvement on communication compared to the state-of-the-art implementation. Its end-to-end running time is at least $$70\%$$ 70 % faster in a 10Mbps network. Using the recent results on compressed $$\varSigma $$ Σ -protocol theory, we obtain a discrete-log-based constant-round zero-knowledge argument with $$\mathcal {O}(C^{1/2})$$ O ( C 1 / 2 ) communication and common random string length, improving over the state of the art that has linear-size common random string and requires heavier computation. We improve the communication of a designated n -verifier zero-knowledge proof from $$\mathcal {O}(nC/B+n^2B^2)$$ O ( n C / B + n 2 B 2 ) to $$\mathcal {O}(nC/B+n^2)$$ O ( n C / B + n 2 ) . To demonstrate the scalability of our compilers,

Abstract Actively secure two-party computation (2PC) is one of the canonical building blocks in modern cryptography. One main goal for designing actively secure 2PC protocols is to reduce the communication overhead, compared to semi-honest 2PC protocols. In this paper, we make significant progress in closing this gap by proposing two new actively secure constant-round 2PC protocols, one with one-way communication of $$2\kappa +5$$ 2 κ + 5 bits per AND gate (for $$\kappa $$ κ -bit computational security and any statistical security) and one with total communication of $$2\kappa +\rho +5$$ 2 κ + ρ + 5 bits per AND gate (for $$\rho $$ ρ -bit statistical security). In particular, our first protocol essentially matches the one-way communication of semi-honest half-gates protocol. Our optimization is achieved by three new techniques: The recent compression technique by Dittmer et al. (Crypto 13510:57–87, 2022) shows that a relaxed preprocessing is sufficient for authenticated garbling that does not reveal masked wire values to the garbler. We introduce a new form of authenticated bits and propose a new technique of generating authenticated AND triples to reduce the one-way communication of preprocessing from $$5\rho +1$$ 5 ρ + 1 bits to 2 bits per AND gate for $$\rho $$ ρ -bit statistical security. Unfortunately, the above compressing technique is only compatible with a less compact authenticated garbled circuit of size $$2\kappa +3\rho $$ 2 κ + 3 ρ bits per AND gate. We designed a new authenticated garbling that does not use information-theoretic MACs but rather dual execution without leakage to authenticate wire values in the circuit. This allows us to use a more compact half-gates based authenticated garbled circuit of size $$2\kappa +1$$ 2 κ + 1 bits per AND gate, and meanwhile keep compatible with the compression technique. Our new technique can achieve one-way communication of $$2\kappa +5$$ 2 κ + 5 bits per AND gate. In terms of total communication, we notice that the communication overhead of the consistency checking method by Dittmer et al. (Crypto 13510:57–87, 2022) can be optimized by adding one-round of interaction and utilizing the Free-XOR property. This reduces the online communication from $$2\kappa +3\rho $$ 2 κ + 3 ρ bits down to $$2\kappa +\rho +1$$ 2 κ + ρ + 1 bits per AND gate. Combined with our first contribution, this yields total amortized communication of $$2\kappa +\rho +5$$ 2 κ + ρ + 5 bits.

Private Function Encryption (PFE) enables two parties, one holding a private input$x$and the other in possession of a private function$f$, to compute$f(x)$in such that each party learns nothing substantial beyond$f(x)$. PFE is typically achieved by evaluating Yao's two-party computation protocol over a universal circuit that encodes the private function into a private input. Thus, the efficiency of the PFE protocol highly relies on the size of the underlying universal circuit. A universal circuit (UC) is a general-purpose circuit that can simulate arbitrary circuits (up to a certain size$n$). In 1976, Valiant provided a recursive construction of universal circuits and gave a theoretical construction of UC of asymptotic (multiplicative) size$4.75 n\log n$respectively, which matches the asymptotic lower bound$\Omega (n\log n)$up to some constant factor. More recently, (Kiss et al. 2016) validated the practicality of universal circuits in real-world privacy-preserving applications. Subsequent work by (Günther et al. 2017) and (Alhassan et al. 2020) enhanced UCs’ practicality through hybrid constructions with various optimizations. This work focuses on optimizing the size efficiency of universal circuits. Our contributions are three-fold:•Optimized component:We first optimize the underlying component of Valiant's universal circuits to achieve an asymptotic size of$4.5 n\log n$4.5nlogn.•More efficient framework:We propose an improved framework for constructing universal circuits, under which we give a UC construction of asymptotic size$3n\log n$3nlogn. This improves the previous state-of-the-art construction by 33%, which corresponds to the same fraction of reduction in the communication cost of UC-based PFE protocols.•Tigher lower bound:To complement our constructive results, we show that the (multiplicative) size of the universal circuits is lower bounded by$2n\log n$2nlogn.We implement the 2-way universal circuits and evaluate their performance against other implementations, confirming our theoretical analysis.

Private Set Intersection (PSI) allows two mutually distrusting parties to compute the intersection of their sets without revealing any additional information, and has found numerous applications. A part of applications require labeled PSI in the unbalanced setting, where a server holds a label for each item in a set that is much larger than the set held by a client, and the client obtains the intersection and the corresponding labels. In this paper, we present a new concretely efficient labeled PSI protocol in the unbalanced setting, without using computation-heavy homomorphic encryption. Our protocol is based on Distributed Point Function (DPF) with hardware acceleration from fixed-key AES-NI, and has communication complexity linear in the size of a small set of the client and sublinear in the size of a large set of the server. Our protocol exploits two Oblivious Pesudorandom Function (OPRF) protocols, based on Diffle-Hellman PRFs or block ciphers, to achieve a trade-off between computation and communication. Our implementation demonstrates that our protocol outperforms the previous labeled and unbalanced PSI protocols. In particular, for two sets with respective$2^{24}$and 1 items, where each item has a 32-byte label, our protocol takes 1.19 seconds for an end-to-end performance, resulting in$26 \times $improvement compared to the state-of-the-art protocol by Cong et al. (CCS 2021). In terms of the cost of the one-time initialization, we speed up the computations more than$325\times $in the above comparison.

Through tremendous efforts, the communication cost of secure multi-party computation (MPC) in the honest-majority setting has been significantly improved. In particular, the state-of-the-art honest-majority MPC protocol by Escudero et al. (CCS'22) takes 12 field elements in total per multiplication gate for arithmetic circuits in the online phase. However, it still requires$12 log (5n/4$) bits of online communication per AND gate for Boolean circuits. That is, for Boolean circuits, no MPC protocol with constant online communication is known. In this paper, we present an unconditionally secure MPC protocol for Boolean circuits in the honest-majority setting, which has constant online communication complexity and the offline communication complexity linear to the number$n$of parties. We first describe the semi-honest MPC protocol and then show how to extend it to achieve malicious security, where the maliciously secure protocol has the same communication cost as the semi-honest protocol. In particular, our protocol achieves the amortized communication cost 36 bits per AND gate in the online phase and 30n + 24 bits per AND gate in the offline phase.

Transformer models have gained significant attention due to their power in machine learning tasks. Their extensive deployment has raised concerns about the potential leakage of sensitive information during inference. However, when being applied to Transformers, existing approaches based on secure two-party computation (2PC) bring about efficiency limitations in two folds: (1) resource-intensive matrix multiplications in linear layers, and (2) complex non-linear activation functions like $\mathsf{GELU}$ and $\mathsf{Softmax}$. This work presents a new two-party inference framework $\mathsf{Nimbus}$ for Transformer models. Specifically, we propose a new 2PC paradigm to securely compute matrix multiplications based on an outer-product insight, which achieves $2.9\times \sim 12.5\times$ performance improvements compared to the state-of-the-art (SOTA) protocol. Furthermore, through a new observation of utilizing the input distribution, we propose an approach of low-degree polynomial approximation for $\mathsf{GELU}$ and $\mathsf{Softmax}$, which improves the performance of the SOTA polynomial approximation by $2.9\times \sim 4.0\times$, where the average accuracy loss of our approach is 0.08\% compared to the non-2PC inference without privacy. Compared with the SOTA two-party inference, $\mathsf{Nimbus}$ improves the end-to-end performance of $BERT_{base}$ inference by $2.7\times \sim 4.7\times$ across different network settings.

Secure two-party computation (2PC) in the RAM model has attracted huge attention in recent years. Most existing results only support semi-honest security, with the exception of Keller and Yanai (Eurocrypt 2018) with very high cost. In this paper, we propose an efficient RAM-based 2PC protocol with active security and one-bit leakage.1)We propose an actively secure protocol for distributed point function (DPF), with one-bit leakage, that is essentially as efficient as the state-of-the-art semi-honest protocol. Compared with previous work, our protocol takes about 50× less communication for a domain with 220entries, and no longer requires actively secure generic 2PC.2)We extend the dual-execution protocol to allow reactive computation, and then build a RAM-based 2PC protocol with active security on top of our new building blocks. The protocol follows the paradigm of Doerner and shelat (CCS 2017). We are able to prove that the protocol has end-to-end one-bit leakage.3)Our implementation shows that our protocol is almost as efficient as the state-of-the-art semi-honest RAM-based 2PC protocol, and is at least two orders of magnitude faster than prior actively secure RAM-based 2PC without leakage, providing a realistic trade-off in practice.

The overhead of non-linear functions dominates the performance of the secure multiparty computation (MPC) based privacy-preserving machine learning (PPML). This work introduces a family of novel secure three-party computation (3PC) protocols, Bicoptor, which improve the efficiency of evaluating non-linear functions. The basis of Bicoptor is a new sign determination protocol, which relies on a clever use of the truncation protocol proposed in SecureML (S&P 2017). Our 3PC sign determination protocol only requires two communication rounds, and does not involve any preprocessing. Such sign determination protocol is well-suited for computing non-linear functions in PPML, e.g. the activation function ReLU, Maxpool, and their variants. We develop suitable protocols for these non-linear functions, which form a family of GPU-friendly protocols, Bicoptor. All Bicoptor protocols only require two communication rounds without preprocessing. We evaluate Bicoptor under a 3-party LAN network over a public cloud, and achieve more than 370,000 DReLU/ReLU or 41,000 Maxpool (find the maximum value of nine inputs) operations per second. Under the same settings and environment, our ReLU protocol has a one or even two orders of magnitude improvement to the state-of-the-art works, Falcon (PETS 2021) or Edabits (CRYPTO 2020), respectively without batch processing.

Multi-user (mu) security considers large-scale attackers that, given access to a number of cryptosystem instances, attempt to compromise at least one of them. We initiate the study of mu security of the so-called GGM tree that stems from the pseudorandom generator to pseudorandom function transformation of Goldreich, Goldwasser, and Micali, with a goal to provide references for its recently popularized use in applied cryptography. We propose a generalized model for GGM trees and analyze its mu prefix-constrained pseudorandom function security in the random oracle model. Our model allows to derive concrete bounds and improvements for various protocols, and we showcase on the Bitcoin-Improvement-Proposal standard Bip32 hierarchical wallets and function secret sharing protocols. In both scenarios, we propose improvements with better performance and concrete security bounds at the same time. Compared with the state-of-the-art designs, our SHACAL3 - and Keccak -p-based Bip32 variants reduce the communication cost of MPC-based implementations by 73.3% to 93.8%, whereas our AES -based function secret sharing substantially improves mu security while reducing computations by 50%.

Abstract The Learning Parity with Noise (LPN) problem represents the average-case analogue of the NP-Complete problem “decoding linear codes”, and it has been extensively studied in learning theory, coding theory and cryptography with applications to quantum-resistant cryptographic schemes. However, LPN also suffers from large public key size which is the common drawback that hinders code-based cryptography from being practical. In this paper, we study a sparse variant of LPN whose public matrix consists of sparse vectors instead of following uniform distribution. We show a win–win argument that at least one of the following assumption is true: (i) either the hardness of sparse LPN is implied by that of the standard LPN under the same noise rate; (ii) or there exists new black-box constructions of public-key encryption schemes and oblivious transfer protocols from standard LPN. Since the second assumption relies on the infeasible noise regimes for LPN-based public-key cryptography, we believe that the first assumption is more likely to hold, i.e. sparse LPN is as hard as standard LPN. Finally, we give a (heuristic) method to further compress the sparse public matrix by evaluating pseudorandom functions with keys made public, whose security again resorts to the aforementioned win–win technique.

Secure search looks for and retrieves records from a (possibly cloud-hosted) encrypted database while ensuring the confidentiality of the queries. Researchers are paying increasing attention to secure search in recent years due to the growing concerns about database privacy. However, the low efficiency of (especially multiplicative) homomorphic operations in secure search has hindered its deployment in practice. To address this issue, Akavia et al. [CCS 2018, PETS 2019] proposed new protocols that bring down the number of multiplications in the search algorithm from O(n2) to O(n log2 n), and then to O(n log n), where n is the size of the database.

Many implementations of secure computation use fixed-key AES (modeled as a random permutation); this results in substantial performance benefits due to existing hardware support for AES and the ability to avoid recomputing the AES key schedule. Surveying these implementations, however, we find that most utilize AES in a heuristic fashion; in the best case this leaves a gap in the security proof, but in many cases we show it allows for explicit attacks.Motivated by this unsatisfactory state of affairs, we initiate a comprehensive study of how to use fixed-key block ciphers for secure computation-in particular for OT extension and circuit garbling-efficiently and securely. Specifically: · Weconsider several notions of pseudorandomness for hash functions (e.g., correlation robustness), and show provably secure schemes for OT extension, garbling, and other applications based on hash functions satisfying these notions. · We provide provably secure constructions, in the (non-programmable) random-permutation model, of hash functions satisfying the different notions of pseudorandomness we consider. Taken together, our results provide end-to-end security proofs for implementations of secure-computation protocols based on fixed-key block ciphers (modeled as random permutations). Perhaps surprisingly, at the same time our work also results in noticeable performance improvements over the state-of-the-art.

The authors analyse the security of K eccak (the winner in SHA‐3 competition) by focusing on the zero‐sum distinguishers of its underlying permutation (named K eccak ‐ f ). The authors’ analyses are developed by using the division property, a generalised integral property that was initially used in the integral cryptanalysis of symmetric‐key algorithms. Following the work pioneered by Todo at CRYPTO 2015, they first formalise and prove a more delicate propagation rule of the division property under the assumption that the S‐box's specification is known to attackers. Then, they apply this rule to the inverse S‐box in K eccak ‐ f with a further study on properties of its algebraic degree. They find that the rate of decline in the division property is gentler than that of a randomly chosen S‐box. Meanwhile, they get the same results for the S‐box in A scon permutation. Thanks to this vulnerable property, they can improve the higher‐order differential characteristics against the inverse of K eccak ‐ f in terms of the required number of chosen plaintexts. As an application, they give new zero‐sum distinguishers on full 24‐round K eccak ‐ f of size . To the authors’ knowledge, this is currently the best zero‐sum distinguishers of full‐round K eccak ‐ f permutation. Incidentally, they give the corresponding results for 12‐round A scon permutation.

Code-based masking schemes have been shown to provide higher theoretical security guarantees than Boolean masking. In particular, one interesting feature put forward at CARDIS 2016 and then analyzed at CARDIS 2017 was the socalled security order amplification: under the assumption that the leakage function is linear, it guarantees that an implementation performing only linear operations will have a security order in the bounded moment leakage model larger than d - 1, where d is the number of shares. The main question regarding this feature is its practical relevance. First of all, concrete block ciphers do not only perform linear operations. Second, it may be that actual leakage functions are not perfectly linear (raising questions regarding what happens when one deviates from such assumptions). In this paper, we show that the issue of only linear operations can be provably avoided and that it is possible to obtain security order amplification for any functionality to implement. We then show that (not so) slightly non-linear leakage functions do not annihilate the nice properties (i.e., that the code-based schemes we consider remain interesting compared to the Boolean masking). We conclude with a performance evaluation of the proposals, showing that the performance overheads are moderate for a reasonable number of shares (we studied when the number of the shares d = 2,3,4). In additional, our results could be specified to the case of provable security for low entropy masking, which can be considered as a side bonus of our contributions. We give some preliminary results on how to construct the low entropy masking schemes with provable high security order against linear leakage.

Smart devices without an interactive UI (e.g., a smart bulb) typically rely on specific provisioning schemes to connect to wireless networks. Among all the provisioning schemes, SmartCfg is a popular technology to configure the connection between smart devices and wireless routers. Although the SmartCfg technology facilitates the Wi-Fi configuration, existing solutions seldom take into serious consideration the protection of credentials and therefore introduce security threats against Wi-Fi credentials.

Differential power analysis (DPA), as a very practical type of side-channel attacks, has been widely studied and used for the security analysis of cryptographic implementations. However, as the development of the chip industry leads to smaller technologies, the leakage of cryptographic implementations in nanoscale devices tends to be nonlinear (i.e., leakages of intermediate bits are no longer independent) and unpredictable. These phenomena make some existing side-channel attacks not perfectly suitable, i.e., decreasing their performance and making some common used prior power models (e.g., Hamming weight) to be much less respected in practice. To solve the above issues, we introduce the regularization process from statistical learning to the area of side-channel attack and propose the ridge-based DPA. We also apply the cross-validation technique to search for the most suitable value of the parameter for our new attack methods. In addition, we present theoretical analyses to deeply investigate the properties of ridge-based DPA for nonlinear leakages. We evaluate the performance of ridge-based DPA in both simulation-based and practical experiments, comparing to the state-to-the-art DPAs. The results confirm the theoretical analysis. Further, our experiments show the robustness of ridge-based DPA to cope with the difference between the leakages of profiling and exploitation power traces. Therefore, by showing a good adaptability to the leakage of the nanoscale chips, the ridge-based DPA is a good alternative to the state-to-the-art ones.

It has been widely adopted to minimize the maintenance cost by predicting potential vulnerabilities before code audits in academia and industry. Most previous research dedicated to file/component level vulnerability prediction models is coarse- grained and may suffer from cost-prohibitive and impractical security testing activities. In this paper, we focus on a cost- aware vulnerability prediction model and present a just-in-time change-level code review tool called VulDigger to dig suspicious ones from a sea of code changes. Our contributions benefit from the case study of Mozilla Firefox by constructing a large-scale vulnerability-contributing changes (VCCs) dataset in a semi-automatic fashion. We then further manifest a classification tool with a mixture of established and new metrics derived from both software defect prediction and vulnerability prediction. Consequently, the precision of such tool is extremely promising (i.e., 92%) for an effort-aware software team. We also examine the return on investment by training a regression model to locate most skeptical changes with fewer lines to inspect. Our findings suggest that such model is capable of pinpointing 31% of all VCCs with only 20% of the effort it would take to audit all changes (i.e., 55% better than random predictor). Our outputs can assist as an early step of continuous security inspections as it provides immediate feedback once developers submit changes to their code base.

Several factors (e.g., balancedness, good correlation immunity) are considered as important properties of Boolean functions for using in cryptographic primitives. A Boolean function is perfect algebraic immune if it is with perfect immunity against algebraic and fast algebraic attacks. There is an increasing interest in construction of Boolean function that is perfect algebraic immune combined with other characteristics, like resiliency. A resilient function is a balanced correlation-immune function. This paper uses bivariate representation of Boolean function and theory of finite field to construct a generalized and new class of Boolean functions on even variables by extending the Carlet-Feng functions. We show that the functions generated by this construction support cryptographic properties of 1-resiliency and (sub)optimal algebraic immunity and further propose the sufficient condition of achieving optimal algebraic immunity. Compared experimentally with Carlet-Feng functions and the functions constructed by the method of first-order concatenation existing in the literature on even (from 6 to 16) variables, these functions have better immunity against fast algebraic attacks. Implementation results also show that they are almost perfect algebraic immune functions.

While the increasing digitalization of our society and amalgamation of embedded devices into the ever-increasing facets of our daily life (e.g., in smart and intelligent vehicles, smart cities and smart nations, and critical infrastructure sectors) have resulted in improved productivity and quality of life, the trend has also resulted in a trend of increasing frequency and sophistication of cyber exploitation and cyber threats. Hence, there is a need for coordinated efforts from the research community to address resulting concerns using both cryptographic and non-cryptographic solutions, such as those presented in this special section.

Related-key attacks (RKAs) are a flavor of powerful physical attacks, which allow an adversary to modify the secret key stored in a cryptographic device and subsequently observe the effect of such modifications on the output of the device. Designing secure encryption schemes against such attacks is a challenging task, especially for a large class of such physical attacks which are usually captured by related-key derivation functions. In this work, we achieve the security of public key encryptions (PKEs) against a new and broad function class that consists of almost all efficiently invertible functions in two different ways. Specifically, we first give a generic construction of PKE which is proven secure against such a broad function class under the standard chosen-ciphertext security. Moreover, we present two practical concrete constructions, both of which are shown to be secure against such function class under standard assumptions in the standard model. At last, we give a detailed performance analysis, which shows that our constructions can not only resist to a large class of RKAs but also achieve a good efficiency.

Side-channel attacks are an increasingly important concern for the security of cryptographic embedded devices, such as the SIM cards used in mobile phones. Previous works have exhibited such attacks against implementations of the 2G GSM algorithms (COMP-128, A5). In this paper, we show that they remain an important issue for USIM cards implementing the AES-based MILENAGE algorithm used in 3G/4G communications. In particular, we analyze instances of cards from a variety of operators and manufacturers, and describe successful Differential Power Analysis attacks that recover encryption keys and other secrets (needed to clone the USIM cards) within a few minutes. Further, we discuss the impact of the operator-defined secret parameters in MILENAGE on the difficulty to perform Differential Power Analysis, and show that they do not improve implementation security. Our results back up the observation that physical security issues raise long-term challenges that should be solved early in the development of cryptographic implementations, with adequate countermeasures.

We revisit the problem of basing signcryption SC tag key encapsulation mechanism KEM on standard assumptions and standard model and present direct constructions of SC-KEM/tag-KEM, which satisfy confidentiality and unforgeability with respect to adversarially chosen keys where the adversary is given more advantageous attack environment than existing models in the literature;are based on the standard decisional bilinear Diffie-Hellman and computational Diffie-Hellman assumptions without random oracle;do not use strongly unforgeable signature schemes as building blocks; andprovide comparable performance to existing SC-KEM/tag-KEM schemes.

A typical but trivial layout of alphanumeric buttons in the touchscreen setting is to arrange the 10 digits and 26 letters in a natural order. This arrangement does not take into account the frequencies of letters and digits when the users touch the buttons to key in their passwords or messages. We examine large scale datasets of over 141 million passwords collected from several leading websites for social networking, Internet forums, gaming, dating, and various other online service providers in China, and find that the distribution of letters in passwords is quite close to that in Chinese language. Based on the letter/digit frequencies, we further propose an alphanumeric button layout scheme with the following advantages: the buttons are clicked as uniformly as possible, so that the lifetime of the touchscreen can be prolonged and finger oil residues may scatter more evenly over the button area of the screen; and in the meantime, the movements of users' fingers are improved to enhance good user experience when inputting messages. The idea behind the layout is potentially applicable to diversified races.

Graphical password methods rely on human experience and hand selection (not well-quantified metric) to evaluate the appropriateness and the confusion of the challenge images. In this paper we propose to use for authentication Chinese characters, for which the entropy can be up to 9.65 (much larger than other languages). We first show an algorithmic framework to authenticate a user and then present an empirical analysis conducted at a university. The advantages of the framework include the following: the storage overhead is low; no personal experience or hand selection is involved; there is no predefined dictionary of likely choices; and it can be easily referenced by personal-style cues. Our study shows that the number of participants that prefer our framework is much close to that in favor of graphical passwords, with an interesting outcome that the two groups of participants present significantly distinct backgrounds. Our framework and graphical passwords can be used as candidate authentication methods for users with different backgrounds. We also measure user choices of patterns and find that there is a slight preference of the 3$\times$3 grid to the circle patterns. While the proposed framework prescribes the challenge characters, the users have the option to define challenge characters of their own.

ABSTRACT In password‐based or two‐factor (password and smart card) authentications, password changing is one of common techniques used to improve the security of the systems protected by the password. However, the password‐changing operations in existing password authentications either depend on the login phase or violate the common practice that an old password should not be valid for subsequent login after being updated. On the other hand, password mistyping is very common in reality, which may be random or be skewed by the adversary via technical means or social engineering manipulation [i.e., a kind of denial‐of‐service (DoS) attack]. In human‐centric authentication mechanisms, password changing and DoS resilience are not marginal issues. The paper addresses the requirements of robust password changing in authentication and presents , a password authentication scheme with robust password changing, DoS resilience, and card‐compromise security. Thus, the proposal can be viewed as a suitable candidate instantiation for authentication services of human‐centric security, by embedding in the computer and software systems. also achieves other appealing features, such as self‐healing ability and strong privacy protection, which may be useful for human‐centric applications. Copyright © 2013 John Wiley & Sons, Ltd.

Recently, there has been renewed interest in basing cryptographic primitives on weak secrets, where the only information about the secret is some non-trivial amount of (min-) entropy. From a formal point of view, such results require to upper bound the expectation of some function f(X), where X is a weak source in question. We show an elementary inequality which essentially upper bounds such `weak expectation' by two terms, the first of which is independent of f, while the second only depends on the `variance' of f under uniform distribution. Quite remarkably, as relatively simple corollaries of this elementary inequality, we obtain some `unexpected' results, in several cases noticeably simplifying/improving prior techniques for the same problem. Examples include non-malleable extractors, leakage-resilient symmetric encryption, seed-dependent condensers and improved entropy loss for the leftover hash lemma.

A (worst-case) 2-source extractor is a deterministic algorithm that transforms pairwise independent weak random sources into almost uniform random strings. Despite non-constructive proofs that such objects exist with almost optimal parameters, it has been a longstanding open problem to construct `explicit' (aka efficient) functions for sources of `small' constant entropy rate. In particular, best known constructions either require entropy rate of at least 0.4999 (due to Bourgain), or one source must remain with constant entropy rate above half (due to Raz). Motivated by cryptographic applications, we observe that if one source is a leaky source (or it contains a few deterministically extractable entropy), then we will be able to efficiently extract almost all entropy from both sources with nearly optimal entropy loss. Further, our extractor (for leaky sources) does not suffer from the half entropy rate barrier, and it works for all linear (and even sub-linear) entropy sources. The extractor is constructed using the technique of alternating extraction by Dziembowski and Pietrzak (FOCS 2007). Finally, we show that the extractor is almost a worse-case extractor (for the same parameters) in the sense that it only fails for a negligible fraction of sources.

Cryptographic systems and protocols are the core of many Internet security procedures (such as SSL, SSH, IPSEC, DNSSEC, secure mail, etc.). At the heart of all cryptographic functions is a good source of randomness, and for efficiency, the primitive of pseudorandom generator (PRG). PRG can also be used in the design of stream ciphers, for secure communications. The Internet is nowadays composed of many types of devices with very different hardware and software characteristics. Hence, one of the concerns in such open environments is the information "leakage" and its exploitation via the so-called "side channel attacks".

We discuss the following problem: how to guarantee privacy of a circuit if an adversary can eavesdrop on its wires, where the functionality of the circuit is assumed public and the adversary attempts to discover information regarding the computation, namely, input, intermediate results and output. We present a solution by introducing a private stateful circuit that securely (against probing attacks) computes the same function as the original circuit does. This is achieved with a reasonable increase in circuit size and depth.