@article{liuscalable,year={2024},title={Scalable Multi-Party Computation Protocols for Machine Learning in the Honest-Majority Setting},author={Liu, Fengrun and Xie, Xiang and Yu, Yu},}
2023
ASIACRYPT 2023
Algebraic Attacks on Round-Reduced RAIN and Full AIM-III
Kaiyi
Zhang
, Qingju
Wang
, Yu
Yu
, Chun
Guo
, and Hongrui
Cui
@misc{cryptoeprint:2023/1397,year={2023},author={Zhang, Kaiyi and Wang, Qingju and Yu, Yu and Guo, Chun and Cui, Hongrui},title={Algebraic Attacks on Round-Reduced RAIN and Full AIM-III},howpublished={Cryptology ePrint Archive, Paper 2023/1397},url={https://eprint.iacr.org/2023/1397},}
TCC 2023
Security Proofs for Key-Alternating Ciphers with Non-Independent Round Permutations
Liqing
Yu
, Yusai
Wu
, Yu
Yu
, Zhenfu
Cao
, and Xiaolei
Dong
@misc{cryptoeprint:2023/1355,author={Yu, Liqing and Wu, Yusai and Yu, Yu and Cao, Zhenfu and Dong, Xiaolei},title={Security Proofs for Key-Alternating Ciphers with Non-Independent Round Permutations},howpublished={Cryptology ePrint Archive, Paper 2023/1355},year={2023},url={https://eprint.iacr.org/2023/1355},}
CRYPTO 2023
Revisiting the Constant-sum Winternitz One-time Signature with Applications to SPHINCS+ and XMSS
@misc{cryptoeprint:2023/850,year={2023},author={Zhang, Kaiyi and Cui, Hongrui and Yu, Yu},title={Revisiting the Constant-sum Winternitz One-time Signature with Applications to SPHINCS+ and XMSS},howpublished={Cryptology ePrint Archive, Paper 2023/850},url={https://eprint.iacr.org/2023/850},}
EUROCRYPT 2023
Actively Secure Half-Gates with Minimum Overhead under Duplex Networks
@misc{cryptoeprint:2023/278,year={2023},author={Cui, Hongrui and Wang, Xiao and Yang, Kang and Yu, Yu},title={Actively Secure Half-Gates with Minimum Overhead under Duplex Networks},howpublished={Cryptology ePrint Archive, Paper 2023/278},doi={10.1007/978-3-031-30617-4_2},url={https://eprint.iacr.org/2023/278},}
IEEE S&P 2023
Bicoptor: Two-round Secure Three-party Non-linear Computation without Preprocessing for Privacy-preserving Machine Learning
L.
Zhou
, Z.
Wang
, H.
Cui
, Q.
Song
, and Y.
Yu
In 2023 IEEE Symposium on Security and Privacy (SP) , May
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.
@inproceedings{10179449,author={Zhou, L. and Wang, Z. and Cui, H. and Song, Q. and Yu, Y.},booktitle={2023 IEEE Symposium on Security and Privacy (SP)},title={Bicoptor: Two-round Secure Three-party Non-linear Computation without Preprocessing for Privacy-preserving Machine Learning},year={2023},volume={},issn={},pages={534-551},keywords={privacy;cloud computing;protocols;batch production systems;machine learning;throughput;computational efficiency},doi={10.1109/SP46215.2023.10179449},url={https://doi.ieeecomputersociety.org/10.1109/SP46215.2023.10179449},publisher={IEEE Computer Society},address={Los Alamitos, CA, USA},month=may,}
2022
ASIACRYPT 2022
A Non-heuristic Approach to Time-space Tradeoffs and Optimizations for BKW
@misc{cryptoeprint:2022/1163,author={Zhou, Yuanyuan and van de Pol, Joop and Yu, Yu and Standaert, François-Xavier},title={A Third is All You Need: Extended Partial Key Exposure Attack on CRT-RSA with Additive Exponent Blinding},howpublished={Cryptology ePrint Archive, Paper 2022/1163},year={2022},url={https://eprint.iacr.org/2022/1163},}
EUROCRYPT 2022
Cryptanalysis of Candidate Obfuscators for Affine Determinant Programs
@article{tches-2021-31289,title={Learning Parity with Physical Noise: Imperfections, Reductions and FPGA Prototype},journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},publisher={Ruhr-Universität Bochum},volume={2021, Issue 3},pages={390-417},url={https://tches.iacr.org/index.php/TCHES/article/view/8979},doi={10.46586/tches.v2021.i3.390-417},author={Bellizia, Davide and Hoffmann, Clément and Kamel, Dina and Liu, Hanlin and Méaux, Pierrick and Standaert, François-Xavier and Yu, Yu},year={2021},}
NPJ Quantum Information
Experimental authentication of quantum key distribution with post-quantum cryptography
Liu-Jun
Wang
, Kai-Yi
Zhang
, Jia-Yong
Wang
, Jie
Cheng
, Yong-Hua
Yang
, Shi-Biao
Tang
, Di
Yan
, Yan-Lin
Tang
, Zhen
Liu
, Yu
Yu
, and
others
@article{wang2021experimental,title={Experimental authentication of quantum key distribution with post-quantum cryptography},author={Wang, Liu-Jun and Zhang, Kai-Yi and Wang, Jia-Yong and Cheng, Jie and Yang, Yong-Hua and Tang, Shi-Biao and Yan, Di and Tang, Yan-Lin and Liu, Zhen and Yu, Yu and others},journal={npj quantum information},volume={7},number={1},pages={67},year={2021},publisher={Nature Publishing Group UK London},}
ESORICS 2021
MPC-in-Multi-Heads: A Multi-Prover Zero-Knowledge Proof System: (or: How to Jointly Prove Any NP Statements in ZK)
Hongrui
Cui
, Kaiyi
Zhang
, Yu
Chen
, Zhen
Liu
, and Yu
Yu
In Computer Security – ESORICS 2021: 26th European Symposium on Research in Computer Security, Darmstadt, Germany, October 4–8, 2021, Proceedings, Part II , May
With the rapid development of distributed computing, the traditional zero-knowledge proofs (ZKP) are becoming less adequate for privacy-preserving applications in the distributed setting. Take “double financing” as an example: multiple financial providers jointly prove that the sum of their committed values is no more than a given threshold, which generalizes the “range proof” to the multiple-prover setting. Therefore, traditional zero-knowledge proof does not seemingly lend itself to this problem on its own. We identify and fill this gap by formalizing the ZKP system in the multi-prover setting (MPZK) that proves arbitrary NP statements with distributed witnesses. Our MPZK system offers zero-knowledge as long as one prover is honest (while others can collude arbitrarily), and thus is applicable to “double financing”, “credit checking”, and various other multi-prover applications. We then propose a generic black-box construction from multiparty computation, referred to as “MPC-in-Multi-Heads”, and prove its security under the simulation-based paradigm. We also offer a proof-of-concept implementation and present its experimental results.
@inproceedings{10.1007/978-3-030-88428-4_17,author={Cui, Hongrui and Zhang, Kaiyi and Chen, Yu and Liu, Zhen and Yu, Yu},title={MPC-in-Multi-Heads: A Multi-Prover Zero-Knowledge Proof System: (or: How to Jointly Prove Any NP Statements in ZK)},year={2021},isbn={978-3-030-88427-7},publisher={Springer-Verlag},address={Berlin, Heidelberg},url={https://doi.org/10.1007/978-3-030-88428-4_17},doi={10.1007/978-3-030-88428-4_17},booktitle={Computer Security – ESORICS 2021: 26th European Symposium on Research in Computer Security, Darmstadt, Germany, October 4–8, 2021, Proceedings, Part II},pages={332–351},numpages={20},location={Darmstadt, Germany}}
2020
ASIACRYPT 2020
Packed Multiplication: How to Amortize the Cost of Side-channel Masking ?
Weijia
Wang
, Chun
Guo
, François-Xavier
Standaert
, Yu
Yu
, and Gaëtan
Cassiers
@misc{cryptoeprint:2020/1103,author={Wang, Weijia and Guo, Chun and Standaert, François-Xavier and Yu, Yu and Cassiers, Gaëtan},title={Packed Multiplication: How to Amortize the Cost of Side-channel Masking ?},howpublished={Cryptology ePrint Archive, Paper 2020/1103},year={2020},note={\url{https://eprint.iacr.org/2020/1103}},url={https://eprint.iacr.org/2020/1103},}
ESORICS 2020
A lattice-based key-insulated and privacy-preserving signature scheme with publicly derived public key
Wenling
Liu
, Zhen
Liu
, Khoa
Nguyen
, Guomin
Yang
, and Yu
Yu
In European Symposium on Research in Computer Security , May
@inproceedings{liu2020lattice,title={A lattice-based key-insulated and privacy-preserving signature scheme with publicly derived public key},author={Liu, Wenling and Liu, Zhen and Nguyen, Khoa and Yang, Guomin and Yu, Yu},booktitle={European Symposium on Research in Computer Security},pages={357--377},year={2020},organization={Springer}}
PKC 2020
Tweaking the Asymmetry of Asymmetric-Key Cryptography on Lattices: KEMs and Signatures of Smaller Sizes
Jiang
Zhang
, Yu
Yu
, Shuqin
Fan
, Zhenfeng
Zhang
, and Kang
Yang
@inproceedings{cispa3105,year={2020},author={Wen, Rui and Yu, Yu and Xie, Xiang and Zhang, Yang},title={LEAF: A Faster Secure Search Algorithm via Localization, Extraction, and Reconstruction},booktitle={ACM SIGSAC Conference on Computer and Communications Security},url={https://publications.cispa.saarland/3105/},}
S&P 2020
Efficient and Secure Multiparty Computation from Fixed-Key Block Ciphers
First proposed in CryptoNote, a collection of popular privacy-centric cryptocurrencies have employed Linkable Ring Signature and a corresponding Key Derivation Mechanism (KeyDerM) for keeping the payer and payee of a transaction anonymous and unlinkable. The KeyDerM is used for generating a fresh signing key and the corresponding public key, referred to as a stealth address, for the transaction payee. The stealth address will then be used in the linkable ring signature next time when the payee spends the coin. However, in all existing works, including Monero, the privacy model only considers the two cryptographic primitives separately. In addition, to be applied to cryptocurrencies, the security and privacy models for Linkable Ring Signature should capture the situation that the public key ring of a signature may contain keys created by an adversary (referred to as adversarially-chosen-key attack), since in cryptocurrencies, it is normal for a user (adversary) to create self-paying transactions so that some maliciously created public keys can get into the system without being detected .
@inproceedings{10.1007/978-3-030-29959-0_35,author={Liu, Zhen and Nguyen, Khoa and Yang, Guomin and Wang, Huaxiong and Wong, Duncan S.},editor={Sako, Kazue and Schneider, Steve and Ryan, Peter Y. A.},title={A Lattice-Based Linkable Ring Signature Supporting Stealth Addresses},booktitle={Computer Security -- ESORICS 2019},year={2019},publisher={Springer International Publishing},address={Cham},pages={726--746},isbn={978-3-030-29959-0}}
ASIACRYPT 2019
Collision Resistant Hashing from Sub-exponential Learning Parity with Noise
Yu
Yu
, Jiang
Zhang
, Jian
Weng
, Chun
Guo
, and Xiangxue
Li
@article{zhang2019z,title={Z-channel: Scalable and efficient scheme in zerocash},author={Zhang, Yuncong and Long, Yu and Liu, Zhen and Liu, Zhiqiang and Gu, Dawu},journal={Computers \& Security},volume={86},pages={112--131},year={2019},publisher={Elsevier},}
Inscrypt 2018
Goshawk: a novel efficient, robust and flexible blockchain protocol
Cencen
Wan
, Shuyang
Tang
, Yuncong
Zhang
, Chen
Pan
, Zhiqiang
Liu
, Yu
Long
, Zhen
Liu
, and Yu
Yu
In Information Security and Cryptology: 14th International Conference, Inscrypt 2018, Fuzhou, China, December 14-17, 2018, Revised Selected Papers 14 , May
@inproceedings{wan2019goshawk,title={Goshawk: a novel efficient, robust and flexible blockchain protocol},author={Wan, Cencen and Tang, Shuyang and Zhang, Yuncong and Pan, Chen and Liu, Zhiqiang and Long, Yu and Liu, Zhen and Yu, Yu},booktitle={Information Security and Cryptology: 14th International Conference, Inscrypt 2018, Fuzhou, China, December 14-17, 2018, Revised Selected Papers 14},pages={49--69},year={2019},organization={Springer},}
Provable Order Amplification for Code-Based Masking: How to Avoid Non-Linear Leakages Due to Masked Operations
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 so-called 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 additiona, 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.
@article{10.1109/TIFS.2019.2912549,author={Wang, Weijia and Yu and Standaert, Francois-Xavier},title={Provable Order Amplification for Code-Based Masking: How to Avoid Non-Linear Leakages Due to Masked Operations},year={2019},issue_date={November 2019},publisher={IEEE Press},volume={14},number={11},issn={1556-6013},url={https://doi.org/10.1109/TIFS.2019.2912549},doi={10.1109/TIFS.2019.2912549},journal={Trans. Info. For. Sec.},month=nov,pages={3069–3082},numpages={14}}
2018
Defcon China 2018
Passwords in the Air: Harvesting Wi-Fi Credentials from SmartCfg Provisioning
Changyu
Li
, Quanpu
Cai
, Juanru
Li
, Hui
Liu
, Yuanyuan
Zhang
, Dawu
Gu
, and Yu
Yu
In Proceedings of the 11th ACM Conference on Security & Privacy in Wireless and Mobile Networks , Nov
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.This paper conducts a security analysis against eight SmartCfg based Wi-Fi provisioning solutions designed by different wireless module manufacturers. Our analysis demonstrates that six manufacturers provide flawed SmartCfg implementations that directly lead to the exposure of Wi-Fi credentials: attackers could exploit these flaws to obtain important credentials without any substantial efforts on brute-force password cracking. Furthermore, we keep track of the smart devices that adopt such Wi-Fi provisioning solutions to investigate the influence of the security flaws on real world products. Through reversely analyzing the corresponding apps of those smart devices we conclude that the flawed SmartCfg implementations constitute a wide potential impact on the security of smart home ecosystems.
@inproceedings{10.1145/3212480.3212496,author={Li, Changyu and Cai, Quanpu and Li, Juanru and Liu, Hui and Zhang, Yuanyuan and Gu, Dawu and Yu, Yu},title={Passwords in the Air: Harvesting Wi-Fi Credentials from SmartCfg Provisioning},year={2018},isbn={9781450357319},publisher={Association for Computing Machinery},address={New York, NY, USA},url={https://doi.org/10.1145/3212480.3212496},doi={10.1145/3212480.3212496},booktitle={Proceedings of the 11th ACM Conference on Security \& Privacy in Wireless and Mobile Networks},pages={1–11},numpages={11},keywords={Smart devices, Wi-Fi provisioning},location={Stockholm, Sweden},series={WiSec '18}}
CNS 2018
Dynamic Practical Byzantine Fault Tolerance
Xu
Hao
, Long
Yu
, Liu
Zhiqiang
, Liu
Zhen
, and Gu
Dawu
In 2018 IEEE Conference on Communications and Network Security (CNS) , Nov
@inproceedings{8433150,author={Hao, Xu and Yu, Long and Zhiqiang, Liu and Zhen, Liu and Dawu, Gu},booktitle={2018 IEEE Conference on Communications and Network Security (CNS)},title={Dynamic Practical Byzantine Fault Tolerance},year={2018},volume={},number={},pages={1-8},keywords={Protocols;Security;Conferences;Communication networks;Computer crashes;Fault tolerance;Fault tolerant systems},doi={10.1109/CNS.2018.8433150},}
NSS 2018
Secure Scheme Against Compromised Hash in Proof-of-Work Blockchain
Fengjun
Chen
, Zhiqiang
Liu
, Yu
Long
, Zhen
Liu
, and Ning
Ding
Blockchain is built on the basis of peer-to-peer network, cryptography and consensus mechanism over a distributed environment. The underlying cryptography in blockchain, such as hash algorithm and digital signature scheme, is used to guarantee the security of blockchain. However, past experience showed that cryptographic primitives do not last forever along with increasing computational power and advanced cryptanalysis. Therefore, it is crucial to investigate the issue that the underlying cryptography in blockchain is compromised.
@inproceedings{10.1007/978-3-030-02744-5_1,author={Chen, Fengjun and Liu, Zhiqiang and Long, Yu and Liu, Zhen and Ding, Ning},editor={Au, Man Ho and Yiu, Siu Ming and Li, Jin and Luo, Xiapu and Wang, Cong and Castiglione, Aniello and Kluczniak, Kamil},title={Secure Scheme Against Compromised Hash in Proof-of-Work Blockchain},booktitle={Network and System Security},year={2018},publisher={Springer International Publishing},address={Cham},pages={1--15},isbn={978-3-030-02744-5},}
2017
ASIACRYPT 2017
Two-Round PAKE from Approximate SPH and Instantiations from Lattices
@misc{cryptoeprint:2017/838,author={Zhang, Jiang and Yu, Yu},title={Two-Round PAKE from Approximate SPH and Instantiations from Lattices},howpublished={Cryptology ePrint Archive, Paper 2017/838},year={2017},url={https://eprint.iacr.org/2017/838},}
2016
CRYPTO 2016
Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN
@misc{cryptoeprint:2016/514,author={Yu, Yu and Zhang, Jiang},title={Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN},howpublished={Cryptology ePrint Archive, Paper 2016/514},year={2016},url={https://eprint.iacr.org/2016/514},}
EUROCRYPT 2016
Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN
Yu
Yu
, and John
Steinberger
In Proceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology — EUROCRYPT 2016 - Volume 9666 , Nov
Pseudorandom functions PRFs play a central role in symmetric cryptography. While in principle they can be built from any one-way functions by going through the generic HILL SICOMP 1999 and GGM JACM 1986 transforms, some of these steps are inherently sequential and far from practical. Naor, Reingold FOCS 1997 and Rosen SICOMP 2002 gave parallelizable constructions of PRFs in NC$^22 and TC^00 based on concrete number-theoretic assumptions such as DDH, RSA, and factoring. Banerjee, Peikert, and Rosen Eurocrypt 2012 constructed relatively more efficient PRFs in NC^11 and TC^00 based on "learning with errors" LWE for certain range of parameters. It remains an open problem whether parallelizable PRFs can be based on the "learning parity with noise" LPN problem for both theoretical interests and efficiency reasons as the many modular multiplications and additions in LWE would then be simplified to AND and XOR operations under LPN.In this paper, we give more efficient and parallelizable constructions of randomized PRFs from LPN under noise rate n^-cn-c for any constant 0 Furthermore, our constructions are security-lifting by exploiting the redundancy of low-noise LPN. We show that in addition to parallelizability in almost constant depth the PRF enjoys either of or any tradeoff between the following:A PRF on a weak key of sublinear entropy or equivalently, a uniform key that leaks any 1 - o11-o1-fraction has comparable security to the underlying LPN on a linear size secret.A PRF with key length lambda λ can have security upı̈ źto 2^Olambda /log lambda $2Oλ/logλ, which goes much beyond the security level of the underlying low-noise LPN. where adversary makes upı̈ źto certain super-polynomial amount of queries.
@inproceedings{10.5555/3081738.3081744,author={Yu, Yu and Steinberger, John},title={Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN},year={2016},isbn={9783662498958},publisher={Springer-Verlag},address={Berlin, Heidelberg},booktitle={Proceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 9666},pages={154–183},numpages={30},}
2015
CRYPTO 2015
(Almost) Optimal Constructions of UOWHFs from 1-to-1, Regular One-Way Functions and Beyond
We revisit the problem of black-box constructions of universal one-way hash functions (UOWHFs) from several typical classes of one-way functions (OWFs), and give respective constructions that either improve or generalize the best previously known.
For any 1-to-1 one-way function, we give an optimal construction of UOWHFs with key and output length $varTheta (n) by making a single call to the underlying OWF. This improves the constructions of Naor and Yung (STOC 1989) and De Santis and Yung (Eurocrypt 1990) that need key length O(ncdot omega (log n)).
For any known-(almost-)regular one-way function with known hardness, we give an optimal construction of UOWHFs with key and output length varTheta (n) and a single call to the one-way function.
For any known-(almost-)regular one-way function, we give a construction of UOWHFs with key and output length O(ncdot omega (1)) and by making omega (1) non-adaptive calls to the one-way function. This improves the construction of Barhum and Maurer (Latincrypt 2012) that requires key and output length O(ncdot omega (log n)) and omega (log n) calls.
For any weakly-regular one-way function introduced by Yu et al. at TCC 2015 (i.e., the set of inputs with maximal number of siblings is of an n^-c-fraction for some constant c), we give a construction of UOWHFs with key length O(ncdot log n) and output length varTheta (n). This generalizes the construction of Ames et al. (Asiacrypt 2012) which requires an unknown-regular one-way function (i.e., c=0$).
Along the way, we use several techniques that might be of independent interest. We show that almost 1-to-1 (except for a negligible fraction) one-way functions and known (almost-)regular one-way functions are equivalent in the known-hardness (or non-uniform) setting, by giving an optimal construction of the former from the latter. In addition, we show how to transform any one-way function that is far from regular (but only weakly regular on a noticeable fraction of domain) into an almost-regular one-way function.
TCC 2015
The Randomized Iterate, Revisited - Almost Linear Seed Length PRGs from a Broader Class of One-Way Functions
We revisit “the randomized iterate” technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma (which is folklore in leakage resilient cryptography), and use it to provide a simpler and more modular proof for the Haitner-Harnik-Reingold PRGs from regular OWFs.
@inproceedings{10.1007/978-3-662-46494-6_2,author={Yu, Yu and Gu, Dawu and Li, Xiangxue and Weng, Jian},editor={Dodis, Yevgeniy and Nielsen, Jesper Buus},title={The Randomized Iterate, Revisited - Almost Linear Seed Length PRGs from a Broader Class of One-Way Functions},booktitle={Theory of Cryptography},year={2015},publisher={Springer Berlin Heidelberg},address={Berlin, Heidelberg},pages={7--35},isbn={978-3-662-46494-6},}
2013
ASIACRYPT 2013
Pseudorandom Generators from Regular One-Way Functions: New Constructions with Improved Parameters
We revisit the problem of basing pseudorandom generators on regular one-way functions, and present the following constructions:
@inproceedings{10.1007/978-3-642-42045-0_14,author={Yu, Yu and Li, Xiangxue and Weng, Jian},editor={Sako, Kazue and Sarkar, Palash},title={Pseudorandom Generators from Regular One-Way Functions: New Constructions with Improved Parameters},booktitle={Advances in Cryptology - ASIACRYPT 2013},year={2013},publisher={Springer Berlin Heidelberg},address={Berlin, Heidelberg},pages={261--279},isbn={978-3-642-42045-0},}
CRYPTO 2013
Leakage-Resilient Symmetric Cryptography under Empirically Verifiable Assumptions
François-Xavier
Standaert
, Olivier
Pereira
, and Yu
Yu
Leakage-resilient cryptography aims at formally proving the security of cryptographic implementations against large classes of side-channel adversaries. One important challenge for such an approach to be relevant is to adequately connect the formal models used in the proofs with the practice of side-channel attacks. It raises the fundamental problem of finding reasonable restrictions of the leakage functions that can be empirically verified by evaluation laboratories. In this paper, we first argue that the previous “bounded leakage” requirements used in leakage-resilient cryptography are hard to fulfill by hardware engineers. We then introduce a new, more realistic and empirically verifiable assumption of simulatable leakage, under which security proofs in the standard model can be obtained. We finally illustrate our claims by analyzing the physical security of an efficient pseudorandom generator (for which security could only be proven under a random oracle based assumption so far). These positive results come at the cost of (algorithm-level) specialization, as our new assumption is specifically defined for block ciphers. Nevertheless, since block ciphers are the main building block of many leakage-resilient cryptographic primitives, our results also open the way towards more realistic constructions and proofs for other pseudorandom objects.
@inproceedings{10.1007/978-3-642-40041-4_19,author={Standaert, Fran{\c{c}}ois-Xavier and Pereira, Olivier and Yu, Yu},editor={Canetti, Ran and Garay, Juan A.},title={Leakage-Resilient Symmetric Cryptography under Empirically Verifiable Assumptions},booktitle={Advances in Cryptology -- CRYPTO 2013},year={2013},publisher={Springer Berlin Heidelberg},address={Berlin, Heidelberg},pages={335--352},isbn={978-3-642-40041-4},}
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.
@inproceedings{10.1007/978-3-642-36594-2_1,author={Dodis, Yevgeniy and Yu, Yu},editor={Sahai, Amit},title={Overcoming Weak Expectations},booktitle={Theory of Cryptography},year={2013},publisher={Springer Berlin Heidelberg},address={Berlin, Heidelberg},pages={1--22},isbn={978-3-642-36594-2},}
CT-RSA 2013
Practical Leakage-Resilient Pseudorandom Objects with Minimum Public Randomness
One of the main challenges in leakage-resilient cryptography is to obtain proofs of security against side-channel attacks, under realistic assumptions and for efficient constructions. In a recent work from CHES 2012, Faust et al. proposed new designs of stream ciphers and pseudorandom functions for this purpose. Yet, a remaining limitation of these constructions is that they require large amounts of public randomness to be proven leakage-resilient. In this paper, we show that tweaked designs with minimum randomness requirements can be proven leakage-resilient in minicrypt. That is, either these constructions are secure, or we are able to construct public-key cryptographic primitives from symmetric-key building blocks and their leakage functions (which is very unlikely). Hence, our results improve the practical relevance of two important leakage-resilient pseudorandom objects.
@inproceedings{10.1007/978-3-642-36095-4_15,author={Yu, Yu and Standaert, Fran{\c{c}}ois-Xavier},editor={Dawson, Ed},title={Practical Leakage-Resilient Pseudorandom Objects with Minimum Public Randomness},booktitle={Topics in Cryptology -- CT-RSA 2013},year={2013},publisher={Springer Berlin Heidelberg},address={Berlin, Heidelberg},pages={223--238},isbn={978-3-642-36095-4},}
@inproceedings{6404713,author={Yu, Yu and Li, Xiangxue and Qian, Haifeng},booktitle={2012 IEEE Information Theory Workshop},title={Two-source extractors for leaky sources},year={2012},volume={},number={},pages={452-456},keywords={Entropy;Data mining;Cryptography;Helium;Computer science;Information theory;Conferences},doi={10.1109/ITW.2012.6404713},}