diff options
Diffstat (limited to 'content/implementation.tex')
| -rw-r--r-- | content/implementation.tex | 10 |
1 files changed, 9 insertions, 1 deletions
diff --git a/content/implementation.tex b/content/implementation.tex index 6de7e4b..d6dbef4 100644 --- a/content/implementation.tex +++ b/content/implementation.tex @@ -31,7 +31,15 @@ So as to not worry about any other network serialization, this framework uses Go \subsection{Mapping strings to Ed25519 points} -There exists no deterministic and reversible mapping from integer values to elliptic curve points. However There is a probabilistic algorithm called the Koblitz's method\cite{Koblitz}. It starts by choosing a number that will be used as a ``stride''. The string you want to encode as a point has to be interpreted as a group element and multiplied by the stride. The result of this multiplication must also be a group element. This means your message space is made smaller by a factor ``stride''. Now you can check if your result has a corresponding $x$ coordinate, in the case of Ed25519. If it has one you are done, if it doesn't you add $1$ to your current trial $y$ coordinate and check again. This continues up until your trial $y$ coordinate reaches the value of $first\_trial\_y\_coordinate + stride$. If you haven't found a suitable $y$ coordinate by now this mapping algorithm fails. +So to use the homomorphic property of ElGamal we need to directly encode user input of the \cmix network into, in this case, valid curve points. + +\subsubsection{Elligator} + +An algorithm that might spring to mind first is the Elligator algorithm\cite{Bernstein:2013:EEP:2541806.2516734} to map curve points to strings indistinguishable from random strings. However this is the exact reverse of the operation I need in \cmix. Elligator works by converting curve points to a representative, a random string. However not every possible string of that size is an representative of a curve point. This makes it impossible to use the Elligator reverse mapping for this problem. + +\subsubsection{Koblitz's method} + +There exists no deterministic and reversible mapping from integer values to elliptic curve points. However there is a probabilistic algorithm called the Koblitz's method\cite{Koblitz}. It starts by choosing a number that will be used as a ``stride''. The string you want to encode as a point has to be interpreted as a group element and multiplied by the stride. The result of this multiplication must also be a group element. This means your message space is made smaller by a factor ``stride''. Now you can check if your result has a corresponding $x$ coordinate, in the case of Ed25519. If it has one you are done, if it doesn't you add $1$ to your current trial $y$ coordinate and check again. This continues up until your trial $y$ coordinate reaches the value of $first\_trial\_y\_coordinate + stride$. If you haven't found a suitable $y$ coordinate by now this mapping algorithm fails. You can map a point back to the original string by dividing the y coordinate with the ``stride''. This works because of integer division and because we only add a value less than the stride to the original number. |