I'm basing this off of the Algorithms section of the paper, which is kind of hard to understand, so I would appreciate someone else checking this. Also, I hope you're doing this for fun and not planning on using this for real cryptography without thorough analysis by professionals and academics,
The public Boolean function (13) is a series of clauses ANDed together, x -> ^ c_j(x)
. Each clause is a series of subclauses ORed together, x -> V(...)
. And each subclause is an element of the input x_[I(i, j)]
XORed with some sign s(i, j)
.
The signs come from a matrix of Booleans and are chosen randomly as 1 or 0, which is pretty straightforward, but picking the elements out of the input is trickier. The input is a vector of Booleans, and we want a random way to choose which one to put in each subclause. So, we make a matrix of integers size m, k
and call it I
. For each row in this matrix, c_j(x)
has to be true for the private key (since they will be ANDed together). So, generate a row of random integers (from 1
to n
so we don't go out of bounds of the input) and a row of random signs. Each of these should be k
items, since they will be rows of their matrices.
Once we've come up with candidate rows, we need to make sure they satisfy the private key. So, for each index in the row, we derive a subclause for the function c_j
and make sure at least one is true (since they will be ORed together). For example, the first elements might be 5 and 1, so we XOR the 5th element of the private key with 1 and see if it is true. Continue down the rows until at least one is true, and if it is, add the rows to your matrices.
Thinking in the other direction, if you have the matrices I
and s
, you can check a candidate key pretty easily. For each row of the matrices, make sure that with the integer from I
indexing the key, you get a value that can be XORed with the Boolean from s
.
Let's take the rows [1, 3, 2]
and [1, 0, 0]
, and a candidate key [1, 1, 0]
. First, take the first element from the key (1
) and XOR it with 1
. This gives you 0
, so continue on. Take the third element from the key (0
) and XOR it with 0
. This gives 0
, so keep going. Finally, we XOR the second element (1
) and the third sign (0
) to get 1
. Since we got a 1
, these rows work with this key.
Best Answer
There isn't always a perfect solution, but you have many alternatives to choose from:
Use named arguments, if available in your language. This works very well and has no particular drawbacks. In some languages, any argument can be passed as a named argument, e.g.
updateRow(item, externalCall: true)
(C#) orupdate_row(item, external_call=True)
(Python).Your suggestion to use a separate variable is one way to simulate named arguments, but does not have the associated safety benefits (there's no guarantee that you used the correct variable name for that argument).
Use distinct functions for your public interface, with better names. This is another way of simulating named parameters, by putting the paremeter values in the name.
This is very readable, but leads to a lot of boilerplate for you, who is writing these functions. It also can't deal well with combinatorial explosion when there are multiple boolean arguments. A significant drawback is that clients can't set this value dynamically, but must use if/else to call the correct function.
Use an enum. The problem with booleans is that they are called "true" and "false". So, instead introduce a type with better names (e.g.
enum CallType { INTERNAL, EXTERNAL }
). As an added benefit, this increases the type safety of your program (if your language implements enums as distinct types). The drawback of enums is that they add a type to your publicly visible API. For purely internal functions, this doesn't matter and enums have no significant drawbacks.In languages without enums, short strings are sometimes used instead. This works, and may even be better than raw booleans, but is very susceptible to typos. The function should then immediately assert that the argument matches a set of possible values.
None of these solutions has a prohibitive performance impact. Named parameters and enums can be resolved completely at compile time (for a compiled language). Using strings may involve a string comparison, but the cost of that is negligible for small string literals and most kinds of applications.