So how can Bob a lock down a message for a given amount of time, and get Alice to prove some work in order to read the message? For this we need to find a intrinsically sequential work task (so that it is cannot be run in a parallel manner). Ron Rivest [paper] defined a puzzle which was fairly easy to compute [\(O(\log(n))\)] and more difficult to solve [\(O(n^2)\)]. For this we create a random value (\(a\)) and then raise it to the power of \(2^t\), and where \(t\) is the difficulty level:
Time-lock puzzles/Proof of Work (squaring)OutlineThe method, as outlined by Rivest [paper] defines the usage of a squaring process which increases the work to compute the key. Now let's say that Bob wants to make sure that Alice cannot open a message within a given amount of time. Initially Bob starts with two prime numbers (\(p\)) and (\(q\)) and determines (\(n\)): \(n = p \times q\) We can also calclate PHI as: \(PHI = (p-1) \times (q-1)\) Next we create an encryption key (\(K\)) and with a message (\(M\)) we encrypt: \(C_m=Encrypt(K,M)\) Next we select a random value (\(a\)) and a difficulty level (\(t\)), and compute a value of \(b\) which is added to the key (\(K\)): \( C_K = K + a^{2^t} \pmod n \) Bob will then send {\({n,a,t,C_K,C_m}\)} to Alice, and get her to prove her work in order to decrypt the cipher message (\(C_m\)). Alice then takes the values and computes the key with: \(Key = C_K - a^{2^t} \pmod n \) and which will have a workload dependent on the difficulty (t). Bob, though, does not have the same workload at Alice, as he knows some or the original values. For him, he uses PHI to reduce the complexity: \( \epsilon = 2^t \pmod {PHI}\) And then the calculation of the value to find becomes: \(b = a^e \pmod n\) Message: The quick brown fox Keyseed: 12345 Key: WZRHGrsBESr8wYFZ9sx0tPURuZgG2lmzyvWpwXPKz8U= Keyval: 40517827634140982427891826463487354397562163067645485726320510288945209855941 Bob sends this as the puzzle N: 580851965563854829725809206141825916677454309261703879630091472978305957048534640380745461828 7525932811499665099257674691573742312634492877501558241926510855265445655865943438821912402793071 4101937187690331388952928999846217357829744504540231133743739186730370422530668189420896715571065 0547358575154790342206849212094827367872131512046364176440501080488076457751799130665018200405365 4755677171480098164870018127440284136797039199208818583865459976018367716791615092378912189828151 3940093485238595133368707040032458961340590434288414979880228734657295401299054013238618927900089 54081042521197986890397363455472811639 a: 101 t: 1 CK: 40517827634140982427891826463487354397562163067645485726320510288945209866142 Encrypted: gAAAAABbCrlEUvLDQQX6gIiGqA81TTHzm5rD4Y6c4I5X5-qnkhGzqC8lOojkzmmy4cIJ3WXIn9aKO_5P3VY21ScNDf0wtOsTXo93-GbmwF6-_hBtyInh6g8= Alice receives and now computes Key guess= 40517827634140982427891826463487354397562163067645485726320510288945209855941 Decrpyted: The quick brown fox As an example, for values the computing the key for Alice (with a=999) are: t=8 0.000999927520752 seconds t=16 0.208999872208 seconds t=18 2.0 seconds t=20 26.7730000019 seconds Results from 3.5GHz Xeon processor And here is some sample code. We u.se SHA-256 to hash the seed. # https://asecuritysite.com/encryption/pow2?Length=10 import datetime import time import hashlib import base64 from cryptography.fernet import Fernet from base64 import b64decode, b64encode import random message="hello" keyseed = "12345" a = random.randint(99999,999999) t= 8 print ("Message:\t",message) print ("Keyseed:\t",keyseed) p=75184456329323393981453160999168869619896388565246270326667621020749883434526629149123313289822093813309128973674541785507146180116583118006552309466590981238828120901809218798591532127897713278598850326780359769279464340716666681725354754726329143696440538687112219849324721464631600820710676683650403820541 q=77256921699294288099751913986725879141470275753142260831695319390868938092522018978912165340760059157501314281329434440243543281733706145540078343592028736575027896004544593182243130855408638162095082271337507750610446164552740816661833414846974163466111988532153163988528271485739448606877973413411116622979 n = p*q PHI = (p-1)*(q-1) h = hashlib.sha256(keyseed.encode()).digest() key=base64.urlsafe_b64encode(h) encrypted = Fernet(key).encrypt(message.encode()) print ("Key:",key) keyval = int(b64decode(key).hex(),16) print ("Keyval:",keyval) CK = (keyval + a**(2**t)) % n print ("\n\nBob sends this as the puzzle") print ("N:\t",n) print ("a:\t",a) print ("t:\t",t) print ("CK:\t",CK) print ("Encrypted:\t",encrypted) print ("\n\nAlice receives and now computes") t1 = time.time() Key = (CK - a**(2**t)) % n t2 = time.time() print ("\nKey guess (int):",Key) Keyguess = base64.urlsafe_b64encode( Key.to_bytes(32,byteorder='big')) print ("Key guess:",Keyguess) decrypted = Fernet(Keyguess).decrypt(encrypted) print ("Decrypted:",decrypted ) print ("Time for Alice to compute:",t2-t1) #print "\n\n--------Bob's calculation---------------------" #t1 = time.time() #eps = (2**t) % PHI #b =(a**eps) % n #t2 = time.time() #print "Bob\'s value", b #print "Time for Bob to compute:",t2-t1 Presentation |