U47.org Forum: [Network Security Think Tank] Fuzzy Extra

Active Topics

Memberlist

Help

The Cadet School
U47.org Forum :: The Cadet School

Topic: [Network Security Think Tank] Fuzzy Extra

Author

Message

<< Prev Topic | Next Topic >>

PhillipOgle
Matrose
Matrose

Joined: 16 August 2022
Online Status: Offline
Posts: 5

Posted: 16 August 2022 at 04:30 \| IP Logged

[Network Security Think Tank] Fuzzy Extractor and Its
Application _ Password

Original Title [Network Security Think Tank] Fuzzy
Extractor and Its Application This paper introduces the
definition application and limitation of fuzzy extractor
The limitations of the fuzzy extractor are that it can
only extract the entropic information source once and
that the public information is tampered with which will
lead to the generation of the wrong key Therefore this
paper introduces the reusable
hemp extraction
centrifuge robust fuzzy extractor and gives its
definition construction and points out its potential
application scenarios Introduction Uniformly distributed
random variables are widely used in cryptography For
example the most important element in a cryptosystem is
the key and the security of a cryptosystem depends on the
uniform randomness of the key In addition for public key
encryption or digital signature schemes the encryption
algorithm or signature algorithm also requires the
participation of random numbers to ensure the CPA
security or unforgeability of the encryption algorithm An
important question is how to generate uniformly
distributed random bits A source that generates random
bits with a certain entropy is called a Randomness Source
If the string generated by the "random source" is not
only "uniformly distributed" in the key space but also
"accurately reproduced" The "random source" can then be
used to generate the encryption and decryption keys for
the cryptographic algorithm However in real life there
are almost no such random sources that are uniformly
random and accurately reproduced In reality there are
many random sources with noise which have high (minimum)
entropy but are not uniformly random and each sampling
result is similar but there are some small deviations
(noise)

For example Human biological information such as
fingerprint voiceprint iris etc; Noise of electronic
components (unclonable function); Quantum information Can
we cryptographically transform these noisy random sources
into good random sources that produce random bits that
are "uniformly distributed" and "exactly reproduced" If
so then these random sources can be used by us and
provide an endless stream of reproducible random numbers
wiped film
evaporator for the cryptosystem Fuzzy extractor In
the past two decades many cryptographers have devoted
themselves to the study of how to use cryptographic
techniques to make noisy random sources to generate
uniformly random and accurately reproducible strings
Definition of Fuzzy Extractor In 2004 Dodis et al
Proposed the concept of fuzzy extractor to solve this
problem The fuzzy extractor FE = (Gen Rep) has two
algorithms the generative algorithm and the regenerative
algorithm The extractor is described as follows see
Figure 1 Gen (PR) Generation algorithm Gen inputs a
string w (one sample of a random source of noise) and
outputs a string R and a public helper string P; Rep(w'P)
R' Regeneration algorithm input W ' (another sample of a
random source of noise) and a public helper string P a
string R' is output Correctness The correctness
requirement is that if the distance between the two
samples w and w 'is close enough then R' = R that is R
can be reproduced accurately; Security The security
requirement is that if the random source has enough
entropy then R is uniformly random Expand the full text
The fuzzy extractor construct propose by Dodis et al
Depends on two component namely an (ordinary not fuzzy)
extractor and a secure sketch The extractor [13] can
convert non-uniform strings into uniform strings which
can be implemented using universal functions while the
secure sketch is dedicated to error correction which can
be implemented using linear error correction codes
Application of Fuzzy Extractor Using the fuzzy extractor
a noisy random source can be transformed into a uniformly
random and accurately reproduced string Fuzzy extractors
can be used in cryptosystems

Symmetric key generation Using the fuzzy extractor the
user can extract a random string R and a public helper
string P by calling the generation algorithm Gen (w) (P
R) with his own biological information (that is a noisy
random source) as input This random string R can be used
as the key of the cryptosystem to participate in the
cryptosystem and the public help string P is stored
without confidentiality The key R is destroyed as soon as
the cryptosystem has run When the cryptographic system
needs the key again for cryptographic operation the user
takes his own biometric information (ie noisy random
source) and the public helper string P as inputs and
calls the regeneration algorithm Rep (w ' P) R' to
reproduce the key R Therefore the user does not need to
store the key and the fuzzy extractor can recover the key
safely and reliably only by inputting own biological
information when the user needs the key each time thereby
solving the problems of key generation and storage After
that the key R is applied to the symmetric cipher
algorithm and Enc (R m) can be used to encrypt the
plaintext m to obtain the ciphertext C and Dec (R C) can
be used to decrypt the ciphertext C and recover the
plaintext m This is shown in Figure 2 Key agreement from
close secret Two-party key agreement is also possible
using the fuzzy extractor technique Let Alice have a
secret message w and Bob have a secret message w' Where
the distances of w and w 'are close For example Alice and
Bob are doing quantum key distribution; Alice and Bob are
listening to a noisy radio station at the same time;
Alice knows Bob's iris information Alice can use the
fuzzy extractor to act on w to obtain the secure key R
and a public helper string P send P to Bob and Bob can
call the fuzzy extractor regeneration algorithm Rep (w '
P) R to reproduce the key R Thus Alice and Bob complete
the key agreement See Figure 3 Application of GPRS in
public key cryptosystem Public-key cryptography typically
rely on difficult assumptions Hard assumptions generally
require uniformly random strings Uch as the ElGamal
encryption scheme rely on the "decisional Diffie-Hellman"
assumption associated with the discrete logarithm hard
problem The discrete logarithm problem is described as
follows Given a group of size p p is a large prime G is
the generator of the group and for a X p chosen uniformly
at random let Given y G computing the discrete logarithm
of y is the discrete logarithm problem For if X 'is not
uniformly distributed solving the discrete logarithm
problem for Z may no longer be difficult Through the
fuzzy extractor the user can extract a uniformly random X
from a noisy random source as the private key of the
ElGamal encryption scheme as the public key of the
ElGamal encryption scheme Robust fuzzy extractor The
security of fuzzy extractor only considers the passive
attack That is the public helper string P can be known by
the adversary but P cannot be tampered with by the
adversary If the adversary tampers with P then the
recovery algorithm Rep of the fuzzy extractor is likely
to get a wrong output R ′ But in real life an active
adversary may tamper with P For example in the key
agreement process an aggressive adversary can intercept

P and send a wrong P 'to Bob (see Figure 4) Then Bob's
call to the recovery algorithm Rep of the fuzzy extractor
is likely to result in a wrong output R ' If R ≠ R ' the
key negotiation fails In order to solve the above problem
Boyen et al [4] proposed the concept of robust fuzzy
extractor in 2005 There are two definitions of security
for the robustness of fuzzy extractors namely "pre-
application" robustness and "post-application" robustness
The robustness before application ensures that the
adversary submits a tampered one when he only sees the
public help string P and the recovery algorithm of the
fuzzy extractor can only output and can not produce a
wrong one However in practical applications if a user
uses R in some cryptographic schemes some or even all of
the information of R will be leaked to the adversary In
this case "pre-application" robustness no longer applies
" Post-application "robustness" can solve this problem
The post-application robustness guarantees that the
adversary can only output the recovery algorithm of the
fuzzy extractor when he sees P and R and submits a
tampered Boyen et al [4] proposed a general method to
transform fuzzy extractors into "pre-application" robust
fuzzy extractors by using Hash functions However in the
security proof the Hash function is regarded as a random
oracle so the security is based on the Random Oracle
model In 2006 Dodis et al [7] first constructed a "post-
application" robust fuzzy extractor under the standard
model In their construction inputting a bit string w of
length n and min-entropy m the extractor can extract a
uniformly distributed bit string of length l = (2m −
n)/3 It can be seen that the extracted random string does
not exceed 1/3 of the minimum entropy m In 2008 K a n u K
u R t H I and R e y Z I n C I t e { Kanukurthi 2008 }
constructed a "post-application" robust fuzzy extractor
and the length of the extracted random string is longer l
= (2m-n)/2 bits In 2009 Dodis et al [9] proved that in
the trivial model if the entropy rate (m/n) of the input
w is less than half then the robustness of the fuzzy
extractor is impossible to achieve In order to solve this
problem Cramer et al [6] proposed a new cryptographic
primitive algebraic manipulation detection (AMD) in 2008
At the same time a robust fuzzy extractor is constructed
by using AMD codes under the Common Reference String
(CRS) model CRS model means that the Common Reference
String is fixed in the hardware and no one can tamper
with the CRS Their proposed extractor breaks the line
that the entropy rate of a random source needs to be
greater than half of its length under the trivial model
Nonetheless the entropy loss of this extractor is
enormous Fuzzy extractor with repeatable extraction Using
the fuzzy extractor the user can extract the secure key
from his own biological information for encryption and
decryption and does not need to save the key After
enjoying the above convenience users may want to extract
multiple secure and reliable keys from their biometric
information and apply them to different organizations and
different scenarios However A person's biological
information is unique and cannot be altered or created;
The fuzzy extractor ensures the security of extracting a
key from a noisy random source And the security of
drawing multiple different keys from the same random
source cannot be guaranteed In order to solve the above
problem Boyen [3] proposed the concept of reusable fuzzy
extractor (Reusable Fuzzy Extractor) in 2004

The reusable fuzzy extractor (Reusable Fuzzy Extractor)
allows the production algorithm of the fuzzy extractor
Gen (w) (P R) to extract Gen multiple times over multiple
noisy versions of the random source W Suppose that w w1
wρ is the result of multiple reads of a random source W
then they are statistically correlated Invoking (P R) Gen
(w) (Pi Ri) Gen (wi) can get multiple sets of outputs (P
R) { Pi Ri } _ (I ∈ { 1 2 ρ})。 Let [ρ] = { 1 2
ρ } the reusable requirement of the fuzzy extractor is
that given { P _ I R _ I } I ∈ [ρ] and P R is still
pseudorandom In [3] Boyen proposed two construction
schemes for reusable fuzzy extractors and defined
"outsider security" and "insider security" Outward
security is defined as follows The adversary dynamically
chooses δi and gets Pi where (Pi Ri) Gen (w + δi) The
final (P R) { Pi Ri } I ∈ { 1 2 ρ } should be
pseudorandom to the adversary The definition of inward
security is as follows the adversary not only gets but
also sees where the choice is made by the adversary and R
is required to be pseudo-random to the adversary It can
be seen that inward security is stronger than outward
security but it is also more difficult to achieve In [3]
reusable fuzzy extractors that achieve inward security
are built on a "random oracle" model And the amount of
crosstalk δi must be independent of w In 2017 Apon et al
[2] upgraded the scheme proposed by Fuller et al [10] to
obtain a weak reusable fuzzy extractor whose weak
security depends on the LWE assumption Its security model
is similar to the "outward security" in [3] but only
requires that the offsets δi submitted by the adversary
satisfy dis (δi) ≤ t But as in the scheme in [10] the
error that Apon et al's Reusable fuzzy extractor can
tolerate is only logarithmic In 2018 we proposed a
reusable fuzzy extractor based on the LWE assumption and
the scheme can tolerate errors at the linear level [14]
In 2016 Canetti et al [5] proposed a general construction
scheme for reusable fuzzy extractors and an important
module used in the general construction is "digital
locker" In its security model for w w1 There is no
restriction on the dependence of wρ Therefore the
security model is also the strongest one at present
However there are only two implementations of "digital
locker" one uses Hash function to construct digital
locker and the security of digital locker depends on
"random oracle"; the other is based on non-standard DDH
variant assumption In addition their scheme can only
tolerate sub-linear level errors and has structural
requirements on the distribution of noise random sources
Then Alamelou et al [1] constructed a reusable fuzzy
extractor using the technical tool of "digitallocker"
proposed by Canetti et al [5] which is applicable to both
Hamming distance and distance between sets The ability of
their scheme to tolerate errors is improved to the linear
level However they need to subdivide the random source
into multiple blocks each of which is in a character set
that is large enough and has enough entropy In 2018 we
[16] proposed a concrete scheme for reusable fuzzy
extractors based on the standard DDH hardness assumption
The scheme is based on the standard assumptions of the
standard model and can tolerate linear level errors
However it is required that for any two reading results
wi and WJ of the same random source W the difference wi-
wj does not leak too much information about the
information source W

From the results w1 of multiple readings of the same
random source W There are three main directions for the
development of reusable fuzzy extractors (1) wi can be
arbitrarily correlated but the security can only rely on
"random oracles" or non-standard assumptions; (2) for any
two reading results wi and WJ of the same random source W
the difference wi − WJ does not leak too much
information about the information source W; (3) the
difference δi (= wi − w) of any two reading results wi
and WJ is controlled by the adversary This is summarized
in Figure 7 Table 1 summarizes the specific performance
of each scheme Before 2018 no researcher has proposed the
construction of fuzzy extractor under the standard model
to meet both robustness and reusability but we have
realized the fuzzy extractor with both for the first time
and the research results were published in the 2018 sub-
secret meeting Our Result Reusable Robust Fuzzy Extractor
In 2018 we defined reusable robust fuzzy extractors and
gave a general construction method Simply speaking
reusable robust fuzzy extractors satisfy both reusability
and robustness The modules used by our general
construction method are as follows Symmetric key
encapsulation mechanism (Symmetric Key Encapsulation
Mechanism SKEM for short) whose security requirement is
Key-Shift (KS) security; Secure Sketch (SS) with
Homogeneity; Extractor (Ext) with homogeneity; Lossy
Algebraic Filter (LAF) with Homogeneity We construct a
Key-Shift (KS) -secure SKEM based on the DDH problem a
homomorphic SS using linear error-correcting codes and a
homomorphic Ext using universal hash; A lossy algebraic
filter with homogeneity can be constructed based on the
DLIN problem [11] Through such a concrete construction we
obtain the first construction scheme of a fuzzy extractor
that is both reusable and robust (reusable robust fuzzy
extractor) with the following properties There is CRS in
the scheme so it is established on the CRS model;
Robustness is "post-application" robustness; The scheme
can tolerate linear level errors; Reusability and
robustness can be achieved under the standard model based
on DDH and DLIN assumptions to prove; In the security
model the adversary can control the offset δ _ I to
satisfy dis (δ _ I) ≤ DT Our work was published in
AsiaCrypt2018 (see [15] for the eprint version) and the
comparison with previous related work is listed in Figure
7 and Table 1 Our specific plan The reusable robust fuzzy
extractor rrFE = (rrFE Init rrFE Gen rrFE Rep) is
constructed as shown in Figure 8 and Figure 9 and the
requirements of the components are as follows Symmetric
key encapsulation mechanism (Symmetric Key Encapsulation
Mechanism abbreviated as SKEM) SKEM = (SKem Init SKem Enc
SKem Dec) whose key space is δκ The encapsulated key
space is κ

Secure Sketch with Homogeneity (SS) SS = (SS Gen SS Rec)
the measurement space is and Extractor (Ext for short)
with homogeneity A lossy algebraic filter with
homogeneity (Lossy Algebraic Filter LAF for short) LAF =
(FGen FEval FTag) whose domain is and label space is
Application prospect With the reusable robust fuzzy
extractor rrFE = (rrFE Init rrFE Gen rrFE Rep) the user
can use his own biometric information W as a noisy random
source cbd centrifugal
extractor such as a fingerprint which the user can
obtain via a fingerprint reading device (w1 wj wn)
then call the generation algorithm to generate (P1 R1)
(PjRj) (Pn Rn) Rj is used as a private key in
different scenarios such as access control devices
banking systems and smart homes The operation is as
follows (see Figure 9 and Figure 11) CRS generation CRS
is generated by using a rrFE Init and is solidified in
hardware; Key generation taking the biometric information
W as input the generation algorithm rrFE Gen (CRS W) is
called to generate a key R and a public helper string P;
Use the key and destroy it The key R participates in the
arithmetic operation of the cryptosystem and is destroyed
after use But that public help string P is store (not
necessarily secret); Key recovery when the cryptosystem
is used again the recovery algorithm rrFE Rep (CRS P W ')
is invoked with the public helper string P and the
(noisy) biometric information W ^' as input If the output
is the authentication is not passed; otherwise the output
R 'is the recovered key Destroy after using key R ' From
the properties of reusable robust fuzzy extractors we
have that the following holds

The correctness of the fuzzy extractor ensures that Rj
can be recovered by reading the fingerprint information
and calling the recovery algorithm when the user needs
Rj; The reusability of the fuzzy extractor guarantees
that every Rj J ∈ [n] is pseudorandom and even if some
Ri is leaked Rj J ≠ I is still pseudorandom; The
robustness of the fuzzy extractor ensures that if a
public help string Pj has been tampered with the fuzzy
extractor outputs that Pj has been tampered with Now we
still take the key agreement as an example to illustrate
the specific use of the reusable robust fuzzy extractor
With the reusable robust fuzzy extractor two users Alice
and Bob with close secret information can make "multiple"
key agreements see fig 12 and fig 13 CRS generation Alice
uses rrFE Init to generate CRS solidifies the CRS in
hardware and sends the CRS to Bob through a secure
channel Key generation Alice takes the secret information
W in her possession as input calls the generation
algorithm rrFE Gen (CRS W) and generates a key R and a
public helper string P; Key agreement Alice sends a
public helper string P of the key to Bob and Bob invokes
the recovery algorithm rrFE Rep (CRS P W ') If W and W'
are close enough R can be correctly recovered
From the properties of reusable robust fuzzy extractors
we have that the following holds The correctness of the
fuzzy extractor guarantees that Alice and Bob will get
the same Rj if the public help string Pj has not been
tampered with; The reusability of the fuzzy extractor
guarantees that each Rj J ∈ [n] is pseudorandom and even
if a R _ I is leaked Rj J ≠ I is still pseudorandom; The
robustness of the fuzzy extractor ensures that if a
public help string P _ J has been tampered with the fuzzy
extractor will output a message to the user that P _ J
has been tampered with the key negotiation has failed and
another negotiation is required

References [1] Q Alamélou P Berthier C Cachet SCauchie B
Fuller P Gaborit and S SimhadriPseudoentropic isometries
A new framework for fuzzy extractor reusability In J Kim
G AhnS Kim Y Kim J López and T Kim editorsAsiaCCS 2018
pages 673684 ACM 2018 [2] D Apon C Cho K Eldefrawy and
J KatzEfficient reusable fuzzy extractors from LWEIn S
Dolev and S Lodha editors CSCML2017 volume 10332 of LNCS
pages 118SpringerHeidelberg 2017 [3] X Boyen Reusable
cryptographic fuzzy extractorsIn V Atluri B Pfitzmann and
P D McDanieleditors CCS 2004 pages 8291 ACM 2004 [4] X
Boyen Y Dodis J Katz R Ostrovsky and A D Smith Secure
remote authentication using biometric data In R Cramer
editorEUROCRYPTvolume 3494 of LNCS pages 147163
Springer Heidelberg 2005 [5] R Canetti B Fuller O Paneth
L Reyzinand A D Smith Reusable fuzzy extractors for low-
entropy distributions In M Fischlin and J Coron editors
EUROCRYPT 2016volume 9665 of LNCS pages 117
146SpringerHeidelberg 2016

[6] R Cramer Y Dodis S Fehr C Padró and DWichs
Detection of algebraic manipulation with applications to
robust secret sharing and fuzzy extractors In N P Smart
editor EUROCRYPT 2008 volume 4965 of LNCS pages 471
488Springer Heidelberg 2008 [7] Y Dodis J Katz L Reyzin
and A D SmithRobust fuzzy extractors and authenticated
key agreement from close secrets In C Dworkeditor CRYPTO
2006 volume 4117 of LNCSpages 232250 Springer
Heidelberg 2006 [8] Y Dodis L Reyzin and A D Smith Fuzzy
extractors How to generate strong keys from biometrics
and other noisy data In C Cachin and J Camenisch editors
EUROCRYPT 2004 volume 3027 of LNCS pages 523540Springer
Heidelberg 2004 [9] Y Dodis and D Wichs Non-malleable
extractors and symmetric key cryptography from weak
secrets In M Mitzenmacher editor STOC 2009pages 601610
ACM 2009 [10] B Fuller X Meng and L Reyzin Computational
fuzzy extractors In K Sako and P Sarkareditors ASIACRYPT
2013 volume 8269 of LNCS pages 174193 Springer
Heidelberg2013 [11] D Hofheinz Circular chosen-ciphertext
security with compact ciphertexts In T Johansson and PQ
Nguyen editors EUROCRYPT 2013 volume 7881 of LNCS pages
520536 SpringerHeidelberg 2013

[12] B Kanukurthi and L Reyzin An improved robust fuzzy
extractor In R Ostrovsky R DPrisco and I Visconti editors
SCN 2008volume 5229 of LNCS pages 156171Springer
Heidelberg 2008 [13] V Shoup A computational introduction
to number theory and algebra Cambridge University Press
2006 [14] Y Wen and S Liu Reusable fuzzy extractor from
LWE In W Susilo and G Yang editors ACISP 2018 volume
10946 of LNCS pages 1327Springer Heidelberg 2018 [15] Y
Wen and S Liu Robustly reusable fuzzy extractor from
standard assumptions Cryptology ePrint Archive Report
2018/818 2018 https//eprintiacrorg/2018/818 [16] Y Wen S
Liu and S Han Reusable fuzzy extractor from the
decisional diffie-hellman assumption Designs Codes and
Cryptography2018 Author > > > Liu Shengli part-time
expert of Tongmoshi Laboratory professor and doctoral
supervisor of Department of Computer Science and
Engineering Shanghai Jiaotong University mainly studies
the theory and practice of public key cryptography

Wen Yunhua Ph D candidate Grade 2013 Shanghai Jiao Tong
University focuses on the reusability and robustness of
noisy extractors (This article is selected from the
second issue of Information Security and Communication
Security in 2019) Original statement > > > The original
articles published on this WeChat public account are
welcome to be forwarded by individuals Without
authorization other media Wechat public numbers and
websites are not allowed to reproduce Return to Sohu to
see more Responsible Editor
toptiontech.com

If you wish to post a reply to this topic you must first login
If you are not already registered you must first register

Printable version

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot delete your posts in this forum
You cannot edit your posts in this forum
You cannot create polls in this forum
You cannot vote in polls in this forum