The Lizard Method of Point Reversal

A common operation on elliptic curves is to hash data onto a point onto the curve. But can we reverse the point back to the hashed data? For this, we can use the Lizard method within a Ristretto group constructed from Edwards25519. It was first defined by Abraham Westerbaan [1]:

Overall, if we do not want to reverse the point back to data, we should use the Derive() method:

Ristretto prime-order group built from Edwards25519

If we need to reverse the point back to data, we can use the SetLizard() method:

m:="Hello"
 
var p ristretto.Point

 h := sha256.Sum256([]byte(m))

 var ret [16]byte
 copy(ret[:], h[:])

 
 p.SetLizard(&ret) 

In this case, we create a SHA256 hash, and then copy 16 bytes into the curve point (p). To reverse, we can then apply [here]:

m:="Hello" 
var p ristretto.Point
 var outBuf [16]byte

 h := sha256.Sum256([]byte(m))

 var ret [16]byte
 copy(ret[:], h[:])

 
 p.SetLizard(&ret) 

 _=p.LizardInto(&outBuf) 

outBuf will then contain the 16 lower bytes of the hash value of the message. A sample run of a message of “Ristretto is traditionally a short shot of espresso coffee”, gives a lower 16 bytes of SHA256 as 5bda9ccfb18cba655815796cca76b56d, and which is then encoded into the Lizard point of “ODoeJvsK7nHF1AV1BeieOn83iESS4F9v0l0cHR-nRHg”. This can then be reversed to give the original hash [here]:

Message=  Ristretto is traditionally a short shot of espresso coffee
Hash=   5bda9ccfb18cba655815796cca76b56d
Lizard point=  ODoeJvsK7nHF1AV1BeieOn83iESS4F9v0l0cHR-nRHg

Reverse=  5bda9ccfb18cba655815796cca76b56d

The full code is [here]:

package main

import (

 "fmt"
 "crypto/sha256"

 "github.com/bwesterb/go-ristretto"
 "os"

)


func main() {

  m:="hello"

  argCount := len(os.Args[1:])
  if argCount > 0 {
  m =os.Args[1]
  }



 var p ristretto.Point
 var outBuf [16]byte

 h := sha256.Sum256([]byte(m))

 var ret [16]byte
 copy(ret[:], h[:])

 
 p.SetLizard(&ret) 

 _=p.LizardInto(&outBuf) 


 fmt.Printf("Message=\t\t%s\n",m)
 fmt.Printf("Hash=\t\t\t%x\n",h[:16])
 fmt.Printf("Lizard point=\t\t%v\n",p)

 fmt.Printf("\nReverse=\t\t%x\n",outBuf)


}

References

[1] Westerbaan, A., & Hendriks, L. (2020, June). Polymorphic encryption and pseudonymisation of IP network flows. In 2020 IFIP Networking Conference (Networking) (pp. 494–498). IEEE. https://arxiv.org/pdf/1911.02674v2.pdf