Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Implement Interpolation and Decryption Algorithm #5

Open
ymarcus93 opened this issue Apr 6, 2020 · 0 comments
Open

Implement Interpolation and Decryption Algorithm #5

ymarcus93 opened this issue Apr 6, 2020 · 0 comments
Assignees
@ymarcus93
Labels
protocol

Comments

@ymarcus93
Copy link
Owner

From the paper on p.11:

Since the code for generating the (U, s) values occurs on the client side, a malicious adversary could alter the (U,s) values of their share, producing combinations that cannot be used to derive a valid key, k. To mitigate this threat, the decryption algorithm is provided a vector of matched shares containing (U,s) values as well as ciphertexts to be decrypted. The algorithm first tries to interpolate the first two (U, s) values. If a valid key, k, is found, it is used to decrypt as many remaining c_e or c_a values as possible. Otherwise, it tries to interpolate and find a valid k with all remaining shares. If no valid key is found, an error message is produced for the current share and the algorithm moves onto repeat this process for the next share. This process is described below.

See the attached algorithm (from the paper): inter-decrypt-alg.pdf
@ymarcus93 ymarcus93 self-assigned this Apr 6, 2020
ymarcus93 added a commit that referenced this issue Apr 7, 2020
@ymarcus93
Add functionality for DLOC/LOC decryption of assignment and entry data
f7e4a6e 
Currently, we follow a naive approach. Both DecryptAssignmentData() and
DecryptEntryData() take a list of matched (by pi) DLOC/LOC ciphertexts and
encrypted assignment/entry data. We decrypt the DLOC/LOC ciphertexts to
get the (U, S, c_x), where x = a|e, tuples and then attempt to
interpolate all (U, S) pairs to find k. The problem is that if we are given one malformed
pair, the entire process fails. This is a problem that can easily be
fixed if we implement the smarter algorithm mentioned in the paper (see issue #5).

If we assume no malicious (U, S) pairs, then the process finds k and
correctly decrypts c_x to get the assignment/entry key that can be used
to decrypt the data given.

+ Update main.go to show this decryption process
ymarcus93 added a commit that referenced this issue Apr 9, 2020
@ymarcus93
Add functionality for DLOC/LOC decryption of assignment and entry data
f6140bf 
Currently, we follow a naive approach. Both DecryptAssignmentData() and
DecryptEntryData() take a list of matched (by pi) DLOC/LOC ciphertexts and
encrypted assignment/entry data. We decrypt the DLOC/LOC ciphertexts to
get the (U, S, c_x), where x = a|e, tuples and then attempt to
interpolate all (U, S) pairs to find k. The problem is that if we are given one malformed
pair, the entire process fails. This is a problem that can easily be
fixed if we implement the smarter algorithm mentioned in the paper (see issue #5).

If we assume no malicious (U, S) pairs, then the process finds k and
correctly decrypts c_x to get the assignment/entry key that can be used
to decrypt the data given.

+ Update main.go to show this decryption process
ymarcus93 added a commit that referenced this issue Apr 11, 2020
@ymarcus93
Decryption of data now takes ciphertexts to use and find k from
10f8b23 
Previously decryption of entry/assignment data would take locCiphertexts
and dlocCiphertexts (respectively), derive k, and decrypt the data.
After doing some more testing, it seems that if we attempt to find a k
value (via interpolation) on a set of points P, where P contains > 1
points with the same x-value (i.e. same user hash), the method fails to
find k. The method even fails if you pass another point on the same line
(but different x-value).

When do we run into this case in the protocol? We run into this when the
same user submits two distinct entries of the same perp. Even if there
is a match on the same perp with a different user, the function fails to
find k as described above.

Clearly, the root of the problem is interpolation. I believe a simpler
fix than this commit would be to follow the interpolation/decryption
algorithm mentioned in the paper and try two shares at a time and
decrypt as many ciphertexts as possible. That change would require a
slight refactor/redesign of how loc.go is setup (order of operations,
etc.) However, for time constraints, I'm choosing to delay doing this.
See issue #5 for the tracking of this.

For now, this commit solves the problem explained above by utilizing an
earlier change done in matching.go. matching.go now returns a filtered
list of matched tuples with unique user IDs. We now pass this list into
loc.go and use this list to find k, while the greater superset (includes
multiple entries on same perp from same user) is used for decryption of
entry/assignment data. The current implemenation is slightly bad because
we actually decrypt ciphertexts more than once--we do it once for the
designated k-ciphertexts and another for the entire universe. We can fix
this by doing a union first and marking which ciphertexts are designated
for deriving k; however, at this point we might as well just solve #5
and do a better design of loc.go. Again, for time constraint reasons we
are keeping this quick solution for now.

This commit fixes the problem above because the filtered list to find k
only contains ciphertexts from distinct users.
ymarcus93 added a commit that referenced this issue Apr 11, 2020
@ymarcus93
Decryption of data now takes ciphertexts to use and find k from
558b24d 
Previously decryption of entry/assignment data would take locCiphertexts
and dlocCiphertexts (respectively), derive k, and decrypt the data.
After doing some more testing, it seems that if we attempt to find a k
value (via interpolation) on a set of points P, where P contains > 1
points with the same x-value (i.e. same user hash), the method fails to
find k. The method even fails if you pass another point on the same line
(but different x-value).

When do we run into this case in the protocol? We run into this when the
same user submits two distinct entries of the same perp. Even if there
is a match on the same perp with a different user, the function fails to
find k as described above.

Clearly, the root of the problem is interpolation. I believe a simpler
fix than this commit would be to follow the interpolation/decryption
algorithm mentioned in the paper and try two shares at a time and
decrypt as many ciphertexts as possible. That change would require a
slight refactor/redesign of how loc.go is setup (order of operations,
etc.) However, for time constraints, I'm choosing to delay doing this.
See issue #5 for the tracking of this.

For now, this commit solves the problem explained above by utilizing an
earlier change done in matching.go. matching.go now returns a filtered
list of matched tuples with unique user IDs. We now pass this list into
loc.go and use this list to find k, while the greater superset (includes
multiple entries on same perp from same user) is used for decryption of
entry/assignment data. The current implemenation is slightly bad because
we actually decrypt ciphertexts more than once--we do it once for the
designated k-ciphertexts and another for the entire universe. We can fix
this by doing a union first and marking which ciphertexts are designated
for deriving k; however, at this point we might as well just solve #5
and do a better design of loc.go. Again, for time constraint reasons we
are keeping this quick solution for now.

This commit fixes the problem above because the filtered list to find k
only contains ciphertexts from distinct users.
ymarcus93 added a commit that referenced this issue Apr 11, 2020
@ymarcus93
Decryption of data now takes ciphertexts to use and find k from
1224cb2 
Previously decryption of entry/assignment data would take locCiphertexts
and dlocCiphertexts (respectively), derive k, and decrypt the data.
After doing some more testing, it seems that if we attempt to find a k
value (via interpolation) on a set of points P, where P contains > 1
points with the same x-value (i.e. same user hash), the method fails to
find k. The method even fails if you pass another point on the same line
(but different x-value).

When do we run into this case in the protocol? We run into this when the
same user submits two distinct entries of the same perp. Even if there
is a match on the same perp with a different user, the function fails to
find k as described above.

Clearly, the root of the problem is interpolation. I believe a simpler
fix than this commit would be to follow the interpolation/decryption
algorithm mentioned in the paper and try two shares at a time and
decrypt as many ciphertexts as possible. That change would require a
slight refactor/redesign of how loc.go is setup (order of operations,
etc.) However, for time constraints, I'm choosing to delay doing this.
See issue #5 for the tracking of this.

For now, this commit solves the problem explained above by utilizing an
earlier change done in matching.go. matching.go now returns a filtered
list of matched tuples with unique user IDs. We now pass this list into
loc.go and use this list to find k, while the greater superset (includes
multiple entries on same perp from same user) is used for decryption of
entry/assignment data. The current implemenation is slightly bad because
we actually decrypt ciphertexts more than once--we do it once for the
designated k-ciphertexts and another for the entire universe. We can fix
this by doing a union first and marking which ciphertexts are designated
for deriving k; however, at this point we might as well just solve #5
and do a better design of loc.go. Again, for time constraint reasons we
are keeping this quick solution for now.

This commit fixes the problem above because the filtered list to find k
only contains ciphertexts from distinct users.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@ymarcus93 ymarcus93

Labels
protocol
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@ymarcus93