1 of 29

VOLE-in-the-Head and the�FAEST Post-Quantum Signature Scheme

Peter Scholl

ZKProof, 2 August 2023

2 of 29

Based on

Peter Scholl

2

Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures From VOLE-in-the-Head

with Carsten Baum, Lennart Braun, Cyprien Delpech de Saint Guilhem, Michael Klooß,

Emmanuela Orsini, Lawrence Roy

CRYPTO 2023

FAEST Digital Signature Scheme

+ Christian Majenz, Shibam Mukherjee, Sebastian Ramacher, Christian Rechberger

Submission to NIST PQC Standardization process

3 of 29

Zero-knowledge proofs

Peter Scholl

3

Prover

Verifier

I believe you

4 of 29

Families of ZK Proofs

4

Proof size

Prover runtime

Groth16

STARKs

Ligero

MPC-in-the-head

VOLE-ZK

Succinct

Linear

5 of 29

VOLE-in-the-Head: a general tool for making VOLE-ZK proofs publicly verifiable

Symmetric assumptions (AES/SHAO):

Non-interactive (Fiat-Shamir)

Proof size: slightly larger than VOLE-ZK:

Large fields: 1-2 field elements per mult.
Small fields: 4-16 field elements

5

Application:

Post-quantum signature based on AES
Submitted to NIST PQC Standardization Call

Simplicity

Speed

Application: FAEST

Post-quantum signature based on AES

Submitted to NIST PQC Standardization Call

6 of 29

VOLE-in-the-Head: a general tool for making VOLE-ZK proofs publicly verifiable

Application: FAEST post-quantum

signature scheme

6

Speed

Simplicity

Security

AES/SHA

Linear size

7 of 29

7

VOLE-ZK

in the designated verifier setting

8 of 29

Background: VOLE�(vector oblivious linear evaluation)

Peter Scholl

8

VOLE

Prover

Verifier

Can be instantiated with OT, HE, LPN…

9 of 29

ZK from VOLE (designated verifier)

Peter Scholl

9

[BMRS 21, WYKW 21]

10 of 29

ZK from VOLE via Commit-and-Prove

Peter Scholl

10

[BMRS 21, WYKW 21]

11 of 29

Multiplication gates in VOLE-ZK

Peter Scholl

11

[DIO 21, YSWW 21]

12 of 29

Cost analysis for VOLE-ZK

Peter Scholl

12

13 of 29

13

VOLE-in-the-Head

Adding public verifiability

14 of 29

MPC-in-the-Head vs VOLE-in-the-head:�high-level differences

Peter Scholl

14

challenge

15 of 29

MPC-in-the-Head vs VOLE-in-the-head:�high-level differences

Peter Scholl

15

VOLE

16 of 29

How to do VOLE-in-the-head?

Peter Scholl

16

All-but-one

vector commitment

Convert to VOLE

Run VOLE-ZK proof

17 of 29

How to do VOLE? Warm-up: using OT

Peter Scholl

17

18 of 29

How to do VOLE-in-the-head? Just commit!

Peter Scholl

18

Postpone until after VOLE-ZK proof

19 of 29

VOLE-in-the-head: some details

Peter Scholl

19

Needs consistency check

20 of 29

More details: consistency checking

Peter Scholl

20

21 of 29

Application to�Post-Quantum Signatures

Peter Scholl

21

Call for Additional Digital Signature Schemes

22 of 29

Paradigm for ZK-based signatures

Peter Scholl

22

23 of 29

AES: a ZK-friendly OWF?

Peter Scholl

23

24 of 29

Proving AES-128 in FAEST

Peter Scholl

24

S-Box

25 of 29

Proving the AES S-Box

Peter Scholl

25

S-Box

26 of 29

Peter Scholl

26

Mult. check

VOLE consistency check

Open VOLE outputs

S-Box

27 of 29

FAEST performance

Peter Scholl

27

	Sign (ms)	Verify (ms)	\|sig\| (bytes)
FAEST-128s	57.4	54.7	5 006
FAEST-128f	10.6	8.7	6 336
FAEST-256s	192.8	172.8	22 100
FAEST-256f	53.3	38.6	28 400

28 of 29

FAEST: example performance

Peter Scholl

28

	Sign/Verify	Size
FAEST-128s		5 006 B
FAEST-128f		6 336 B
FAEST-256s		22 100 B
FAEST-256f		28 400 B

29 of 29

Conclusion

VOLE-ZK proofs:

Lightweight and fast with linear size
VOLE-in-the-head: publicly verifiable

FAEST signature:

Conservative security
Reasonable performance

Resources:

Paper: https://ia.cr/2023/996

PQ signature: https://faest.info

Peter Scholl

29

Thank you!