(Full) Leakage resilience of Fiat-Shamir signatures over lattices

doi:10.1007/s11704-021-0586-3

Front. Comput. Sci.

2022, Vol. 16

Issue (5) : 165819 https://doi.org/10.1007/s11704-021-0586-3

RESEARCH ARTICLE

(Full) Leakage resilience of Fiat-Shamir signatures over lattices

Yuejun LIU^1,², Yongbin ZHOU^1,²(

), Rui ZHANG^1,², Yang TAO¹

¹. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
². School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China

Download: PDF(1340 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Fiat-Shamir is a mainstream construction paradigm of lattice-based signature schemes. While its theoretical security is well-studied, its implementation security in the presence of leakage is a relatively under-explored topic. Specifically, even some side-channel attacks on lattice-based Fiat-Shamir signature (FS-Sig) schemes have been proposed since 2016, little work on the leakage resilience of these schemes appears. Worse still, the proof idea of the leakage resilience of FS-Sig schemes based on traditional number-theoretic assumptions does not apply to most lattice-based FS-Sig schemes. For this, we propose a framework to construct fully leakage resilient lattice-based FS-Sig schemes in the bounded memory leakage (BML) model. The framework consists of two parts. The first part shows how to construct leakage resilient FS-Sig schemes in BML model from leakage resilient versions of non-lossy or lossy identification schemes, which can be instantiated based on lattice assumptions. The second part shows how to construct fully leakage resilient FS-Sig schemes based on leakage resilient ones together with a new property called state reconstruction. We show almost all lattice-based FS-Sig schemes have this property. As a concrete application of our fundamental framework, we apply it to existing lattice-based FS-Sig schemes and provide analysis results of their security in the leakage setting.

Keywords leakage resilience lattice-based signatures Fiat-Shamir paradigm side-channel attacks post-quantum cryptography

Corresponding Author(s): Yongbin ZHOU

Just Accepted Date: 03 March 2021 Issue Date: 31 December 2021

Cite this article:

Yuejun LIU,Yongbin ZHOU,Rui ZHANG, et al. (Full) Leakage resilience of Fiat-Shamir signatures over lattices[J]. Front. Comput. Sci., 2022, 16(5): 165819.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-021-0586-3
https://academic.hep.com.cn/fcs/EN/Y2022/V16/I5/165819

Fig.1 The high-level overview of our framework

Tab.1 Leakage resilience of SIS-based FS-Sig schemes

Tab.2 Leakage resilience of LWE-based FS-Sig schemes. “?” denotes that security against leakage is unknown by our analysis

$K e y G e n (1 λ)_$ $(p k, s k) ← I G e n (1 λ)$	$S i g n (s k, μ)_$ $w h i l e z = ⊥ d o$
return ( $p k, s k$ )	$(a, s t) ← P 1 (s k)$
	$c = H (a μ)$
	$z ← P 2 (s k, a, c, s t)$
$V e r i f y (p k, μ, σ)_$ $P a r s e σ = (c, z)$	end while
return V $(p k, a, c, z) = ? 1 ∧ c = ? H (a μ)$	return $σ = (c, z)$

Tab.3

E x p 0_

(p k, s k) ← I G e n (1 λ)

while

z = ⊥

(a, s t) ← P 1 (s k)

c = H (a μ)

z ← P 2 (s k, a, c, s t)

end whilereturn

σ = (c, z)

E x p 1_

(p k, s k) ← I G e n (1 λ)

while

z = ⊥

(a, s t) ← P 1 (s k)

c ← C h S e t

z ← P 2 (s k, a, c, s t)

c = H (a μ)

end while return

σ = (c, z)

E x p 2_

(p k, s k) ← I G e n (1 λ)

while

z = ⊥

c ← C h S e t

(a, c, z) ← S i m (p k, c)

c = H (a μ)

end whilereturn

σ = (c, z)

Tab.4

E x p 3_

p k l s ← L I G e n (1 λ)

while

z = ⊥

c ← C h S e t

(a, c, z) ← S i m (p k l s, c)

c = H (a μ)

end while

return

σ = (c, z)

Tab.5

$I G e n (1 λ)_$	$P 2 (s k, a, c, s t)_$
$A ← Z q n × m$	$z = y + S c$
$S ← D S m × k$	return $z = z$ with probability min $(D y m (z) D y, S c m (z), 1)$ , otherwise $z = ⊥$
$T = A S$
return $(p k = (A, T), s k = S)$

$P 1 (s k)_$	$V (p k, a, c, z)_$
$y ← D y m$	if $w = A z ? T c$ and $‖ z ‖ ≤ η σ m$ then
$w = A y$	return $1$
return $a = w, s t = (w, y)$	else
	return $0$
	end if

Tab.6

Algorithm $S i m (p k = (A, T))$
$z ← D y m$ $c ← C h S e t$ $w = A z ? T c$ return $(a = w, c, z = z)$ with probability $1 M$

Tab.7

$I G e n (1 λ)_$	$P 2 (s k, a, c, s t)_$
$A ← Z q n × m$	$z = [z 1 ‖ z 2] = y + [S ‖ E] c$
$S ← D S m × k$	return $z = z = [z 1 ‖ z 2]$ with probability min $(D y m + n (z) D y, [S ‖ E] c m + n (z), 1)$ , otherwise $z = ⊥$
$E ← D E n × k$
$T = A S + E$
return $(p k = (A, T), s k = (S, E))$

$P 1 (s k)_$	$V (p k, a, c, z)_$
$y 1 ← D y m$	if $w = A z 1 + z 2 ? T c$ and $‖ z ‖ ∞ ≤ η σ m + n$
$y 2 ← D y n$	return $1$
$y = [y 1 ‖ y 2]$	else
$w = A y 1 + y 2$	return $0$
return $a = w, s t = (w, y)$	end if

Tab.8

Algorithm LIGen(

1 λ

)

A ← Z q n × m S ← D S m × k E ← D E n × k T ← Z q n × k

return

p k l s = (A, T)

Tab.9

$K e y G e n (1 λ)_$	$S i g n (s k, μ)_$
$A ← Z q n × m$	while $z = ⊥$ do
$S ← D S m × k$	$y ← D y m$
$T = A S$	$w = A y$
return $(p k = (A, T), s k = S)$	$c = H (w μ)$
	$z = y + S c$
$V e r i f y (p k, μ, σ = (c, z))_$	return $σ = (c, z)$ with probability min $(D y m (z) D y, S c m (z), 1)$ , otherwise $z = ⊥$
if $c = H (A z ? T c μ$ ) and $‖ z ‖ ≤ η σ m$ then
return $1$	end while
else
return $0$
end if

Tab.10

Scheme	Public key size	Secret key size	Signature size	Assumption
Lyu12-Sig [6]	$n ? (m + k) ? log ? q$	$m ? k ? log ? (2 d + 1)$	$m ? log ? (12 σ) + κ$	$S I S q, n, m, β$
Our SIS-base scheme	$n ? (m + k) ? log ? q$	$m ? k ? log ? (2 d + 1)$	$m ? log ? (12 σ) + κ$	$S I S q, n, m, β$
BG14-Sig [8]	$n ? (m + k) ? log ? q$	$(m + n) ? k ? log ? (12 α)$	$(m + n) ? log ? (12 σ) + κ$	$L W E q, n, m, χ α$
Our LWE-base scheme^*	$n ′ ? (m ′ + k ′) ? log ? q ′$	$(m ′ + n ′) ? k ′ ? log ? (12 α)$	$(m ′ + n ′) ? log ? (12 σ) + κ$	$L W E q ′, n ′, t, χ α$ ^**

Tab.11 Comparisons between the proposed schemes and the existing ones

1	National Institute of Standards and Technology (NIST). Post-quantum cryptography standardization. 2016
2	Fouque P A, Hoffstein J, Kirchner P, Lyubashevsky V, Pornin T, Prest T, Ricosset T, Seiler G, Whyte W, Zhang Z F. FALCON: fast-Fourier lattice-based compact signatures over NTRU. Submission to the NIST Post-Quantum Cryptography Standardization. 2019
3	L Ducas , E Kiltz , T Lepoint , V Lyubashevsky , P Schwabe , G Seiler , D Stehlé . CRYSTALS-Dilithium: a lattice-based digital signature scheme. Journal of IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018, 2018( 1): 238– 268
4	A Fiat, A Shamir. How to prove yourself: practical solutions to identification and signature problems. In: Proceedings on Advances in Cryptology – CRYPTO. 1987, 186– 194
5	V Lyubashevsky. Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security. 2009, 598– 616
6	V Lyubashevsky. Lattice signatures without trapdoors. In: Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2012, 738– 755
7	L Ducas, A Durmus, T Lepoint, V Lyubashevsky. Lattice signatures and bimodal Gaussians. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 40– 56
8	S Bai, S D Galbraith. An improved compression technique for signatures based on learning with errors. In: Proceedings of Cryptographers’ Track at the RSA Conference. 2014, 28– 47
9	Bindel N, Akleylek S, Alkim E, Barreto P S L M, Buchmann J, Eaton E, Gutoski G, Krämer J, Longa P, Polat H, Ricardini J E, Zanon G. qTESLA. Submission to the NIST Post-Quantum Cryptography Standardization. 2019
10	L G Bruinderink, A Hülsing, T Lange, Y Yarom. Flush, gauss, and reload – a cache attack on the BLISS lattice-based signature scheme. In: Proceedings of the 18th International Conference on Cryptographic Hardware and Embedded Systems. 2016, 323– 345
11	P Pessl, L G Bruinderink, Y Yarom. To BLISS-B or not to be: attacking strongSwan’s implementation of post-quantum signatures. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 1843−1855
12	L Ducas. Accelerating bliss: the geometry of ternary polynomials. Journal of IACR Cryptology ePrint Archive, 2014
13	T Espitau, P A Fouque, B Gérard, M Tibouchi. Side-channel attacks on BLISS lattice-based signatures: exploiting branch tracing against strongSwan and electromagnetic emanations in microcontrollers. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 1857−1874
14	S Dziembowski, K Pietrzak. Leakage-resilient cryptography. In: Proceedings of 2008 49th Annual IEEE Symposium on Foundations of Computer Science. 2008, 293– 302
15	J Katz, V Vaikuntanathan. Signature schemes with bounded leakage resilience. In: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security. 2009, 703– 720
16	J Alwen, Y Dodis, D Wichs. Leakage-resilient public-key cryptography in the bounded-retrieval model. In: Proceedings of the 29th Annual International Cryptology Conference. 2009, 36– 54
17	Y Dodis, K Haralambiev, A Lopez-Alt, D Wichs. Cryptography against continuous memory attacks. In: Proceedings of 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. 2010, 511– 520
18	C Hazay, A López-Alt, H Wee, D Wichs. Leakage-Resilient cryptography from minimal assumptions. In: Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2013, 160– 176
19	J Katz, N Wang. Efficiency improvements for signature schemes with tight security reductions. In: Proceedings of the 10th ACM Conference on Computer and Communications Security. 2003, 155– 164
20	S Goldwasser, Y T Kalai, C Peikert, V Vaikuntanathan. Robustness of the learning with errors assumption. In: Proceedings of Innovations in Computer Science – ICS. 2010, 230– 240
21	Z Brakerski, N Döttling. Hardness of LWE on general entropic distributions. In: Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2020, 551– 575
22	S Garg, A Jain, A Sahai. Leakage-resilient zero knowledge. In: Proceedings of the 31st Annual Cryptology Conference. 2011, 297– 315
23	M Abdalla, P A Fouque, V Lyubashevsky, M Tibouchi. Tightly-secure signatures from lossy identification schemes. In: Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2012, 572– 590
24	E Kiltz, V Lyubashevsky, C Schaffner. A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model. In: Proceedings of the 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2018, 552– 586
25	P Kocher, J Jaffe, B Jun. Differential power analysis. In: Proceedings of the 19th Annual International Cryptology Conference. 1999, 388– 397
26	J A Halderman, S D Schoen, N Heninger, W Clarkson, W Paul, J A Calandrino, A J Feldman, J Appelbaum, E W Felten. Lest we remember: Cold boot attacks on encryption keys. In: Proceedings of the 17th USENIX Security Symposium. 2008, 45– 60
27	A Akavia, S Goldwasser, V Vaikuntanathan. Simultaneous hardcore bits and cryptography against memory attacks. In: Proceedings of the 6th Theory of Cryptography Conference. 2009, 474– 495
28	M Naor, G Segev. Public-key cryptosystems resilient to key leakage. In: Proceedings of the 29th Annual International Cryptology Conference. 2009, 18– 35
29	Z Brakerski, Y T Kalai, J Katz, V Vaikuntanathan. Overcoming the hole in the bucket: public-key cryptography resilient to continual memory leakage. In: Proceedings of IEEE 51st Annual Symposium on Foundations of Computer Science. 2010, 501– 510
30	Y Dodis, K Haralambiev, A López-Alt, D Wichs. Efficient public-key cryptography in the presence of key leakage. In: Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security. 2010, 613– 631
31	E Boyle, G Segev, D Wichs. Fully leakage-resilient signatures. In: Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2011, 89– 108
32	T Malkin, I Teranishi, Y Vahlis, M Yung. Signatures resilient to continual leakage on memory and computation. In: Proceedings of the 8th Theory of Cryptography Conference. 2011, 89– 106
33	S Faust, C Hazay, J B Nielsen, P S Nordholt, A Zottarel. Signature schemes secure against hard-to-invert leakage. In: Proceedings of the 18th International Conference on the Theory and Application of Cryptology and Information Security. 2012, 98– 115
34	J B Nielsen, D Venturi, A Zottarel. Leakage-resilient signatures with graceful degradation. In: Proceedings of the 17th International Workshop on Public Key Cryptography. 2014, 362– 379
35	Y Dodis , R Ostrovsky , L Reyzin , A Smith . Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing, 2008, 38( 1): 97– 139
36	J Alwen, S Krenn, K Pietrzak, D Wichs. Learning with rounding, revisited - new reduction, properties and applications. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 57– 74
37	V Lyubashevsky, G Neven. One-shot verifiable encryption from lattices. In: Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2017, 293– 323
38	Z Brakerski, N Döttling. Lossiness and entropic hardness for Ring-LWE. In: Proceedings of the 18th Theory of Cryptography Conference. 2020, 1– 27

[1]

Download

[1]	Mingming JIANG,Yupu HU,Hao LEI,Baocang WANG,Qiqi LAI. Lattice-based certificateless encryption scheme[J]. Front. Comput. Sci., 2014, 8(5): 828-836.
[2]	Mingwu ZHANG,Yi MU. Key continual-leakage resilient broadcast cryptosystem from dual system in broadcast networks[J]. Front. Comput. Sci., 2014, 8(3): 456-468.

Viewed

Full text

Abstract

Cited

Shared

Discussed