博客

CSCI971/CSCI471 Modern Cryptography

Winter 2023

代写密码学作业 Prove BLS signature scheme is secure assuming co-CDH assumption holds in pairing e and H is modeled as a random oracle.

Assignment 2 (25 marks)

Note: if you give a long-redundant answer and it is hard to find the key points, marks will be deducted.

1.ZK protocols given in the lectures can be extended to a more generalized form which is called Sigma protocols. Sigma protocol can be defined between a Prover and a Verifier as follows:

Let R ⊆X × Y be an effective relation where X, Y and R are efficiently recognizable finite sets.

Elements of Y are called statements. If (?, ?) ∈ ?, then x is called a witness for y. P is an interactive protocol algorithm called the prover, which takes as input a witness-statement pair (x, y) ∈ R. V is an interactive protocol algorithm called the verifier, which takes as input a statement y ∈ R, and which outputs accept or reject.

To start the protocol, P computes a message t, called the commitment, and sends t to V; Upon receiving P’s commitment t, V chooses a challenge c at random from a finite challenge space C, and sends c to P; Upon receiving V’s challenge c, P computes a response z and sends z to V; Upon receiving P’s response z, V outputs either accept or reject, which must be computed strictly as a function of the statement y and the conversation (t, c, z). The name Sigma protocol comes from the fact that the “shape” of the message flows in such a protocol is vaguely reminiscent of the shape of the Greek letter Σ. 代写密码学作业

Sigma protocol can be used for proving linear relations among group elements. Let G be a cyclic group of prime order q generated by g. We define Boolean formulas ? as follows where g and u are elements of G.

We can define relation for a specific class F of such formulas:

A statement is a formula ∅ ∈ F, and a witness for ∅ is an assignment (α₁, … , α_n) ∈ to x₁, … , x_n that makes the formula true. The following figure demonstrates the protocol.

By applying the above generic sigma protocol, write down the ZK protocols satisfying the following relations.

1) For α, β, γ ∈z_q, (g^α, g^β, g^γ) is a DH-triple if γ = αβ.

Namely, (u, v, w) is a DH-triple if and only if there exists β ∈ z_q such that v = g^β and w = u^β. The relation is as follows (prove the DH relation). 3 marks

2) Give the ZK protocol satisfying the following relation. 3 marks

3) Suppose Alice has one ciphertexts (v₀, e₀) that encrypt a message m under Bob’s public key u₀, and another (v₁, e₁) that encrypts the same message m under Bill’s public key u₁. She wants to convince to a third party that this is true without revealing anything else. The encryption algorithm is multiplicative version of Elgamal encryption algorithm. Please write down the relation and the protocol. 3 marks

4) Similar to the above case that Alice has two ciphertexts encrypts the same message m, but this time under only Bob’s public key u. Please write down the relation and the protocol. Notice that in this case,Alice does not even need to know the message itself which is not the case in (3). 3 marks

2.BLS signature. Let e: G₀ × G₁ → G_T( be a pairing where G₀, G₁and G_T( are cyclic groups of prime order q,and g₀ ∈ G₀, g₁ ∈ G₁ are two generators in the corresponding groups. 代写密码学作业

H is a hash function maps messages to elements in G₀. BLS works as follows:

-G(): The key generation algorithm runs as follows

α←Z_q,

The public key is pk := u, and the secret key is sk := α

-S(sk, m) : To sign a message m ∈ M using a secret key sk = α ∈ Zq, do:

σ←H(m)^α ∈Go, output σ

-V(pk, m,σ) : To verify a signature σ ∈ Go on a message m ∈ M,

It can be shown that BLS signature scheme is secure under the co-CDH problem which is described as follows.

co-CDH Problem. 代写密码学作业

For a given adversary A, the attack game is defined as follows:

• The challenger computes

And gives the tuple (u₀, u₁, v₀) to the adversary. Notice here Go is used twice, once in group G₁ and once in group G₁.

• The adversary outputs some

The advantage of the attack is defined as coCDHadv[A, e] = Pr( )

We say that the co-CDH assumption holds for pairing e if for all efficient adversary A the coCDHadv[A, e] is negligible.

1). Write down the verification step. 2 marks

2). Prove BLS signature scheme is secure assuming co-CDH assumption holds in pairing e and H is modeled as a random oracle. Proof should be organized in the figure style between the challenger and the adversary.

(Hint: apply the similar strategy as RSA-FDH) 4 marks

3). Signature aggregation is a feature to compress signatures on different messages, issued using different signing keys, into a single short aggregate signature. The aggregated short signature convinces the verifier that all the input messages were properly signed. It has many real-world applications, and the most significant one is the certificate chain. 代写密码学作业

It contains multiple certificates issued by different authorities, and one can aggregate all the signatures in the chain into a single short aggregated signature. This shrinks the overall length of the certificate chain, which makes it more efficient regarding the storage size. An aggregate signature scheme SA is a signature scheme with two additional efficient algorithms A and VA as follows.BLS signatures can be easily aggregated by the following procedure.

Please write down the VA algorithm. 3 marks

4). The above BLS aggregated signature is not secure. An adversary can launch an attack which can make a user sign some message, but actually he or she did not actually sign. Please describe the attack, and try to fix the flaw. 4 marks

Submission:

Submit the pdf file to the Moodle site. The following information should be provided on the top.

CSCI971/CSCI471 Modern Cryptography

Assignment 2

Name:_________

Student Number:_____________

Plagiarism:

A plagiarised assignment will receive a zero mark (and be penalised according to the university rules).

更多代写：加拿大Econ网课代上  gre代考多少钱  美国组织学代写  民族学essay代写  欧美文学论文代写  Cloud Computing作业代写

合作平台：essay代写 论文代写 写手招聘 英国留学生代写