123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303 |
- use na::{DMatrix, DVector};
- use pairing::{PrimeField, Field};
- use pairing::bls12_381::{Fq, FqRepr};
- pub fn u64_to_field<F: PrimeField>(x: u64) -> F {
- F::from_repr(
- <F::Repr as From<u64>>::from(x)
- ).unwrap()
- }
- #[derive(Debug, Clone, PartialEq)]
- pub enum Gate<'a> {
- Attribute(&'a [u8]),
- Threshold {t: usize, children: Vec<Gate<'a>>},
- }
- impl<'a> Gate<'a> {
- fn children(self) -> Vec<Gate<'a>> {
- match self {
- Gate::Threshold {children, ..} => children,
- Gate::Attribute (_) => Vec::new(),
- }
- }
- fn label(self) -> &'a [u8] {
- match self {
- Gate::Threshold {..} => b"",
- Gate::Attribute (l) => l,
- }
- }
- fn lsss(&self) -> DMatrix<u64> {
- match self {
- &Gate::Attribute (_) => DMatrix::from_row_slice(1, 1, &[1u64]),
- &Gate::Threshold {t, ref children} => {
- let m = children.len();
- DMatrix::from_fn(m, t, |i, j| {
- ((i as u64) + 1).pow(j as u32)
- })
- }
- }
- }
- fn rec_msp(ast: AS<'a>) -> AS<'a>{
- // find the first threshold-tree string rather than a simple attribute
- let at = ast.rho.iter().enumerate().skip_while(|&(_, g)| {
- match *g {
- Gate::Attribute (_) => true,
- Gate::Threshold {..} => false,
- }
- }).next();
- // if none is found, simply return ast, we're done.
- // otherwise, [cont.]
- if let Some((i, g)) = at {
- let mg = g.lsss();
- // refresh rho with the resolved attribute
- let mut rho = ast.rho.clone();
- rho.remove(i);
- // XXX. lots of cloning for the safety god.
- // perhaps the fact that we're inside a class can spare us
- // the copy of all the gates?
- for c in g.clone().children().iter() {
- rho.insert(i, c.clone());
- }
- let (m1, d1) = ast.m.shape();
- let (m2, d2) = mg.shape();
- // insert the lsss matrix into m
- let w = ast.m.row(i).kronecker(&mg.column(0));
- let mg = mg.remove_column(0);
- let m = ast.m.remove_row(i);
- let m = DMatrix::from_fn(
- m1 + m2 - 1,
- d1 + d2 - 1,
- |row, col| {
- if row < i && col < d1 { m[(row, col)] }
- else if row < i && col >= d1 { 0 }
- else if row < i+m2 && col < d1 { w[(row-i, col)] }
- else if row < i+m2 && col >= d1 { mg[(row-i, col-d1)] }
- else if row >= i+m2 && col < d1 { m[(row-m2, col)] }
- else { 0 }
- }
- );
- Self::rec_msp(AS {m, rho})
- } else {
- ast.clone()
- }
- }
- fn msp(self) -> AS<'a> {
- let rho = vec![self];
- let m = DMatrix::from_row_slice(1, 1, &[1u64]);
- let ast = Self::rec_msp(AS {m, rho});
- ast
- }
- }
- #[derive(Clone)]
- struct AS<'a> {
- m: DMatrix<u64>,
- rho: Vec<Gate<'a>>,
- }
- impl<'a> AS<'a> {
- fn gen_shares<F: PrimeField>(&self) -> DVector<F> {
- let m = DMatrix::<F>::from_fn(self.m.nrows(), self.m.ncols(),
- |row, col| { u64_to_field(self.m[(row, col)]) }
- );
- DVector::from_fn(self.m.nrows(),
- |row, col| { F::one() }
- )
- }
- }
- mod tc {
- use std::str;
- use std::str::FromStr;
- use nom::{digit, alphanumeric};
- use msp::Gate;
- named!(parens <Gate>, ws!(delimited!(tag!("("), threshold_gate, tag!(")") )) );
- named!(threshold_gate <Gate>,
- do_parse!(
- t: threshold >>
- children: attributes >>
- (Gate::Threshold {t, children})
- )
- );
- named!(attributes < Vec<Gate<'a>> >,
- many1!(preceded!(tag!(","), parse))
- );
- named!(threshold <usize>,
- map_res!(map_res!(ws!(digit), str::from_utf8),
- FromStr::from_str)
- );
- named!(attribute <Gate>,
- map!(ws!(alphanumeric), Gate::Attribute)
- );
- named!(pub parse <Gate>,
- alt!(attribute | parens)
- );
- }
- mod bc {
- use nom::{IResult, alphanumeric};
- use msp::Gate;
- named!(parens<Gate>, ws!(delimited!( tag!("("), expr, tag!(")") )) );
- named!(attribute <Gate>,
- map!(ws!(alphanumeric), Gate::Attribute)
- );
- named!(gate <Gate>,
- alt!(attribute | parens)
- );
- named!(term <Gate<'a>>,
- do_parse!(
- init: gate >>
- res: fold_many0!(
- pair!(alt!(tag!("^") | tag!("∧") | tag!("and")), gate),
- init,
- |acc, (op, g): (&[u8], Gate<'a>)| {
- let v: Vec<Gate<'a>> = vec![acc, g];
- Gate::Threshold {t: 2usize, children: v}
- }
- ) >>
- (res)
- )
- );
- named!(expr <Gate<'a>>,
- do_parse!(
- init: term >>
- res: fold_many0!(
- pair!(alt!(tag!("v") | tag!("or") | tag!("∨")), term),
- init,
- |acc, (op, g): (&[u8], Gate<'a>)| {
- let v: Vec<Gate<'a>> = vec![acc, g];
- Gate::Threshold {t: 2usize, children: v}
- }
- ) >>
- (res)
- )
- );
- // XXX. this needs to be changed into a result type.
- // Also note that making instead "expr" pub will fuck up everything
- // because the "lifetime is not defined" - not sure I really understood why.
- pub fn parse(i: &[u8]) -> IResult<&[u8], Gate, u32> {
- expr(i)
- }
- }
- #[test]
- fn test_tc_parse() {
- // see eprint 2010/374
- let policy = b"(2, (2, (3, I, J, K, L), G, H), (2, A, B, C), (2, D, E, F))";
- let (_, pp) = tc::parse(policy).unwrap();
- let msp = pp.msp();
- assert_eq!(msp.rho.len(), 12);
- let expected = DMatrix::from_row_slice(12, 2 + (2-1) + (3-1) + (2-1) + (2-1),
- &[1, 1, 1, 0, 0, 0, 0,
- 1, 1, 2, 0, 0, 0, 0,
- 1, 1, 3, 0, 0, 0, 0,
- 1, 2, 0, 1, 0, 0, 0,
- 1, 2, 0, 2, 0, 0, 0,
- 1, 2, 0, 3, 0, 0, 0,
- 1, 3, 0, 0, 1, 0, 0,
- 1, 3, 0, 0, 2, 0, 0,
- 1, 3, 0, 0, 3, 1, 1,
- 1, 3, 0, 0, 3, 2, 4,
- 1, 3, 0, 0, 3, 3, 9,
- 1, 3, 0, 0, 3, 4, 16,
- ]
- );
- assert_eq!(expected, msp.m)
- }
- use std::collections::VecDeque;
- pub struct Bfs<'a> {
- stack: VecDeque<Gate<'a>>
- }
- impl<'a> Bfs<'a> {
- fn new(g: Gate<'a>) -> Self {
- let mut stack = VecDeque::new();
- stack.push_back(g);
- Bfs { stack }
- }
- }
- impl<'a> Iterator for Bfs<'a> {
- type Item = Gate<'a>;
- fn next(&mut self) -> Option<Self::Item> {
- let g = self.stack.pop_front()?;
- let children = g.clone().children();
- self.stack.extend(children.iter().cloned());
- Some(g)
- }
- }
- #[test]
- fn test_bc_parse() {
- let policy = b"intern and topsecret or xkeyscore";
- let (_, gate) = bc::parse(policy).unwrap();
- let children = gate.children();
- assert_eq!(children.len(), 2);
- }
- #[test]
- fn test_bfs() {
- let policy = b"1 and (3 and 4)";
- let (_, gate) = bc::parse(policy).unwrap();
- assert_eq!(gate.clone().children().len(), 2);
- let mut bfs = Bfs::new(gate);
- let root = bfs.next();
- let expected = Gate::Attribute(b"1");
- assert_eq!(Some(expected), bfs.next());
- assert_eq!(bfs.next().unwrap().children().len(), 2);
- }
- #[test]
- fn test_matrix_field() {
- let policy = b"1 and 2";
- let (_, gate) = bc::parse(policy).unwrap();
- let msp = gate.msp();
- let m = msp.m;
- let mm = DVector::<Fq>::from_fn(m.ncols(),
- |row, col| {
- u64_to_field(m[(row, col)])
- }
- );
- let v = DVector::from_fn(m.ncols(), |row, col| { 1u64 });
- let vv = DVector::from_fn(m.ncols(), |row, col| { Fq::one() });
- let d = mm.dot(&vv);
- }
|