Number of messages upper limmit

[BasileiosKal]

Through the use of expand_message we put an upper limit to the number of signed messages.

expand_message aborts if len_in_bytes is larger than 2^16 - 1 = 65535. In our case len_in_bytes = count * expand_len. The count can be (at most) equal to the number of signed messages (during ProofGen, if we decide to hide all messages). In the current ciphersuite expand_len = 48. As a result, the count can be at most 1365 which means that the total number of signed messages can also be at most 1365 (or at least a prover cannot choose to not disclose more than 1365 messages).

That's quite unfortunate IMO, since the 1365 messages limit seems quite small to me!

How to solve this??

Not sure what the best solution is. The root of the problem is step 9 in ProofGen, i.e., the step:

9. (m~_j1, ..., m~_jU) = hash_to_scalar(PRF(prf_len), U)

since U cannot be more than 1365. Should we call hash_to_scalar in a loop with multiple calls to the PRF or extent the output length of the PRF to get more seeds if we need more than 1365 scalars?? Or should we define expand_message alternatives with higher output limits (2^32 would be nice, however this would create more implementation barriers comparatively)??

[BasileiosKal]

Discussed on the WG call of the 22nd of August. One proposed option by @andrewwhitehead is to use the PRF as an input to proofGen and iterate through it in a loop to create the different scalars. For testing we can then supply a deterministic PRF (like seeded ChaCha), instead of a seed. Will document the different options and revisit.

[christianpaquin]

As we discussed on the call today, perhaps good to measure the perf difference in practice after prototyping both approaches.

[BasileiosKal]

To track the conversation here, the currently discussed proposals are,

1. Call PRF in a loop, no hashes.
2. Call expand_message in a loop and the PRF once.
3. Call both expand_message and the PRF in a loop.

The tradeoff (naturally) is between efficiency and simplicity. We also have to consider how testable ProofGen will be.

Bellow the updated proposals for the new messages upper limit are described in detail + their theoretical performance.

Note: When it comes to security, none of them is constant time. However, side chanel attacks will have minimum impact since the number of loops is O(U), where U is revealed in each proof.

A. PRF in a loop

The simplest solution, avoiding any hash operation, getting 48 bytes out of the PRF and reducing mod the group order.

// U: number of undisclosed messages
// prf_out_len = ceil(log2(r)/8)
1. for i in (1, ..., U):
2.     m~_i = OS2IP(PRF(prf_out_len)) mod r

B. expand_message in a loop

This solution proposed by Riad Wahby (who I thank again!!), uses expand_message in a loop with different DST's to guarantee independence. The proposal in the context of our spec is the following,

result = get_random_bytes(msg, len_in_bytes, dst)

Procedure:
1.  dst_next = I2OSP(0, 4) || dst
2.  random_bytes = ""

//  Get some random bytes
3.  numexp = floor(len_in_bytes / 7910)
4.  if numexp >= 2^32, ABORT
5.  for j in (1, ..., numexp):   // assumming that if numexp = 0 the loop will not run
6.     tmp = expand_message(msg, dst_next, 8160)
7.     random_bytes = random_bytes || tmp[0..7910]
8.     dst_next = I2OSP(j, 4) || tmp[7910..8160]

//  Get remaining random bytes (dst_next here MUST be the last one computed in the loop)
9.  tmp = expand_message(msg, dst_next, (len_in_bytes mod 7910))
10. random_bytes = random_bytes || tmp

11. return random_bytes[0..len_in_bytes]

The above will be used by hash_to_scalar to get all the bytes necessary.

C. expand_message and PRF in a loop

A combination of the above, using hash_to_scalar as a black box, for a "middle of the road" solution,

rand_scalars = get_random_scalars(PRF, count, dst)

Procedure:
1. scalars = []
2. max_count = floor(8160/expand_len)   // 170 for our ciphersuites
3. ell = floor(count/max_count)
4. for i in (1, ..., ell):
5.     rand_scalars = hash_to_scalar(PRF(prf_out_len), max_count, dst)
6.     scalars.push(rand_scalars) // push all elements from rand_scalars to the scalars list 

// Get the remaining random scalars
7. rand_scalars = hash_to_scalar(PRF(prf_out_len), count mod max_count, dst)
8. return scalars.push(rand_scalars)

Then in the ProofGen we can just call

8. (1, r2, e~, r2~, r3~, s~, m~_1, ..., m~_U) = get_random_scalars(PRF, 6+U)

For performance I'm using hash function and PRF calls as an indicator. The shown performance is for the "worst case" where we using BLS12381-SHA256 ciphersuit, i.e., expand_message_xmd with SHA-256.

• Let U be the number of undisclosed messages. Let also for simplicity U > 170.
• Let ell = ceil(U * expand_len / hash_out_len) + 1 the number of hash invocations in expand_message_xmd

Note: The actual formulas for B and C are:

• for A: 0 hash calls
• for B: Hash calls: floor(U*48/8160) * 256 + ceil((U*48 mod 8160)/32) + 2
• for C: Hash calls: floor(U/170) * 256 + ceil(1.5 * (U mod 170)) + 2

[BasileiosKal]

UPDATES:

1. turns out the limit is lower than expected, i.e., 170 scalars instead of 1365. The reason is that it must hold (count * expand_len) / h_out < 250 where h_out the output len of the hash in bytes (i.e., 32 for sha256). Find the updated operations bellow.
2. Find prototypes and benchmarks >>> here.
3. Some benchmarking results are shown bellow. Find the complete report attached.

Performance:

Option	U = 100	U = 2000	U = 4000
A. PRF in a loop, no hashes	13.632 μs	270.03 μs	562.10 μs
B. expand_message in a loop	90.851 μs	6.0476 ms	11.581 ms
C. expand_message and PRF in a loop	87.211 µs	1.8040 ms	3.3749 ms

From the above, IMO option A. (i.e., circumvent expand_message all together) seems like the better approach if we can also add a note for avoiding entropy attacks (like using a deterministic PRF with a random seed maybe)?? benchmarks.zip