Quiz
7b Homomorphic encryption and Attribute-based credentials
This quiz has question types that open in the usual player.
Questions in this quiz (20)
1[blank_start]Group[blank_end] homomorphism
Given (G, +) , (H, x) two groups, the function h: G => H is a group homomorphism if for all u, v in G,
h(u [blank_start]+[blank_end] v ) = h(u) [blank_start]x[blank_end] h(v)- A+
- Bx
- CGroup
2Homomorphic cryptosystems are [blank_start]malleable[blank_end] by nature
There exists an homomorphism between their cipher text and plaintext space
h(x) = Dec(x) => [blank_start]homomophism[blank_end] between C and P
[blank_start]Partial[blank_end] homomorphic support [blank_start]1[blank_end] arithmetic operation:
Enc: (P, [blank_start]+[blank_end]) => (C, [blank_start]x[blank_end])
for all m1, m2 in P, Enc(m1) [blank_start]x[blank_end] Enc(m2) = Enc(m1 [blank_start]+[blank_end] m2)
- Ax
- B+
- C+
- Dx
- E1
- FPartial
- Ghomomophism
- Hmalleable
3Paillier cryptosystem is [blank_start]additive[blank_end]ly homomorphic:
> Let p, q = 2 [blank_start]prime[blank_end]s s.t. gcd(pq, (p-1) (q-1)) = 1
> n = pq
> d = (p-1)(q-1)
> u = f^-1(n) mod n
> Private key: ([blank_start]d[blank_end], u)
> Public key: [blank_start]n[blank_end]
For message m in P, r in Z*_n^2 (cyclic group order n^2)
Enc(m) = (1+n)^m * r^n mode n^2
Dec(c) = ( [ c^f(n) mod n^2] - 1 )/ n * f^-1(n) mod n
ex. p = 11, q = 17
n = 11 * 17 = 187, n^2 = 34969
f(n) = 160
m = 175, r = 83 in Z*_187
cipher text = (1+[blank_start]187[blank_end])^[blank_start]175[blank_end] * [blank_start]83[blank_end]*187 mode [blank_start]34969[blank_end] = 23911
decryption:
m = ( [ 23911^[blank_start]160[blank_end] mod 34969] - [blank_start]1[blank_end] )/ [blank_start]187[blank_end] * [ [blank_start]160[blank_end]^-1 mod [blank_start]187[blank_end]] mod 187 = 175 = m- Aadditive
- Bprime
- Cd
- Dn
- E187
- F175
- G83
- H34969
- I160
- J1
- K187
- L160
- M187
4Possible ways of authentication:
> Username & [blank_start]password[blank_end]
> Bio[blank_start]metric[blank_end]s
> Client [blank_start]certificate[blank_end]s
> [blank_start]Challenge[blank_end] response with public key cryptography (ssh)- Apassword
- Bmetric
- Ccertificate
- DChallenge
5Issuer or Identity Provider (IdP): entity that [blank_start]validate[blank_end]s the information in the documents
Verifier or Service Provider (SP): entity that [blank_start]verifie[blank_end]s that the information is [blank_start]correct[blank_end] and provides a service- Avalidate
- Bverifie
- Ccorrect
6[blank_start]Attribute[blank_end]-based credentials (anonymous credentials):
> Attributes are encoded as n[blank_start]umber[blank_end]s, may represent, e.g.,
• Membership status (normal user, premium user)
• Name
• Age
• Social security number
• Random identifiers
• Application-specific identifiers
Need credentials to satisfy these properties:
>[blank_start]Unforgeability[blank_end]: only the [blank_start]issuer[blank_end] should be able to produce [blank_start]valid[blank_end] credentials.
> [blank_start]Selective[blank_end] [blank_start]disclosure[blank_end]: the user can hide ir[blank_start]relevant[blank_end] attributes
> [blank_start]Issuer[blank_end] [blank_start]unlinkability[blank_end]: the issuer should not be able to [blank_start]recognize[blank_end] a
credential that it previously issued
>[blank_start]Verifier[blank_end] [blank_start]unlinkability[blank_end]: the verifier should not be able to link two consecutive showings of the [blank_start]same[blank_end] credential
- AAttribute
- Bumber
- CUnforgeability
- Dissuer
- Evalid
- FSelective
- Gdisclosure
- Hrelevant
- IIssuer
- Junlinkability
- KVerifier
- Lunlinkability
- Msame
- Nrecognize
7Traditional signatures satisfy issuer unlinkability.
- ATrue
- BFalse
8Blind signatures:
signer signs a message m with[blank_start]out[blank_end] knowing what it signs. Moreover, it cannot later [blank_start]recognize[blank_end] this signature.
Needed property: [blank_start]Issuer[blank_end] [blank_start]unlinkability[blank_end]
- Aout
- Brecognize
- CIssuer
- Dunlinkability
9zero-knowledge proof: Cave of Ali Baba
Peggy (the prover) discovers a cave with a secret door. When she speaks the right password the door opens. She need to prove to Victor (verifier) that she can opens the door without revealing the [blank_start]password[blank_end].
[blank_start]Repeat[blank_end]edly:
1. Peggy enters the cave and picks a random [blank_start]side[blank_end].
2. Victor enters and shouts left/right
3. Peggy exists at the requested [blank_start]side[blank_end].
- ARepeat
- Bside
- Cside
- Dpassword
10Properties of zero-knowledge proofs
> [blank_start]Completeness[blank_end]: If the statement is true, an honest prover can [blank_start]convince[blank_end] an honest verifier that the [blank_start]statement[blank_end] is true.
> [blank_start]Soundness[blank_end]: If the statement is false, a cheating prover [blank_start]cannot[blank_end] convince an honest verifier with very [blank_start]high[blank_end] [blank_start]probability[blank_end] (i.e., very close to 1).
> [blank_start]Zero[blank_end]-[blank_start]knowledge[blank_end]: If the statement is true, [blank_start]no[blank_end] verifier learns [blank_start]anything[blank_end] other than the fact that the [blank_start]statement[blank_end] is [blank_start]true[blank_end].- ACompleteness
- Bconvince
- Cstatement
- DSoundness
- Ecannot
- Fhigh
- Gprobability
- HZero
- Iknowledge
- Jno
- Kanything
- Lstatement
- Mtrue
11For every verifier there exists some [blank_start]simulator[blank_end] that given the [blank_start]validity[blank_end] of the statement (and without interacting with an honest prover) can
produce transcripts that “look like” an interaction between the verifier and an honest prover.
Ali baba's cave: [blank_start]agree[blank_end] on the test order 'right', 'left, 'right', 'right'.
Solution: Peggy & Victor enters together, Peggy makes a [blank_start]loop[blank_end].
- Aloop
- Bagree
- Csimulator
- Dvalidity
12Zero knowledge proof example: Schnorr signature (adds 'text' to hash)
y = [blank_start]g[blank_end]^x
> Prover P: publishes y and pretend to know [blank_start]x[blank_end]
> P commits to w and publishes t = g^w
> Prover P: Generate challenge c = H([blank_start]y[blank_end], [blank_start]t[blank_end], 'txt')
> Prover P: publishes s = [blank_start]cx[blank_end] + w
< Verifier: verifies that g^s = g^([blank_start]cx[blank_end]+w) = (g^x)^[blank_start]c[blank_end] * g^w = [blank_start]y[blank_end]^c * t
>> without knowing x, Prover P cannot calculate [blank_start]s[blank_end]- Ag
- Bx
- Cy
- Dt
- Ecx
- Fcx
- Gc
- Hy
- Is
13Proof of [blank_start]knowledge[blank_end]: There exists an extractor that, given a successful prover, can extract the wit[blank_start]ness[blank_end] (value of which knowledge is being proved).
>> By running 2 times the zero-knowledge proof in the pic, we could've calculated [blank_start]x[blank_end] = ([blank_start]s1[blank_end] - s2)/(c1 - [blank_start]c2[blank_end])
- As1
- Bc2
- Cx
- Dknowledge
- Eness
14Honest-verifier special soundness
• Given two answers to a single commitment: can extract the secret.
• Hence, a cheating prover can answer at most [blank_start]one[blank_end] challenge.
• Soundness probability is: 1 - [blank_start]1[blank_end]/[blank_start]p[blank_end]- A1
- Bp
- Cone
15Example of use of zero-knowledge proof: privacy [blank_start]pass[blank_end]
Goal: automatically [blank_start]allow[blank_end] real users, implemented by Cloudflare and Tor browser.
Needed properties:
[blank_start]unlinkability[blank_end]: cloudflare (adversary) should not be able to [blank_start]link[blank_end] tokens to the same user
- Apass
- Ballow
- Cunlinkability
- Dlink
16Privacy pass: g = generator
1) Obtaining token:
> User: Pick t = {0, 1}^128, Pick b in cyclic group Z_p. Send B = H(t)^[blank_start]b[blank_end], H = hash func
< Cloud: Having sk = s, pk = h = g^s. Send C = [blank_start]B[blank_end]^[blank_start]s[blank_end] (signs)
> User: Get token (t, T), where T = C^([blank_start]b[blank_end]^-1) = H([blank_start]t[blank_end])^s
2) Show token:
> User: Sends t, T
< Cloud: checks H(t)^s = [blank_start]T[blank_end]
- AT
- Bb
- Ct
- Ds
- EB
- Fb
17The private pass uses the proof of equivalence of logarithm to validate the token:
PK{(s): h = g^s and C = B^s}- ATrue
- BFalse
18[blank_start]BBS[blank_end]+ credentials: a signature scheme
• Given a credential (A, e, s)
• [blank_start]Hidden[blank_end] attributes: (a_i)i in H (not shown to verifier)
• [blank_start]Disclos[blank_end]ed attributes: (a_i)i in D (shown to verifier)
• Construct the “proof”: (see picture)
- ABBS
- BHidden
- CDisclos
19Select the Properties of BBS+ credentials
- AUnforgeability
- BSelective disclosure:
- CIssuer unlinkability
- DVerifier unlinkability
20We can always revoke a credential that is being misused / user decided to withdraw:
> [blank_start]Blacklistable[blank_end] [blank_start]anonymous[blank_end] credentials:
• For every [blank_start]transaction[blank_end], user produces a [blank_start]token[blank_end]
• Tokens belong to users, but SP cannot determine which user
• Users use a [blank_start]credential[blank_end] to prove that the token is correctly formed
:( users can make [blank_start]unlimited[blank_end] number of tokens
> [blank_start]Limit[blank_end] the number of [blank_start]use[blank_end]s: [blank_start]n[blank_end]-times anonymous credentials can be used for at most n times. Thereafter, verifiers can recognize [blank_start]reuse[blank_end]
:) [blank_start]limit[blank_end] the number of tokens a user can create
> [blank_start]User[blank_end] driven revocation: Token = (t, T = [blank_start]t[blank_end]^[blank_start]s[blank_end]), and user makes [blank_start]s[blank_end] public, then verifiers can check a token h, # against all revoked s1, s2, ... sn
:( Suffers from [blank_start]backward[blank_end] [blank_start]linkability[blank_end] problems
> [blank_start]Issuer[blank_end] driven revocation: Issuer [blank_start]add[blank_end]s random attribute a0. User constructs token: (t, T = t^a0) where t = a random element. Now issuer can reveal [blank_start]a0[blank_end] to [blank_start]revoke[blank_end] a credential.
:) Issuer can trace [blank_start]user[blank_end]s with[blank_start]out[blank_end] their knowledge
:) [blank_start]No[blank_end] backward unlinkability
OR
Use accumulators to hold a blacklist.- ABlacklistable
- Banonymous
- Ctransaction
- Dtoken
- Ecredential
- Funlimited
- GLimit
- Huse
- In
- Jreuse
- Klimit
- LUser
- MIssuer
- Ns
- Obackward
- Plinkability
- QNo
- Ruser
- Sout
- Tadd
- Ua0
- Vrevoke
- Wt
- Xs
Information
- Description
- - Information security (7 PIR, Zero knowledge Proof, Paillier, Cyclic group) Quiz on 7b Homomorphic encryption and Attribute-based credentials, created by Yawen Hou on 11/06/2019.
- Author
- Yawen Hou
- Language
- English
- Views
- 0
- Tags
- Rating
- No ratings yet Rate this quiz