Back
Puzzle 2

29th November

19:00 UTC

Built by: Applied Cryptography Group @ Stanford

With great power comes great responsibility.


View the solution

Puzzle Preparation

To give you a better chance of solving this puzzle, we suggest that you look through some relevant background materials.


See puzzle details on Github

Puzzle link

Click the link for background material on Discrete Logarithm Problems with Auxiliary Inputs by Jung Hee Cheon.

Link

Click the link for background material - Ariel Gabizon’s write-up about Cheon’s discrete log attack.

Link

Puzzle Hints

1. Try using the Bls12Cheon::pairing functionality to calculate the following pairing values: e(P, Q), e(τP, Q), e(τ^{d_1} P, τ^{d_2} Q) ∈ F_{p^k}. Can you apply Cheon’s attack to these values?
2. Look at the algorithm described on pages 4-5 of Cheon’s paper, and apply this algorithm to the three values from Hint #1 to find τ in time O(√(q/d)).
3. Since we know the lower and upper bounds on k_0, the m in the BSGS algorithm to kind k_0 can be smaller than expected - it can be be sqrt(B - A)

Puzzle Winners


gold 01

niooss-ledger

Puzzle completed

Score

1000

silver 02

Konstantce

Puzzle completed

Score

988.8

bronze 03

bkomuves

Puzzle completed

Score

900


You can see all of the scores for this puzzle in the spreadsheet here.

Puzzle Solution

The winner of the puzzle write up was submitted by niooss-ledger. You can view the solution and puzzle write up here. The background material required to solve the puzzle is also covered in the write up.